A first-class approach to genericity

ABSTRACT

This paper describes how to add first-class generic types---including mixins---to strongly-typed OO languages with nominal subtyping such as Java and C#. A generic type system is "first-class" if generic types can appear in any context where conventional types can appear. In this context, a mixin is simply a generic class that extends one of its type parameters, e.g., a class C<T> that extends T. Although mixins of this form are widely used in Cpp (via templates), they are clumsy and error-prone because Cpp treats mixins as macros, forcing each mixin instantiation to be separately compiled and type-checked. The abstraction embodied in a mixin is never separately analyzed.Our formulation of mixins using first-class genericity accommodates sound local (class-by-class) type checking. A mixin can be fully type-checked given symbol tables for each of the classes that it directly references---the same context in which Java performs incremental class compilation. To our knowledge, no previous formal analysis of first-class genericity in languages with nominal type systems has been conducted, which is surprising because nominal subtyping has become predominant in mainstream object-oriented programming languages.What makes our treatment of first-class genericity particularly interesting and important is the fact that it can be added to the existing Java language without any change to the underlying Java Virtual Machine. Moreover, the extension is backward compatible with legacy Java source and class files. Although our discussion of a practical implementation strategy focuses on Java, the same implementation techniques could be applied to other object-oriented languages such as C# or Eiffel that support incremental compilation, dynamic class loading, and nominal subtyping.

REFERENCES

• 1: Ole Agesen , Stephen N. Freund , John C. Mitchell, Adding type parameterization to the Java language, Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.49-65, October 05-09, 1997, Atlanta, Georgia, United States
• 2: E. Allen, J. Bannet, and R. Cartwright. Mixins in Generic Java are sound. Technical report, Rice University, 2002.
• 3: Eric Allen , Robert Cartwright, The case for run-time types in generic Java, Proceedings of the inaugural conference on the Principles and Practice of programming, 2002 and Proceedings of the second workshop on Intermediate representation engineering for virtual machines, 2002, June 13-14, 2002, Dublin, Ireland
• 4: E. Allen and R. Cartwright. Safe instantiation in Generic Java. In Technical Report, Computer Science Department, Rice University, 2003. Available at http://www.cs.rice.edu/CS/PLT/Publications.
• 5: Eric Allen , Robert Cartwright , Brian Stoler, Efficient Implementation of Run-time Generic Types for Java, Proceedings of the IFIP TC2/WG2.1 Working Conference on Generic Programming, p.207-236, July 11-12, 2002
• 6: Davide Ancona , Giovanni Lagorio , Elena Zucca, Jam - A Smooth Extension of Java with Mixins, Proceedings of the 14th European Conference on Object-Oriented Programming, p.154-178, June 12-16, 2000
• 7: Davide Ancona , Elena Zucca, A theory of mixin modules: basic and derived operators, Mathematical Structures in Computer Science, v.8 n.4, p.401-446, August 1998 [doi>10.1017/S0960129598002576]
• 8: Davide Ancona , Elena Zucca, A theory of mixin modules: algebraic laws and reduction semantics, Mathematical Structures in Computer Science, v.12 n.6, p.701-737, December 2002 [doi>10.1017/S0960129502003687]
• 9: J. Bloch and N. Gafter. Personal communication, 2002.
• 10: Gilad Bracha, The programming language jigsaw: mixins, modularity and multiple inheritance, University of Utah, Salt Lake City, UT, 1992
• 11: Gilad Bracha , William Cook, Mixin-based inheritance, Proceedings of the European conference on object-oriented programming on Object-oriented programming systems, languages, and applications, p.303-311, September 1990, Ottawa, Canada
• 12: G. Bracha, M. Odersky, D. Stoutamire, and P. Wadler. GJ Specification, 1998.
• 13: Gilad Bracha , Martin Odersky , David Stoutamire , Philip Wadler, Making the future safe for the past: adding genericity to the Java programming language, Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.183-200, October 18-22, 1998, Vancouver, British Columbia, Canada
• 14: Luca Cardelli , Simone Martini , John C. Mitchell , Andre Scedrov, An extension of system F with subtyping, Information and Computation, v.109 n.1-2, p.4-56, Feb. 15/March 1994 [doi>10.1006/inco.1994.1013]
• 15: Robert Cartwright , Guy L. Steele, Jr., Compatible genericity with run-time types for the Java programming language, Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.201-215, October 18-22, 1998, Vancouver, British Columbia, Canada
• 16: Matthew Flatt , Shriram Krishnamurthi , Matthias Felleisen, A Programmer's Reduction Semantics for Classes and Mixins, Formal Syntax and Semantics of Java, p.241-269, January 1999
• 17: Erich Gamma , Richard Helm , Ralph Johnson , John Vlissides, Design patterns: elements of reusable object-oriented software, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 18: Atshushi Igarashi , Benjamin Pierce , Philip Wadler, Featherwieght Java: a minimal core calculus for Java and GJ, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.132-146, November 01-05, 1999, Denver, Colorado, United States
• 19: Andrew Kennedy , Don Syme, Design and implementation of generics for the .NET Common language runtime, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.1-12, June 2001, Snowbird, Utah, United States
• 20: Sean McDirmid , Matthew Flatt , Wilson C. Hsieh, Jiazzi: new-age components for old-fasioned Java, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.211-222, October 14-18, 2001, Tampa Bay, FL, USA
• 21: David A. Moon, Object-oriented programming with flavors, Conference proceedings on Object-oriented programming systems, languages and applications, p.1-8, September 29-October 02, 1986, Portland, Oregon, United States
• 22: Joseph A. Bank , Andrew C. Myers , Barbara Liskov, Parameterized types for Java, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.132-145, January 15-17, 1997, Paris, France [doi>10.1145/263699.263714]
• 23: Martin Odersky , Philip Wadler, Pizza into Java: translating theory into practice, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.146-159, January 15-17, 1997, Paris, France [doi>10.1145/263699.263715]
• 24: Benjamin C. Pierce, Types and programming languages, MIT Press, Cambridge, MA, 2002
• 25: Alan Snyder, CommonObjects: an overview, Proceedings of the 1986 SIGPLAN workshop on Object-oriented programming, p.19-28, June 09-13, 1986, Yorktown Heights, New York, United States
• 26: Sun Microsystems, Inc. JSR 14: Add generic types to the Java Programming Language, 2001.
• 27: Sun Microsystems, Inc. JSR-14 v1.3 prototype compiler source code, 2003. Available at http://www.jcp.org/en/jsr/detail?id=014.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.5 Object-oriented Programming

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
      D.3.3 Language Constructs and Features

General Terms:
Design, Languages