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
--
http://mail.python.org/mailman/listinfo/python-list
