Bernd Brassel wrote:
Thanks for your answer Simon.
Simon Marlow wrote:
Bernd Brassel wrote:
Consider the following program:
module Stack where
import System.IO.Unsafe
main = print (sim (replicate 1299959 ()))
sim [] = True
sim (_:xs) = goodStack (sim xs)
goodStack x = fromJust (Just x) --no stack overflow
badStack x = unsafePerformIO (return x) --stack overflow
fromJust (Just x) = x
goodStack == id, and GHC even with no optimisation will transform it
into id, and inline it into sim. So with goodStack, sim ends up being
tail-recursive. With badStack, sim is no longer tail recursive
(unsafePerformIO is not inlined), so it runs out of stack. Simple!
Is it really that simple? I guess that in a lazy language we have to
look a bit closer to see what is tail recursive and what is not. If I
understand you correctly, you say that if goodStack was not inlined you
would have a bad stack as well, right?
My apologies - I oversimplified things. You're quite right, it looks like
the unsafePerformIO version ought to be tail-recursive too.
It turns out to be rather subtle. If you replace unsafePerformIO by
unsafeDupablePerformIO (from GHC.IOBase), then you do indeed get
tail-recursion. But this is only due to a clever trick in the RTS: what
happens is that (sim xs) is a thunk, so when evaluating it, even in a
tail-recursive position, an update frame is pushed on the stack. The next
recursive call to (sim xs) pushes another update frame on the stack, and so
on. Since these update frames are all adjacent to one another, a trick
known as "stack squeezing" can squash them down into a single frame, and
this is what happens for unsafeDupablePerformIO.
The ordinary unsafePerformIO is performing stack squeezing once per call,
because the stack squeezing is done by the same code that does the
"duplicate computation" check that unsafePerformIO needs to do. Stack
squeezing doesn't look at the same bit of stack twice, so subsequent
squeezings don't manage to remove any update frames. I've fixed this in my
tree. It also needed some tweaks to the heuristic which decides whether to
squeeze or not based on a cost/benefit tradeoff.
So the upshot is: you can use unsafeDupablePerformIO right now, or you can
wait until I've tested and committed this patch to get tail-recursion with
unsafePerformIO.
I've no idea how it works in Hugs, you'll have to ask them :)
Cheers,
Simon
_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
