[Python-Dev] Any interest in tail call optimization as a decorator?
Crutcher Dunnavant
crutcher at gmail.com
Tue Feb 7 11:46:45 CET 2006
Maybe someone has already brought this up, but my searching hasn't
revealed it. Is there any interest in something like this for the
functional module?
#!/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):
def func(*args, **kwargs):
try:
raise ZeroDivisionError
except ZeroDivisionError:
f = sys.exc_info()[2].tb_frame
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.
--
Crutcher Dunnavant <crutcher at gmail.com>
littlelanguages.com
monket.samedi-studios.com
More information about the Python-Dev
mailing list