Why doesn't year=year+1 fail with stack overflow?

Question

year.hs:

year = year + 1

main = print year

This is not a tail recursive call:

year = year + 1
year = (year + 1) + 1
year = ((year + 1) + 1) + 1
...

However runhaskell year.hs does not output anything, which indicates that it run into infinite loop.

Does Haskell compiler make optimizations even for non tail recursive calls?

Answer 1

Because of laziness (plus the monomorphism restriction^†). Basically when you say

year = year + 1

and then evaluate year, Haskell saves space for the result, and then when it sees year it tries to re-use the same result. So when year + 1 tries to evaluate year, the code for year doesn't actually get entered.

In GHC, to implement multi-threading^‡, what it actually does is block the current thread when it tries to obtain the value of a variable that's already being evaluated. Then when the evaluation finishes, it resumes execution of the blocked thread. In this case, the thread is being blocked on an evaluation it itself is doing, which is why you get a deadlock.

If you instead say

year () = year () + 1

then running year () does give a stack overflow for me.

---

^† The monomorphism restriction comes into play because if you add a type signature

year :: Num a => a
year = year + 1

the compiler is perfectly free to treat the Num a dictionary like the () parameter, yielding a stack overflow. In this case that's not really a problem, but not caching intermediate results is a big problem in real computations. In this case, it looks like GHC is actually putting the recursion inside the abstraction over the dictionary, producing code more like

year () = let y = y + 1 in y

which also doesn't produce a stack overflow.

---

^‡ Compiling the code (with GHC) in single-threaded mode yields

<<loop>>

which means GHC detected the infinite loop and decided to complain about it.