Tail Call Optimization as a Decorator

[Kay Schluehr]

Crutcher wrote:
> This is fun :)
> {Note: I take no responsibilty for anyone who uses this in production
> code}
>
> #!/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 (and only 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.

Hey Crutcher, what a beautifull and elegant hack! Have you already
contributed it to the Python cookbook? 

Kay