Skip to content

@karanlyons /tail_call_decorator.py
Created

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Tail Call Decorator for Python
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import sys
if not hasattr(sys, '_getframe'):
try:
raise Exception
except:
if not hasattr(sys.exc_info()[2], 'tb_frame') or not hasattr(sys.exc_info()[2].tb_frame, 'f_back'):
raise ImportError("Unable to capture frames. sys._getframe() is not supported in this Python implementation, and the traceback object does not conform to CPython specifications.")
else:
def _getframe(level=0):
"""
A reimplementation of `sys._getframe()`. `level` is the number
of levels deep into the stack to grab the frame from
(default: 0).
`_getframe()` is a private function, and isn't guaranteed to
exist in all versions and implementations of Python. This
function is about 2x slower.
`sys.exc_info()` only returns helpful information if an
exception has been raised.
"""
try:
raise Exception
except:
frame = sys.exc_info()[2].tb_frame # sys.exc_info() returns (type, value, traceback).
for i in xrange(0, level + 1): # + 1 to account for our exception.
frame = frame.f_back
finally:
sys.exc_clear()
return frame
setattr(sys, '_getframe', _getframe)
finally:
sys.exc_clear()
def tail_call(function):
"""
A decorator for functions set up for tail call optimization. If your
function *isn't* set up for tail call optimization, this won't work
as intended.
You should probably never use this.
(Mutually recursive functions work, so long as all functions have the
`@tail_call` decorator.)
"""
def wrapper(*args, **kwargs):
"""
Wraps a function optimized for tail calls, allowing them to reuse the
stack.
(If someone writes a function that just happens to return a sequence
whose first element is "We're our own grandparent.", we're totally
hosed. But this saved us creating a new class of Exception. Which we
really should have just done instead.)
"""
try:
if sys._getframe(2) and sys._getframe(0).f_code == sys._getframe(2).f_code: # Check to make sure we aren't our own grandparent.
return ("We're our own grandparent.", args, kwargs) # No results found by Google. Fingers crossed.
except ValueError:
pass
while True:
result = function(*args, **kwargs) # Will be called decorated, hence the grandparents above.
try:
if result[0] == "We're our own grandparent.":
args = result[1]
kwargs = result[2]
else:
return result
except TypeError:
return result
return wrapper
if __name__ == '__main__':
@tail_call
def tail_factorial(n, current=1):
"""
Factorial function designed for tail recursion.
"""
if n == 1:
return current
else:
return tail_factorial(n - 1, current * n)
print tail_factorial(sys.getrecursionlimit() * 10) # Python's recursion limit is usually 1000.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.