[comp.lang.lisp] Reference Counts

gupta@uicsgva.UUCP (10/13/87)

	I am looking for papers on the use of reference counts for
garbage collection. 
	I have Spector's paper (1982)  in which he shows how the concept of 
defining reference can be used to manage the deallocation of reentrant objects 
too.
	The only other similar reference I have found is a paper by 
J. Dana Eckart.
	Any other recent papers ?

Aloke Gupta
CSL Univ of Ill at Urbana-Champaign

Ref:  - J.D. Eckart and R.J. LeBlanc, "Distributed Garbage Collection in 
	distributed systems", Procedings of the SIGPLAN '87 Symposium on 
	Interpretors and Interpretive Techniques , June 1987

      - David Spector, "Minimal Overhead Garbae Collection of Complex List 
	Structures", ACM SIGPLAN Notices,vol. 17, No.3, pp. 80-82, March 1982

rbbb@acornrc.UUCP (David Chase) (10/15/87)

> 
> 	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

oz@yetti.UUCP (10/16/87)

In article <3600002@uicsgva> gupta@uicsgva.UUCP writes:
>
>	I am looking for papers on the use of reference counts for
>garbage collection. 
>...
>	Any other recent papers ?

The following are not recent, but very useful (I especially find
Standish's chapter excellent.):

	Jacques Cohen, "Garbage Collection of Linked Data Structures"
	Acm Computing Surveys 13(3) Sep. 1981

	Thomas Standish, "Data Structure Techniques"
	Addison-Wesley, 1980
	[5.4 - Storage Reclamation / 5.4.3 Incremental Garbage
	Collection]

oz
-- 
You see things, and you say "WHY?"  	Usenet: [decvax|ihnp4]!utzoo!yetti!oz
But I dream things that never were; 	        ......!seismo!mnetor!yetti!oz
and say "WHY NOT?"			Bitnet: oz@[yusol|yulibra|yuyetti]
[Back To Methuselah]  Bernard Shaw 	Phonet: [416] 736-5257 x 3976