> Are there any good ways to determine why one has a Control
> Stack Overflow? Are there good ways to avoid them?
hugs/Install mentions this configure-time option.
--enable-stack-dumps
Enable printing of the top and bottom few objects on the stack when
stack overflow happens. This feature is currently (Sept'97) just a
proof of concept. We welcome suggestions (and/or code) to make it
useful for people who don't have an intimate knowledge of how the
G machine operates.
Using this option has a high overhead so you'll want to build 2 copies of
Hugs - one with, one without.
With this option on, a Control Stack overflow triggers a stack dump
which lists which functions were executing at the time. It should
mostly make sense if you have a little understanding of how lazy
evaluation works and can make reasonable guesses about some of the
more cryptically named functions. (Cryptically named functions are
usually generated by instance declarations, local function declarations,
and case expressions).
You can tweak the amount of information displayed by changing UPPER_DISP
and LOWER_DISP in hugs/src/storage.c.
If you get a segmentation fault and suspect it is caused by a stack
overflow (it usually is), you could try invoking hugsStackOverflow
from inside the debugger. There's a reasonabale chance it will give
useful output though you'll probably have to quit and restart afterwards.
> One would think that writing recursions to be tail recursive
> would do it, but I notice that even foldl can get a Control
> Stack Overflow, so that doesn't do it.
[If this isn't on the comp.lang.functional FAQ, it should be.]
Consider this small example:
foldl (+) 0 [1..10] -- phase 1
=>
foldl (+) (0+1) [2..10]
=>
foldl (+) (0+1+2) [3..10]
...
=>
(((0 + 1) + 2) + 3) + ... 10 -- phase 2
=>
((1 + 2) + 3) + ... 10
=>
(3 + 3) + ... 10
=>
6 + ... 10
...
55
The first phase is indeed tail-recursive and takes little stack space
(but notice that it allocates O(n) cells on the heap).
Evaluating the additions though requires O(n) stack space because it
has to go down a tree-shaped data structure (ie the representation of
0+1+...10) of depth n.
The problem is that you really want to force evaluation of the
accumulating parameter as you go along.
foldl (+) 0 [1..10] -- phase 1
=>
foldl (+) 1 [2..10]
=>
foldl (+) 3 [3..10]
...
foldl (+) 55 []
=>
55
The Hugs Prelude provides foldl' - a variant of foldl which does this
and which runs the above example in constant stack/heap space. The
definitions of foldl and foldl' are:
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs
foldl' :: (a -> b -> a) -> a -> [b] -> a
foldl' f a [] = a
foldl' f a (x:xs) = (foldl' f $! f a x) xs
(I don't recall if foldl' is in Haskell98, but $! is so you can define
it yourself if you're using a compiler that doesn't provide it.)
Section 6.3 of Bird and Wadler's book "Introduction to Functional
Programming" has a brief (but good) discussion of this. The function
they call "strict" is called "$!" in Haskell98 (to emphasise its
relationship to "$").
--
Alastair Reid [EMAIL PROTECTED] http://www2.cs.utah.edu/~reid/
