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

This decorator implements tail call optimization through stack introspection.

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

9 comments

Maciej Obarski 18 years, 1 month ago  # | flag

sys.setrecursionlimit. Cool idea :) It should also be mentioned that for recursion level lower than 13000 you can simply use sys.setrecursionlimit(15000) which is faster (but consumes more memory).

phukregistration phukregistration 18 years, 1 month ago  # | flag

This guy needs to program in a real language, or fix his broken python implementation. I'm reminded of Steele's "Lambda the Ultimate Declarative", which is available here: http://library.readscheme.org/page1.html

page 39:

"Auslander and Strong discuss a technique for 'removing recursion' from PL/I programs which LISP programmers will recognize as a source-to-source semi-compilation. The technique essentially consists of of [sic] introducing an auxiliary array to serve as a stack (though the cited paper manages in the example to use an already existing array be means of a non-trivial subterfuge), and transforming procedure calls into GOTO's plus appropriate stack manipulations to simulate return addresses. What is astrounding is that this simple trick shortened the size of the example code by 8% and shortened the run time by a whopping 40%! They make the reason clear: "the implmentation of the recursive stack costs PL/I 336 bytes per level of recursive call ..." The GOTO's, on the other hand, presumable compile into single branch instructions, and the stack manipulations are just a few arithmetic instructions.

"Even more astounding, particularly in the light of existing compiler technology for LISP and other languages, is that Auslander and Strong do not advocate fixing the PL/I compiler to compile procedure calls using their techniques (as LISP compilers have, to some extent, for years). Instead, they say: "These tehniques can be applied to a program without an understanding of its purpose. Howerver they are complex enough so that we are inclined to teach them as tools for programmers rather than try to mechanize them as an option in an optimizing compiler." The bulk of thier transformations are well within the capability of an optimizing compiler. The problem is that historically procedure calls have received little attention from those who design optimizing compilers; Auslander and Strong how suggest that, since this is the case, we should rewrite all procedure calls into other constructs that the compiler understands better! This seems to defeat the entire purpose of having a high-level language."

So I recommend that this very smart fellow just start working in a language with tail-call optimization, or perhaps he should fix the Python implementation. He's clearly to smart to waste his life on such things.

sasa sasa 18 years, 1 month ago  # | flag

catching flies with vinegar. Maybe, but you're not too smart to try to attract Lisp converts by flaming them. (It's not working for the RIAA, either.)

phukregistration phukregistration 18 years, 1 month ago  # | flag

Which converts? What's the flame?

The stuff I quoted is from 30 years ago. Is there really any excuse for this sort of ass-backwards behavior, given that it was identified as such 30 years ago?

I'm not trying for converts. You either want to work with a decent language, or you don't.

sasa sasa 18 years, 1 month ago  # | flag

wow. does stackless python handle this?

seriously, nice hack, but python makes me want to puke my guts up.

would this be any faster if instead of waiting for grandparency it just waited for stack overflow? something in between?

sasa sasa 18 years, 1 month ago  # | flag

A version that uses lazy evaluation instead of exceptions: http://lambda-the-ultimate.org/node/1331#comment-15165

It also works with mutual recursion and handles mixed tail/non-tail calls okay.

sasa sasa 18 years, 1 month ago  # | flag

p.s. Sorry Sjoerd, whoever you are! -- I used bugmenot.

Michel Salim 18 years, 1 month ago  # | flag

Fix to support mutual tail recursion. The exception thrown needs to include the function to be called, so when an exception is handled, not only are the arguments updated, but the function to be called next as well.

I wrote about it here (link to updated source included):

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