An efficient machine-independent procedure for garbage collection in various list structures

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An efficient machine-independent procedure for garbage collection in various list structures

Full text

Pdf (709 KB)

Source

Communications of the ACM archive
Volume 10 , Issue 8 (August 1967) table of contents

Pages: 501 - 506

Year of Publication: 1967

ISSN:0001-0782

Authors

H. Schorr	IBM Corp., Menlo Park, CA
W. M. Waite	Univ. of Colorado, Boulder

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 76, Citation Count: 49

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/363534.363554 What is a DOI?

ABSTRACT

A method for returning registers to the free list is an essential part of any list processing system. In this paper, past solutions of the recovery problem are reviewed and compared. A new algorithm is presented which offers significant advantages of speed and storage utilization. The routine for implementing this algorithm can be written in the list language with which it is to be used, thus insuring a degree of machine independence. Finally, the application of the algorithm to a number of different list structures appearing in the literature is indicated.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	NEWELL, A. (ED.) Information Processing Language-W Manual, 2nd ed. Prentice Hall, Englewood N. J., 1964.
	2	John McCarthy, Recursive functions of symbolic expressions and their computation by machine, Part I, Communications of the ACM, v.3 n.4, p.184-195, April 1960 [doi>10.1145/367177.367199]
	3	H. Gelernter , J. R. Hansen , C. L. Gerberich, A Fortran-Compiled List-Processing Language, Journal of the ACM (JACM), v.7 n.2, p.87-101, April 1960 [doi>10.1145/321021.321022]
	4	George E. Collins, A method for overlapping and erasure of lists, Communications of the ACM, v.3 n.12, p.655-657, Dec. 1960 [doi>10.1145/367487.367501]
	5	J. Weizenbaum, Knotted list structures, Communications of the ACM, v.5 n.3, p.161-165, March 1962 [doi>10.1145/366862.366897]
	6	J. Weizenbaum, Symmetric list processor, Communications of the ACM, v.6 n.9, p.524-536, Sept. 1963 [doi>10.1145/367593.367617]
	7	WILKES, M. V. An experiment with a self-compiling compiler for a simple list-processing language. Annual Review in Automatic Programming, Vol. 4. Pergamon Press, N.Y. 1964, pp. 1-48.
	8	M. V. Wilkes, Lists and why they are useful, Proceedings of the 1964 19th ACM national conference, p.61.1-61.5, January 1964 [doi>10.1145/800257.808911]
	9	W. T. Comfort, Multiword list items, Communications of the ACM, v.7 n.6, June 1964 [doi>10.1145/512274.512288]
	10	A. Evans, Jr. , A. J. Perlis , H. Van Zoeren, The use of threaded lists in constructing a combined ALGOL and machine-like assembly processor, Communications of the ACM, v.4 n.1, p.36-41, Jan. 1961 [doi>10.1145/366062.366081]
	11	William M. Waite , H. Schorr, A note on the formation of free list, Communications of the ACM, v.7 n.8, p.478, Aug. 1964 [doi>10.1145/355586.364800]
	12	Maurice H Halstead, Machine-independent computer programming, Spartan Books, 1962
	13	J. Harold McBeth, Letters to the editor: on the reference counter method, Communications of the ACM, v.6 n.9, p.575, Sept. 1963 [doi>10.1145/367593.367649]

