适当的尾递归 [英] Proper tail recursion

问题描述

是否可行，和/或希望让Python优化尾递归

调用，类似于Scheme和gcc -O2？即有效编译：


def foo（n）：

返回foo（n-1）


进入：


def foo（n）：

goto foo（n-1）


这会自然只能在优化的字节码中启用。


在一个不相关的，Scheme-ish注释中，有没有办法让生成器

访问自己？即我希望能够写下这个：


def gen（）：

yield get_current_continuation（），someothergenerator（）

谢谢，

克里斯

解决方案

Christopher T King< sq *** ***@WPI.EDU>写在

新闻：Pi ************************************* * @ccc4 .wpi.edu：

是否可行，和/或希望让Python优化尾递归
调用，类似于Scheme和gcc -O2？即有效编译：

def foo（n）：
返回foo（n-1）

到此：

def foo（n）：
goto foo（n-1）

这自然只会在优化的字节码中启用。

在一个不相关的，Scheme-ish音符上，有没有办法让发电机进入自己？即我想写这个：

def gen（）：
yield get_current_continuation（），someothergenerator（）

谢谢，
Chris

只是因为一个函数看起来递归你，并不意味着它实际上是被调用的时候它是递归的。


你打算如何处理这个？


def foo（n）：

return foo（ n-1）


def baz（n）：

返回0


bar = foo

foo = baz

bar（3）


一种解决方案可能是提供一个关键字，指的是当前的

执行函数：这不仅对递归有用，而且对函数的
访问属性也有用。这些方法和发生器的帮助

如你所说，很难引用自己。


然而，我不相信目前有任何获取当前执行函数或生成器对象的简单方法

Duncan Booth< [e-mail]>写道：

Christopher T King< sq ****** @ WPI.EDU>在
新闻中写道：Pi ************************************** @ ccc4。 wpi.edu：

是否可行，和/或希望让Python优化尾递归
调用，类似于Scheme和gcc -02？即有效编译：

仅仅因为函数看起来递归，并不意味着它在被调用时实际上是递归的。
您如何处理此问题？
def foo（n）：
返回foo（n-1）
def baz（n）：
返回0
bar = foo
foo = baz
bar（3）


而不是消除尾递归，可以实现

一般尾调用优化。使编译器识别尾部调用不应该太难，即


返回垃圾邮件（params）


在任何try语句之外。然后它可以生成字节代码

TAIL_CALL而不是CALL_FUNCTION。在调用spam（）之前，TAIL_CALL会丢弃当前堆栈帧的
$ b $。


这并没有给你提高性能/>
函数调用，但至少它使尾部递归函数

在恒定空间中运行。


当然，有些需要注意如果被调用函数是访问调用函数名称空间的本地

函数，则确保当前

堆栈帧不被丢弃。即，

的情况


def parrot（x）：

def spam（n）：

返回n + y

y = x * x

返回垃圾邮件（5）


调用''返回垃圾邮件（5）''必须确保垃圾邮件（）可以访问''y''
。这可能需要在许多

案例中进行运行时检查。 （在通常情况下，在呼叫者中没有本地功能

，当然可以静态确定。）

嗯，有一个属性' 'func_closure''关于函数对象，

如果它没有访问

周围的命名空间，那么快速浏览似乎是None。


但是，我不相信目前有任何简单的方法来获取当前正在执行的函数或生成器对象。

提升和捕获异常，并挖掘

追溯对象可能会给你足够的信息来做

。但它不是很漂亮，而且我不确定它是否可以在C-Python，Jython，PyPy，Psyco以及其他任何

其他产品之间移植。 Python编译器/解释器。

-

Thomas Bellman，Lysator计算机俱乐部，Link？ping大学，瑞典

谁说的人它不可能做到！ bellman @ lysator.liu.se

永远不会打断正在这样做的人。 ！做爱 - Nicht Wahr！

2004年7月6日星期二，Thomas Bellman写道：

Duncan Booth< me @ privacy.net>写道：

只是因为一个函数看起来递归你，并不意味着它在被调用时实际上是递归的。

如何你打算办理这个吗？

def foo（n）：
return foo（n-1）

def baz（n）：
返回0

bar = foo
foo = baz
bar（ 3）

而不是消除尾递归，可以实现一般尾调用优化。使编译器识别尾部调用，即在任何try语句之外返回垃圾邮件（params）

不应该太困难。然后它可以生成字节代码
TAIL_CALL而不是CALL_FUNCTION。在调用spam（）之前，TAIL_CALL会丢弃当前的堆栈帧。

这并没有给你提供没有进行
函数调用的性能提升，但至少它使尾部递归功能在恒定的空间中运行。

他说的话。 :)我不是要将递归函数优化为循环，

但只是用函数结尾处的普通调用替换为

调用。

当然，如果被调用的函数是访问调用函数命名空间的本地函数，则需要注意确保当前的堆栈框架不被丢弃。
[snip]

我只是在这里猜测（我对内部的了解并不太好），

但是在闭包的情况下，抛弃堆栈空间是不行的，

因为所需的任何变量都保存在函数的func_closure中

属性？修改你的例子：


def parrot（x）：

def spam（n）：

返回n + y

y = x * x

返回垃圾邮件


打印鹦鹉（3）（5）


按预期返回28，并且（大致）功能上与你的parrot（）函数的尾部调用版本没有区别

。

但是，我不相信目前有任何简单的方法来掌握当前正在执行的函数或生成器对象。

