Tag-free garbage collection using explicit type parameters

ABSTRACT

We have constructed a practical tag-free garbage collector based on explicit type parameterization of polymorphic functions, for a dialect of ML. The collector relies on type information derived from an explicitly-typed 2nd-order representation of the program, generated by the compiler as a byproduct of ordinary Hindley-Milner type inference. Runtime type manipulations are performed lazily to minimize execution overhead. We present details of our implementation approach, and preliminary performance measurements suggesting that the overhead of passing type information explicitly can be made acceptably small.

REFERENCES

• 1: Shail Aditya , Alejandro Caro, Compiler-directed type reconstruction for polymorphic languages, Proceedings of the conference on Functional programming languages and computer architecture, p.74-82, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165192]
• 2: Shail Aditya , Christine H. Flood , James E. Hicks, Garbage collection for strongly-typed languages using run-time type reconstruction, Proceedings of the 1994 ACM conference on LISP and functional programming, p.12-23, June 27-29, 1994, Orlando, Florida, United States
• 3: A. W. Appel. P~untime tags aren't necessary. Lisp and Symbolic Computation, 2:153-62, 1989.
• 4: Andrew W. Appel, Compiling with continuations, Cambridge University Press, New York, NY, 1992
• 5: Lennart Augustsson, Implementing Haskell overloading, Proceedings of the conference on Functional programming languages and computer architecture, p.65-73, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165191]
• 6: Hans-Juergen Boehm , Mark Weiser, Garbage collection in an uncooperative environment, Software—Practice & Experience, v.18 n.9, p.807-820, September 1988 [doi>10.1002/spe.4380180902]
• 7: Benjamin Goldberg, Tag-free garbage collection for strongly typed programming languages, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.165-176, June 24-28, 1991, Toronto, Ontario, Canada
• 8: Benjamin Goldberg , Michael Gloger, Polymorphic type reconstruction for garbage collection without tags, Proceedings of the 1992 ACM conference on LISP and functional programming, p.53-65, June 22-24, 1992, San Francisco, California, United States
• 9: Robert Harper , John C. Mitchell, On the type structure of standard ML, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.2, p.211-252, April 1993 [doi>10.1145/169701.169696]
• 10: Robert Harper , Greg Morrisett, Compiling with Non-Parametric Polymorphism (Preliminary Report), Carnegie Mellon University, Pittsburgh, PA, 1994
• 11: m. P. Jones. Partial evaluation for dictionary-free overloading. Technical Report YALEU/DCS/RR- 959, Yale University Dept. of Computer Scinece, Apr. 1993.
• 12: Xavier Leroy, Unboxed objects and polymorphic typing, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.177-188, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143205]
• 13: X. Leroy and M. Mauny. The Carol Light system, Release 0.6, Documentation and User's Manual, 1993.
• 14: R. Morrison , A. Dearle , R. C. H. Connor , A. L. Brown, An ad hoc approach to the implementation of polymorphism, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.3, p.342-371, July 1991 [doi>10.1145/117009.117017]
• 15: John Peterson , Mark Jones, Implementing type classes, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.227-236, June 21-25, 1993, Albuquerque, New Mexico, United States
• 16: S. L. Peyton Jones, C. Hall, K. Hammond, W. Parta/n, and P. Wadler. The Glasgow Haskell compiler: a technical overview. In Proc. UK Joint Framework for Information Technology (JFIT) Technical Conference, Keele, 1993.
• 17: M. Tofte. Operational Semantics and Polymorphic Type Inference. PhD thesis, Edinburgh University, 1988. C2T-52-88.
• 18: Andrew Peter Tolmach, Debugging standard ML, Princeton University, Princeton, NJ, 1992
• 19: P. Wadler , S. Blott, How to make ad-hoc polymorphism less ad hoc, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.60-76, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75283]
• 20: A. K. Wright. Polymorphism for imperative languages without imperative types. Technical Report TR93-200, Rice University Dept. of Computer Science, Feb. 1993.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Type structure

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: ML
      D.3.3 Language Constructs and Features
          Subjects: Procedures, functions, and subroutines
      D.3.4 Processors
          Subjects: Compilers

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Functional constructs

General Terms:
Algorithms, Design, Languages