Haskell program outputs `<<loop>>`

Question

I wrote a Haskell program that preforms a binary search on a list. At least that's what I thought it does. When I compiled the program with ghc v7.6.3 and ran the program I got the following output:

progname: <<loop>>

What on earth does this output mean? Does it mean I had an infinite loop that ghc optimized away? How am I supposed to debug this?

Burette

Are you aware of the ghci debugger? You can also re-purpose HPC to find out which code is NOT being executed as a way to narrow down a loop. – Candancecandela

@ThomasM.DuBuisson GHCI raises: Exception: <<loop>>. I assume the compiled output progname: <<loop>> is and STDERR message. Does this mean I have an infinite loop? – Burette

Yes, it's the RTS (runtime system) detecting an infinite loop (which it can do in certain cases). – Boyne

@ThomasM.DuBuisson @Boyne If one of you composes an answer describing that <<loop>> is an exception raise by the runtime system in the event of a detectable infinite loop, I'll accept your answer. – Burette

It's specifically when it detects the infinite loop that results when evaluating a specific constructor requires evaluating that constructor. – Yapok

@Yapok Thanks, I found the problem, had c = k - c instead of c = k - n. The circular reference is what raise the exception. Surprised that compiled...!? – Burette

@awashburn You can have self-referential values that are fully defined. fibs = 0 : scanl (+) 1 fibs, for instance. That's why it's allowed. – Yapok

Answer 1

As several of the comments have said, this is the Haskell RTS detecting an infinite loop at run-time. It cannot always detect such loops, but in simple cases it can.

For example,

x = x + 1

will compile just fine, but provoke an exception at run-time. (Incidentally, this is an exception - in particular, you can catch it if you want. But you probably don't "want".)

So why does GHC even let this compile? Well, because if I replace + with, say, :, then the expression now terminates just fine. (It represents a 1-element circular list.) The compiler can't tell at compile-time what is and is not sensible recursion. The RTS can't always tell at run-time; but when it can tell something's wrong, it'll let you know by throwing an exception at you.

Atrice

Is there any way to force Haskell to also output which infinite loop it found? – Karns

@Karns Sadly no. About the best you could do is try to catch the exception and print out where you caught it from - but that would require you to have some idea where to start looking in the first place. Usually loop bugs are something as silly as a typo (e.g., you meant x = foo y but accidentally wrote x = foo x). – Atrice

@Karns If you compile with profiling enabled, the following will tell you where the exception was throw: ./progName +RTS -xc -RTS – Burette

@Atrice Could you add your example ( x = foo x) to your answer? I know this is an old question but I was just sent here from google with the same error and it was a simple issue like what you said. That may provide value to other haskell noobs like myself (and comments aren't forever). – Quasijudicial

The comment from @Burette is what those who land on this question are looking for. – Wacker