4

What are the usual causes of "Error C stack overflow" in the Hugs Haskell implementation.

2
  • 4
    Which implementation? HUGS? NHC? GHC? Mar 17, 2010 at 14:02
  • 1
    All the answers seem to be talking about overflowing the Haskell runtime's stack. The C stack is different, at least in GHC. Is this a confusing error message, or is the problem actually FFI-related. (I have done a lot of FFI work and have never seen this. But I use GHC.)
    – jrockway
    Mar 18, 2010 at 1:17

4 Answers 4

11

This can come up if you are used to functional languages in which it is common to do tail-recursion factorization. Say you have a function:

sum = go 0
    where
    go accum [] = accum
    go accum (x:xs) = go (accum+x) xs

Which, incidentally, is the same as

sum = foldl (+) 0

If we evaluate the function we can see the problem:

sum [1,2,3,4]
go 0 [1,2,3,4]
go (0+1) [2,3,4]
go ((0+1)+2) [3,4]
go (((0+1)+2)+3) [4]
go ((((0+1)+2)+3)+4) []
(((0+1)+2)+3)+4

Now to evaluate that expression Haskell uses a stack:

EXPR            | STACK
(((0+1)+2)+3)+4 | 
((0+1)+2)+3     | +4
(0+1)+2         | +3 +4
(0+1)           | +2 +3 +4
1               | +2 +3 +4
3               | +3 +4
6               | +4
10              |

And this is where an overflow can occur. If you evaluated sum [1..10^6], that stack would be a million entries deep.

But note the pathology here. You recurse over a list only to build up a huge fscking expression ("thunk"), and then use a stack to evaluate it. We would rather evaluate it as we are recursing, by making the tail recursion strict:

sum = go 0
    where
    go accum [] = accum
    go accum (x:xs) = accum `seq` go (accum+x) xs

That says to evaluate accum before trying to evaluate the recursive call, so we get (this may take a some patience to understand):

sum [1,2,3,4]
go 0 [1,2,3,4]
let accum = 0 in accum `seq` go (accum+1) [2,3,4]
go (0+1) [2,3,4]
let accum = 0+1 in accum `seq` go (accum+2) [3,4]
go (1+2) [3,4]
let accum = 1+2 in accum `seq` go (accum+3) [4]
go (3+3) [4]
let accum = 3+3 in accum `seq` go (accum+4) []
go (6+4) []
6+4
10

So as we are traversing the list, we are computing the sum so we don't have to use a deep stack to evaluate the result. This modified tail recursion pattern is encapsulated in Data.List.foldl', so:

sum = foldl' (+) 0

A good rule of thumb is to never use foldl, because it always builds up giant thunks. Use foldl' instead. If the output type has lazy structure (eg. a list or a function), use foldr. But there is no silver bullet for avoiding a stack overflow in general, you just have to understand the evaluation behavior of your program. This can be hard sometimes.

But, if I understand correctly, a stack overflow always comes from trying to evaluate a gigantic thunk, though. So look for places where those could be created, and force evaluation to happen earlier.

0
1

A runaway recursion is the most likely candidate... You need to give more info though for a more precise answer.

1

Here's some code that could cause a runaway recursion:

main =
  let x = x :: Int
  in print x

What happens here is that when x is evaluated in print x it starts, then finds out that to complete its evaluation it needs to evaluate x.

4
  • 2
    That probably won't cause a stack overflow though, because of TCO (note that x is a tail call in x). This would be an infinite loop.
    – luqui
    Mar 17, 2010 at 14:42
  • Hmmm... So it is, luqui. I was sure that kind of code generated stack faults last time I tried it (admittedly a few years ago). Mar 17, 2010 at 15:23
  • Oops. I was right, but different situation. If I run that code in GHCi it just loops forever. If I compile it and run it I get the error: a.out: <<loop>> Mar 17, 2010 at 15:24
  • 2
    ttmrichter, that's not stack overflow. GHC's RTS detects that you're evaluating the same thunk and "solves" the halting problem magically :)
    – Wei Hu
    Mar 17, 2010 at 17:48
0

The most likely cause has to be uncontrolled recursion. Each recursive call consumes a little more stack space for its input/ouput parameters.

1
  • 2
    Only if you define "recursion" correctly. Haskell has a pretty different idea of what consumes stack space than most functional languages.
    – luqui
    Mar 17, 2010 at 14:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.