Hacker News new | past | comments | ask | show | jobs | submit
How does the compiler know whether it's just really long or infinite?

One straightforward approach is to use Hoare logic [1], specifically the method of loop invariants and loop conditions. If you have a loop where the conditions are expressed only in terms of invariants then the conditions will never change truth values during iteration of the loop, thus you have an infinite loop.

Now, some loops are written deliberately like this, i.e. "while (true)", and so there you need to look at whether the body of the loop contains any side effects (reading input, printing, etc). Then you have what is called a "productive infinite loop", such as an event loop or a REPL. Of course you can't prove this sort of loop will ever halt, since the user may never elect to issue the quit command, but these sorts of loops often tend to spend most of their time with the process sleeping until the operating system wakes them up to handle an event.

[1] https://en.wikipedia.org/wiki/Hoare_logic