Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site brl-tgr.ARPA
Path: utzoo!watmath!clyde!burl!ulysses!allegra!mit-eddie!think!harvard!seismo!brl-tgr!tgr!bilbo.barry@ucla-locus.ARPA
From: bilbo.barry@ucla-locus.ARPA (Barry Gold)
Newsgroups: net.lang.c
Subject: Re: Recoding LISP programs in C
Message-ID: <2239@brl-tgr.ARPA>
Date: Fri, 18-Oct-85 02:46:36 EDT
Article-I.D.: brl-tgr.2239
Posted: Fri Oct 18 02:46:36 1985
Date-Received: Sat, 19-Oct-85 08:11:39 EDT
Sender: news@brl-tgr.ARPA
Lines: 26

Paul Eggert at UCSB found a neat hack for doing mark and gather garbage
collectors in a language like c:

run through the c stack (yes, it's not portable, but you only have to
rewrite a few (~10) lines to port it to most implementations):  pretend
everything you find there is a pointer to the stuff you're trying to
collect.  Now check each such pointer to make sure it actually points into
the area(s) you're collecting and is properly aligned.  If not, ignore it;
if it appears OK, mark the thing it points to.

(This works only if the 'type' of a lisp (or similar) object can be determined
from its address/the 'pointer' to it.)

When you're done, you'll have marked everything you should have marked
(because they're all in 'c' variables somewhere on the stack--except for
global or "special" variables, which you should keep in an array somewhere).
You'll also have marked a few things that are garbage--that should be thrown
away/freed/put on the available space list.  Paul claims that this 
falsely marked garbage will amount to less than 10% of the collectable
garbage.

So you'll hold on to everything you should hold on to, and also leave some
uncollected garbage lying around.  Chances are, you'll get that uncollected
stuff on the NEXT garbage collect.  So you trade-off: you need slightly
bigger spaces (to allow for that uncollected garbage), BUT the garbage
collecter AND the normal routine entry/exit run faster.