[Haskell-cafe] space leak hints?

[Uwe Hollerbach]

Good evening, all, I wonder if I could tap your collective wisdom
regarding space leaks? I've been messing about with haskeem, my little
scheme interpreter, and I decided to see if I could make it run
reasonably space-efficiently. So far... no.

Here's what I tried: I wrote a tiny scheme program to compute Collatz
sequences for successive numbers, starting from 1 and incrementing
forever (well, in principle). Because real scheme implementations are
fully tail-call-optimized, this'll run in constant memory; I checked
that with mzscheme, and it does indeed work. With my little
interpreter, that's not the case: memory usage grows continually,
although apparently less-than-linearly. I've built the interpreter
with the profiling stuff described on the wiki and in RWH Ch 25 turned
on and have made a few runs with that; I stuck the postscript plot
that's the result of one of those runs onto my web site at
http://www.korgwal.com/haskeem/run2.ps.

The full source to the interpreter is a little large to paste into
this message; it's available on my web site, and also on hackage. But
according to the plot, there appear to be three main memory allocation
issues, and they seem to all be related, if I'm reading stuff
correctly. The core of the interpreter is a function, evalLisp, which
evaluates scheme forms. There are of course a fair number of different
forms, but the largest generic usage is "evaluate each of a list of
forms, returning the value of the last of them as the overall result".
In order to express that in a couple of different places, and to
accomodate the possibility of an empty list, I have a really tiny
function lastOrNil which just calls "last" on a (haskell) list,
checking for the possibility of an empty list, and returning a haskeem
LispVal object:

> lastOrNil = liftM lON
>   where lON [] = List []
>        lON l = last l

(sorry, proportional fonting may be throwing this off).

It's this function which is directly implicated in two of the top
three memory pigs, and nearly directly in the third one as well. If I
could eliminate the memory growth in these three cost centers, I would
already capture over 90% of the growth in this benchmark, which would
make me very happy indeed. But I don't really understand what is going
on here. It seems entirely plausible, indeed likely, that the list
which I'm traversing there is not fully evaluated. So I've tried
adding 'seq' to this function. Uhhh... from memory, I dumped it after
it didn't work, I had

> lastOrNil = liftM lON
>   where lON [] = List []
>               lON (l:[]) = l
>               lON (l:ls) = seq l (lON ls)

(again, proportional fonting might mess me up here.)

As I said, I dumped this after it made no difference whatsoever. I
also tried bang-patterns in a couple of places, strictness annotation
of my basic LispVal types... nothing. It all made exactly no
difference, as far as I could tell. I've tried a couple of google
searches, but haven't come up with anything better than what I've
already described. So I'm a stumped chump!

I'd be grateful for any suggestions... thanks in advance!

Uwe