[Haskell-cafe] Stack, Heap and GHC

[Ian Lynagh]

On Fri, Dec 15, 2006 at 10:05:38AM +0000, Felix Breuer wrote:
> On Thu, 14 Dec 2006 15:31:54 -0800, David Roundy <droundy at darcs.net> wrote:
> > 
> > main = do putStrLn "strict foldl1"
> >           print $ foldl1' (\a b -> a + 1) $ [1..largenum]
> >           putStrLn "lazy foldl1"
> >           print $ foldl1 (\a b -> a + 1) $ [1..largenum]
> 
> 2) Let me see if I get this right. The strict version runs in constant
> space because in the expression
> 
>   (((1 + 1) + 1) ... + 1)
> 
> the innermost (1 + 1) is reduced to 2 right away.

The strict version never creates the expression (((1 + 1) + 1) ... + 1).
It's easier to see with foldl':

    foldl' (\a b -> a + 1) 0 [1..3]
                                    { evaluates 0+1 = 1 }
 -> foldl' (\a b -> a + 1) 1 [2..3]
                                    { evaluates 1+1 = 2 }
 -> foldl' (\a b -> a + 1) 2 [3..3]
                                    { evaluates 2+1 = 3 }
 -> foldl' (\a b -> a + 1) 3 []
 -> 3

> The lazy version first
> uses a huge amount of heap space by building the entire expression
> 
>   (((1 + 1) + 1) ... + 1)
> 
> on the heap. The evaluation of this expression starts by placing the 
> outermost + 1 on the stack and continues inward, not actually reducing
> anything, before everything has been placed on the stack, which causes
> the overflow. Correct?

Right, foldl doesn't evaluate its argument as it goes, so it builds
(((0+1)+1)+1) (on the heap):

    foldl (\a b -> a + 1) 0 [1..3]
 -> foldl (\a b -> a + 1) (0+1) [2..3]
 -> foldl (\a b -> a + 1) ((0+1)+1) [3..3]
 -> foldl (\a b -> a + 1) (((0+1)+1)+1) []
 -> (((0+1)+1)+1)

Now we need to evaluate (((0+1)+1)+1) to get the final answer. You can
imagine a simple recursive evaluation function which, in the call 
    evaluate (((0+1)+1)+1)
recursively calls
    evaluate ((0+1)+1)
which recursively calls
    evaluate (0+1)
and it is this recursion that has a stack that overflows.


Thanks
Ian