追溯对象可能会为您提供足够的信息。但它不是很漂亮，而且我不确定它是否可以在C-Python，Jython，PyPy，Psyco以及任何其他Python编译器/解释器之间移植。

我不需要它那么糟糕;） - 它只是在我的代码中做了一个整洁的

一般化，而不是特殊的 - 将''无'的产量包装成

指的是产生它的发电机。

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 foo(n):
goto foo(n-1)

This would naturally only be enabled in optimized bytecode.

On an unrelated, Scheme-ish note, is there any way for a generator to
access itself? i.e. I want to be able to write this:

def gen():
yield get_current_continuation(),someothergenerator()

Thanks,
Chris

解决方案

Christopher T King <sq******@WPI.EDU> wrote in
news:Pi**************************************@ccc4 .wpi.edu:

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 foo(n):
goto foo(n-1)

This would naturally only be enabled in optimized bytecode.

On an unrelated, Scheme-ish note, is there any way for a generator to
access itself? i.e. I want to be able to write this:

def gen():
yield get_current_continuation(),someothergenerator()

Thanks,
Chris

Just because a function looks recursive to you, doesn''t mean it actually is
recursive when it gets called.

How do you propose to handle this?

def foo(n):
return foo(n-1)

def baz(n):
return 0

bar = foo
foo = baz
bar(3)

One solution might be to provide a keyword which refers to the currently
executing function: this would be useful not only for recursion but also to
access attributes on the function. These help with methods and generators
which as you noted find it hard to reference themselves.

However, I don''t believe there is at present any easy way to get hold of
the current executing function or generator object.

Duncan Booth <[e-mail]> wrote:

Christopher T King <sq******@WPI.EDU> wrote in
news:Pi**************************************@ccc4 .wpi.edu:

Is it feasable, and/or desirable to have Python optimize tail-recursive
calls, similar to Scheme and gcc -O2? i.e. effectively compile this:

Just because a function looks recursive to you, doesn''t mean it actually is
recursive when it gets called. How do you propose to handle this? def foo(n):
return foo(n-1) def baz(n):
return 0 bar = foo
foo = baz
bar(3)
Instead of doing tail recursion elimination, one could implement
general tail call optimization. It shouldn''t be too difficult to
make the compiler recognize tail calls, i.e

return spam(params)

outside any try statement. It could then generate the byte code
TAIL_CALL instead of CALL_FUNCTION. TAIL_CALL would throw away
the current stack frame before calling spam().

This doesn''t give you the performance improvement of not making a
function call, but at least it makes a tail recursive function
run in constant space.

Of course, some care needs to be taken to ensure that the current
stack frame isn''t thrown away if the called function is a local
function accessing the namespace of the calling function. I.e,
in the case

def parrot(x):
def spam(n):
return n + y
y = x*x
return spam(5)

the call to ''return spam(5)'' must make sure that ''y'' is
accessible to spam(). That might need a runtime check in many
cases. (In the common case of there being no local functions at
all in the caller, it can be determined statically, of course.)
Hmm, there is an attribute ''func_closure'' on function objects,
that at a quick glance seems to be None if it doesn''t access the
surrounding namespace.

However, I don''t believe there is at present any easy way to get hold of
the current executing function or generator object.

Raising and catching an exception, and digging through the
traceback object might give you enough information to do
that. But it''s not very pretty, and I''m not sure that it
is portable between C-Python, Jython, PyPy, Psyco, and any
other Python compiler/interpreter.
--
Thomas Bellman, Lysator Computer Club, Link?ping University, Sweden
"The one who says it cannot be done should ! bellman @ lysator.liu.se
never interrupt the one who is doing it." ! Make Love -- Nicht Wahr!

On Tue, 6 Jul 2004, Thomas Bellman wrote:

Duncan Booth <[e-mail]> wrote:

Just because a function looks recursive to you, doesn''t mean it actually is
recursive when it gets called.

How do you propose to handle this?

def foo(n):
return foo(n-1)

def baz(n):
return 0

bar = foo
foo = baz
bar(3)

Instead of doing tail recursion elimination, one could implement
general tail call optimization. It shouldn''t be too difficult to
make the compiler recognize tail calls, i.e

return spam(params)

outside any try statement. It could then generate the byte code
TAIL_CALL instead of CALL_FUNCTION. TAIL_CALL would throw away
the current stack frame before calling spam().

This doesn''t give you the performance improvement of not making a
function call, but at least it makes a tail recursive function
run in constant space.

What he said. :) I don''t mean to optimize recursive functions into loops,
but simply to replace normal calls at the end of functions with tail
calls.
Of course, some care needs to be taken to ensure that the current
stack frame isn''t thrown away if the called function is a local
function accessing the namespace of the calling function.
[snip]

I''m just guessing here (my knowledge of the internals isn''t too great),
but in the case of closures, isn''t it okay to throw away the stack space,
since any variables needed are kept in the function''s func_closure
attribute? To modify your example:

def parrot(x):
def spam(n):
return n + y
y = x*x
return spam

print parrot(3)(5)

This returns 28, as expected, and is (roughly) functionally no different
from a tail-callified version of your parrot() function.

However, I don''t believe there is at present any easy way to get hold of
the current executing function or generator object.

Raising and catching an exception, and digging through the
traceback object might give you enough information to do
that. But it''s not very pretty, and I''m not sure that it
is portable between C-Python, Jython, PyPy, Psyco, and any
other Python compiler/interpreter.

I don''t need it that badly ;) -- it just would have made a neat
generaliztion in my code, rather than special-casing a yield of ''None'' to
refer to the generator that yielded it.

这篇关于适当的尾递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！