[Haskell-cafe] what is a stack overflow?

[S. Alexander Jacobson]

Ok.  I guessed I was producing a big expression 
of the form

   addToFM (addToFM (addToFM (addToFM (addToFM ...)

I tried to solve it by doing

   (addToFM $! fm) key val

But still got an error.  I then tried the same 
with the wrapper code, but still got the error.

Is there a way to profile stack usage using GHCi 
(without compiling) to find the problem?

-Alex-


On Mon, 24 Jan 2005, Iavor Diatchki wrote:

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

______________________________________________________________
S. Alexander Jacobson tel:917-770-6565 http://alexjacobson.com