对于Haskell中如何评估"loop = loop"的方式感到好奇。

Question

我曾认为这样的表达式会导致Haskell永远执行下去。但在GHCi和编译后的程序中，它们的行为让我感到惊讶。

例如，在GHCi中，这些表达式会一直阻塞，直到我按下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参数函数的特殊规则，还是我不知道的更一般的特殊情况？

[编辑]：

另一个问题：如果这是编译器的特殊处理，那么为什么要这样做，当不可能检查所有无限循环时？“熟悉”的语言不关心像 while (true)； 或 int f() { return f(); } 这样的情况，对吗？

非常感谢。

- Phil

Answer 1

GHC 将 Haskell 实现为图还原机。将您的程序想象成一个图，每个值都是一个节点，并且有一条从每个依赖该值的值指向它的线。但我们采用了惰性计算，因此实际上您只有一个节点--为了对该节点进行评估，GHC 必须“进入”它并将其打开到带有参数的函数。然后，它会将函数调用替换为函数体，并尝试将其缩减到足够简化的程度以使其进入标准形式等。

以上内容非常简单粗略，我相信省略了一些必要的细节。

无论如何，当 GHC 进入一个值时，通常会在节点被评估时用黑洞替换该值（或者根据您的术语，当闭包被约简时）这有许多目的。首先，它可以防止潜在的空间泄漏。如果节点引用一个其他地方未使用的值，则黑洞允许该值在节点被评估时进行垃圾回收。第二，这可以防止某些类型的重复工作，因为在多线程环境中，两个线程可能会尝试同时进入相同的值。黑洞会导致第二个线程阻塞而不会评估已经被评估的值。最后，这恰好允许限制形式的循环检测，因为如果线程尝试重新进入其自己的黑洞，我们可以抛出异常。

下面是一个更加隐喻性的解释。如果我有一系列指令来移动屏幕上的乌龟（在 Logo 中），没有办法告诉我它们会产生什么形状，或者该形状是否会在运行时终止。但是，如果在运行它们时，我注意到乌龟的路径已经交叉，我可以向用户指示“啊哈！乌龟已经穿过了它的路径！”因此我知道乌龟已经到达了它之前到达过的地方--如果路径是通过评估图的节点形成的电路，那么这告诉我们我们正在loop中。然而，乌龟也可能沿着例如扩展螺旋线的路径行进。它永远不会终止，但它也永远不会越过其先前的路径。

因为使用了黑洞技术，出于多种原因，我们对评估所遵循的“路径”有一定的概念。如果路径交叉，我们可以检测到并抛出异常。然而，有无数种事情会发散，这些事情并不涉及路径交叉。在这些情况下，我们无法检测，并且不会抛出异常。

关于当前黑洞实现的超极客技术细节，请参见Simon Marlow在最近的Haskell Implementors Workshop上的演讲“Scheduling Lazy Evaluation on Multicore”，该演讲位于http://haskell.org/haskellwiki/HaskellImplementorsWorkshop/2010底部。

- sclv

Answer 2

在一些有限的情况下，编译器可以确定这样一个循环存在于其其他控制流分析的一部分中，并在此时用代码替换循环项，以抛出适当的异常。当然，这不能在所有情况下都做到，只能在一些更明显的情况下，其中它从编译器正在进行的其他工作自然地产生。

至于为什么Haskell比其他语言更容易发现这一点： - 这些情况不会发生在像C这样的严格语言中。这些循环特别发生在惰性变量的计算取决于其自身值的情况下。 - 例如，C语言在循环中具有非常具体的语义；即按照什么顺序执行什么操作。因此，它们被迫实际执行循环。但是，Haskell定义了一个特殊的值_|_（“底部”），用于表示错误值。对自己严格的值 - 即，它们依赖于自己的值来计算 - 是_|_。对_|_进行模式匹配的结果可能是无限循环或异常；你的编译器在这里选择了后者。 - Haskell编译器非常关注执行严格性分析 - 即，证明某个表达式依赖于某些其他表达式 - 以便执行某些优化。这个循环分析自然而然地成为严格性分析器的一个边缘情况，必须以某种方式处理。

- bdonlan

---

谢谢bdonlan。我刚刚更新了我的问题。那么，试图检测无限循环的原因是什么？为什么在编译时没有警告，但在运行时却有异常？ - Phil

替换这些事物为错误的通常术语是“黑洞化”。另请参考例如fixIO，它本质上做了相同的事情。 - barsoap

虽然 GHC确实可以检测到简单的let loop = loop in ...结构，但是问题中的示例实际上并没有使用“其他控制流分析”进行检测，而是通过“黑洞”机制在运行时进行检测。 - nominolo