[Haskell-cafe] Re: A guess on stack-overflows - thunks build-up and tail recursion

[wren ng thornton]

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 
> thunks.
> 
> 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.

Yes.

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.

-- 
Live well,
~wren