This is a tail call implementation in Python that uses no stack introspection and is therefore likely to be compatible with all implementations of Python.
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 | class TailCall(Exception):
def __init__(self, f, *args, **kwargs):
self.f = f
self.args = args
self.kwargs = kwargs
def has_tail_calls(f):
def tail_call_wrapper(*args, **kwargs):
current_func = f
while True:
try:
return current_func(*args, **kwargs)
except TailCall, e:
current_func = getattr(e.f, '_tail_callable', e.f)
args = e.args
kwargs = e.kwargs
tail_call_wrapper._tail_callable = f
tail_call_wrapper.__doc__ = f.__doc__
return tail_call_wrapper
@has_tail_calls
def sum_range(n, total=0):
"""Sum the integers from 1 to n.
Obviously the same as n(n+1)/2, but this is a test, not a demo.
>>> sum_range(1)
1
>>> sum_range(100)
5050
>>> sum_range(100000)
5000050000L
"""
if not n:
return total
else:
raise TailCall(sum_range, n - 1, n + total)
@has_tail_calls
def fact2(n, v=1):
"""Factorial.
>>> fact2(1)
1
>>> fact2(2)
2
>>> fact2(3)
6
>>> fact2(4)
24
>>> fact2(20)
2432902008176640000L
"""
if not n:
return v
else:
raise TailCall(fact2, n - 1, v * n)
if __name__ == '__main__':
import doctest
doctest.testmod()
|
A tail call allows a function to return the result of another function without leaving an entry on the stack. Tail recursion is a specific case of tail calling.
This recipe provides a fairly simple way to make tail calls in Python. It is similar to the other tail call recipes at ASPN, but in this case the tail call is explicit, eliminating the need to introspect the stack. It is probably compatible with all implementations of Python.
To enable tail calling in any function, use the @has_tail_calls decorator and replace "return f(...)" statments with "raise TailCall(f, ...)". The decorator will catch TailCall exceptions and call the specified function, unwrapping the tail call decorator if there is one. The decorator will continue to call functions until a function returns a value rather than raise TailCall.
A minor tweak would be to replace
with
ie, put the raise inside a function.
It could also be named tailreturn. I'm not sure what's best.
tailcall(). Yes, that makes for a definite improvement.
Benefits? The benefit of avoiding stack inspections in tail recursion decorators isn't really an original contribution:
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/496691
So are there any real benefits of this new solution? As I pointed out in the comment section to the quoted recipe, Crutchers genuinely original decorator is slower but more stable on mutual recursive functions which are both decorated. It would be great if this class of decorators can be advanced in either direction of performance or stability.