[Haskell-cafe] Re: A guess on stack-overflows - thunks build-up
and tail recursion
wren ng thornton
wren at freegeek.org
Fri Mar 20 20:22:29 EDT 2009
Günther Schmidt wrote:
> the point I wanted to stress though is that the stack overflow does
> actually not occur doing the recursive algorithm, just a build-up of
> The algorithm itself will eventually complete without the stack overflow.
> The problem occurs when the result value is needed and thus the thunks
> need to be reduced, starting with the outermost, which can't be reduced
> without reducing the next one .... etc and it's these reduction steps
> that are pushed on the stack until its size cause a stack-overflow.
A further detail is that even evaluating the thunks may succeed without
stack overflow, provided the thunks are of the right sort.
For example, if your functions are data constructors then things are
fine (modulo strict constructors). The reason is that evaluation
proceeds to WHNF, so it terminates as soon as you hit the first head,
though there may still be thunks further down.
Another example is if your function is something like const which, in
effect, only needs to look at a small finite portion of the input and
then ignores the rest. Again, this function will return some (weak-)head
before pulling on enough thunks to overflow the stack.
In both of these cases it's the interplay of laziness with WHNF
evaluation which saves things. The problem with (+ :: Int->Int->Int) is
that it's strict in both arguments and so it has to evaluate the entire
tree of thunks before it can return any head. So here, using a strict
fold amortizes the evaluation across the recursion which ensures that
peak stack usage is always within bounds.
For the data constructor example above, using a strict fold is not a win
because it means you necessarily force the entire data structure, even
though you may only need a portion of it. And for some data structures,
namely functions, you'll increase total work and allocation even if you
do end up needing the whole thing.
For the const example, the strictness of the fold is neutral provided
that it follows the grain of the function. That is, if there's a
computation that you throw away, you want to be sure to evaluate things
from the direction that you don't end up evaluating something before
later finding out you're going to throw it away.
More information about the Haskell-Cafe