My tail call optimizing decorator - comp.lang.python

Message from discussion My tail call optimizing decorator

Miguel Perez

View profile

More options Sep 26 2007, 9:40 am

Newsgroups: comp.lang.python

From: Miguel Perez <Wiseman1...@gmail.com>

Date: Wed, 26 Sep 2007 13:40:44 -0000

Local: Wed, Sep 26 2007 9:40 am

Subject: My tail call optimizing decorator

  Reply to author
  |
  Forward
  | Print
  | View thread
  | Show original
  | Report this message
  | Find messages by this author
  

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

Reply to author Forward