loops - 好奇 Haskell 中如何评估 "loop = loop"

Question

我认为这样的表达式会导致 Haskell 永远评估。但是 GHCi 和编译程序中的行为让我感到惊讶。

例如，在 GHCi 中，这些表达式一直阻塞到 I Control+C ，但不消耗 CPU。看起来像是在 sleep 。

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 必须“输入”它并将它打开到一个带有参数的函数。然后它用函数体替换函数调用，并尝试将其减少到足以使其成为头部正常形式等。

以上内容非常随意，为了简洁起见，我肯定会省略一些必要的细节。

在任何情况下，当 GHC 输入一个值时，它通常会在评估节点时将其替换为黑洞(或者，根据您的术语，在减少闭包时)这有很多目的。首先，它堵住了潜在的空间泄漏。如果节点引用了一个在其他地方都没有使用的值，那么即使在评估节点时，黑洞也会允许对该值进行垃圾收集。其次，这可以防止某些类型的重复工作，因为在多线程环境中，两个线程可能会尝试输入相同的值。黑洞将导致第二个线程阻塞，而不是评估已经被评估的值。最后，这恰好允许有限形式的循环检测，因为如果一个线程试图重新进入它自己的黑洞，我们可以抛出一个异常。

这里有一个更隐喻的解释。如果我有一系列指令在屏幕上移动乌龟(在 Logo 中)，则没有一种方法可以判断它们将产生什么形状，或者该形状是否在不运行它们的情况下终止。但是，如果在运行它们时，我注意到乌龟的路径已经越过了自己，我可以向用户指示“啊哈!乌龟已经越过了它的路径!”所以我知道乌龟已经到达了它以前的位置——如果路径是通过评估图的节点的回路，那么这告诉我们我们处于一个循环中。然而，乌龟也可以进入，例如，一个膨胀的螺旋。它永远不会终止，但它也永远不会越过它之前的路径。

因此，由于使用了黑洞，出于多种原因，我们有一些关于评估遵循的标记“路径”的概念。如果路径与自身相交，我们可以判断并抛出异常。然而，有一百万种不涉及路径交叉本身的事物分歧的方式。在这些情况下，我们无法判断，也不要抛出异常。

有关当前黑洞实现的超极客技术细节，请参阅 Simon Marlow 在最近的 Haskell 实现者研讨会上的演讲，“在多核上调度延迟评估”，位于 http://haskell.org/haskellwiki/HaskellImplementorsWorkshop/2010 底部。 .