Frege是否執行尾部呼叫優化？

Question

在Frege中優化了尾部調用。我知道在Java或者編譯爲像Clojure和Scala這樣的JVM字節碼的語言中都沒有TCO。弗雷格呢？

Answer 1

Frege通過簡單地生成while循環來進行尾遞歸優化。

通用尾部呼叫通過懶惰來「處理」。如果編譯器看到對已知（間接）遞歸的可疑函數的尾調用，則會返回一個延遲結果（一個thunk）。因此，調用該函數的真正負擔在於調用者。這樣，可以避免深度依賴於數據的堆棧。這就是說，靜態堆棧深度在功能語言中本來就比Java更深。因此，有些程序需要更大的堆棧（即使用-Xss1m）。

有病態的情況下，大thunk被建立，當他們被評估，會發生堆棧溢出。一個臭名昭着的例子是foldl函數（與Haskell中的問題相同）。因此，Frege中的標準左摺疊是fold，它是累加器中的尾遞歸和嚴格的，因此在常量堆棧空間中工作（如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 ）。但它所得到的僅僅是（奇數（pred n））。因此，它試圖評估這個thunk，從而得到另一個thunk（甚至（pred（pred n）））。甚至必須在返回其中已經評估了n-2的另一個thunk（odd（pred（n-2））之前必須評估（pred（pred n））以查看參數是0還是1 這樣，所有調用在JVM級別）是從println內部完成的，在任何時候甚至都不會調用奇數，反之亦然。

如果取消註釋內聯指令，則得到even的尾遞歸版本，並且結果獲得10倍。更快

不用說，這種笨拙的算法是僅用於演示 - 通常一個會檢查甚至岬有位操作

這裏是另一個版本，那就是病態的，將堆棧overflo女：

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應該有一天有適當的尾部呼叫，這也不會改變。原因是嚴格函數論證中的遞歸。

Answer 2

@Landei TCO在Scala中完全不支持...試試這個。

def foo() { def bar() { println("bar"); foo() }; println("foo"); bar() } 

請注意，我沒有足夠的信譽來直接發表評論。查找評論我在原始問題的評論中回覆。