Frege是否执行尾部调用优化？

Question

在Frege中对尾部调用进行了优化。我知道Java和Clojure和Scala等编译成JVM字节码的语言都没有TCO。那Frege呢？

Answer 1

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

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

也就是说，在函数式语言中，静态堆栈深度本质上比Java更深。因此，需要为一些程序提供更大的堆栈(即使用-Xss1m)。

有一些病态的情况，其中构建了大的块，当它们被评估时，将会发生堆栈溢出。一个臭名昭著的例子是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 to (even (pred (pred N)。even必须计算(pred (pred n))以查看参数是0还是1，然后返回另一个thunk (odd (pred ( n-2 ))，其中n-2已被计算。这样，所有调用(在JVM级别)都是从println内部完成的。在任何时候，even都不会实际调用odd，反之亦然。

如果取消对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)又必须充分评估even (pred n)，因此它将占用2*n个堆栈帧。

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