Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.

My tail call optimizing decorator

Skip to first unread message

Miguel Perez

Sep 26, 2007, 9:40:44 AM9/26/07
Please critique this tail call optimizing decorator I've written. I've
tried to fix the pitfalls of other proposed decorators, and the result
is this one that supports mutual recursion, does not use exceptions,
stack inspection or any implementation-dependent hack, and is pretty
short and fast - the fastest out of the ones I could find and try. In
fact, in tail-recursive environments I tested the impact of using the
decorator is difficult to even measure, as the extra time the
decorator takes to run is probably saved by the better use of cache
memory. The only caveat is that if used in a function that's not
called in a tail-recursive fashion, bad things will happen.

def tailcall(f):
'''Decorator that implements tail call optimization.

Supports cooperative tail call - even when only one of the functions
decorated, and all exceptions pass through it. You can tell the
that have been tail optimized because they have "tco" before them in
stack frame.

The only caveat is that if you attempt to decorate a function that
called in a tail recursive fashion from another decorated function,
get wrong results.'''
tdata = [False] #[Optimizing?]
DO_CALL = object() #Call marker
def tco(*a, **aa):
if tdata[0]:
return DO_CALL, a, aa
tdata[0] = True
ret = f(*a, **aa)
while type(ret) is tuple and ret and ret[0] is DO_CALL:
ret = f(*ret[1], **ret[2])
tdata[0] = False
return ret
tco.__doc__ = f.__doc__
return tco

0 new messages