Name: Anonymous 2007-09-27 17:42 ID:4a99BlE3
Please critique this tail call optimizing decorator I've just 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. (It's, incidentally, the simplest @tailcall implementation to me as well.) 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 (I suppose) saved by the better use of cache memory. The only caveat it has is that if used in a function that's not called in a tail-recursive fashion, bad things will happen. How to use? Simple: just decorate the shit out of your tail-recursive functions.
def tailcall(f):
'''Decorator that implements tail call optimization.
Supports cooperative tail call - even when only one of the functions
is decorated, and all exceptions pass through it. You can tell the
functions that have been tail optimized because they have "tco" before
them in the stack frame.
The only caveat is that if you attempt to decorate a function that
isn't called in a tail recursive fashion from another decorated
function, you'll get wrong results.'''
tdata = [False] #[Optimizing?]
DO_CALL = object() #Call marker
def tco(*a, **aa):
if tdata[0]:
return DO_CALL, a, aa
else:
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