Non tail-recursive function not blowing up in GHCi. Why?

Question

I was expecting to see my stack blow with the following code.. yet it didn't:

*Main> let blowwss x = if x == 0 then 0 else (1 + blowwss (x-1)) *Main> blowwss 1000000 1000000

The function doesn't seem to be tail-recursive, so I'm wondering what may I be missing. Is GHCi's stack bigger than I thought (how can I see it's stack size, btw?). Is it using some kind of trampoline to get over this? Is it smart enough to convert the function to its iterative counterpart?

Thanks

Note that you don't generally need tail recursion in Haskell to achieve O (1) space complexity. E.g. an infinite lazy list can be consumed right in place and for every thunk that's built up, one is garbage-collected. Conversely, tail-recursive functions also may blow the stack when not strict enough, because the tail-call itself is merely placed on the stack. — The best way to control such issues is to not to write explicit recursion at all, but rely on e.g. folds with well-known strictness properties. — leftaroundabout
– leftaroundabout, Commented Dec 1, 2013 at 14:18
I didn't get it. "tail-recursive functions also may blow the stack when not strict enough, because the tail-call itself is merely placed on the stack." I thought the compiler would rewrite the tail call function as its iterative counterpart? — devoured elysium
– devoured elysium, Commented Dec 1, 2013 at 15:17
@devouredelysium check out haskell.org/haskellwiki/Tail_recursion and blog.sigfpe.com/2007/07/data-and-codata.html. — jberryman
– jberryman, Commented Dec 1, 2013 at 19:14

kosmikus · Accepted Answer · 2013-12-01 14:15:22Z

GHCi's stack is bigger than you think. IIRC, the default stack size is 500M for GHCi, whereas the default stack size for a compiled program is currently 8M. You can set a smaller limit yourself to see that you get a stack overflow (or you can increase your argument significantly).

$ ghci +RTS -K1M GHCi, version 7.6.3: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer-gmp ... linking ... done. Loading package base ... linking ... done. Prelude> let blowwss x = if x == 0 then 0 else (1 + blowwss (x-1)) Prelude> blowwss 1000000 *** Exception: stack overflow

Note that GHC has a stack size limit purely to prevent infinite / unexpectedly deep loops in situations that are most likely programming errors. In principle, the stack can grow indefinitely (constrained by the system memory, of course). Even if you specify a large stack size, the stack actually starts much smaller, but can grow up to the limit. There's currently discussion about possibly removing the limit completely in future versions of GHC.

Would you happen to know the reasoning why GHCi's stack size is larger than that of default compiled programs?
@ThomasEding No, I don't really know. But it seems that there's no separation in stack size between GHC/GHCi and the programs it interprets, and it's at least difficult to change from within GHCi during a session, so a high default seems to make sense.

Mihai Maruseac · Accepted Answer · 2013-12-01 14:20:46Z

You have used a too small value for that. I've moved your function on a separate file

blowwss x = if x == 0 then 0 else (1 + blowwss (x-1)) main = do print $ blowwss 10000000000 print $ blowwss 10000000000000

and then compiled and run

[mihai@esgaroth tmp]$ ghc --make 1.hs [1 of 1] Compiling Main ( 1.hs, 1.o ) Linking 1 ... [mihai@esgaroth tmp]$ ./1 Stack space overflow: current size 8388608 bytes. Use `+RTS -Ksize -RTS' to increase it.

Running this in GHCI I get a high load and then a stack overflow. That is because GHCi's stack is higher, I guess somewhere around 512M.

Collectives™ on Stack Overflow

Non tail-recursive function not blowing up in GHCi. Why?

2 Answers 2

2 Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Linked

Related