为什么Perl如此害怕"深度递归"？

Question

我最近偶然发现了高阶Perl这本书,它基本上提出了以功能方式在Perl中做事的方法.作者解释说,Perl拥有Lisp的7个核心功能中的6个,而C没有.

我有一个问题,看起来像一个递归解决方案的好候选人,我以这种方式编码.但Perl抱怨"深度递归".我google了一下,发现一个Perl和尚解释说"Perl不是Haskell".当递归深度超过100个级别时,默认情况下,您会收到投诉.

有有办法来扩展这个限制或完全关闭它,但我的问题是:

• 有没有理由让Perl对递归这么紧张,而Haskell根本就没有？

Answer 1

因为在Haskell中,我们有懒惰和保护递归和尾调用优化,而Perl没有.

这实质上意味着每个函数调用都会分配一组称为"堆栈"的内存,直到函数返回为止.当你编写递归代码时,由于这些嵌套的函数调用,你会积累大量的内存,最终会堆积溢出.TCO允许对未使用的块进行优化.

没有它,依靠递归并不是一个好主意.例如,假设您写了一个递归版本map,它会崩溃任何体面的大小列表.在Haskell中,受保护的递归意味着对于大型列表,递归解决方案比类似"循环"的函数要快得多.

TLDR:Haskell的实现旨在处理函数/递归样式,并且perl的实现不是在过去的好时代,100级函数调用是一个理智的限制.

Answer 2

"深度递归"警告是可选的,并且指示某些事情可能出错:大多数情况下,一个函数一遍又一遍地调用自身(Perl是一种多范式语言,很多人都不喜欢)吨使用官能成语).即使有意识地使用递归,也很容易忘记基本情况.

关闭"深度递归"警告很容易:

use warnings;
no warnings 'recursion';

sub recurse {
  my $n = shift;
  if ($n) {
    recurse($n - 1);
  }
  else {
    print "look, no warnings\n";
  }
}

recurse(200);

输出:

look, no warnings

确实,Perl不执行尾递归优化,因为这会弄乱caller输出(这对于像pragma或者某些事情来说是至关重要的Carp).如果你想手动执行尾调用,那么

return foo(@args);

变

@_ = @args; # or something like `*_ = \@args`
goto &foo;

虽然如果你愚蠢地local讨厌,可能会发生坏事@_.

Answer 3

在无限分配最终耗尽可用内存后，失控递归将使 Perl 程序或 Haskell 程序崩溃。两种语言都以不同的方式处理这个潜在的陷阱。

\n\n

珀尔

\n

Perl 是一种多范式语言，但本质上是过程性的，该范式中的深堆栈深度可能表明失控的递归。有关此诊断的perldiag 文档也说明了这一点，并强调了这一点。

\n

\n

\n
• 匿名子程序的深度递归
\n
• 子例程的深度递归"%s"
  \n(W 递归) 该子例程调用自身的次数（直接或间接）比返回的次数多 100 次。这可能表示无限递归，除非您正在编写奇怪的基准程序，在这种情况下它表示其他内容。
\n

\n

\n

它只是一个运行时警告，因此如果您认为它是虚假的，请使用编译指示禁用它。

\n

sub known_deep_recursion {\n  no warnings \'recursion\';\n\n  ...;\n}\n

\n

Perl 文档的同一部分描述了一种更激进且显然不必要的方法来实现相同的效果。

\n

\n

perl通过重新编译二进制文件，将 C 预处理器宏设置为所需值，可以将该阈值从 100 更改PERL_SUB_DEPTH_WARN为所需值。

\n

\n\n

哈斯克尔

\n

Haskell 是一种纯函数式语言，其中递归至关重要。以尾递归方式编写 Haskell ，如下所示

\n

\n

如果递归调用的最终结果是函数本身的最终结果，则递归函数是尾递归的。如果必须进一步处理递归调用的结果（例如，向其添加 1，或在其开头添加另一个元素），则它不是尾递归。

\n

\n

利用编译器对惰性求值和保护递归的支持，这意味着编写良好的 Haskell 代码可以既简洁又具有出色的性能。

\n

但 Haskell 也不能免受与递归相关的失控分配的影响。写得不好的Haskell 代码也会出现堆栈问题，如堆栈溢出所述页面所述。

\n

\n

Haskell 中没有调用堆栈。相反，我们找到了一个模式匹配堆栈，其条目本质上是 case 表达式，等待其审查者进行足够的评估，以便它们可以匹配构造函数 (WHNF)。

\n

当 GHC 计算 thunked [即未计算的] 表达式时，它使用内部堆栈。这个用于 thunk 评估的内部堆栈在实践中可能会溢出。

\n

\n

Haskell 没有像过程语言那样的调用堆栈，因此这些崩溃被称为空间泄漏。

\n

\n

Haskell 程序有时会消耗比所需更多的内存，这通常是由于懒惰太多或太少造成的。

\n

\n

例如，下面的简单 Haskell 程序

\n

mysum :: [Integer] -> Integer\nmysum = foldr (+) 0\n\nmain = print (mysum [1..10000000000])\n

\n

当在我的机器上运行时 \xe2\x80\x94 如果它不在你的机器上运行，则增加上限直到它 \xe2\x80\x94 结果

\n

mysum：内存不足

\n

将程序更改为

\n

import Data.List (foldl\')\n\nmysum :: [Integer] -> Integer\nmysum = foldl\' (+) 0\n \nmain = print (mysum [1..10000000000])\n

\n

需要一段时间才能运行，但最终会以正确的结果终止。对于初学者来说，推理 Haskell 程序\xe2\x80\x99s 的空间使用情况可能很棘手。使用探查器消除空间泄漏是一个高级主题。

\n\n

概括

\n

两者都是优秀的语言，尤其是在各自的领域。我们程序员有时会犯错误。资源限制和停机问题将始终对我们不利。编程语言以自己的方式处理这些限制。

\n