Proper tail-recursion in Python and Hy

Hy is a lisp dialect of Python. It has full cross-language support, meaning that any code you write in Hy can be imported into Python, and vice versa. This means that you can add functional goodies to your existing app, without having to go all in. You also have access to the full extent of Python, which has many great packages and support all over.

However, Hy is missing proper tail-recursion! Sure, you can use loop-recur and trampoline (much like in Clojure), but it’s not the same! Then you have to explicitly worry about tail-recursion, which comes down hard on its usability. Personally, I utilize tail-recursion a lot when programming in the functional paradigm, and hitting an maximum recursion depth exception is something I have to keep in mind.

As proper tail-recursion is missing in Python, We first have to implement tail-recursion in Python . This was done using a decorator and an exception. The exception, TailCall allows us to escape the functions stack without returning anything, and the decorator allows us to catch these exceptions, unwrap the function which should be called next and call it. This is done until there is no exception thrown, and thus no recursive call at the end. That’s when we return from the function proper. This turns the tail-recursion into a while loop structure, which is exactly what we want.

The con is though that this is slower than doing it in the interpreter itself, but you gain proper tail-recursion, which is a huge pro in itself. This should also be about as efficient as using the loop-recur or trampoline macros/functions, so it’s not too bad.

Having implemented proper tail-recursion in Python, we then turn to the problem of using it in Hy, so that is done automatically, without having to explicity throw a TailCall exception and wrapping it with a decorator.

This is done by using a __future__ import, so as to make it optional (seeing as it would cause performance and debugging issues). There has been a pending pull request for some time now 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!

Edit: I posted this originally on my blog, but I’ve decided to republish it on medium. The pull request has not received much attention, as seems to be common with non-trivial pull requests on open source projects. I do most of my functional programming in Haskell, so I’ve not been motivated to pursue it’s acceptance further. If anyone is interested in bringing attention to the request and/or contribute to it, feel free to comment on it on GitHub.


Originally published at blog.mpg.is on February 22, 2016.