[Haskell-cafe] what is a stack overflow?
S. Alexander Jacobson
alex at alexjacobson.com
Tue Jan 25 11:03:30 EST 2005
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?
On Mon, 24 Jan 2005, Iavor Diatchki wrote:
> it may happen for different reasons,
> but a common one is when you have a foldl pattern (programming with an
> 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  (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) 
> 1 + 0 [2,3]
> 0 [1,2,3]
> now poping...
> 1 [2,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
> 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
> 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?
>> S. Alexander Jacobson tel:917-770-6565 http://alexjacobson.com
>> On Mon, 24 Jan 2005, Iavor Diatchki wrote:
>>> 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.
>>> 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....
>>>> S. Alexander Jacobson tel:917-770-6565 http://alexjacobson.com
>>>> Haskell-Cafe mailing list
>>>> Haskell-Cafe at haskell.org
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
S. Alexander Jacobson tel:917-770-6565 http://alexjacobson.com
More information about the Haskell-Cafe