Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.3 4.3bsd-beta 6/6/85; site ucbvax.BERKELEY.EDU
Path: utzoo!decvax!ucbvax!nrl-aic.ARPA!hoey
From: hoey@nrl-aic.ARPA (Dan Hoey)
Newsgroups: mod.ai
Subject: Xerox vs Symbolics -- Reference counts vs Garbage collection
Message-ID: <528057941.hoey@nrl-aic>
Date: Thu, 25-Sep-86 14:45:40 EDT
Article-I.D.: nrl-aic.528057941.hoey
Posted: Thu Sep 25 14:45:40 1986
Date-Received: Sat, 27-Sep-86 05:23:26 EDT
Sender: daemon@ucbvax.BERKELEY.EDU
Organization: The ARPA Internet
Lines: 32
Approved: ailist@sri-stripe.arpa

In AIList Digest V4 #191, Steven J. Clark responds to the statement
that ``Garbage collection is much more sophisticated on Symbolics''
with his belief that ``To my knowledge this is absolutely false.  S.
talks about their garbage collection more, but X's is better.''

Let me first deplore the abuse of language by which it is claimed that
Xerox has a garbage collector at all.  In the language of computer
science, Xerox reclaims storage using a ``reference counter''
technique, rather than a ``garbage collector.''  This terminology
appears in Knuth's 1973 *Art of Computer Programming* and originated in
papers published in 1960.  I remain undecided as to whether Xerox's
misuse of the term stems from an attempt at conciseness, ignorance of
standard terminology, or a conscious act of deceit.

The question remains of whether Interlisp-D or Zetalisp has the more
effective storage reclamation technique.  I suspect the answer depends
on the programmer.  If we are to believe Xerox, the reference counter
technique is fundamentally faster, and reclaims acceptable amounts of
storage.  However, it is apparent that reference counters will never
reclaim circular list structure.  As a frequent user of circular list
structure (doubly-linked lists, anyone?), I find the lack tantamount to
a failure to reclaim storage.  Apparently Xerox's programmers perform
their own careful deallocation of circular structures (opening the
cycles before dropping the references to the structures).  If I wanted
to do that, I would write my programs in C.

I have never understood why Xerox continues to neglect to write a
garbage collector.  It is not necessary to stop using reference counts,
but simply to have a garbage collector available for those putatively
rare occasions when they run out of memory.

Dan Hoey