What causes <<loop>>?

[Antti-Juhani Kaijanaho]

On Sat, Nov 08, 2008 at 10:32:38AM -0600, Creighton Hogg wrote:
> So I'm trying to debug an issue that is causing GHC to emit the
> <<loop>> warning.  I was hoping to get more information about what
> exactly that tells me about the kind of problem, other than the
> obvious interpretation that I appear to be getting into some kind of
> infinite loop.  What is GHC detecting when it emits that warning?

It basically means that you have - somewhere in your program - a recursive
definition (of something that's not a function) that refers to itself without
going through a data constructor.

A safe recursive definition would be
  let x = Foo (x+1)
However, if you leave out the constructor,
  let x = x + 1
you get a <<loop>> (or a deadlock).

The reason is, when the value of the definition is demanded, it is computed up
to the topmost data constructor (formally, up to "weak head normal form",
WHNF).  Any recursive reference to that value below that constructor is safe,
but if the value itself is needed to compute itself before a constructor is
reached, bad things (namely, either <<loop>> or a deadlock) happen.

The way GHC sometimes detects these situation is that when it starts demanding
the value of a variable[1], it first binds that variable to a special tag called
a "blackhole".  If the evaluation reaches a data constructor without incident,
the blackhole is overwritten with that constructor.  If, however, evaluation
happens to demand the value of a variable that's blackholed, GHC immediately
knows that the wrong kind of recursion has happened.  Thus, my second example
will bomb, since the addition operator finds a blackhole at "x".

Of course, in real programs the recursion can be very indirect, and finding the
culprit can be hard.


[1] More accurately, read "thunk" for "variable" in that paragraph.
-- 
Antti-Juhani Kaijanaho, Jyväskylä, Finland
http://antti-juhani.kaijanaho.fi/newblog/
http://www.flickr.com/photos/antti-juhani/