[Haskell-cafe] what is a stack overflow?

[Iavor Diatchki]

hi,
it may happen for different reasons,
but a common one is when you have a foldl pattern (programming with an
accumulator),
for example like this:

sumList1 [] accum      = accum
sumList1 (x:xs) accum  = sumList1 xs (x + accum)

this adds a list of numbers with an accumulator. 
because haskell is lazy however, the additions (the accumulator)
are not evaluated, instead the compiler builds a big expression,
that is to be evaluated later. for example:
sumList1 [1,2,3] 0 = sumList1 [2,3] (1 + 0) = sumList1 [3] (2 + (1 + 0)) = 
sumList1 [] (3 + (2 + (1 + 0)) = 3 + (2 + (1 + 0)
notice that the accumlator is not evaluated as you go along.
now the way this expression is evaluated (roughly) is:
start pushing... (stack on the rhs)
3 + (2 + (1 + 0)     []
2 + (1 + 0)            [3]
1 + 0                    [2,3]
0                          [1,2,3]
now poping...
1                          [2,3]
3                          [3]
6                           []
and the result is 6.
if the list is very long, you will need to push very many things on
the stack to evaluate the expression, and so you might run out of
stack.

the way to avoid this problem is to not create the big expression,
by forcing the accumulator to be evaluated "as you go along" rather
then once at the end.
this can be done like this:

sumList2 [] accum = accum
sumList2 (x:xs) accum = sumList2 xs $! (x + accum)

($!) is like ($) except that it forces the evaluation of its arguments.
now the expression is likely to be evaluated using very little stack
(if the compiler notices that we have a tail recursive call, and it should)

hope this helped
-iavor







On Mon, 24 Jan 2005 19:19:09 -0500 (Eastern Standard Time), S.
Alexander Jacobson <alex at alexjacobson.com> wrote:
> Thank you iavor.  But the -K option doesn't appear
> to work with ghci.  And I guess the bigger
> question is what sort of code  causes a
> stack overflow.  If 5M is enough stack for most
> programs then I obviously have some basic coding
> error which is causing a stack overflow...
> 
> What sort of code causes that?
> 
> -Alex-
> ______________________________________________________________
> S. Alexander Jacobson tel:917-770-6565 http://alexjacobson.com
> 
> On Mon, 24 Jan 2005, Iavor Diatchki wrote:
> 
> > hi,
> > programs compile with GHC have a bunch of command line switches.
> > you can see them by typing:
> > myProg +RTS -help
> > one of them enables you to specify stack space, e.g.
> > myPorg +RTS -K5M
> >
> > (very briefly) the stack is a part of memory used by the compiler to
> > pass around arguments
> > to functions, and for temporary computations.
> > -iavor
> >
> >
> >
> >
> > On Mon, 24 Jan 2005 17:16:08 -0500 (Eastern Standard Time), S.
> > Alexander Jacobson <alex at alexjacobson.com> wrote:
> >> GHC assumes the user knows the difference between
> >> the heap and the stack.  I don't.  No matter how
> >> much heap I specify on the GHCi command line, I
> >> get a stack overflow exception.  I have no idea
> >> what that means or how to remedy it.  Hints?
> >>
> >> Note: My program is basically creating a few 100k
> >> item FiniteMaps.  I don't think that should exceed
> >> the memory on my laptop....
> >>
> >> -Alex-
> >>
> >> ______________________________________________________________
> >> S. Alexander Jacobson tel:917-770-6565 http://alexjacobson.com
> >> _______________________________________________
> >> Haskell-Cafe mailing list
> >> Haskell-Cafe at haskell.org
> >> http://www.haskell.org/mailman/listinfo/haskell-cafe
> >>
> >
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>