Intro

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 Scheme¹ 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”

My “fix”² 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 inspect module’s 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 transformer.visit(syntaxtree).

The 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>)

into

<add_argname1>=<expression1>
<add_argname2>=<expression2>
continue

add_argname1 and 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)

…we get 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.