Two days ago, this tail call decorator
by Crutcher Dunnavant was mentioned on LtU. It’s a clever little trick: the decorator returns a new function that, when called, checks if its grandparent
is itself. This would mean that a function declared to be tail-call-optimized is called from another tail-called-optimized function, and so the caller’s frame in the stack can be wiped. How does it do this? The function throws an exception. This is caught by the grandparent, which then calls the saved function with the arguments passed in the exception.
This is the original implementation:
#!/usr/bin/env python2.4 # This program shows off a python decorator( # which implements tail call optimization. It # does this by throwing an exception if it is # it's own grandparent, and catching such # exceptions to recall the stack. import sys class TailRecurseException: def __init__(self, args, kwargs): self.args = args self.kwargs = kwargs def tail_call_optimized(g): """ This function decorates a function with tail call optimization. It does this by throwing an exception if it is it's own grandparent, and catching such exceptions to fake the tail call optimization. This function fails if the decorated function recurses in a non-tail context. """ def func(*args, **kwargs): f = sys._getframe() if f.f_back and f.f_back.f_back and f.f_back.f_back.f_code == f.f_code: raise TailRecurseException(args, kwargs) else: while 1: try: return g(*args, **kwargs) except TailRecurseException, e: args = e.args kwargs = e.kwargs func.__doc__ = g.__doc__ return func @tail_call_optimized def factorial(n, acc=1): "calculate a factorial" if n == 0: return acc return factorial(n-1, n*acc) print factorial(10000) # prints a big, big number, # but doesn't hit the recursion limit. @tail_call_optimized def fib(i, current = 0, next = 1): if i == 0: return current else: return fib(i - 1, next, current + next) print fib(10000) # also prints a big number, # but doesn't hit the recursion limit.
There is a subtle bug: after handling the exception, func then calls its own saved version of g, not the g of the func that throws the exception. Modifying func and the TailRecurseException class so that the function to be called can be passed in the exception solves this nicely:
class TailRecurseException: def __init__(self, g, args, kwargs): self.g = g self.args = args self.kwargs = kwargs ... def func(*args, **kwargs): f = sys._getframe() if f.f_back and f.f_back.f_back and f.f_back.f_back.f_code == f.f_code: raise TailRecurseException(g, args, kwargs) else: newg = g while 1: try: return newg(*args, **kwargs) except TailRecurseException, e: newg = e.g args = e.args kwargs = e.kwargs ...
Throwing an exception just to handle the required stack manipulation because the interpreter won’t handle it is grossly inefficient, granted, and requiring the programmer to declare functions as optimizable is not be ideal, but still a really neat trick.
As a side note, if a function can be called in tail and non-tail position, a non-decorated version should be made available, otherwise bad things can happen:
@tail_call_optimized def add1(n): return (n+1) @tail_call_optimized def add2(n): return add1(add1(n))
This returns 41.
Update: added isTailCall by jorend. Now it is safe to optimize every function (though for efficiency reason you’d only optimize the ones that make tail calls).