public
Created

Tail Call Decorator for Python

  • Download Gist
tail_call_decorator.py
Python
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 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113
#!/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.

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.