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"　也不知道确切的意思，所以也不知道下面的代码写的对不对。

下面的代码是上面的链接里面的那个人写的.

#!/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.

评论

17 楼 cookoo 2007-06-12  

gigix 写道

cookoo 写道

simohayha 写道

cookoo 写道

不支持也没什么，Ruby也没有，Java spec也不要求。尾递归就是个loop, 直接写loop好了。FP不鼓励写loop那是另外一回事。

哦，原来这样，为什么不鼓励写loop呢，还有就是python中的异常开销是不是不大？

因为传统上循环总需要个计数器，也就是side effect拉。所以FP鼓励用递归或list comprehension，有点洁癖之嫌吧？

至少有一个最新的理由：
函数式的列表操作（map/reduce/filter）是可以拆分的
比如reduce，你可以把一个大列表分成几个小列表，分别对它们做reduce，得到的结果放进同一个列表再做reduce，效果是一样的
map，更是如此
filter，同样
所以你就可以把“分解成小列表的操作”放在几个核上运行
这样就可以充分利用多核的计算能力

大部分情况都如你所说，不过也有例外，比如前后依赖的lazy list：
fibs = 0 : 1 : [ a + b | (a, b) <- zip fibs (tail fibs)]

另外我觉得这是实现细节，聪明点的编译器也许能辨别能否把loop拆开来并行，比如考虑矩阵相乘操作。

16 楼 gigix 2007-06-11  

cookoo 写道

simohayha 写道

cookoo 写道

不支持也没什么，Ruby也没有，Java spec也不要求。尾递归就是个loop, 直接写loop好了。FP不鼓励写loop那是另外一回事。

哦，原来这样，为什么不鼓励写loop呢，还有就是python中的异常开销是不是不大？

因为传统上循环总需要个计数器，也就是side effect拉。所以FP鼓励用递归或list comprehension，有点洁癖之嫌吧？

至少有一个最新的理由：
函数式的列表操作（map/reduce/filter）是可以拆分的
比如reduce，你可以把一个大列表分成几个小列表，分别对它们做reduce，得到的结果放进同一个列表再做reduce，效果是一样的
map，更是如此
filter，同样
所以你就可以把“分解成小列表的操作”放在几个核上运行
这样就可以充分利用多核的计算能力

15 楼 simohayha 2007-06-11  

cookoo 写道

simohayha 写道

cookoo 写道

不支持也没什么，Ruby也没有，Java spec也不要求。尾递归就是个loop, 直接写loop好了。FP不鼓励写loop那是另外一回事。

哦，原来这样，为什么不鼓励写loop呢，还有就是python中的异常开销是不是不大？

因为传统上循环总需要个计数器，也就是side effect拉。所以FP鼓励用递归或list comprehension，有点洁癖之嫌吧？

恩，map的存在可能也是一个原因.

14 楼 cookoo 2007-06-11  

simohayha 写道

cookoo 写道

不支持也没什么，Ruby也没有，Java spec也不要求。尾递归就是个loop, 直接写loop好了。FP不鼓励写loop那是另外一回事。

哦，原来这样，为什么不鼓励写loop呢，还有就是python中的异常开销是不是不大？

因为传统上循环总需要个计数器，也就是side effect拉。所以FP鼓励用递归或list comprehension，有点洁癖之嫌吧？

13 楼 simohayha 2007-03-02  

Arbow 写道

我说python的异常处理是不是开销不大？Java里面可不敢这样搞

呵呵，python in nutshell 有这么一句

引用

In Python, exceptions are considered appropriate whenever they make a program simpler and more robust, even if that means that exceptions are raised rather frequently

12 楼 simohayha 2007-02-26  

cookoo 写道

不支持也没什么，Ruby也没有，Java spec也不要求。尾递归就是个loop, 直接写loop好了。FP不鼓励写loop那是另外一回事。

哦，原来这样，为什么不鼓励写loop呢，还有就是python中的异常开销是不是不大？

11 楼 cookoo 2007-02-15  

不支持也没什么，Ruby也没有，Java spec也不要求。尾递归就是个loop, 直接写loop好了。FP不鼓励写loop那是另外一回事。

10 楼 simohayha 2007-02-14  

这个我就不懂了。应该是开销不大吧？

9 楼 Arbow 2007-02-14  

我说python的异常处理是不是开销不大？Java里面可不敢这样搞

8 楼 simohayha 2007-02-14  

if f.f_back and f.f_back.f_back and f.f_back.f_back.f_code == f.f_code

nnd总算我也懂了，原来把and的计算规则忘了，嘿嘿。

x and y ,if x is false 结果就是x 否则结果是　y.

