Making the world safe for garbage collection

ABSTRACT

This paper describes the formal specifications of garbage collection in the programming language Cedar Mesa. They were developed as part of the process of identifying a safe subset of Mesa for which garbage collection was possible. The purpose of the specifications was to provide a precise definition of safety, along with criteria for checking the safety of proposed language features. Thus the specifications had to characterize the "invisibility" of the collector, as well as describe the services it provides. A beneficial effect of the specification effort was that the process of constructing the specifications led to a number of discoveries that improved the quality of the language.

REFERENCES

• 1: J. G. Mitchell et al., Mesa Language Manual, Report CSL-79-3, Xerox Palo Alto Research Center, April, 1979.
• 2: Charles M. Geschke , James H. Morris, Jr. , Edwin H. Satterthwaite, Early experience with Mesa, Communications of the ACM, v.20 n.8, p.540-553, Aug. 1977 [doi>10.1145/359763.359771]
• 3: 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]
• 4: H. Bekic and K. Walk, "On formalization of storage properties," in E. Engeler, editor, Semantics of Algorithmic Languages, Springer Verlag Lecture Notes in Mathematics, vol 188, 1971.
• 5: K. Walk, "Modelling of storage properties of higher-level languages," International Journal of Computer and Information Sciences, 2:1 (March 1973) pp 1-24.
• 6: 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]
• 7: 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]
• 8: 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]