Hacker News Reader

Comment by prolepunk | Hacker News Reader

First of all the solution of this problem is computationally impossible so this tool makes me feel realy uneasy I'd never use it -- it would actually make predictable easily reproducible bugs impossible to report when this tool is activated. It makes an assumption that infinite loops are just stuck with a false condition and nothing else is affected by that, which I believe is fundametally false.

View on HN

It appears to take memory snapshots. If it detects a repeat in the snapshots it knows that the program will loop indefinitely. Of course it can't detect all infinite loops, but a sizeable subset.

In theory I believe it can actually detect all infinite loops, for an extremely generous definition of "can detect". On a finite-memory machine, a computation fails to halt iff it eventually repeats a state, which it must do in finite time, since there are only finitely many possible states (the finite-ness is what makes the halting problem not apply). However, that finite time might be extremely large, perhaps longer than the age of the universe. A http://en.wikipedia.org/wiki/Busy_beaver function gives an upper bound on how long it can be.

But yeah, the practical use is to tell you when a computation is already looping, for the large subset of infinite loops that result in states being repeated relatively quickly.

> On a finite-memory machine, a computation fails to halt iff it eventually repeats a state

This is too strong of a statement. Lots of software simply loops, repeating the same state over and over, until an external interrupt occurs.

Good point; I guess I was thinking of the simplified textbook case of computations with no external interaction. I wonder if this MIT system is able to exclude the most likely false positives, like polling for input? On the other hand, maybe polling too long for input counts as an infinite---or at least, too long---loop for their use-case of interrupting user programs that seem to be hanging, so that the user can save.

The busy beaver function gives very loose upper bound... A better bound: If the computer can be described with $n$ bit of information, and a program did not terminate with $2^n+1$ operations, then the program has a infinite loop.

$n$ is usually the memory + cpu cache size.

Only if you take a very liberal definition of memory. The following probably isn't an infinite loop, even though it'd look like one under normal definitions of memory (either RAM or RAM+disk):

    $ while ping -W 2 -q -c 1 www.google.com; do sleep 10; done

Eventually, the network will go down.

It only takes memory snapshots to find next end-of-loop instruction in binary code to jump to it, with source equivalent of it being:

   while True:
      if loop_var > 9000:
        break
      loop_var += 1

My main complaint that might as well detect a repeat in snapshot but I really doubt that it detects extraneous changes in loop variables that might be caused by stray infinite loop logic.

From programming perspective it's better to crash hard and let the error be known rather than fail silently and introduce more sublte errors.

From user perspective, what is the point of saving file in a program that is falling over when you could potentially save a corrupt file and instead of retaining some of the work the user will end up with a blob of useless data. I guess you could do Save As... and then manually compare changed data with last save. Still I'd be extremelly suspicious of it.

From programming perspective it's better to crash hard and let the error be known rather than fail silently and introduce more sublte errors.

I am absolutely shocked that nobody else has even hinted at this. I wouldn't recommend this tool in almost any circumstance.

Reply on news.ycombinator.com