7 楼 Arbow 2007-02-14  

sys._getframe:

引用

_getframe( [depth])

Return a frame object from the call stack. If optional integer depth is given, return the frame object that many calls below the top of the stack. If that is deeper than the call stack, ValueError is raised. The default for depth is zero, returning the frame at the top of the call stack.
This function should be used for internal and specialized purposes only.

Frame Object:

引用

Frame objects
Frame objects represent execution frames. They may occur in traceback objects (see below).
Special read-only attributes: f_back is to the previous stack frame (towards the caller), or None if this is the bottom stack frame; f_code is the code object being executed in this frame; f_locals is the dictionary used to look up local variables; f_globals is used for global variables; f_builtins is used for built-in (intrinsic) names; f_restricted is a flag indicating whether the function is executing in restricted execution mode; f_lasti gives the precise instruction (this is an index into the bytecode string of the code object).

总算看懂了，
if f.f_back and f.f_back.f_back and f.f_back.f_back.f_code == f.f_code
当属于自身的递归调用（fib()调用fib()）时，上面语句返回true，抛出个 TailRecurseException，然后下面的代码截取异常后直接执行函数。这样就不需要用到堆栈了，也不会溢出。用异常来做控制流啊 多少次递归操作就会抛出多少次异常

6 楼 simohayha 2007-02-13  

呵呵，他这边注释说　This function fails if the decorated 
  function recurses in a non-tail context　。

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)

这段代码我也不懂什么意思
注释也看不太懂

It does this by throwing an exception 
  if it is it's own grandparent

nnd,好郁闷运行了下10000，显卡驱动直接挂掉，无语了.

5 楼 Arbow 2007-02-13  

你给的那段代码：
@tail_call_optimized
标记了这个的function可以被tail_call_optimized这个方法proxy，查看tail_call_optimized(g)，它应该是先判断此方法是否为尾递归类型？我也不太清楚

    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)  

如果是，则执行这个函数，当抛出TailRecurseException时就截获它，然后再次继续执行下去，避免堆栈不够的问题。

    else:   
      while 1:   
        try:   
          return g(*args, **kwargs)   
        except TailRecurseException, e:   
          args = e.args   
          kwargs = e.kwargs   

尾递归方式的函数，执行起来还是跟迭代差不多快的，主要是python不执行这种优化，有stack容量限制，这个proxy就解决它了，比较精妙，收藏一下

4 楼 simohayha 2007-02-13  

python 中的递归是有　限制的，默认情况下over a depth of 1,000就会抛出异常，可是你还能通过sys模块的setrecursionlimit来设置递归的限制，不过这个设置也是有限制的，它依赖于你的操作系统和c的库，文档里面好像说 大概不会超过 几千层.

呵呵那段代码现在基本能看懂了.

ps:不知道为什么python不把 尾递归优化　加进去，嘿嘿，希望下个版本能加进去.

3 楼 Arbow 2007-02-13  

优化是编译器/解析器来做的，但是这种风格的代码需要自己来写。

貌似python没有做这优化处理，计算10000就出问题了：

print "Fibonacci(10000)=", fib(10000)
print "Total time:", (time.time()*1000-t*1000)

就会出错了

引用

...
  File "Fib.py", line 9, in tailRecursionFib
    return tailRecursionFib(n-1, f1+f2, f1)
  File "Fib.py", line 9, in tailRecursionFib
    return tailRecursionFib(n-1, f1+f2, f1)
RuntimeError: maximum recursion depth exceeded

栈溢出
http://www.iteye.com/t/17585.html

应该是没有优化了

2 楼 simohayha 2007-02-13  

那么python 中可是实现这种优化吗？

那么　象　FP语言 中的尾递归优化　是自动的？还是说要你自己实现？

ps:　论坛现在的搜索好不稳定，经常就什么都搜索不出来了.

1 楼 Arbow 2007-02-13  

是指“尾递归优化”吧，比如下面的程序

def fib(n):
	if(n==0):
		return 0;
	return tailRecursionFib(n,1,0)

def tailRecursionFib(n, f1, f2):
	if(n==1):
		return f1
	return tailRecursionFib(n-1, f1+f2, f1)

import time
t = time.time()
print "Fibonacci(700)=", fib(700)
print "Total time:", (time.time()*1000-t*1000)

return tailRecursionFib(n-1, f1+f2, f1) 这行递归调用，可以直接优化为跳转指令而不是函数调用（需要保存堆栈），这样速度会快很多，接近于迭代。以前T1讨论过的，很多FP语言都支持这种优化。


e.找到了，见 http://www.iteye.com/post/32289 的最下面