40

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?

recursion.ninja
  • 5,377
  • 7
  • 46
  • 78
  • 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. – Thomas M. DuBuisson Feb 01 '14 at 23:58
  • @ThomasM.DuBuisson GHCI raises: `Exception: <>`. I assume the compiled output `progname: <>` is and STDERR message. Does this mean I have an infinite loop? – recursion.ninja Feb 02 '14 at 00:02
  • 4
    Yes, it's the RTS (runtime system) detecting an infinite loop (which it can do in certain cases). – Fixnum Feb 02 '14 at 00:16
  • @ThomasM.DuBuisson @Fixnum If one of you composes an answer describing that `<>` is an exception raise by the runtime system in the event of a detectable infinite loop, I'll accept your answer. – recursion.ninja Feb 02 '14 at 00:42
  • 8
    It's specifically when it detects the infinite loop that results when evaluating a specific constructor requires evaluating that constructor. – Carl Feb 02 '14 at 01:41
  • @Carl 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...!? – recursion.ninja Feb 02 '14 at 03:49
  • 5
    @awashburn You can have self-referential values that are fully defined. `fibs = 0 : scanl (+) 1 fibs`, for instance. That's why it's allowed. – Carl Feb 02 '14 at 05:19

1 Answers1

40

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.

recursion.ninja
  • 5,377
  • 7
  • 46
  • 78
MathematicalOrchid
  • 61,854
  • 19
  • 123
  • 220
  • 6
    Is there any way to force Haskell to also output *which* infinite loop it found? – Bakuriu Mar 05 '14 at 19:21
  • 2
    @Bakuriu 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`). – MathematicalOrchid Mar 06 '14 at 08:45
  • 10
    @Bakuriu If you compile with profiling enabled, the following will tell you where the exception was throw: `./progName +RTS -xc -RTS` – recursion.ninja Sep 08 '15 at 11:31
  • @MathematicalOrchid 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). – jkeuhlen Jun 14 '16 at 21:41
  • The comment from @recursion.ninja is what those who land on this question are looking for. – cornuz Feb 17 '23 at 18:13