Sirs,
Your discussion of incremental garbage collection interested me. I
have implemented a LISP interpreter which uses "erasure by reference-counting"
instead of garbage collection. I use this in conjunction with MIDI, because
I can get reliable response times from LISP. In doing this I have tried
to collect as many papers about reference-counting LISP systems as possible.
Unfortunately the trail of papers has gone cold, it seems reference-counting
was discarded as early as 1958.
Does anyone have references to papers describing reference-counting? I would
be grateful for some help on this one.
Thanks in advance,
Bill Birch
------------------------------------------------------------------------------
Tel: + 44 1 637 9111 x 1311 (Work) Snail: Flat 7, 1 Brookfield Ave.
Sutton, SM1 3QP, U.K.
--
Automatic Disclaimer:
The views expressed above are those of the author alone and may not
represent the views of the IBM PC User Group.
We have written a Scheme system based on reference counters as the
main mechanism of memory management. The reason we decided on
reference counters was mainly that Scheme uses first class functions
and continuations. This kind of semantics require that the stack be
saved and restored from time to time. Experiments with T (Scheme like
system from Yale) shows that the cost of garbage collection can be
extensive when first class continuations are used extensively.
In our system, we do not use the hardware stack. Instead, we allocate
all objects on the heap. The reference counter mechanism makes sure
that "stack frames" are returned immediately to the system, in case
there is no capture of continuations.
Of course, reference counters have a major disadvantage. They cannot
handle circular structures. For that reason, we are going to add a
traditional garbage collector as well. We predict that the traditional
garbage collector will be invoked fairly infrequently.
The reference counter mechanism also makes the system fairly portable.
We do not need to divide the heap into zones of different data types,
nor decide in advance on the size of the heap. In fact, we use a
minor variation of "malloc" and "free", which seems to work fine.
A generational garbage collector is almost as good as reference
counters. It requires that the program behave "the lisp way": Objects
are either short lived or long lived, but not in between.
Reference counters do not require this kind of behavior.
Like generational garbage collectors (when the program behaves
correctly), the cost of reference counters is proportional to the
amount of memory allocated but thrown away, whereas other garbage
collectors have a cost proportional to the amount of memory allocated
but *still in use*.
Finally, we have noticed an interesting feature with reference
counters: In our system, we have a "window" data type. For instance, we
can write:
=> (define x (window-create ...))
x
and a window appears on the screen. Now if we do:
=> (set! x 4)
the system can no longer reference the window, so the reference
counter mechanism destroys the window, and the window disappears from
the screen. In a system with a traditional garbage collector, one
would have had to wait for the garbage collector to be run.
Robert Strandh
University of Bordeaux I