问题描述
我正在使用此工具，用户可以在其中定义和添加[config文件|内容文本文件|等]自己的模板"(例如胡须等)，它们可以引用其他模板，从而引发循环.就在我要创建最大循环"设置时，我用runghc意识到了一段时间后，该程序仅以<<loop>>的告别消息退出.这实际上对我来说已经足够了，但引起了一些思考:
I'm working on this tool where the user can define-and-include in [config files | content text-files | etc] their own "templates" (like mustache etc) and these can reference others so they can induce a loop. Just when I was about to create a "max-loops" setting I realized with runghc the program after a while just quits with farewell message of just <<loop>>. That's actually good enough for me but raises a few ponderations:
-
GHC或运行时如何真正检测到它陷入了循环，以及如何区分所需的长时间运行的操作和意外的无限循环?停顿的问题仍然是我最后检查过的一件事.
how does GHC or the runtime actually detect it's stuck in a loop, and how would it distinguish between a wanted long-running operation and an accidental infinite loop? The halting problem is still a thing last I checked..
可以自定义设置为编译器或运行时的任何(时间或迭代)限制吗?
any (time or iteration) limits that can be custom-set to the compiler or the runtime?
仅是runghc还是存在于所有最终编译输出中?
is this runghc-only or does it exist in all final compile outputs?
在构建版本中，任何-o(优化)标志是否会在以后设置，从而禁用这种明显的内置循环检测?
will any -o (optimization) flags set much later when building releases disable this apparent built-in loop detection?
我当然可以找出所有困难的方法，但是谁知道也许有人已经对此进行了更详细的研究..(对于"haskell" "<<loop>>"，用google/ddg很难，因为它们会去除尖括号，然后显示结果) 如何在Haskell中循环"等.)
All stuff I can figure out the hard way of course, but who knows maybe someone already looked into this in more detail.. (hard to google/ddg for "haskell" "<<loop>>" because they strip the angle brackets and then show results for "how to loop in Haskell" etc..)
推荐答案
这是对GHC中实现的STG运行时的简单改进".我将分享我的理解，但是GHC专家可能会提供更多有用和准确的信息.
This is a simple "improvement" of the STG runtime which was implemented in GHC. I'll share what I have understood, but GHC experts can likely provide more useful and accurate information.
在进行了几次优化之后，GHC编译为称为Core的中间语言.您可以使用ghc -ddump-simpl ...
GHC compiles to an intermediate language called Core, after having done several optimizations. You can see it using ghc -ddump-simpl ...
在Core中，非常粗略地讲，未评估的绑定(如let x = 1+y+x in f x)会创建一个thunk.在某个地方分配了一些内存来表示闭包，并且使x指向该闭包.
Very roughly, in Core, an unevaluated binding (like let x = 1+y+x in f x) creates a thunk. Some memory is allocated somewhere to represent the closure, and x is made to point at it.
当(如果有)x被f强制执行时，将评估thunk.这是改进之处:在评估开始之前，x的重击将被称为BLACKHOLE的特殊值覆盖.在对x进行评估(针对WHNF)之后，黑洞再次被实际值覆盖(因此，例如f x = x+x，我们就不会重新计算它).
When (and if) x is forced by f, then the thunk is evaluated. Here's the improvement: before the evaluation starts, the thunk of x is overwritten with a special value called BLACKHOLE. After x is evaluated (to WHNF) then the black hole is again overwritten with the actual value (so we don't recompute it if e.g. f x = x+x).
如果黑洞被强行使用，则会触发<<loop>>.这实际上是IO异常(也可以用纯代码引发这些异常，所以很好).
If the black hole is ever forced, <<loop>> is triggered. This is actually an IO exception (those can be raised in pure code, too, so this is fine).
示例:
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都被视为一个不同的重击，因此不会在其中强行插入黑洞.
Note that each call of h 0 is considered a distinct thunk, hence no black hole is forced there.
棘手的部分是，要了解在Core中实际创建了哪些thunk并不是一件容易的事，因为GHC在发布Core之前可以执行一些优化.因此，我们应该将<<loop>>视为奖励，而不是GHC给予的/硬性保证.未来的新优化可能会将某些<<loop>>替换为实际的非终止.
The tricky part is that it's not completely trivial to understand which thunks are actually created in Core since GHC can perform several optimizations before emitting Core. Hence, we should regard <<loop>> as a bonus, not as a given / hard guarantee by GHC. New optimizations in the future might replace some <<loop>>s with actual non-termination.
如果您想用Google搜索一些东西，"GHC，blackhole，STG"应该是不错的关键字.
If you want to google something, "GHC, blackhole, STG" should be good keywords.
这篇关于<<<循环>>>是如何工作的?错误“工作"详细地?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！