Frege是否执行尾调用优化？

Question

尾部调用是否在Frege中进行了优化.我知道在Java和编译为JVM字节码的语言中都没有TCO,如Clojure和Scala.弗雷格怎么样？

Answer 1

Frege通过简单地生成while循环来执行Tail Recursion Optimization.

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

话虽这么说,静态堆栈深度本质上在功能语言中比在Java中更深.因此,某些程序需要被赋予更大的堆栈(即使用-Xss1m).

存在病态情况,其中构建了大的thunk,并且当它们被评估时,将发生堆栈溢出.一个臭名昭着的例子是foldl函数(与Haskell中的问题相同).因此,Frege中的标准左侧折叠是折叠,它在累加器中是尾递归和严格的,因此在常量堆栈空间中工作(如Haskells foldl').

下面的程序应该不会在2分或3秒堆栈溢出,但打印"假":

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(奇数(pred n)).因此它试图评估这个thunk,它得到另一个thunk(even(pred(pred n))).甚至必须评估(pred(pred n))以查看参数是0还是1,然后返回另一个thunk(odd(pred(n-2)),其中n-2已经被评估.这样,所有的调用(at JVM级别)是在println中完成的.甚至实际上都不会调用奇数,反之亦然.

如果取消注释内联指令,则会获得偶数的尾递归版本,并且结果的获得速度提高十倍.

毋庸置疑,这种笨拙的算法仅用于演示 - 通常可以通过一些操作来检查均匀性.

这是另一个版本,它是病态的并且会堆栈溢出:

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有一天应该有适当的尾调用,这也不会改变.原因是严格函数的参数中的递归.