好奇如何在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-arg函数,还是一个我不知道的更普遍的特殊情况？

[编辑]:

还有一个问题:如果这恰好是编译器的特殊处理,那么在无法检查所有无限循环时执行此操作的原因是什么？"熟悉的"语言并不关心像while (true);或者这样的案例int f() { return f();},对吗？

非常感谢.

Answer 1

GHC将Haskell实现为图形缩减机.将您的程序想象成一个图形,每个值都作为一个节点,并从它到每个值所依赖的值.除此之外,我们很懒,所以你真的只从一个节点开始 - 为了评估该节点,GHC必须"输入"它并将其打开到带参数的函数.然后它将函数调用替换为函数体,并尝试将其减少到足以使其成为头部正常形式等.

上面的内容非常简洁,为了简洁起见,我肯定要省略一些必要的细节.

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

这是一个更隐喻的解释.如果我有一系列指令在屏幕周围移动一只乌龟(标识),那么没有一种方法可以判断它们将产生什么样的形状,或者这种形状是否在没有运行的情况下终止.但是,如果在运行它们时,我注意到乌龟的路径已经越过,我可以向用户表明"啊哈!乌龟穿过了它的路径!" 所以我知道乌龟已经到达了之前的位置 - 如果路径是通过评估图形节点的电路,那么告诉我们我们处于循环中.然而,乌龟也可以进入,例如,膨胀的螺旋.它永远不会终止,但它也永远不会超越它的先前道路.

因此,由于使用黑洞,出于多种原因,我们对评估所遵循的标记"路径"有一些概念.如果路径穿过自己,我们可以告诉并抛出异常.但是,有一百万种方法可以分散,而不涉及穿越自身的路径.在这些情况下,我们无法分辨,也不会抛出异常.

有关当前实施黑洞的超级技术细节,请参阅Simon Marlow在最近的Haskell实施者研讨会上的演讲,"在多核上安排懒惰评估"在http://haskell.org/haskellwiki/HaskellImplementorsWorkshop/2010的底部.

Answer 2

在一些有限的情况下,编译器可以确定这样的循环作为其他控制流分析的一部分存在,并且在那时用引发适当异常的代码替换循环术语.当然,这并非在所有情况下都能做到,而只是在一些更明显的情况下,它们自然而然地脱离了编译器正在做的其他工作.

至于为什么Haskell比其他语言更常见:

• 这些情况不会发生在C等严格的语言中.这些循环特别发生在惰性变量的计算取决于它自己的值时.
• 诸如C之类的语言在循环中具有非常特定的语义; 即,做什么的顺序.因此,他们被迫实际执行循环.然而,Haskell定义了一个特殊值_|_("底部"),用于表示错误的值.对自己严格的值 - 即,它们依赖于自己的计算值 - 是_|_.模式匹配的结果_|_可以是无限循环或异常; 你的编译器在这里选择后者.
• Haskell编译器对执行严格性分析非常感兴趣 - 即,证明某个表达式依赖于某些其他表达式 - 以执行某些优化.这种循环分析自然地作为严格性分析器中的边缘情况而自然地出现,必须以这种或那种方式处理.