10

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

4
  • 1
    Searching for ghc loop gives a few relevant results, including Haskell program outputs `<<loop>>` and this Haskell Cafe message.
    – duplode
    Commented Jan 7, 2017 at 3:40
  • 2
    Despite the halting problem, it is clearly possible to detect non-termination in a limited amount of cases (i.e. an algorithm which proves a program is non-terminating or fails with no answer after a finite amount of time is possible). In short, <<loop>> means that GHC found an expression of the form let x = x in x after simplification, and rewrote it to throw .. where .. is a special exception which produces the message you see when evaluated - I can't recall what this exception is called, but you may not catch it. Commented Jan 7, 2017 at 8:07
  • 6
    @user2407038 I don't believe that's true. I'm pretty sure that <<loop>> detection is entirely at runtime, and detects any case of a value depending on itself, not just being trivially defined as itself.
    – Carl
    Commented Jan 7, 2017 at 8:31
  • 4
    AFAIK GHC raises a <<loop>> whenever, when evaluating a thunk, it finds that it has to evalute the very same thunk to obtain a value. This is more general than what @user2407038 describes. Itis possible to catch many cases of non-termination, the halting problem simply says that we cannot catch all of them.
    – Bakuriu
    Commented Jan 7, 2017 at 9:08

1 Answer 1

8

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.

1
  • 2
    A small correction: when a thread enters a black hole, it puts itself on a list of threads to be woken up and blocks (returns to the scheduler). After all another thread might be in the middle of evaluating the same thunk we wanted to evaluate. GHC sends the <<loop>> exception when it detects a deadlock. Commented Jan 7, 2017 at 13:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.