[Python-Dev] Any interest in tail call optimization as a decorator? (original) (raw)

Crutcher Dunnavant crutcher at gmail.com
Tue Feb 7 11:46:45 CET 2006

Maybe someone has already brought this up, but my searching hasn't revealed it. Is there any interest in something like this for the functional module?

#!/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): def func(*args, **kwargs): try: raise ZeroDivisionError except ZeroDivisionError: f = sys.exc_info()[2].tb_frame 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.

-- Crutcher Dunnavant <crutcher at gmail.com> littlelanguages.com monket.samedi-studios.com

More information about the Python-Dev mailing list