471,334 Members | 1,433 Online
Bytes | Software Development & Data Engineering Community
Post +

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 471,334 software developers and data experts.

My tail call optimizing decorator

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
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

Sep 26 '07 #1
0 1133

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

10 posts views Thread by Christopher T King | last post: by
4 posts views Thread by Crutcher | last post: by
19 posts views Thread by Kay Schluehr | last post: by
6 posts views Thread by mh | last post: by
35 posts views Thread by Muzammil | last post: by

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.