Unboxed objects and polymorphic typing

ABSTRACT

This paper presents a program transformation that allows languages with polymorphic typing (e.g. ML) to be implemented with unboxed, multi-word data representations. The transformation introduces coercions between various representations, based on a typing derivation. A prototype ML compiler utilizing this transformation demonstrates important speedups.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: A. W. Appel. l~un-time tags aren't necessary. Lisp and Symbolic Computation, 2(2), June 1989.
• 3: Andrew W. Appel, Compiling with continuations, Cambridge University Press, New York, NY, 1992
• 4: Andrew W. Appel , David B. MacQueen, A standard ML compiler, Proc. of a conference on Functional programming languages and computer architecture, p.301-324, October 1987, Portland, Oregon, United States
• 5: J. F. Bartlett. Compacting garbage collector with ambiguous roots. Technical report, DEC Western Research Laboratory, 1988.
• 6: L. Cardelli. The functional abstract machine. Polymorphism, 1 (1), 1983.
• 7: Luca Cardelli , Peter Wegner, On understanding types, data abstraction, and polymorphism, ACM Computing Surveys (CSUR), v.17 n.4, p.471-523, Dec. 1985 [doi>10.1145/6041.6042]
• 8: Frederick Chow , John Hennessy, Register allocation by priority-based coloring, ACM SIGPLAN Notices, v.19 n.6, p.222-232, June 1984
• 9: G. Cousineau , P.-L. Curien, The categorical abstract machine, Science of Computer Programming, v.8 n.2, p.173-202, April 1, 1987 [doi>10.1016/0167-6423(87)90020-7]
• 10: Luis Damas , Robin Milner, Principal type-schemes for functional programs, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.207-212, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582176]
• 11: Gerry Kane, MIPS RISC architecture, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 12: Robin Milner , Mads Tofte , Robert Harper, The definition of Standard ML, MIT Press, Cambridge, MA, 1990
• 13: 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]
• 14: S. L. Peyton-Jones. Unboxed values as first-class citizens. In Functional Programming Languages and Computer Architecture, volume 523 of Lecture Notes in Computer Science, 1991.
• 15: Satish R. Thatte, Coercive type isomorphism, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.29-49, June 1991, Cambridge, Massachusetts, United States
• 16: Mads Tofte, Type inference for polymorphic references, Information and Computation, v.89 n.1, p.1-34, Nov. 1990 [doi>10.1016/0890-5401(90)90018-D]
• 17: Niklaus Wirth, Programming in MODULA-2 (3rd corrected ed.), Springer-Verlag New York, Inc., New York, NY, 1985

INDEX TERMS

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

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

          Nouns: ML
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures
      D.3.4 Processors
          Subjects: Compilers

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Operational semantics
      F.3.3 Studies of Program Constructs
          Subjects: Type structure

General Terms:
Algorithms, Languages, Verification