Thursday, April 9, 2009

An obvious solution

The reason the Lisp Machine doesn't have tail recursion is that there is too much random cruft on the stack. The reason there was so much cruft on the stack was because of the garbage collector. The connection there is probably not obvious.

The PDP-10 on which MACLISP ran had an address space of 2^18 words (a word was 36-bits and cold hold both the car and cdr of a cons cell). The CADR Lisp machine had an address space of 2^24 words. The words were 32 bits, so the Lisp Machine could run an enormous 64 megabyte image. Of corse no one could afford anywhere near that much memory, so the CADR had something like 192K of RAM and the rest was paged to disk. (The LMI Lambda doubled the address space by snarfing a bit from the data tags.)

When the CADR needed to garbage collect, it would stop and copy. and copy... and copy .... and copy .... and copy .... The disk was slow and copying the image meant a lot of disk traffic. It was so slow that it was much faster to reboot the machine and restart your program. In fact, you didn't have to reserve a chunk of address space for GC if you didn't mind rebooting, and then you could run longer between reboots.

People got used to this mode of programming and added a lot of code to the machine to support it. You could allocate in discardable regions of memory, you could dynamically allocate on the stack, you could manage allocation pools and explicitly free objects. Some people became wizards at writing completely non-consing code.

But I always thought that the computer should handle the mundane tasks of memory management, and I wasn't going to contort my code to make up for a lame collector. Besides, I'd heard something about `ephemeral garbage collection' and I thought the machine was supposed to do that.

My microcode tracer tended to cons a lot of lexical closures. It would run out of memory for even moderately sized runs. I had three options for making progress:
  1. Rewrite the code to avoid consing at all costs.
  2. Figure out how to save and restore the intermediate state of the tracer so we could make progress across several reboots.
  3. Turn on the garbage collector.
That's a no-brainer.