This is fun :)
{Note: I take no responsibilty for anyone who uses this in production
code}
#!/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 (and only 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. 4 2096
Crutcher wrote: This is fun :) {Note: I take no responsibilty for anyone who uses this in production code}
#!/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 (and only 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.
Hey Crutcher, what a beautifull and elegant hack! Have you already
contributed it to the Python cookbook?
Kay
I've tossed it to python-dev, but how do I submit it to the cookbook?
Neat stuff! I commented on the ActiveState post, but for completeness,
I modified your code to support mutual recursions, and used jorend's
isTailCall() to make it safe to call an optimized function in a
non-tail-call context. http://the-dubois-papers.blogspot.co...decorator.html This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Christopher T King |
last post by:
Is it feasable, and/or desirable to have Python optimize tail-recursive
calls, similar to Scheme and gcc -O2? i.e. effectively compile this:
def foo(n):
return foo(n-1)
into this:
def...
|
by: Stephen Thorne |
last post by:
Decorators have been getting lots of air-time at the moment, but only
really the syntax. After a short discussion on irc the other night I
decided to download python2.4 from experimental and write...
|
by: Ole Nielsby |
last post by:
I just wonder if this is possible with C++/clr.
I'm trying to .NET-enable an interpreter for a Lisp flavoured
language, the interpreter written in NASM which I have
managed to port to MASM....
|
by: Kay Schluehr |
last post by:
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/496691
|
by: Josiah Manson |
last post by:
In the following program I am trying to learn how to use functional
programming aspects of python, but the following program will crash,
claiming that the recursion depth is too great. I am...
|
by: shailesh |
last post by:
hi all,
I m new joiny.
I read that most of the compiler auto detect tail recursion in
program. can any body tell me that is Code compoaser studio for TI dsp
supports?
rgds,
|
by: Miguel Perez |
last post by:
Please critique this tail call optimizing decorator I've written. I've
tried to fix the pitfalls of other proposed decorators, and the result
is this one that supports mutual recursion, does not...
|
by: ssecorp |
last post by:
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/496691
so I try it and when I run:
@Decorators.tail_recursion
def fibtr(n):
def fibt(a, b, n):
if n <= 1:
return b
else:
return...
|
by: Muzammil |
last post by:
int harmonic(int n) {
if (n=1) {
return 1;
}
else {
return harmonic(n-1)+1/n;
}
}
can any help me ??
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing,...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new...
| |