Python tail-call decorator

Two days ago, this tail call decorator
by Crutcher Dunnavant was mentioned on LtU. It’s a clever little trick: the decorator returns a new function that, when called, checks if its grandparent
is itself. This would mean that a function declared to be tail-call-optimized is called from another tail-called-optimized function, and so the caller’s frame in the stack can be wiped. How does it do this? The function throws an exception. This is caught by the grandparent, which then calls the saved function with the arguments passed in the exception.

This is the original implementation:


#!/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 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.

There is a subtle bug: after handling the exception, func then calls its own saved version of g, not the g of the func that throws the exception. Modifying func and the TailRecurseException class so that the function to be called can be passed in the exception solves this nicely:

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

  ...
  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(g, args, kwargs)
    else:
      newg = g
      while 1:
        try:
          return newg(*args, **kwargs)
        except TailRecurseException, e:
          newg = e.g
          args = e.args
          kwargs = e.kwargs
  ...

Throwing an exception just to handle the required stack manipulation because the interpreter won’t handle it is grossly inefficient, granted, and requiring the programmer to declare functions as optimizable is not be ideal, but still a really neat trick.

As a side note, if a function can be called in tail and non-tail position, a non-decorated version should be made available, otherwise bad things can happen:

@tail_call_optimized
def add1(n):
  return (n+1)

@tail_call_optimized
def add2(n):
  return add1(add1(n))

This returns 41.

Modified version, and test cases, available here [IUCS] (backup copy here).

Update: added isTailCall by jorend. Now it is safe to optimize every function (though for efficiency reason you’d only optimize the ones that make tail calls).

12 responses to “Python tail-call decorator

  1. Pingback: Python tail-call optimization, done right « Intuitionistically Uncertain

  2. This sentiment has been particularly prevalent of late given the spate of perfect hand
    held video games for kids in recent years, improvements are slow.

  3. Be inventive — you may learn something very new about you and healthy
    ways to conduct your what is a detox diet. One more reason for giving creative gift baskets of oranges and other items to send
    for their friends or the people they had been sent to spy on.

  4. Japan and Korea diet and weight loss does not begin until college.

    No Facebook Gifts An invitation to play Grand Theft Auto also does
    not count as gifts. You can use a fake e-mail for
    this. Any reasonable person will be happy to receive.

  5. Does your website have a contact page?
    I’m having trouble locating it but, I’d like to send you
    an email. I’ve got some creative ideas for your blog you might be interested in hearing. Either way, great site and I look forward to seeing it expand over time.

  6. But that doesn’t mean you should not be careful enough about the fat or protein intake. Thus, the ectomorph will be pushed to the required calorie zone. Beside this, obesity restricts a number of our physical activities.

  7. Awesome.
    Credit for the information on the write-up Python tail-call decorator | Intuitionistically Uncertain.

    They are in fact particularly effective. I appreciated
    viewing your site.

  8. Hey
    Your posting on Python tail-call decorator | Intuitionistically Uncertain is good & well considered.

    I want to return to view your blog posts.

  9. You may want to be, when your current or future dating zimbabwe.
    Keeping people away when we take when they get to know
    and ask forupdates on their own peculiarities.

    They think they’re doing a better way in bettering the affected partner’s sense of individuality
    and separateness.

  10. Lasik eye surgery in Las Vegas Lasik lasik or laser eye surgery doctor should be involved in the wind.
    In order for you to benefit from lasik vision, and others.
    Please be aware that not all patients get or keep exactly 20/20
    vision, and even latent homosexuality accessed at lasik or
    laser eye surgery 19 may 2009, lasik complications.