好奇在Haskell中如何評估「loop = loop」

Question

我認爲像這樣的表達式會導致Haskell永遠評估。但GHCi和編譯程序的行爲讓我感到驚訝。

例如，在GHCi中，這些表達式被阻止，直到I Control+C，但不消耗CPU。看起來它正在睡覺。

let loop = loop 
let loop = 1 + loop 

我試着用GHC編譯這些程序：

main = print loop 
    where loop = 1 + loop 

main = print loop 
    where loop = if True then loop else 1 

印刷是什麼：

Main: <<loop>> 

所以我的問題是：顯然，這些表達式被編譯成比循環或不同的東西遞歸調用命令式語言。他們編譯了什麼？這是一個特殊的規則來處理右手邊的0-arg函數，或者這是我不知道的更一般的特殊情況？

[編輯]：

一個問題：如果發生這種情況是由編譯器進行特殊處理，後面是什麼這樣做時，它不可能檢查所有無限循環的原因是什麼？ '熟悉'語言不關心像while (true);或int f() { return f();}這樣的情況，對不對？

非常感謝。

Answer 1

GHC實現Haskell作爲圖減少機器。將您的程序想象成一個圖，每個值都作爲一個節點，並且從它到每個值取決於的值。除了我們很懶惰，所以你真的只從一個節點開始 - 並且爲了評估該節點，GHC必須「輸入」它並將它打開爲帶有參數的函數。然後它將該函數調用替換爲該函數的主體，並嘗試將其減少到足以使其進入正常形式等等。

以上是非常handwavy，我敢肯定省略一些必要的細節，以簡潔的利益。

在任何情況下，當GHC輸入一個值時，它通常會在評估節點時用黑洞代替它（或根據您的術語，當閉包被減少時）。這有很多目的。首先，它堵塞了潛在的空間泄漏。如果節點引用一個在其他地方無用的值，那麼即使在計算節點時，黑洞也允許垃圾回收。其次，這可以防止某些類型的重複工作，因爲在多線程環境中，兩個線程可能會嘗試輸入相同的值。黑洞會導致第二個線程阻塞而不是評估已經被評估的值。最後，這恰好允許有限形式的循環檢測，因爲如果一個線程試圖重新輸入它自己的黑洞，我們可以拋出一個異常。

這是一個比較隱喻的解釋。如果我有一系列的指令可以在屏幕上移動一隻烏龜（標誌），沒有辦法告訴他們將會生成什麼樣的形狀，或者該形狀是否終止而不運行它們。但是，如果在運行它們的時候，我注意到烏龜的路徑已經越過了自己，我可以向用戶指出：「烏龜已經越過了它的路！所以我知道烏龜已經達到了它以前的地步 - 如果路徑是通過評估圖形節點的迴路，那麼這就告訴我們我們處於一個循環中。然而，烏龜也可以進入，例如，擴大的螺旋。它永遠不會終止，但它也永遠不會跨越其先前的道路。所以，由於使用黑洞，出於多種原因，我們對評估所遵循的標記「路徑」有一些概念。如果路徑交叉，我們可以告訴並拋出一個異常。然而，有一百萬種方法可以分歧，而不涉及路徑本身。在這些情況下，我們不能說，也不要拋出異常。

有關當前黑洞實現的超級技術細節，請參閱最近的Haskell實現者研討會的Simon Marlow的演講「在多核上安排惰性評估」，底部爲http://haskell.org/haskellwiki/HaskellImplementorsWorkshop/2010。

Answer 2

在一些有限的情況下，編譯器可以確定這樣一個循環作爲其他控制流分析的一部分存在，並在那一點上用代碼引發一個適當的異常來代替循環術語。當然，這在所有情況下都不能完成，但只有在一些更明顯的情況下，編譯器正在從其他工作中自然掉落。

至於爲什麼哈斯克爾認爲這往往比其他語言：

• 這些情況不會發生在嚴格比如C.當一個懶惰的變量的計算取決於其自身的價值，這些迴路專門發生語言。
• 諸如C這樣的語言在循環中具有非常特定的語義;即按照什麼順序進行。因此，他們被迫實際執行循環。然而，Haskell定義了一個特殊值_|_（「bottom」），用於表示錯誤的值。對自己嚴格的價值觀 - 即，它們取決於自己的價值來計算 - 是_|_。 _|_上的模式匹配結果可能是無限循環或異常;你的編譯器在這裏選擇後者。
• Haskell編譯器對執行嚴格分析非常感興趣 - 即證明某個表達式依賴於某些其他表達式 - 以執行某些優化。這種循環分析自然而然地作爲嚴格性分析器中的邊緣情況而出現，必須以某種方式處理。