Sunday, December 21, 2014

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!

No comments:

Post a Comment