clojure - Frege 是否执行尾调用优化？

Question

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

Answer 1

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

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

话虽如此，静态堆栈深度本质上在函数式语言中比在 Java 中更深。因此，某些程序需要提供更大的堆栈(即使用 -Xss1m)。

有一些病态的情况，其中构建了大 thunk，并且在评估它们时，会发生堆栈溢出。一个臭名昭著的例子是 foldl 函数(与 Haskell 中的问题相同)。因此，Frege 中的标准左折叠是 fold，它在累加器中是尾递归且严格的，因此在恒定堆栈空间中工作(如 Haskell 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)。但它得到的只是对 (odd (pred n)) 的一个重击。因此它试图评估这个 thunk，它得到另一个 thunk 到 (even (pred (pred n)))。 even 必须评估 (pred (pred n)) 以查看参数是 0 还是 1，然后返回另一个 thunk (odd (pred (n-2)) 其中 n-2 已经被评估。
这样，所有调用(在 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) 必须完全评估 ojit_code，因此它将需要 2*n 堆栈帧。

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