12

尾调用是否在 Frege 中进行了优化。我知道 Java 和编译成 JVM 字节码的语言（如 Clojure 和 Scala）都没有 TCO。弗雷格呢？

4

1 回答 1

27

Frege 通过简单地生成 while 循环来进行尾递归优化。

一般尾调用是通过懒惰“顺便”处理的。如果编译器看到对已知（间接）递归的可疑函数的尾调用，则返回惰性结果（thunk）。因此，调用该函数的真正负担在于调用者。这样，可以避免深度取决于数据的堆栈。

话虽如此，静态堆栈深度在功能语言中已经比在 Java 中更深了。因此，一些程序需要获得更大的堆栈（即使用-Xss1m）。

在某些病态的情况下，构建大的 thunk 并且在评估它们时会发生堆栈溢出。一个臭名昭著的例子是 foldl 函数（与 Haskell 中的问题相同）。因此，Frege 中的标准左折叠是 fold，它在累加器中是尾递归和严格的，因此可以在恒定的堆栈空间中工作（如 Haskells foldl'）。

以下程序不应堆栈溢出，而是在 2 或 3 秒后打印“false”：

module Test
    -- inline (odd) 
  where

even 0 = true
even 1 = false
even n = odd (pred n)

odd n = even (pred n)

main args =  println (even 123_456_789)

其工作原理如下： println 必须有一个要打印的值，因此尝试评估（甚至 n）。但它得到的只是一个 thunk to (odd (pred n))。因此它试图评估这个 thunk，它得到另一个 thunk 到 (even (pred (pred n)))。even 必须评估 (pred (pred n)) 以查看参数是 0 还是 1，然后返回另一个 thunk (odd (pred (n-2)) 其中 n-2 已经被评估。这样，所有调用 (at JVM 级别）是在 println 中完成的。甚至从来没有真正调用过奇数，反之亦然。

如果取消注释 inline 指令，则会得到 even 的尾递归版本，结果的获得速度提高了十倍。

不用说，这种笨拙的算法仅用于演示——通常人们会通过位操作来检查均匀性。

这是另一个版本，这是病态的并且会堆栈溢出：

even 0 = true
even 1 = false
even n = not . odd  $ n
odd    = even . pred

问题在这里not是尾调用，它的论点很严格（即，要否定某些东西，你必须首先拥有那个东西）。因此，当even n计算时，not必须完全评估odd n哪个，反过来，必须完全评估even (pred n)，因此它将占用 2*n 堆栈帧。

不幸的是，这不会改变，即使 JVM 有一天应该有适当的尾调用。原因是严格函数的参数中的递归。

于 2012-04-05T15:53:57.763 回答