From: keith@neuromancer.uchicago.edu (Keith Waclena)
Subject: Re: reference counting garbage collection
Reply-To: k-waclena@uchicago.edu
Organization: University of Chicago Library
	<NICKEL.92Oct4185459@desaster.cs.tu-berlin.de>
	<1992Oct4.220907.1053@organpipe.uug.arizona.edu>
Date: Mon, 5 Oct 1992 19:30:58 GMT

In article <1992Oct4.220907.1053@organpipe.uug.arizona.edu>
dave@cs.arizona.edu (Dave Schaumann) writes:

   In article <NICKEL.92Oct4185459@desaster.cs.tu-berlin.de>,
   nickel@cs (Juergen Nickelsen) writes:
   >How does reference counting garbage collection (RCGC) deal with
   >circular data structures? 

   It doesn't.  In fact, every time it's been presented to me, it's
   always been with the caveat that "this doesn't work on circular
   structures".

   On the other hand, if cycles in your structures are fairly rare,
   you could use reference-cound collection with an occasional call to
   a mark-and-sweep algorithm to catch the stragglers...

Yes, reference counting in its simplest form doesn't deal with
*arbitrary* cyclic structures, but there are a number of modified
reference counting schemes (mostly from the domain of functional
programming) that have been developed to handle cycles.

In general, you can have cycles if 1. they only arise in predictable
and limited ways, or 2. you augment your reference counting with some
other gc technique (as Dave mentions).

Briefly, the way technique 1 works is by avoiding the problem: if you
always know when a cycle is being created you simply decrement the ref
count (or you simply don't increment it -- whichever way you like to
think about it) for the cyclic ``reference''.  Then your count is
correct.

This is inadequate for say a language like Lisp which allows rplaca-
or rplacd-type *arbitrary* pointer manipulation, because it's too hard
(read: expensive) to tell if the operation is creating a cycle.

An example of technique 1 is in a combinator reduction machine where
all cyclic structures result from the reduction of a limited number of
combinators (like Y).  Another example of technique 1 might be a
tree-structured file system which is generally acyclic but which
allows limited known cycles (say a pointer to the current directory
and a pointer to the parent directory -- you might call these, say, .
and .. :-).  Users can't create arbitrary cycles, but the OS creates
these known cycles everytime a directory is created.

An example of technique 2 is contained in Martinez et al.

Here are a few references (so to speak).

%A Alejandro D. Mart\o'i\(aa'nez
%a martinez
%A Rosita Wachenchauzer
%A Rafael D. Lins
%D 22 February 1990
%T Cyclic Reference Counting with Local Mark-Scan
%J Information Processing Letters
%V 34
%P 31-35
%K functional programming; garbage collection

%L Brow85
%A D. R. Brownbridge
%T Cyclic Reference Counting for Combinator Machines
%B Functional Programming Languages and Computer Architecture
%E Jean-Pierre Jouannaud
%S Lecture Notes in Computer Science
%V 201
%D 1985
%I Springer-Verlag
%C Berlin
%K applicative programming; garbage collection

%A Daniel P. Friedman
%A David S. Wise
%D December 1976
%T Output Driven Interpretation of Recursive Programs, or
Writing Creates and Destroys Data Structures
%J Information Processing Letters
%V 5
%N 6
%K lazy evaluation reference counts

%A T. H. Axford
%D October 1990
%T Reference Counting of Cyclic Graphs for Functional Programs
%J The Computer Journal
%V 33
%N 5
%P 466-470
%K garbage collection

--
Keith Waclena                             	k-waclena@uchicago.edu
                                                MIME / RFC 1341

And remember, it's not only the YP master, but it's also a client.
Newsgroups: comp.programming