An efficient class and object encoding

ABSTRACT

An object encoding translates a language with object primitives to one without. Similarly, a class encoding translates classes into other primitives. Both are important theoretically for comparing the expressive power of languages and for transferring results from traditional languages to those with objects and classes. Both are also important foundations for the implementation of object-oriented languages as compilers typically include a phase that performs these translations.This paper describes a language with a primitive notion of classes and objects and presents an encoding of this language into one with records and functions. The encoding uses two techniques often used in compilers for single-inheritance class-based object-oriented languages: the self-application semantics and the method-table technique. To type the output of the encoding, the encoding uses a new formulation of self quantifiers that is more powerful than previous approaches.

REFERENCES

• AC93: Roberto M. Amadio , Luca Cardelli, Subtyping recursive types, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.4, p.575-631, Sept. 1993 [doi>10.1145/155183.155231]
• AC96: Martin Abadi , Luca Cardelli, A Theory of Objects, Springer-Verlag New York, Inc., Secaucus, NJ, 1996
• ACV96: Martín Abadi , Luca Cardelli , Ramesh Viswanathan, An interpretation of objects and object types, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.396-409, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237809]
• BCP99: Kim B. Bruce , Luca Cardelli , Benjamin C. Pierce, Comparing object encodings, Information and Computation, v.155 n.1-2, p.108-133, Nov./Dec. 1999 [doi>10.1006/inco.1999.2829]
• BF98: Viviana Bono , Kathleen Fisher, An Imperative, First-Order Calculus with Object Extension, Proceedings of the 12th European Conference on Object-Oriented Programming, p.462-497, July 20-24, 1998
• Bru94: Kim Bruce. A paradigmatic object-oriented programming language: Design, static typing and semantics. Journal of Functional Programming, 4(2):127-206, April 1994.
• BSvG95: Kim B. Bruce , Angela Schuett , Robert van Gent, PolyTOIL: A Type-Safe Polymorphic Object-Oriented Language, Proceedings of the 9th European Conference on Object-Oriented Programming, p.27-51, August 07-11, 1995
• Car88: Luca Cardelli, A semantics of multiple inheritance, Information and Computation, v.76 n.2-3, p.138-164, February/March 1988 [doi>10.1016/0890-5401(88)90007-7]
• CCH+89: Peter Canning , William Cook , Walter Hill , Walter Olthoff , John C. Mitchell, F-bounded polymorphism for object-oriented programming, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.273-280, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99392]
• CG99: Dario Colazzo , Giorgio Ghelli, Subtyping Recursive Types in Kernel Fun - Abstract, Proceedings of the 14th Annual IEEE Symposium on Logic in Computer Science, p.137, July 02-05, 1999
• CHC90: William R. Cook , Walter Hill , Peter S. Canning, Inheritance is not subtyping, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.125-135, December 1989, San Francisco, California, United States [doi>10.1145/96709.96721]
• Coo89a: William R. Cook, A denotational semantics of inheritance, 1989
• Coo89b: William Cook. A proposal for making Eiffel type-safe. In 3rd European Conference on Object-Oriented Programming, pages 57-72, Nottingham, UK, July 1989. Cambridge University Press.
• Cra99: Karl Crary. Simple, effcient object encoding using intersection types. Technical Report CMU-CS-99-100, Carnegie Mellon University, Pittsburgh, PA 15213, USA, 1999.
• ESTZ95: Jonathan Eifrig , Scott Smith , Valery Trifonov , Amy Zwarico, An interpretation of typed OOP in a language, Lisp and Symbolic Computation, v.8 n.4, p.357-397, Dec. 1995 [doi>10.1007/BF01018829]
• FHM94: Kathleen Fisher , Furio Honsell , John C. Mitchell, A lambda calculus of objects and method specialization, Nordic Journal of Computing, v.1 n.1, p.3-37, Spring 1994
• Fis96: Kathleen Shanahan Fisher , John C. Mitchell, Type systems for object-oriented programming languages, 1996
• FM95a: Kathleen Fisher , John C. Mitchell, A Delegation-based Object Calculus with Subtying, Proceedings of the 10th International Symposium on Fundamentals of Computation Theory, p.42-61, August 22-25, 1995
• FM95b: Kathleen Fisher , John C. Mitchell, The development of type systems for object-oriented languages, Theory and Practice of Object Systems, v.1 n.3, p.189-220, Fall 1995
• FM96: Kathleen Fisher , John C. Mitchell, Classes = Objects + Data Abstraction, Stanford University, Stanford, CA, 1996
• FM98: Kathleen Fisher , John C. Mitchell, On the relationship between classes, objects, and data abstraction, Theory and Practice of Object Systems, v.4 n.1, p.3-25, 1998 [doi>10.1002/(SICI)1096-9942(1998)4:1<3::AID-TAPO2>3.3.CO;2-2]
• GJS96: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• Gle99a: Neal Glew. Object closure conversion. In Andrew Gordon and Andrew Pitts, editors, 3rd International Workshop on Higher Order Operational Techniques in Semantics, volume 26 of El ectronic Notes in Theoretical Computer Science, Paris, France, September 1999. Elsevier. http://www.elsevier.nl/ locate/entcs/volume26.html.
• Gle99b: Neal Glew, Type dispatch for named hierarchical types, Proceedings of the fourth ACM SIGPLAN international conference on Functional programming, p.172-182, September 27-29, 1999, Paris, France
• Gle00a: Neal Glew. An efficient class and object encoding. Technical Report STAR-TR-00.07-02, STAR Lab, InterTrust Technologies Corporation, 4750 Patrick Henry Drive, Santa Clara, CA 95054-1851, USA, July 2000.
• Gle00b: Arthur Neal Glew , Dexter Kozen, Low-level type systems for modularity and object-oriented constructs, 2000
• Hic: Jason Hickey. Predicative type-theoretic interpretation of objects. Unpublished, author's contact: [e-mail].
• HP95: Martin Hofmann , Benjamin Pierce, Positive subtyping, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.186-197, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199482]
• HP98: Martin Hofmann and Benjamin Pierce. Type destructors. In 5th International Workshop on Foundations of Object Oriented Programming Languages, pages 3-1 to 3-11, San Diego, CA, USA, January 1998.
• Kam88: S. Kamin, Inheritance in smalltalk-80: a denotational definition, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.80-87, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73567]
• KPS95: Dexter Kozen, Jens Palsberg, and Michael Schwartzbach. Efficient recursive subtyping. Mathematical Structures in Computer Science, 5(1):113-125, March 1995.
• KR94: Samuel N. Kamin , Uday S. Reddy, Two semantic models of object-oriented languages, Theoretical aspects of object-oriented programming: types, semantics, and language design, MIT Press, Cambridge, MA, 1994
• LST99: Christopher League , Zhong Shao , Valery Trifonov, Representing Java classes in a typed intermediate language, Proceedings of the fourth ACM SIGPLAN international conference on Functional programming, p.183-196, September 27-29, 1999, Paris, France
• MCG+99: Greg Morrisett, Karl Crary, Neal Glew, Dan Grossman, Richard Samuels, Frederick Smith, David Walker, Stephanie Weirich, and Steve Zdancewic. TALx86: A realistic typed assembly language. In ACM SIGPLAN Workshop on Compiler Support for System Software, volume 0228 of INRIA Research Reports, Atlanta, GA, USA, May 1999.
• Mit90: John C. Mitchell, Toward a typed foundation for method specialization and inheritance, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.109-124, December 1989, San Francisco, California, United States [doi>10.1145/96709.96719]
• MTC+96: Greg Morrisett, David Tarditi, Perry Cheng, Christopher Stone, Robert Harper, and Peter Lee. The TIL/ML compiler: Performance and safety through types. In ACM SIGPLAN Workshop on Compiler Support for System Software, Tucson, AZ, USA, February 1996.
• MWCG99: Greg Morrisett , David Walker , Karl Crary , Neal Glew, From system F to typed assembly language, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.3, p.527-568, May 1999 [doi>10.1145/319301.319345]
• NL98: George C. Necula , Peter Lee, The design and implementation of a certifying compiler, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.333-344, June 17-19, 1998, Montreal, Quebec, Canada
• PT94: Benjamin C. Pierce , David N. Turner, Object-oriented programming without recursive types, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.299-312, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158653]
• Red98: Uday Reddy, Objects as closures: abstract semantics of object-oriented languages, Proceedings of the 1988 ACM conference on LISP and functional programming, p.289-297, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62721]
• Rém94: Didier Rémy, Programming Objects with ML-ART, an Extension to ML with Abstract and Record Types, Proceedings of the International Conference on Theoretical Aspects of Computer Software, p.321-346, April 19-22, 1994
• RR96a: John Reppy and Jon Riecke. Classes in Object MLvia modules. In3rd International Workshop on Foundations of Object Oriented Programming Languages, New Brunswick, NJ, USA, July 1996.
• RR96b: John Reppy , Jon Riecke, Simple objects for Standard ML, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.171-180, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• RV97: Didier Rémy , Jérôme Vouillon, Objective ML: a simple object-oriented extension of ML, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.40-53, January 15-17, 1997, Paris, France [doi>10.1145/263699.263707]
• TMC+96: D. Tarditi , G. Morrisett , P. Cheng , C. Stone , R. Harper , P. Lee, TIL: a type-directed optimizing compiler for ML, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.181-192, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• Vis98: R. Viswanathan, Full Abstraction for First-Order Objects with Recursive Types and Subtyping, Proceedings of the 13th Annual IEEE Symposium on Logic in Computer Science, p.380, June 21-24, 1998
• Vou98: Jerome Vouillon. Using modules as classes. In 5th International Workshop on Foundations of Object Oriented Programming Languages, pages 4-1 to 4-10, San Diego, CA, USA, January 1998.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Object-oriented languages

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

General Terms:
Design, Languages, Performance, Theory