<< loop >>错误如何"正常"工作？

Question

我正在使用这个工具,用户可以在[config files |中定义 - 并包含它 内容文本文件| 他们自己的"模板"(如胡子等),这些可以引用其他人,以便他们可以诱导循环.正当我即将创建一个"max-loops"设置时,我意识到runghc程序一段时间之后只是退出了告别消息<<loop>>.这对我来说实际上已经足够好了但引起了一些思考:

• GHC或运行时如何实际检测到它被卡在循环中,它如何区分所需的长时间运行操作和偶然的无限循环？暂停问题仍然是我检查的最后一个问题..

• 任何(时间或迭代)限制可以自定义设置到编译器或运行时？

• 是runghc- 或者它是否存在于所有最终编译输出中？

• -o当构建版本禁用这个明显的内置循环检测时,是否会设置任何(优化)标志？

所有的东西,我当然可以找出困难的方法,但谁知道也许有人已经更详细地研究了这个...(很难google/ddg "haskell" "<<loop>>"因为他们剥离尖括号然后显示"如何在Haskell中循环"的结果"等......)

Answer 1

这是在GHC中实现的STG运行时的简单"改进".我将分享我所理解的内容,但GHC专家可能会提供更有用和准确的信息.

在完成多项优化后,GHC编译为一种名为Core的中间语言.你可以看到它ghc -ddump-simpl ...

非常粗略地说,在Core中,未评估的绑定(如let x = 1+y+x in f x)会创建一个thunk.某些内存被分配到某个地方以表示闭包,并x使其指向它.

x强制执行(和if)时f,将评估thunk.这是改进:在评估开始之前,thunk x被一个名为的特殊值覆盖BLACKHOLE.在x评估之后(到WHNF)然后再次用实际值覆盖黑洞(因此我们不会重新计算它,例如f x = x+x).

如果黑洞被强行,<<loop>>则触发.这实际上是一个IO异常(那些也可以在纯代码中引发,所以这很好).

例子:

let x = 1+x in 2*x          -- <<loop>>
let g x = g (x+1) in  g 0   -- diverges
let h x = h (10-x) in h 0   -- diverges, even if h 0 -> h 10 -> h 0 -> ...
let g0 = g10 ; g10 = g0 in g0   -- <<loop>>

请注意,每次调用都h 0被认为是一个明显的thunk,因此没有强制黑洞.

棘手的部分是,理解哪些thunk实际上是在Core中创建并不是完全无足轻重的,因为GHC可以在发布Core之前执行多次优化.因此,我们应该<<loop>>视为奖励,而不是GHC的给定/硬性保证.未来的新优化可能会<<loop>>用实际的非终止替换一些s.

如果你想谷歌的东西,"GHC,blackhole,STG"应该是很好的关键词.