This decorator implements tail call optimization through stack introspection.
Python, 60 lines
Download
Copy to clipboard1 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.
|
Tags: algorithms
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).
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.
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.)
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.
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?
Same thing in Javascript. http://w3future.com/weblog/2006/02/#tailCallEliminationInJavascript
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.
p.s. Sorry Sjoerd, whoever you are! -- I used bugmenot.
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