Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!cmcl2!beta!hc!ames!acornrc!rbbb
From: rbbb@acornrc.UUCP (David Chase)
Newsgroups: comp.lang.lisp
Subject: Re: Reference Counts
Message-ID: <468@acornrc.UUCP>
Date: Thu, 15-Oct-87 12:13:07 EDT
Article-I.D.: acornrc.468
Posted: Thu Oct 15 12:13:07 1987
Date-Received: Sat, 17-Oct-87 07:41:15 EDT
References: <3600002@uicsgva>
Organization: Acorn Research Centre, Palo Alto, CA
Lines: 105
Summary: Lots-o-references going way back

> 
> 	I am looking for papers on the use of reference counts for
> garbage collection. 

The conventional wisdom doesn't have a lot to say for reference counting;
fortunately, I have some unconventional references.  These are in a format
suitable for use with BibTeX if you put them in the appropriate wrappers.
(for example, "@article{Collins:MOEL, ... }")

(The original reference)

  AUTHOR = "G. E. Collins",
  TITLE = "A Method for Overlapping and Erasure of Lists",
  JOURNAL = cacm,
  YEAR = 1960, VOLUME = 3, NUMBER = 12, PAGES = {655--657}

(A fun paper, good results)

  AUTHOR = "W. R. Stoye and T. J. W. Clarke and A. C. Norman",
  TITLE = "Some Practical Methods for Rapid Combinator Reduction",
  BOOKTITLE = "{SIGPLAN} Symposium on {LISP} and Functional Programming",
  YEAR = 1984, PAGES = {159--166}

(Three papers on reclamation of circular structures)

  TITLE = "Managing Reentrant Structures Using Reference Counts",
  AUTHOR = "Daniel G. Bobrow",
  JOURNAL = toplas,
  VOLUME = 2, NUMBER = 3, MONTH = jul, YEAR = 1980, PAGES = {269--273}

  AUTHOR = "D. P. Friedman and D.S. Wise",
  TITLE = "Reference Counting Can Manage the Circular Invironments[sic]
           of Mutual Recursion",
  JOURNAL = "Information Processing Letters",
  YEAR = 1979, VOLUME = 8, NUMBER = 1, PAGES = {41--44}

  AUTHOR = "D. R. Brownbridge",
  TITLE = "Cyclic Reference Counting for Combinator Machines",
  BOOKTITLE = "Functional Programming Languages and Computer Architecture",
  YEAR = 1985, PAGES = {273--288}
  (Springer-Verlag Lecture Notes in Computer Science #201)
  (this book contains several other interesting articles; give it a browse)

(compaction and r. c.)

  AUTHOR="David S. Wise",
  TITLE="Morris's Garbage Compaction Algorithm Restores Reference Counts",
  JOURNAL=toplas,
  VOLUME=1, NUMBER=1, MONTH=jul, YEAR=1979, PAGES={115--120}

(the InterLisp collector and the Cedar Mesa collector and a related paper)

  AUTHOR = "L. Peter Deutsch and Daniel G. Bobrow",
  TITLE = "An Efficient, Incremental, Automatic Garbage Collector",
  JOURNAL = cacm,
  VOLUME = 19, NUMBER = 9, YEAR = 1976, MONTH = sep, PAGES = {522--526}

  AUTHOR = "Paul Rovner",
  TITLE = "On Adding Garbage Collection and Runtime Types to a Strongly-Typed,
           Statically Checked, Concurrent Language",
  INSTITUTION = PARC, YEAR = 1985, NUMBER = "CSL-84-7"

  AUTHOR = "Jeffrey M. Barth",
  TITLE = "Shifting Garbage Collection Overhead to Compile Time",
  JOURNAL = cacm,
  VOLUME = 20, NUMBER = 7, YEAR = 1977, MONTH = jul, PAGES = {513--518}

I also recommend the following papers describing behavior of "typical"
programs and allocation strategies, and the results of some "tricks".
These behaviors, of course, depend somewhat on the language, implementation,
and benchmarks chosen.

  AUTHOR = "A. P. Batson and R. E. Brundage",
  TITLE = "Segment Sizes and Lifetimes in {ALGOL} 60 Programs",
  JOURNAL = cacm,
  VOLUME = 20, NUMBER = 1, YEAR = 1977, MONTH = jan, PAGES = {36--44}

  AUTHOR = "D. W. Clark and C. C. Green",
  TITLE = "An Empirical Study of List Structure in {LISP}",
  JOURNAL = cacm,
  VOLUME = 20, NUMBER = 2, YEAR = 1977, MONTH = feb, PAGES = {78--87},

  AUTHOR = "Douglas W. Clark",
  TITLE = "Measurements of Dynamic List Structure Use in {L}isp",
  JOURNAL = ieeese,
  VOLUME = 5, NUMBER = 1, MONTH = jan, YEAR = 1979, PAGES = {51--59}

  TITLE = "Compact Encodings of List Structure",
  AUTHOR = "Daniel G. Bobrow and Douglas W. Clark",
  JOURNAL = toplas,
  VOLUME = 1, NUMBER = 2, MONTH = oct, YEAR = 1979, PAGES =  {266--286}

  AUTHOR = "Norman R. Nielsen",
  TITLE = "Dynamic Memory Allocation in Computer Simulation",
  JOURNAL = cacm,
  YEAR = 1977, VOLUME = 20, NUMBER = 11, MONTH = nov, PAGES = {864--873}

I also have an ever-growing list of references for copying-compacting garbage
collectors.

> Aloke Gupta
> CSL Univ of Ill at Urbana-Champaign

David Chase
Olivetti Research Center, Palo Alto