Tail Call Optimization as a Decorator

[Crutcher]

This is fun
{Note: I take no responsibilty for anyone who uses this in production
code}

#!/usr/bin/env python2.4
# This program shows off a python decorator
# which implements tail call optimization. It
# does this by throwing an exception if it is
# it's own grandparent, and catching such
# exceptions to recall the stack.

import sys

class TailRecurseException:
def __init__(self, args, kwargs):
self.args = args
self.kwargs = kwargs

def tail_call_optimized(g):
"""
This function decorates a function with tail call
optimization. It does this by throwing an exception
if it is it's own grandparent, and catching such
exceptions to fake the tail call optimization.

This function fails if (and only if) the decorated
function recurses in a non-tail context.
"""
def func(*args, **kwargs):
f = sys._getframe()
if f.f_back and f.f_back.f_back \
and f.f_back.f_back.f_code == f.f_code:
raise TailRecurseException(args, kwargs)
else:
while 1:
try:
return g(*args, **kwargs)
except TailRecurseException, e:
args = e.args
kwargs = e.kwargs
func.__doc__ = g.__doc__
return func

@tail_call_optimized
def factorial(n, acc=1):
"calculate a factorial"
if n == 0:
return acc
return factorial(n-1, n*acc)

print factorial(10000)
# prints a big, big number,
# but doesn't hit the recursion limit.

@tail_call_optimized
def fib(i, current = 0, next = 1):
if i == 0:
return current
else:
return fib(i - 1, next, current + next)

print fib(10000)
# also prints a big number,
# but doesn't hit the recursion limit.

 

[Kay Schluehr]

This is fun
{Note: I take no responsibilty for anyone who uses this in production
code}

#!/usr/bin/env python2.4
# This program shows off a python decorator
# which implements tail call optimization. It
# does this by throwing an exception if it is
# it's own grandparent, and catching such
# exceptions to recall the stack.

import sys

class TailRecurseException:
def __init__(self, args, kwargs):
self.args = args
self.kwargs = kwargs

def tail_call_optimized(g):
"""
This function decorates a function with tail call
optimization. It does this by throwing an exception
if it is it's own grandparent, and catching such
exceptions to fake the tail call optimization.

This function fails if (and only if) the decorated
function recurses in a non-tail context.
"""
def func(*args, **kwargs):
f = sys._getframe()
if f.f_back and f.f_back.f_back \
and f.f_back.f_back.f_code == f.f_code:
raise TailRecurseException(args, kwargs)
else:
while 1:
try:
return g(*args, **kwargs)
except TailRecurseException, e:
args = e.args
kwargs = e.kwargs
func.__doc__ = g.__doc__
return func

@tail_call_optimized
def factorial(n, acc=1):
"calculate a factorial"
if n == 0:
return acc
return factorial(n-1, n*acc)

print factorial(10000)
# prints a big, big number,
# but doesn't hit the recursion limit.

@tail_call_optimized
def fib(i, current = 0, next = 1):
if i == 0:
return current
else:
return fib(i - 1, next, current + next)

print fib(10000)
# also prints a big number,
# but doesn't hit the recursion limit.

Hey Crutcher, what a beautifull and elegant hack! Have you already
contributed it to the Python cookbook?

Kay

 

[Crutcher]

I've tossed it to python-dev, but how do I submit it to the cookbook?

 

[Kay Schluehr]

I've tossed it to python-dev, but how do I submit it to the cookbook?

http://aspn.activestate.com/ASPN/Python/Cookbook/

I think it is a good place to stay accessible even if python-dev
overlooks it.

Kay

 

[Michel Salim]

Neat stuff! I commented on the ActiveState post, but for completeness,
I modified your code to support mutual recursions, and used jorend's
isTailCall() to make it safe to call an optimized function in a
non-tail-call context.

http://the-dubois-papers.blogspot.com/2006/03/python-tail-call-decorator.html