pythonで'tail-call elimination'の最適化が可能かどうか
今日python in nutshellを見たときに見ました
Reader who are familiar Lisp, Scheme, or functional-programming languages must in particular be aware that Python does not implement the optimization of "tail-call elimination,"which is so important in these languages. In Python, any call, recursive or not, has the same cost in terms of both time and memory space, dependent only on the number of arguments: the cost does not change, whether the call is a "tail-call"(meaning that the call is the last operation that the caller executes) or any other, nontail call.
pythonではoptimization of「tail-call elimination」は実現できないと言っていましたがgoogleで検索して見つけました
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/474088
しかしfunctional-programmingがよく分からないのでthe optimization of「tail-call elimination」も正確な意味が分からないので、次のコードが正しいかどうか分かりません.
次のコードは上のリンクの中の人が書いたものです.
Reader who are familiar Lisp, Scheme, or functional-programming languages must in particular be aware that Python does not implement the optimization of "tail-call elimination,"which is so important in these languages. In Python, any call, recursive or not, has the same cost in terms of both time and memory space, dependent only on the number of arguments: the cost does not change, whether the call is a "tail-call"(meaning that the call is the last operation that the caller executes) or any other, nontail call.
pythonではoptimization of「tail-call elimination」は実現できないと言っていましたがgoogleで検索して見つけました
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/474088
しかしfunctional-programmingがよく分からないのでthe optimization of「tail-call elimination」も正確な意味が分からないので、次のコードが正しいかどうか分かりません.
次のコードは上のリンクの中の人が書いたものです.
#!/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.