Garbage Collection of Linked Data Structures

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.

	ARNB72	ARNBORG, S. "Storage administration m a virtual memory simulation system," BIT12,2 {1972), 125-141 (CGLMRV}
	ARNB74	ARNBORC,, S. "Optimal memory management in a system with garbage collection," BIT 14, 4 (1974), 375-381. {A}
	AUGE79	Moshe J. Augenstein , Aaron M. Tenenbaum, Data Structures and PL-1 Programming, Prentice Hall Professional Technical Reference, 1979
	BAEC70	BAECKER, H D. "Implementing the ALGOL 68 heap," BIT 10, 4 (1970), 405- 414. {GLV}
	BAEC72	H. D. Baecker, Garbage collection for virtual memory computer systems, Communications of the ACM, v.15 n.11, p.981-986, Nov. 1972 [doi>10.1145/355606.361886]
	BAEC75	BAECKER, H.D. "Areas and recordclasses," Comput J. 18, 3 (Aug. 1975), 223-226. (GL}
	BAER77	BAER, J.L., AND FRIES, H. "On the efficiency of some ILst marking algorithms," in Information processing 1977, B. Gilchrist (Ed.), IFIP, North-Holland, Amsterdam, 1977, pp 751-756. {ABM}
	BAKE78a	H. G. Baker, ACTOR SYSTEMS FOR REAL-TIME COMPUTATION, Massachusetts Institute of Technology, Cambridge, MA, 1978
	BAKE78b	Henry G. Baker, Jr., List processing in real time on a serial computer, Communications of the ACM, v.21 n.4, p.280-294, April 1978 [doi>10.1145/359460.359470]
	BART77	Jeffrey M. Barth, Shifting garbage collection overhead to compile time, Communications of the ACM, v.20 n.7, p.513-518, July 1977 [doi>10.1145/359636.359713]
	BAWD77	BAWDEN, A., GREENBLATT, R., HOLLO- WAY, J., KSmHT, T., MooN, D., AND WEINREB, D. "Lisp machine progress report," Memo 444, A.I Lab, M.I.T., Cambridge, Mass., Aug. 1977 {G}
	BERK64	BERKELEY, E.C., AND BOBROW, D G. (Eds.) The programming language LISP, M.I.T., Cambridge, Mass. 1974, 4th printing. {GL}
	BERR78	BERRY, D M., AND SORKIN, A. "Tnne required for garbage collection in retention block-structures languages," Int. J. Comput. Informatmn Sci. 7, 4 (1978), 361-404. {AL}
	BERZ75	Alfs T. Berztiss , A. T. Berztiss, Data Structures: Theory and Practice, Academic Press, Inc., Orlando, FL, 1975
	BISH77	BISHOP, P.B. "Computer systems with a very large address space and garbage collectmn," Lab. for Computer Science, MIT Rep., TR-178, M.I.T., Cambridge, Mass., May 1977. (ACGLMRSV}
	BOBR67	Daniel G. Bobrow , Daniel L. Murphy, Structure of a LISP system using two-level storage, Communications of the ACM, v.10 n.3, p.155-159, March 1967 [doi>10.1145/363162.363185]
	BOBR68a	BOBROW, D.G. Storage management ~n Lisp, m symbol manipulation languages and techniques, D. G. Bobrow (Ed.), North-Holland, Amsterdam, 1968. {CGMV}
	BOBR68b	Daniel G. Bobrow , Daniel L. Murphy, A note on the efficiency of a LISP computation in a paged machine, Communications of the ACM, v.11 n.8, p.558, Aug. 1968 [doi>10.1145/363567.363581]
	BOBR75	Daniel G. Bobrow, A note on hash linking, Communications of the ACM, v.18 n.7, p.413-415, July 1975 [doi>10.1145/360881.360920]
	BOBR80	Daniel G. Bobrow, Managing Reentrant Structures Using Reference Counts, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.3, p.269-273, July 1980 [doi>10.1145/357103.357104]
	BRAN71	BRANQUART, P, AND LEWI, J. "A scheme of storage allocation and garbage collectmn for Algol 68," m Algol 68 ~m. plementat~on, J. E L. Peck, (Ed.), North-Holland, Amsterdam, 1971, pp. 199-238. {CGLMR}
	CAMP74	CAMPBELL, J.A. "Optimal use of storage in a simple model of garbage collection," Inf. Process Lett. 3, 2 (Nov. 1974), 37-38. {A}
	CHEN70	C. J. Cheney, A nonrecursive list compacting algorithm, Communications of the ACM, v.13 n.11, p.677-678, Nov 1970 [doi>10.1145/362790.362798]
	CLAR75	CLARK, D.W. "A fast algorithm for copying binary trees," Inf. Process. Lett 9, 3 (Dec. 1975), 62-63. {AC)
	CLAR76	Douglas W. Clark, An efficient list-moving algorithm using constant workspace, Communications of the ACM, v.19 n.6, p.352-356, June 1976 [doi>10.1145/360238.360247]
	CLAR77	Douglas W. Clark , C. Cordell Green, An empirical study of list structure in Lisp, Communications of the ACM, v.20 n.2, p.78-87, Feb. 1977 [doi>10.1145/359423.359427]
	CLAR78a	Douglas W. Clark, A fast algorithm for copying list structures, Communications of the ACM, v.21 n.5, p.351-357, May 1978 [doi>10.1145/359488.359491]
	CLAR78b	CLARK, D.W., AND GREEN, C.C. "A note on shared list structure m Lmp," Inf. Process. Lett 7, 6 (Oct. 1978), 312- 314. {B}
	CLAR79	CLARK, D.W. "Measurements of dynamic list structure in Lmp," IEEE Trans Softw. Eng. SE-5, 1 (Jan 1979), 51-59. {BY}
	COHE67a	Jacques Cohen, A use of fast and slow memories in list-processing languages, Communications of the ACM, v.10 n.2, p.82-86, Feb. 1967 [doi>10.1145/363067.363092]
	COHE67b	COHEN, J., AND TRILLING, L. "Remarks on garbage collection using a two level storage," BIT 7, 1 (1967), 22- 30. (BCMV}
	COHE72	COHEN, J., AND ZUCKERMAN, C. "Evalquote in simple Fortran A tutorial on interpretmg Lisp," BIT 12, 3 (1972), 299-317. {CGM}
	COLL60	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]
	DEUT76	L. Peter Deutsch , Daniel G. Bobrow, An efficient, incremental, automatic garbage collector, Communications of the ACM, v.19 n.9, p.522-526, Sept. 1976 [doi>10.1145/360336.360345]
	DIJK76a	DIJKSTRA, E.W. A d~sc~phne of programmmg, Prentice-Hall, Englewood Cliffs, N J., 1976, Chap. 14. {G}
	DIJK76b	Edsger W. Dijkstra , Leslie Lamport , A. J. Martin , C. S. Scholten , E. F. M. Steffens, On-the-fly garbage collection: an exercise in cooperation, Communications of the ACM, v.21 n.11, p.966-975, Nov. 1978 [doi>10.1145/359642.359655]
	DWYE73	DWYER, B. "Simple algorithms for traversmg a tree without an auxiliary stack," Inf. Process. Lett. 2, 5 (Dec. 1973), 143-145. {M)
	ELSO75	ELSON, M. "Data structures," Scmnce Research Associates, 1975. (CGMN}
	FENI69	Robert R. Fenichel , Jerome C. Yochelson, A LISP garbage-collector for virtual-memory computer systems, Communications of the ACM, v.12 n.11, p.611-612, Nov. 1969 [doi>10.1145/363269.363280]
	FENI71	Robert R. Fenichel, List tracing in systems allowing multiple cell-types, Communications of the ACM, v.14 n.8, p.522-526, Aug. 1971 [doi>10.1145/362637.362646]
	FISH74	FmHER, D.A. "Bounded workspace garbage collection in an address order preserving list processing environment," Inf. Process. Lett. 3, 1 (July 1974), 29- 32. {CMR}
	FISH75	David A. Fisher, Copying cyclic list structures in linear time using bounded workspace, Communications of the ACM, v.18 n.5, p.251-252, May 1975 [doi>10.1145/360762.360764]
	FITC78	FITCH, J.P., AND NORMAN, A.C. "A note on compactmg garbage collection," Comput. J. 21, 1 (Feb. 1978), 31- 34. (ABCR}
	FOST68	FOSTER, J.M. L~st processmg, Elsevier Computer Monographs, Elsevier-North Holland, New York, 1968. {G}
	FRAN78	FRANCEZ, N. "An appllcatmn of a method for analysis of cyclic programs," IEEE Trans. Soflw. Eng. 4, 5 (Sept. 1978), 371-377. {P}
	FRIE76	FRIEDMAN, D.P., AND WISE, D.S. "Garbage collecting a heap which mcluded a scatter table," Inf. Process. Lett. 5, 6 (Dec 1976), 161-164. (LM}
	FRIE79	FRIEDMAN, D.P., AND WISE, D.S. "Reference counting can manage the circular environments of mutual recurstun," Inf. Process. Lett. 8, 1 (Jan. 1979), 41-45. (N}
	GERH79	Susan L. Gerhart, A Derivation Oriented Proof of the Schorr-Waite Marking Algorithm, Program Construction, International Summer Schoo, p.472-492, July 26-August 06, 1978
	GOTL78	Leo R. Gotlieb, Data Types and Structures, Prentice Hall PTR, Upper Saddle River, NJ, 1978
	GOYE71	GOVER, P. "A garbage collector to be implemented on a CDC 3100," in Algol 68 zmplementatmn, J. E. L. Peck (Ed.), North-Holland, Amsterdam, 1971, pp 303-317. {CLMR}
	GRIE77	David Gries, An exercise in proving parallel programs correct, Communications of the ACM, v.20 n.12, p.921-930, Dec. 1977 [doi>10.1145/359897.359903]
	GRIE79	GRIES, D. "The Schorr-Waite graph markmg algorithm," Acta inf. 11, 3 (1979), 223-232. (M}
	GRIS72	GRISWOLD, R.E. The macro tmplementatmn of Snobol 4, W. H. Freeman, San Francisco, 1972. {GM}
	HADD67	HADDON, B.K., AND WAITE, W M. "A compaction procedure for variable length storage elements," Comput. J. 10 (Aug. 1967), 162-165. {CR}
	HANS69	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 [doi>10.1145/363219.363225]
	HANS77	HANSON, D.R. "Storage management for an implementation of Snobol 4," Software: Practwe and Experience 7, 2 (1977), 179-192. (BCMLR}
	HART64	HART, T.P., AND EVANS, T.G. "Notes on implementing hsp for the M 460 computer," in BERK64. {C}
	HOAR74	HOARE, C.A.R. "Optimizatmn of store size for garbage collectmn," Inf Process Lett 2, 6 (April 1974), 165-166. (A}
	HORO77	HOROWITZ, E., AND SAHNL S Fundamentals of data structure, Cornputer Science Press, Woodland Hills, Calif., 1977. {ACGMR}
	JONK79	JONKERS, H.B.M. "A fast garbage compaction algorithm," inf Process. Lett. 9, 1 (July 1979), 26-30. (CR}
	KAIN69	R. Y. Kain, Block structures, indirect addressing, and garbage collection, Communications of the ACM, v.12 n.7, p.395-398, July 1969 [doi>10.1145/363156.363175]
	KNUT73	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	KOWA79	Tomasz Kowaltowski, Data Structures and Correctness of Programs, Journal of the ACM (JACM), v.26 n.2, p.283-301, April 1979 [doi>10.1145/322123.322133]
	KUNG77	KUNG, H.T., AND SONG, S.W "An efficient parallel garbage collection system and its correctness proof," Dep Computer Scl., Carnegm-Mellon Univ., Pittsburgh, Sept. 1977. (AP}
	KURO75	KUROKAWA, T. "New marking algorithms for garbage collection," Collection, m Proc. 2nd USA-Japan Computer Conf, 1975, pp. 580-584. (BM}
	KURO79	KUROKAWA, T. "A new fast and safe marking algorithm," Toshiba R&D Center, Kawasakl 210, Japan, Jan. 1979. (BM}
	LAMP76	LAMPO~tT, L. "Garbage collection with multiple processes: An exercise m parallelism," Proc. IEEE Conf. Parallel Processing, Aug 1976. {P}
	LANG72	LANG, B., AND WEGBREIT, B. "Fast compactlficatlon," Rep. 25-72, Harvard Umv., Cambridge, Mass., Nov. 1972. (CMR}
	LARS77	LARSON, R.G "Mm~nizmg garbage collection as a function of regmn size," SIAM J. Computing 6, 4 {Dec. 1977), 663-668. (AV)
	LEE79	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 [doi>10.1145/567752.567758]
	LEE80	K. P. Lee, A linear algorithm for copying binary trees using bounded workspace, Communications of the ACM, v.23 n.3, p.159-162, March 1980 [doi>10.1145/358826.358835]
	LIEB80	LIEBERMAN, H., AND HEWITT, C. "A real-time garbage collector that can recover temporary storage qmckly," MIT Lab for Computer Scmnce Rep TM- 184, M.I.T., Cambridge, Mass., July 1980. (PV}
	LIND73	LINDSTROM, G. "Scannmg hst structures without stacks or tag b~ts," Inf. Process Lett 2, 2 {June 1973), 47- 51. (M}
	LIND74	Gary Lindstrom, Copying list structures using bounded workspace, Communications of the ACM, v.17 n.4, p.198-202, April 1974 [doi>10.1145/360924.360936]
	MARS71	MARSHALL, S. "An Algol-68 garbage collector," in Algol 68 ~mplementat~on, J. E L. Peck (Ed), North-Holland, Amsterdam, 1971, pp. 239-243. (CLMR}
	MINS63	Marvin Minsky, A LISP Garbage Collector Algorithm Using Serial Secondary Storage, Massachusetts Institute of Technology, Cambridge, MA, 1963
	MOON74	MOON, D.A. "MACLlsp reference manual," Project MAC, M.I.T, Cambmdge, Mass., April 1974. (GM}
	MORR78	F. Lockwood Morris, A time- and space-efficient garbage compaction algorithm, Communications of the ACM, v.21 n.8, p.662-665, Aug. 1978 [doi>10.1145/359576.359583]
	MORR79	MORRIS, F.L. "On a comparison of garbage collection techmques," technical correspondence, Commun A CM 22, 10 {Oct. 1979), 571. {C}
	MULL76	MULLER, K G. "On the feasibility of concurrent garbage collectmn," Ph.D. thesis, Tech Hogeschool Delft, March 1976. (P}
	OWIC81	Susan Owicki, Making the world safe for garbage collection, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.77-86, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567539]
	PARE68	PARENTE, R J. "A simulation-oriented memory allocation algorithm," in S~mulatmn Programmtng Languages, J. N. Buxton (Ed), North-Holland, Amsterdam, 1968, pp 198-209 (CL}
	PFAL77	John L. Pfaltz, Computer Data Structures, McGraw-Hill, Inc., New York, NY, 1977
	REIN73	Edward M. Reingold, A nonrecursive list moving algorithm, Communications of the ACM, v.16 n.5, p.305-307, May 1973 [doi>10.1145/362041.362200]
	ROBS73	ROBSON, J M. "An ~mproved algorithm for traversing binary trees without auxiliary stack," Inf. Process Lett. 2, i (March 1973}, 12-14 (M}
	ROBS77	J. M. Robson, A bounded storage algorithm for copying cyclic structures, Communications of the ACM, v.20 n.6, p.431-433, June 1977 [doi>10.1145/359605.359628]
	ROCH71	Arnold Rochfeld, New LISP techniques for a paging environment, Communications of the ACM, v.14 n.12, p.791-795, Dec. 1971 [doi>10.1145/362919.362937]
	ROSS67	Douglas T. Ross, The AED free storage package, Communications of the ACM, v.10 n.8, p.481-492, Aug. 1967 [doi>10.1145/363534.363546]
	SCHO67	H. Schorr , W. M. Waite, An efficient machine-independent procedure for garbage collection in various list structures, Communications of the ACM, v.10 n.8, p.501-506, Aug. 1967 [doi>10.1145/363534.363554]
	SIKL72	SIKLOSSY, L "Fast and read-only algorithms for traversing trees without an auxiliary stack," Inf Process. Lett. 1, 4 (June 1972), 149-152. (M}
	STAN80	Thomas A. Standish, Data Structure Techniques, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1980
	STEE75	Guy L. Steele, Jr., Multiprocessing compactifying garbage collection, Communications of the ACM, v.18 n.9, p.495-508, Sept. 1975 [doi>10.1145/361002.361005]
	TERA78	TERASHIMA, M., AND GOTO, E. "Genetic order and compactlfymg garbage collectors," Inf. Process. Lett. 7, 1 (Jan. 1978), 27-32. {CR}
	THOR72	THORELLI, L.E. "Marking algomthms," BIT 12, 4 (1972), 555-568. {MR)
	THOR76	THORELLI, L.E "A fast compactlfying garbage collector," BIT 16, 4 (1976), 426-441 {CMR}
	TOPO79	TOPOR, R. "The correctness of the Schorr-Waite list marking algomthm," Acta Inf. 11, 3 (1979), 211-221 {M)
	VEIL76	VEILLON, G. "Transformations de programmes recursifs," R A.I R O. Informat~que 10, 9 (Sept. 1976}, 7-20. (M}
	WADL76	Philip L. Wadler, Analysis of an algorithm for real time garbage collection, Communications of the ACM, v.19 n.9, p.491-500, Sept. 1976 [doi>10.1145/360336.360338]
	WAIT73	WAITE, W.M. Implementing software for non-numerw apphcatmns, Prentice- Hall, Englewood Chffs, N.J, 1973. {GCR}
	WALD72	David C. Walden, A note on Cheney's nonrecursive list-compacting algorithm, Communications of the ACM, v.15 n.4, p.275, April 1972 [doi>10.1145/361284.361300]
	WEGB72a	WEGBREIT, B. "A generalized compactffymg garbage collector "Comput. J. 15, 3 (Aug. 1972), 204-208. {CGMR)
	WEGB72b	Wegbreit, B. "A space efficmnt hst structure tracing algorithm," IEEE Trans Computers C21 (Sept. 1972), 1009-1010 {M}
	WEIS67	WEISSMAN, C. L~sp 1 5 primer, Dickenson Publ., Belmont, Calff, 1967. {G)
	WEIZ63	J. Weizenbaum, Symmetric list processor, Communications of the ACM, v.6 n.9, p.524-536, Sept. 1963 [doi>10.1145/367593.367617]
	WEIZ69	Joseph Weizenbaum, Recovery of reentrant list structures in SLIP, Communications of the ACM, v.12 n.7, p.370-372, July 1969 [doi>10.1145/363156.363159]
	WISE77	WISE, D.S., AND FRIEDMAN, D.P. "The one-bit reference count," BIT 17, 4 (1977), 351-359. (GLN}
	WISE79	David S. Wise, Morris's Garbage Compaction Algorithm Restores Reference Counts, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.115-120, July 1979 [doi>10.1145/357062.357070]
	WODO69	WODON, P.L. "Data structure and storage allocation," BIT 9, 3 (1969), 270- 282. (CGLMR}
	WODO71	WODON, P.L. "Methods of garbage collectmn for Algol 68," m Algol 68 tmplementatmn, J. E. L Peck (Ed.), North- Holland, Amsterdam, 1971, pp. 245- 262. (CGLMR}
	YELO77	Lawrence Yelowitz , Arthur G. Duncan, Abstractions, instantiations, and proofs of marking algorithms, Proceedings of the 1977 symposium on Artificial intelligence and programming languages, p.13-21, August 15-17, 1977
	ZAVE75	ZAVE, D.A. "A fast compacting garbage collector," Inf. Process Lett. 3, 6 (July 1975), 167-169. {CMR}