frege - 递归和 StackOverflowError

Question

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

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

Answer 1

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

-- 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)还有其他可能的原因:

尾递归。这在 Frege 中处理最有效，因为尾递归函数被编译为 while 循环。与其他 JVM 语言不同，永远不会真正导致 SO。

显式间接尾递归:(例如 a 尾调用 b ，尾调用 c ，...，尾调用 a )。这也不应该在 Frege 中导致 SO。

构建嵌套如此深以至于 SO 发生在评估中的 thunk。这就是 foldl 中发生的事情在 haskell 。在弗雷格，标准fold在累加器中是严格的，因此在许多情况下是免疫的。但是，以下内容仍然在长列表中溢出:fold (<>) mempty (map (Just . Sum) [1..10000])

长度/折叠类型的递归，如我们的示例中所示。

非尾调用中的递归:

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

  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 的调用深度最好的事物。

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

java -Xss512m ....

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

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

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