CITED BY 49

	Wilfred J. Hansen, Compact list representation: definition, garbage collection, and system implementation, Communications of the ACM, v.12 n.9, p.499-507, Sept. 1969
	Steven J. Karpen, Design and Implementation of a Real Time Information Storage and Retrieval System, Proceedings of the 1971 26th annual conference, p.37-66, January 1971
	Douglas W. Clark, An efficient list-moving algorithm using constant workspace, Communications of the ACM, v.19 n.6, p.352-356, June 1976
	Lawrence Yelowitz , Arthur G. Duncan, Abstractions, instantiations, and proofs of marking algorithms, ACM SIGPLAN Notices, v.12 n.8, p.13-21, August 1977
	Douglas W. Clark, A fast algorithm for copying list structures, Communications of the ACM, v.21 n.5, p.351-357, May 1978
	Edward M. Reingold, A nonrecursive list moving algorithm, Communications of the ACM, v.16 n.5, p.305-307, May 1973
	Norihisa Suzuki, Analysis of pointer “rotation”, Communications of the ACM, v.25 n.5, p.330-335, May 1982
	Gary Lindstrom , Mary Lou Soffa, Referencing and Retention in Block-Structured Coroutines, ACM Transactions on Programming Languages and Systems (TOPLAS), v.3 n.3, p.263-292, July 1981
	Jonathan Sobel , Daniel P. Friedman, Recycling continuations, ACM SIGPLAN Notices, v.34 n.1, p.251-260, Jan. 1999
	Daniel C. Wang , Andrew W. Appel, Type-preserving garbage collectors, ACM SIGPLAN Notices, v.36 n.3, p.166-178, March 2001
	Guy L. Steele, Jr., Multiprocessing compactifying garbage collection, Communications of the ACM, v.18 n.9, p.495-508, Sept. 1975
	R. Y. Kain, Block structures, indirect addressing, and garbage collection, Communications of the ACM, v.12 n.7, p.395-398, July 1969
	R. L. Ashenhurst, Curriculum recommendations for graduate professional programs in information systems, Communications of the ACM, v.15 n.5, p.363-398, May 1972
	George G. Dodd, Elements of Data Management Systems, ACM Computing Surveys (CSUR), v.1 n.2, p.117-133, June 1969
	Manfred Broy , Peter Pepper, Combining Algebraic and Algorithmic Reasoning: An Approach to the Schorr-Waite Algorithm, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.362-381, July 1982
	Pascal Fradet, Collecting more garbage, ACM SIGPLAN Lisp Pointers, v.VII n.3, p.24-33, July-Sept. 1994
	Robert E. Tarjan, Space-Efficient Implementations of Graph Search Methods, ACM Transactions on Mathematical Software (TOMS), v.9 n.3, p.326-339, Sept. 1983
	Gary Lindstrom, Copying list structures using bounded workspace, Communications of the ACM, v.17 n.4, p.198-202, April 1974
	David S. Burris , Kurt Schember, Sorting sequential files with limited auxiliary storage, Proceedings of the 18th annual Southeast regional conference, March 24-26, 1980, Tallahassee, Florida
	Saleh E. Abdullahi , Graem A. Ringwood, Garbage collecting the Internet: a survey of distributed garbage collection, ACM Computing Surveys (CSUR), v.30 n.3, p.330-373, Sept. 1998
	Johannes J. Martin, An efficient garbage compaction algorithm, Communications of the ACM, v.25 n.8, p.571-580, Aug 1982
	Guy Lewis Steele, Jr. , Gerald Jay Sussman, Design of a LISP-based microprocessor, Communications of the ACM, v.23 n.11, p.628-645, Nov. 1980
	Paul Hudak , Robert M. Keller, Garbage collection and task deletion in distributed applicative processing systems, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.168-178, August 15-18, 1982, Pittsburgh, Pennsylvania, United States
	Yoo C. Chung , Soo-Mook Moon , Kemal Ebcioğlu , Dan Sahlin, Reducing sweep time for a nearly empty heap, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.378-389, January 19-21, 2000, Boston, MA, USA
	Jacques Cohen, Garbage Collection of Linked Data Structures, ACM Computing Surveys (CSUR), v.13 n.3, p.341-367, Sept. 1981
	John D. Ramsdell, The CURRY chip, Proceedings of the 1986 ACM conference on LISP and functional programming, p.122-131, August 1986, Cambridge, Massachusetts, United States
	William F. Atchison , Samuel D. Conte , John W. Hamblen , Thomas E. Hull , Thomas A. Keenan , William B. Kehl , Edward J. McCluskey , Silvio O. Navarro , Werner C. Rheinboldt , Earl J. Schweppe , William Viavant , David M. Young, Jr., Curriculum 68: Recommendations for academic programs in computer science: a report of the ACM curriculum committee on computer science, Communications of the ACM, v.11 n.3, p.151-197, March 1968
	William M. Farmer , John D. Ramsdell , Ronald J. Watro, A correctness proof for combinator reduction with cycles, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.1, p.123-134, Jan. 1990
	Yanhong A. Liu , Scott D. Stoller, From recursion to iteration: what are the optimizations?, ACM SIGPLAN Notices, v.34 n.11, p.73-82, Nov. 1999
	W. R. Stoye , T. J. W. Clarke , A. C. Norman, Some practical methods for rapid combinator reduction, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.159-166, August 06-08, 1984, Austin, Texas, United States
	R. J. R. Back , Heikki Mannila , Kari-Jouko Räihä, Derivation of efficient DAG marking algorithms, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.20-27, January 24-26, 1983, Austin, Texas
	Stanley Lee , Willem P. deRoever , Susan L. Gerhart, The evolution of list-copying algorithms and the need for structured program verification, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.53-67, January 29-31, 1979, San Antonio, Texas
	Leszek Gasieniec , Igor Potapov, Time/space efficient compressed pattern matching, Fundamenta Informaticae, v.56 n.1,2, p.137-154, July 2003
	Narendran Sachindran , J. Eliot B. Moss , Emery D. Berger, MC²: high-performance garbage collection for memory-constrained environments, ACM SIGPLAN Notices, v.39 n.10, October 2004
	Martin Ward, Derivation of Data Intensive Algorithms by Formal Transformation: The Schnorr-Waite Graph Marking Algorithm, IEEE Transactions on Software Engineering, v.22 n.9, p.665-686, September 1996
	David F. Bacon , Perry Cheng , V. T. Rajan, A unified theory of garbage collection, ACM SIGPLAN Notices, v.39 n.10, October 2004
	Norihisa Suzuki, Analysis of pointer rotation, Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-11, January 28-30, 1980, Las Vegas, Nevada
	Witawas Srisa-an , Chia-Tien Dan Lo , Ji-en Morris Chang, Active Memory Processor: A Hardware Garbage Collector for Real-Time Java Embedded Devices, IEEE Transactions on Mobile Computing, v.2 n.2, p.89-101, January 2003
	Farhad Mehta , Tobias Nipkow, Proving pointer programs in higher-order logic, Information and Computation, v.199 n.1-2, p.200-227, 25 May 2005
	Timothy J. McEntee, Overview of garbage collection in symbolic computing, ACM SIGPLAN Lisp Pointers, v.1 n.3, p.8-16, August-September 1987
	Robin Williams, A Survey of Data Structures for Computer Graphics Systems, ACM Computing Surveys (CSUR), v.3 n.1, p.1-21, March 1971
	Ricardo Caferra , Rachid Echahed , Nicolas Peltier, Rewriting term-graphs with priority, Proceedings of the 8th ACM SIGPLAN symposium on Principles and practice of declarative programming, July 10-12, 2006, Venice, Italy
	Yossi Matias , Ely Porat, Efficient pebbling for list traversal synopses with application to program rollback, Theoretical Computer Science, v.379 n.3, p.418-436, June, 2007
	David S. Wise , Brian Heck , Caleb Hess , Willie Hunt , Eric Ost, Research Demonstration of a Hardware Reference-Counting Heap, Lisp and Symbolic Computation, v.10 n.2, p.159-181, July 1997
	Henry G. Baker, Lively linear Lisp: “look ma, no garbage!”, ACM SIGPLAN Notices, v.27 n.8, p.89-98, Aug. 1992
	Henry G. Baker, Thermodynamics and garbage collection, ACM SIGPLAN Notices, v.29 n.4, p.58-63, April 1994
	B. Lang , F. Dupont, Incremental incrementally compacting garbage collection, ACM SIGPLAN Notices, v.22 n.7, p.253-263, July 1987
	Richard S. Bird, FUNCTIONAL PEARL: Unfolding pointer algorithms, Journal of Functional Programming, v.11 n.3, p.347-358, May 2001
	Toshiaki Kurokawa, A new fast and safe marking algorithm, ACM Lisp Bulletin