Welcome, guest | Sign In | My Account | Store | Cart

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.

Python, 64 lines
 1
 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.

3 comments

Adam Olsen 16 years, 5 months ago  # | flag

A minor tweak would be to replace

raise TailCall(sum_range, n - 1, n + total)

with

tailcall(sum_range, n - 1, n + total)

ie, put the raise inside a function.

It could also be named tailreturn. I'm not sure what's best.

Shane Hathaway (author) 16 years, 5 months ago  # | flag

tailcall(). Yes, that makes for a definite improvement.

kay schluehr 16 years, 5 months ago  # | flag

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.