In 1986, Hal Abelson and Gerald Jay Sussman recorded some videos for their M.I.T. EECS course on the Structure and Interpretation of Computer Programs. Twenty-seven years later, these videos are still a great resource. But the language featured is the Scheme1 dialect of Lisp and while I can/do follow along in “edwin”, sometimes it’s nice to play in a (language (with (less (parens)))), like python.
One of the early challenges that I faced while trying to follow a scheme course using python was Scheme’s heavily tail-recursive programming idiom. Here’s a toy example from the videos where we define a Peano addition operation that only uses increment and decrement.
;; Sorry, I just can't abide the names "-1+" and "1+" (define (++ x) (1+ x)) (define (-- x) (-1+ x)) ;; here we define our new "+" operation (define (+ x y) (if (= x 0) y (+ (-- x) (++ y)))) ; here we use the new "+" operation inside its own definition
So when we then evaluate
(+ 3 2), that produces
(+ 2 3) then
(+ 1 4) then
(+ 0 5) then just
5. More explicitly:
(if (= x 0) ;; x doesn't equal zero (it is 3), so we call: (+ (-- x) (++ y)) ;; when we substitute the x and y we get: (+ (-- 3) (++ 2)) ;; which expands to: (+ 2 3) ;; so we call our self again (if (= x 0) ;; x doesn't equal zero (it is 2), so we call: (+ (-- x) (++ y)) ;; when we substitute the x and y we get: (+ (-- 2) (++ 3)) ;; which expands to: (+ 1 4) ;; so we call our self again (if (= x 0) ;; x doesn't equal zero (it is 1), so we call: (+ (-- x) (++ y)) ;; when we substitute the x and y we get: (+ (-- 1) (++ 4)) ;; which expands to: (+ 0 5) ;; so we call our self again (if (= x 0) ;; x does equal zero, so we return y y ;; which is 5
You can of course do this in most languages. But Scheme has special support for tail recursion which lets it support an “unbounded number of active tail calls.” Python doesn’t support that, on purpose, really.
To see the difference, lets setup that example in python:
def add(a, b): """ Silly peano addition example where we only use increment/decrement """ if a == 0: return b a-=1 b+=1 return add(a, b)
It works fine for small numbers, but check out what happens when we run it to add 1986 and 27:
Python 2.7.2 (default, Oct 11 2012, 20:14:37) [GCC 4.2.1 Compatible Apple Clang 4.0 (tags/Apple/clang-418.0.60)] on darwin Type "help", "copyright", "credits" or "license" for more information. >>> def add(a, b): ... if a == 0: ... return b ... a-=1 ... b+=1 ... return add(a, b) ... >>> add(1986, 27) Traceback (most recent call last): File "<stdin>", line 1, in <module> File "<stdin>", line 6, in add ... [999 more of those] ... RuntimeError: maximum recursion depth exceeded
This exposes one of the many differences in language philosophy between Scheme and Python. As wikipedia notes, in Scheme it is idiomatic to use tail recursion to express iteration. In Python, the idiom it to use looping control structures or list comprehensions. However, one thing that both Python and Scheme have in common is that they give you more than enough rope. So, let’s “fix” this. Before you read on, you’ll want to check out the examples that Guido linked to.
My “fix”2 is to simply to create a decorator that transparently rewrites recursive tail calls as somewhat more pythonic iterations, such that this:
def add(a, b): if a == 0: return b return add(a-1, b+1)
…transparently becomes this:
def add(a, b): while True: if a == 0: return b a=a-1 b=b+1 continue
To do this automatic rewriting, I’m using the Python ast module, which I’ve been meaning to explore after I saw it used awesomely in some of Berkeley’s Selective Embedded Just-In-Time Specialization software.
First I use the
getsource function to get the source of the decorated function. This immediately imposes two constraints: first, the decorated function must be pure python; second, it must be stored on disk because
inspect can’t get the source of python code fed to the interpreter on a filehandle.
Next, I use
ast.parse to load the source code into a syntax tree. Then I transform that tree with a custom subclass of
ast.NodeTransformer that I’m naming
ReturnCallTransformer. An instance of this transformer is activated with
ReturnCallTransformer instance visits every “return” statement in the decorated function. If the value of the return is a recursive call to the decorated function, it transforms the return statement:
return add(<expression1>, <expression2>)
<add_argname1>=<expression1> <add_argname2>=<expression2> continue
add_argname2 in this example come from the decorated function’s argspec. In the case of
add, the decorated function’s argspec is
['a', 'b'], with an empty defaults list. In the case of a function with a more complex argspec, such as one defined thus:
def doall(thethings, when='now'): the argspec is
['thethings', 'when'] with a defaults list of
['now']. So the argspec is a convenient list of all the local variables we’ll need to explicitly update between loop iterations.
The result is that if we try our add again, this time with our new decorator (called
tct for “tail call transform”):
@tct def add(a, b): """ silly peano addition example """ if a == 0: return b return add(a-1, b+1) print add(1986, 27)
2013. And we get it considerably faster than in the cases where the number of recursive calls fits on the call stack:
$ python ./add_test.py recursive 65.3716890812 seconds for one million runs iterative 40.2533769608 seconds for one million runs $ pypy ./add_test.py recursive 46.3651080132 seconds for one million runs iterative 2.30580806732 seconds for one million runs $ # gotta love pypy
The code for this decorator project is on Github.