好奇在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编译器对执行严格分析非常感兴趣 - 即证明某个表达式依赖于某些其他表达式 - 以执行某些优化。这种循环分析自然而然地作为严格性分析器中的边缘情况而出现，必须以某种方式处理。