haskell - How does the <<loop>> error "work" in detail?

Question

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:

• 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?

• is this runghc-only or does it exist in all final compile outputs?

• will any -o (optimization) flags set much later when building releases disable this apparent built-in loop detection?

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..)

Answer 1

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 compiles to an intermediate language called Core, after having done several optimizations. You can see it using ghc -ddump-simpl ...

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.

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).

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).

Examples:

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>>

Note that each call of h 0 is considered a distinct thunk, hence no black hole is forced there.

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.

If you want to google something, "GHC, blackhole, STG" should be good keywords.