Proper tail recursion in Python and Hy

I recently came across a new language, Hy. It is a Lisp dialect of Python! This means that I can finally start programming as I want in a functional language, Lisp, and not have to worry about whether others can use my code or whether I hit a snag that I can't figure out in lisp, as I can always drop back down to Python if necessary.
Anyways, since it is a Lisp dialect, I wished that it had proper tail recursion, as I utilize tail recursion a lot when programming in Lisp, and hitting a maximum recursion depth exception is quite common for me. As proper tail recursion is missing in Python, I first had to implement tail recursion in Python . I did this using a decorator and an exception, which allows me to bail out of a function without returning anything, and the decorator tries to return from the function and catches these TailCall exceptions, and handles them so that it all works. This is probably a lot slower way of doing it than having it implemented in the interpreter itself, but seeing as you gain instead power to go much deeper in recursion, I think it is a fair trade-off.
The next step was implementing the decorator and exception in Hy. The tail recursion decorator and exception in Hy is a bit awkward, but works well enough.
The final step was implementing it in Hy itself, and I now have a pending pull request for the change. The implementation adds a new import,

(import [__future__ [TailRec]]) 

which the Hy compiler recognizes and turns on tail recursion during the compilation. This adds the decorator around every function that uses tail recursion, and switches the return statements for raising of the TailCall exception. This effectively gives us proper tail recursion in Hy!
This allows us to do things like:

    (defn tcodd [n]
      (if (= n 0)
          False
          (tceven (- n 1))))
    (defn tceven [n] 
      (if (= n 0)
          True
          (tcodd (- n 1))))

    (print (tceven 1000))

and

(defn fact [n]
  (defn facthelper [n acc]
    (if (= n 0)
        acc
        (facthelper (- n 1) (* n acc))))
    (facthelper n 1))
(print (fact 1000))

without ever hitting the recursion depth exceeded exception! Woo!
Here's hoping that it makes it into Hy!

Hy <-> Python Interop

I added Hy <-> Python Interop documentation to the Hy documentation today! Best part of open source is that if you find something missing, you can just add it!

Hy <-> Python interop

By importing Hy, you can use Hy directly from Python!
If you save the following in greetings.hy:

(defn greet [name] (print "hello from hy," name))

Then you can use it directly from python, by importing hy before importing the module. In Python:

import hy
import greetings

greetings.greet("Foo")

You can also declare a function in python (or even a class!) and use it in Hy!
If you save the following in greetings.py in Python:

def greet(name):
    print("hello, %s" % (name))

You can use it in Hy:

(import greetings)
(.greet greetings "foo")

To use keyword arguments, you can use in greetings.py:

def greet(name, title="Sir"):
    print("Greetings, %s %s" % (title,name))

and then in Hy:

(import greetings)
(.greet greetings "Foo")
(.greet greetings "Foo" "Darth")
(apply (. greetings greet) ["Foo"] {"title" "Lord"})

Which would output:

Greetings, Sir Foo

Greetings, Darth Foo

Greetings, Lord Foo

Simple as that! Now keep on the Hy life!

A neat little result.

While going over some homework as a TA in computer science 2 at the University of Iceland, I noticed something I did not know.

We already know that (assuming integer division) that
\[\left( \frac{x}{{10}^i} \right) \mod 10 \]

gives us the \((n-i)\)-th digit of a number (\(n =\left\lfloor{\log_{10}(x)} \right\rfloor \), and  \( i = 0 \) gives you the last digit) when counting in a decimal system. But going over the homework batch where the students were supposed to implement radix sort, I noticed that

\[ \frac{x \mod {10}^{i+1}}{{10}^i} \]

gives you the \(i\)-th digit (where 0 gives you the first)! Pretty cool!

I'm not going to prove this, as I have far to little experience with integer division and the modulus operation, but it seems to work, judging by that my students queues all turn out sorted.