Hi Josef,
| When I load the following script:
|
| > fib' n = fibs!!n
| > where fibs = 0:1:zipWith(+)fibs(tail fibs)
|
| and type:
|
| fib' 100000
|
| I get "Segmentation fault".
| I don't know how important this is to you since you're moving over to the
| STG backend, but it might be important to someone.
The responses so far all seem to be focused on issues related to stack
size. I think they are missing the main point here: There is a problem
with the program. The fact that Hugs 98 crashes on the program is
unfortunate, but is hard to avoid in a portable manner, given the way
that the Hugs 98 evaluator works. It will be nice if STG Hugs avoids
the segmentation violation, but in a sense that is also undesirable
because it hides the problem in the program.
What is the problem? The definition that you've given causes Hugs to
build a huge graph data structure whose depth is proportional to the
argument that you pass to fib', and then evaluate it. Only when you
reach the nth element in the list fibs will you actually start to
evaluate the big expression that has been constructed. And because
you need stack space proportional to the depth of the expression,
large arguments to fib' will require large amounts of stack space.
With a non-recursive evaluator, as in STG Hugs, you may not overflow
the process limits on stack size, but the underlying stack is going
to be there somewhere, probably in the heap, and so a program that
should require only constant space, will actually require space
proportional to the size of its argument.
How do you fix this? A strictness analyzer could help, although I
don't know if STG Hugs includes (or will include) something that
does the job here. The alternative is to modify the program to
avoid the problem. Here is one such modification that should do
the job by forcing evaluation of elements in the list to be
interleaved with the construction of those elements. This program
runs in constant space (modulo the fact that any program using
bignum arithmetic will fail to run in constant space if the bignums
get too big):
fib' n = strictList fibs!!n
where fibs = 0:1:zipWith(+)fibs(tail fibs)
strictList (x:xs) = x `seq` (x : strictList xs)
strictList [] = []
Of course, the real problem goes much deeper than this. We'd all
prefer to think that we could write programs in Haskell without
having to understand how evaluation will proceed, and without
having to understand the associated space requirements. Often,
things work just fine, but your example shows how surprising things
can happen sometimes, even with small programs.
All the best,
Mark
