[Python-Dev] Explicit Tail Calls

[Shane Hathaway]

Hello,

I'm interested in seeing a good way to write tail calls in Python.  Some
algorithms are more readable when expressed using tail recursion.

I know tail call optimization has been discussed before [1], but I would
like to consider a different approach.  The previous discussion centered
on implicit tail call optimization, which incurs the risk of changing
the behavior of currently working code.  (For example, is it safe to
optimize tail calls within try...finally blocks?  Probably not.  And I
generally want all stack frames to appear in tracebacks, unless I say
otherwise.)

I would like to suggest an explicit form of tail calls.  A new built-in
exception type called "Return" will be added, and it will be used like this:

def fact2(n, v):
    if n:
        raise Return(fact2, n-1, v*n)
    else:
        return v

The interpreter will catch Return exceptions and use them to call
something else.  The caller of a function that uses "raise Return" will
see the result of the tail call as the returned value, rather than the
Return exception.  I am not yet considering implementation details.

Not all algorithms are good candidates for this.  I used the fact2
example only because it's readily available.  I know there are other
people interested in tail call optimization in Python [2] [3]; perhaps
some of them are watching and can provide better examples.

Furthermore, there might be some explicit syntax that converts "return
f(...)" statements to "raise Return(f, ...)", such as a decorator.
However, I'm less interested in the syntax and more interested in the
basic capability.

Shane

[1] http://mail.python.org/pipermail/python-dev/2004-July/046150.html
[2] http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/474088
[3] http://www.voidspace.org.uk/python/weblog/arch_d7_2007_09_22.shtml#e833