Re: The joy of garbage collection

robbie.carlton wrote:
> I'm writing a simple lisp interpreter, just for the sheer
> joy of it, and I've fallen down a bit at the memory
> management stage.

You have to think very hard about the exact scope of
learning exercise. The usual idea is to inherit the garbage
collection from the native environment. You write a
meta-circular interpreter, without a garbage collecter, and
the underlying lisp takes care of it for you.

If you specifically want to learn about garbage collection,
well I'm not so sure. Perhaps you need to allocate a big
array and store things in it appropriate to the imaginary
word of your software machine. So maybe a cons is defined by
a defstruct

(defstruct cons mark car cdr)

and car and cdr are always pointers

(defstruct pointer tag mark address)

where address is a number that indexes your big
array. (something like that, I've never tried it)

Then the underlying lisp never needs more memory than the
space required for big array, times a small constant
factor. All the things you put in it don't have pointers
themselves, just "addresses" = numbers in your software
machine, so they don't keep anything else alive.

If you write nils to the big array, then the underlying lisp
can collect the objects thats used to be stored there (once
you have written nil to the last reference.) but I don't
think you need this.

> but it seems that the sweep bit is incompatible with
> storing unboxed data in the heap

I'm very confused here because there are two heaps on the
go. If you have decided to make your educational toy work at
the level of 32-bit words and your big array is

(make-array memory-size :element-type '(unsigned-byte 32))

many lisp implementations will store the unsigned bytes
unboxed. The array is on the heap, and gets collected all in
one go. The elements cannot point anywhere, they are just
numbers.

Meanwhile, inside your education toy, they are not just
numbers. Well maybe the lsb is your tag bit and even ones
are your fixnums, and odd ones are pointers and point
elsewhere in the "heap". You traverse these pointers during
marking. I don't see how they could be on the heap
individually and unboxed, where would the mark bit go, how
could sweep know to leave them?

Maybe the bit you are missing is the free list. Sweep writes
stuff into the cells it sweeps up, organising them into a
linked list. It needs just one cell for the start of the
free list. The rest of the free list hosts itself in the big
array.

I hope I am remembering this right, it is 23 years ago that
I did a Schorr Waite thingy in 6809 assembler. If you want
to learn this stuff today it is an excellent idea to do it
in a high level language, but you will have to fight the
level confusion ie your heap versus the underlying
implementations heap.

Alan Crowe
Edinburgh
Scotland

.

Relevant Pages