[Haskell-cafe] Diagnosing stack overflow

[Matthew Brecknell]

Justin Bailey:
> I am trying to determine why my stack overflows in my medium sized
> program [...snip...]
> 
> prefixesAtLeast :: Int -> [S.ByteString] -> Int
> prefixesAtLeast !0 !ss
>   | null ss = 0
>   | all S.null ss = 0
>   | otherwise = -1
> prefixesAtLeast !n !ss = prefixesAtLeast' n ss
>   where
>       prefixesAtLeast' !n ss
>         | n < 0 = -1
>         | null ss = n
>         | otherwise =
>             let (!s : (!rest)) = ss
>             in
>               prefixesAtLeast' (n - (S.length s)) rest

Stack overflows often occur when you evaluate a "thunk" (unevaluated
computation) which you have previously allowed to become deeply nested.
The usual example is something like:

print $ foldl (+) 0 [1..1000000]
=> print $ foldl (+) (0+1) [2..1000000]
=> print $ foldl (+) ((0+1)+2) [3..1000000]
=> print $ foldl (+) (((0+1)+2)+3) [4..1000000]
=> ...
=> print (...(((0+1)+2)+3)+...+1000000)
=> stack overflow

The key point of the example is that foldl itself doesn't need any of
the intermediate values of the accumulator, so these just build up into
a deeply-nested unevaluated thunk. When print finally demands an
integer, the run-time pushes a stack frame for each level of parentheses
it enters as it tries to evaluate the thunk. Too many parentheses leads
to a stack overflow. Of course, the solution to the example is to use
foldl', whose implementation uses strictness annotations to force
evaluation of the accumulator at each iteration.

In your function, all the thunks you create will be evaluated in the
next recursive call, so it's unlikely that prefixesAtLeast is *in
itself* causing a stack overflow.

However, it's possible that your use of this function is forcing
evaluation of a deeply-nested thunk you've created somewhere else (as
print does in the foldl example). So if your initial indications are
that the stack overflow is occurring somewhere during the evaluation of
prefixesAtLeast, you might want to try following the food-chain back
through its suppliers (parameters) until you find something like the
foldl example.

By they way, your sprinkling of strictness annotations (a sure sign of
stack-overflow desperation!) should not be necessary. Everything you
have annotated should be forced anyway, either immediately or within one
recursive call. In particular, !0 is entirely unnecessary, since
matching against 0 does just as good a job of forcing the parameter
value as the strictness annotation.