检测在Python无限递归或动态语言

最近我试图编译程序，像这样用GCC：检测在Python无限递归或动态语言

int f(int i){ 
    if(i<0){ return 0;} 
    return f(i-1); 
f(100000);

，它跑了就好了。当我检查堆栈帧时，编译器优化程序只使用一个帧，只是跳回到函数的开头，只将参数替换为f。而且 - 编译器甚至没有在优化模式下运行。现在，当我在Python中尝试同样的事情时 - 我碰到了最大递归墙（或者如果我设置递归深度太高，可能会发生堆栈溢出）。

有没有像Python这样的动态语言可以利用这些优化的好处？也许有可能使用编译器而不是解释器来完成这项工作？

只是好奇！

来源

2010-03-24 drozzy

很好的问题。在比较静态和动态语言的同时，我忘记了一切。 – WeNeedAnswers 2010-03-24 12:39:34

您正在讨论的优化称为tail call elimination - 递归调用展开为迭代循环。

对此有一些讨论，但目前的情况是，这不会被添加，至少对于cpython来说是正确的。参见Guido's blog entry进行一些讨论。

但是，确实存在操纵该功能以执行该优化的some decorators。他们通常只获得节省空间，但不是时间（事实上，他们通常较慢）

来源

2010-03-24 12:07:54 Brian

无堆栈python呢？它是否实现了尾部呼叫优化？ – drozzy 2010-03-24 20:57:55

*凹凸**凹凸**凹凸* – drozzy 2010-03-25 20:37:45

@drozzy：不完全确定。我想可能。我已经在pypy上进行了尝试（包括无堆栈版本），但它看起来并不像它实现它（至少目前） – Brian 2010-03-26 14:54:05

它与它是一种动态语言或它被解释的事实无关。 CPython只是不执行Tail Recursion优化。你可能会发现JPython等。

来源

2010-03-24 12:06:39 Yacoby

真的吗？我认为汇编的优点之一是寻找这样的优化策略？我同意编译或解释程序并不重要，但优化是编译强度的有力候选，其中一个就是您可以查找尾递归。 – WeNeedAnswers 2010-03-24 12:50:31

@WeNeed即使语言被解释，它仍然可以经历一个优化阶段，它只是不会像C. – Yacoby 2010-03-24 13:41:02

之类的东西那么长，这意味着它是一个更好，更容易解释，如果你事先告诉它它需要做一些优化，比如F＃和“rec”关键字？ – WeNeedAnswers 2010-03-24 14:24:56

当我检查堆栈帧时，编译器通过跳回到函数的开头并仅将参数替换为f来优化程序以仅使用一帧。

您所描述的内容称为“尾递归”。一些编译器/口译员支持它，有些则不支持。事实上，大多数人不这样做。正如你注意到的，gcc的确如此。实际上，尾递归是Scheme编程语言规范的一部分，因此所有Scheme编译器/解释器必须支持尾递归。另一方面，Java和Python等语言的编译器（以及大多数其他语言，我会下注）不会执行尾递归。

有没有办法像python这样的动态语言可以利用这些不错的优化？

你的意思是，现在，或者你问的是更抽象的术语？抽象地说，是的！动态语言完全有可能利用尾递归（例如Scheme）。但具体讲，不，CPython（规范的Python解释器）没有标志或其他参数来启用尾递归。

来源

2010-03-24 12:07:39 mipadi

函数式程序已经在寻找尾递归问题了，因为这么多地使用堆栈的本质，而C＃，Java等命令则主要使用堆存储。虽然有点奇怪，但是64位.net并没有打破这个堆栈，尽管32位版本的确如此。我知道在F＃中，解决方法是通过在语法（rec）中声明它来使函数递归。 – WeNeedAnswers 2010-03-24 12:45:34

检测在Python无限递归或动态语言

回答

相关问题