[Python-Dev] Any interest in tail call optimization as a decorator?

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