stack overflow

[Simon Peyton-Jones]

Consider=20
	foldl (+) 0 [x1,x2,x3,x4,...

This rewrites to

	foldl (+) (0 + x1) [x2,x3,x4,...]
=3D=3D>	foldl (+) (0 + x1 + x2) [x3,x4,...]
=3D=3D>	foldl (+) (0 + x1 + x2 +x3) [x4,...]

And so on.  So we build up a giant chain of thunks.
Finally we evaluate the giant chain, and that builds up
a giant stack.

Why can't GHC evaluate as it goes?  Because it's only
correct to do so if the function is strict in its second argument,
which (+) is, and so is addToFM.

If GHC were to inline foldl more vigorously, this would happen.
Maybe we should make it do so, to avoid gratuitous leaks.

Simon

| -----Original Message-----
| From: Julian Assange [mailto:proff@iq.org]
| Sent: 24 February 2001 10:50
| To: haskell@haskell.org
| Cc: proff@iq.org
| Subject: stack overflow
|=20
|=20
| -- compile with:
| -- ghc -i/usr/lib/ghc-4.08.1/imports/data -lHSdata=20
| -fglasgow-exts -O -fglasgow-exts wordfreq.hs -o wordfreq
| module Main where
| import List
| import Char(toLower)
| import FiniteMap(fmToList,emptyFM,addToFM,lookupWithDefaultFM)
|=20
| main =3D interact (unlines . pretty . sort . fmToList .
|                  makemap . words  . lower)
|        where
|        pretty l  =3D [w ++ " " ++ show n | (w,n) <- l]
|        sort      =3D sortBy (\(_,n0) (_,n1) -> compare n0 n1)
|        makemap   =3D foldl f emptyFM
| 	           where
| 	           f fm word  =3D addToFM fm word (n+1)
| 	                        where
|                                 n =3D lookupWithDefaultFM fm 0 word
|        lower     =3D map toLower
|=20
|=20
|=20
| When used with a 170k input file, makemap suffers from a stack
| overflow. foldl should be tail recursive. What's the score?
|=20
| Julian
|=20
| _______________________________________________
| Haskell mailing list
| Haskell@haskell.org
| http://www.haskell.org/mailman/listinfo/haskell
|=20