5

您将如何调整这个简单的递归示例，以便进行尾调用优化（而不是 a StackOverflowError）？

count 0 = 0
count n = succ (count (pred n))
count 100000
4

1 回答 1

5

这是我称之为“长度/折叠”类型的堆栈溢出。当递归函数用于计算构成结果的函数应用程序的严格参数时，就会发生这种情况。相比：

-- naive computation of list length
-- this is not like it's defined in Frege, of course
length [] = 0
length (_:xs) = 1 + length xs

当第二个参数中的严格foldr f时也会发生这种情况。f

堆栈溢出（SO）还有其他可能的原因：

  1. 尾递归。这在 Frege 中最有效地处理，因为尾递归函数被编译为 while 循环。与其他 JVM 语言不同，永远不会真正导致 SO。
  2. 显式间接尾递归：（例如a尾调用b，尾调用c，...，尾调用a）。这也不应该导致弗雷格出现 SO。
  3. 构建嵌套如此之深的 thunk，以至于在评估时会发生 SO。这就是foldl在 Haskell 中发生的事情。在弗雷格，fold蓄能器的标准是严格的，因此在许多情况下是免疫的。但是，以下内容仍然会在长列表中溢出：fold (<>) mempty (map (Just . Sum) [1..10000])
  4. length/foldr 类型的递归，如我们的示例所示。
  5. 非尾调用中的递归：

这是最后一种情况的示例：

  even 0 = true
  even n = case even (pred n) of
           true  -> false
           false -> true

第二个等式在语义上等价于even n = not (even (pred n))，因此是 4 的一个更加恶意的变体。

要回答您的问题，在您的示例中，可以使用累加器来创建尾递归版本：

count n = go 0 n
    where
       go acc 0 = acc
       go acc n = go (succ acc) (pred n)

也许值得注意的是，您的示例在 Haskell 中也失败了：

GHCi, version 7.6.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> let count 0 = 0; count n = succ (count (pred n))
Prelude> count 10000
10000
Prelude> count 100000
100000
Prelude> count 1000000
1000000
Prelude> count 10000000
10000000
Prelude> count 100000000
*** Exception: stack overflow

它仅以更高的数字溢出的原因是 Haskell RTS 以更适合函数式编程的方式管理 RAM，而 JVM 在启动时分配一个很小的默认堆栈，可容纳 1000 次的调用深度最好的。

即使在 Frege 中，当您强制 JVM 分配更大的堆栈时，您也可以使用您的程序计算更多的数字：

java -Xss512m ....

经验表明，大小为 512m 的堆栈允许单参数函数的调用深度约为 1000 万。

然而，这不是一个通用的解决方案，因为 JVM 会创建具有此堆栈大小的所有线程。因此浪费了宝贵的 RAM。即使您有足够的 RAM，您也可能无法创建大于 2g 的堆栈。

在 Frege 的下一个主要版本中，堆栈溢出类型 3 和 4（见上文）的某些病理情况将得到更好的管理，希望如此。然而，到今天为止，这种结构仅适用于恰好适合 JVM 堆栈的小问题。

于 2015-10-31T09:42:37.593 回答