How does "loop >> error" work?
I am working on this tool where the user can define and include in [config files | text content files | etc.] their own "patterns" (for example, mustaches, etc.), and they can refer to others so that they can trigger a loop. Just when I was going to create the "max-loops" setting, I realized that after runghc the program after a while just leaves with a farewell message only <<loop>> . This is really enough for me, but causes a few reasons:
how does the GHC or runtime actually detect that it is stuck in a loop, and how would it distinguish the desired long-running operation and a random endless loop? The problem with stopping is another thing I checked.
any (temporary or iterative) limits that can be configured on the compiler or at runtime?
Is it
runghc- or does it exist only in all final compilers?Will any
-o(optimization) flags be set much later when the release build disables this obvious inline loop detection?
All that I can understand, of course, of course, but who knows, maybe someone already examined this in more detail .. (hard for google / ddg for "haskell" "<<loop>>" , because they remove angle brackets, and then show the results for “like a loop in Haskell,” etc.)
This is a simple "improvement" in the STG runtime that was implemented in the GHC. I will share what I understand, but GHC experts can provide more useful and accurate information.
GHC compiles to the intermediate language Core, after several optimizations. You can see it using ghc -ddump-simpl ...
Very rudely, in Core, an unvalued binding (e.g. let x = 1+y+x in fx ) creates a thunk. Some memory is allocated somewhere to represent the closure, and x is pointed to it.
When (and if) x forcibly executed with f , then thunk is computed. Here's the improvement: before starting the evaluation, thunk x overwritten with the special BLACKHOLE value. After evaluating x (for WHNF), the black hole is again overwritten with the actual value (therefore, we do not repeat it if, for example, fx = x+x ).
If a black hole is ever forced, <<loop>> triggered. This is actually an IO exception (they can be created in pure code too, so this is normal).
Examples:
let x = 1+x in 2*x -- <<loop>> let gx = g (x+1) in g 0 -- diverges let hx = h (10-x) in h 0 -- diverges, even if h 0 -> h 10 -> h 0 -> ... let g0 = g10 ; g10 = g0 in g0 -- <<loop>> Note that every call to h 0 is considered a great thunk, so there is no black hole there.
The tricky part is that it’s not completely trivial to understand what tricks are actually created in Core, since the GHC can perform several optimizations before fixing Core. Therefore, we should consider <<loop>> as a bonus, and not as a given / firm guarantee of the GHC. New optimizations in the future may replace some <<loop>> actual non-termination.
If you want something Google, "GHC, blackhole, STG" should be good keywords.