Generics

Wednesday, 29 October – 10:30-12:00

A First-Class Approach to Genericity

Eric Allen, Rice University, eallen@cs.rice.edu
Jonathan Bannet, Rice University, jbannet@rice.edu
Robert Cartwright, Rice University, cork@cs.rice.edu

This paper describes how to add first class generic types—including mixins—to strongly-typed, object-oriented languages with nominal (name-based) 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 its type parameters, e.g., a class C<T> that extends T. Although mixins of this form are widely used in C++ (via templates), they are clumsy and error-prone because C++ 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, in the same sense that Java supports local (class-by-class) compilation. 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 type systems have 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 scheme could be applied to other object-oriented languages such as C# or Eiffel that support incremental compilation, dynamic class loading, and a static type system with nominal subtyping.

A Comparative Study of Language Support for Generic Programming

Ronald Garcia, Indiana University, garcia@osl.iu.edu
Jaakko Jarvi, Indiana University, jajarvi@osl.iu.edu
Andrew Lumsdaine, Indiana University, lums@osl.iu.edu
Jeremy Siek, Indiana University, jsiek@osl.iu.edu
Jeremiah Willcock, Indiana University, jewillco@osl.iu.edu

Many modern programming languages support basic generic programming, sufficient to implement type-safe polymorphic containers. Some languages have moved beyond this basic support to a broader, more powerful interpretation of generic programming, and their extensions have proven valuable in practice. This paper reports on a comprehensive comparison of generics in six programming languages: C++, Standard ML, Haskell, Eiffel, Java (with its proposed generics extension), and Generic C#. By implementing a substantial example in each of these languages, we identify eight language features that support this broader view of generic programming. We find these features are necessary to avoid awkward designs, poor maintainability, unnecessary run-time checks, and painfully verbose code. As languages increasingly support generics, it is important that language designers understand the features necessary to provide powerful generics and that their absence causes serious difficulties for programmers.

Lightweight Confinement for Featherweight Java

Tian Zhao, University of Wisconsin, Milwaukee, tzhao@cs.uwm.edu
Jens Palsberg, Purdue University, palsberg@cs.purdue.edu
Jan Vitek, Purdue University, jv@cs.purdue.edu

Confinement properties impose a structure on object graphs which can be used to enforce encapsulation— which is essential to certain program optimizations, to modular reasoning, and in many cases to software assurance. This paper formalizes the notion of confined type in the context of Featherweight Java. A static type system that mirrors the informal rules of Vitek and Bokopwski is proposed and proven sound. The definition of confined types is extended to confined instantiation of generic classes. Thus allowing for confined collection types in Java and for classes that can be confined post hoc. Confinement types rules are given for Generic Featherweight Java, and proven sound.