Java [Sun95a] is a type-safe, object-oriented programming language that is interesting because of its potential for WWW applications. Because of the widespread interest in Java, its similarity to C and C++, and its industrial support, many organizations may make Java their language of choice.
Java is also interesting because of its machine-independent target architecture, the Java Virtual Machine (JVM) [LY96]. Java is attractive for web applications, in part because Java bytecodes can be statically verified, preventing violations of type safety that might access private information.
Java as currently defined is explicitly a first version that is intended to be extended later. This paper addresses one of the areas where extension is needed, namely, support for generic code. In Java, it is possible to define a new type, such as a set of integers, but it is not possible to capture a set abstraction where the elements of a particular set are homogeneous, but the element type can differ from one set to another. Current Java programs adapt to the lack of genericity by using runtime type discrimination, which is awkward for the programmer and also relatively expensive.
In this paper, we extend Java with parametric polymorphism, a mechanism for writing generic interfaces and implementations. We provide a complete design of this extension and discuss the interaction of parametric polymorphism with other Java features, including ways that generic abstractions can simplify coding with some standard Java classes. We also show how to implement this design efficiently. We sketch an implementation of the design using the existing JVM bytecodes, and also present an extension to the JVM that provides better performance. Finally, we present results from a working prototype of the extended JVM interpreter, showing that our technique improves performance by up to 17% over standard Java. Detailed specifications of our extensions are available in the appendices.
An explicit goal of our work was to be very conservative. We extended Java by adapting an existing, working mechanism with as few changes as possible. We supported the Java philosophy of providing separate compilation with complete inter-module type checking, which also seemed important for pragmatic reasons.
We used the Theta mechanism [LCD+94][DGLM95] as the basis of our language design, because Theta has important similarities to Java. Like Java, it uses declared rather than structural subtyping, and it also supports complete inter-module type checking. We rejected the C++ template mechanism [Sto87] and the Modula-3 [Nel91] generic module mechanism because they do not support our type-checking goal; they require that a generic module must be type checked separately for every distinct use. Furthermore, the most natural implementation of these mechanisms duplicates the code for different actual parameters, even when the code is almost entirely identical.
For the implementation, our concern was to achieve good performance for generic code in both execution speed and code size. An explicit goal was to use the same code for all instances of a generic abstraction, in order to avoid code blowup. Techniques for implementing parameterized code without bytecode extensions lead to slower execution or increased code size. Type checking our parameterized code in the Java bytecode verifier is also efficient: the code of a parametric class need only be verified once, like that of an ordinary class. All our extensions are backward compatible with the current JVM and have little impact on the performance of non-parameterized code. The result is that Java code is not only simpler to write, but also faster. For a simple collection class, avoiding the runtime casts from "Object" reduced run times by up to 17% in our prototype interpreter.
The remainder of the paper is organized as follows. Section 2 provides an informal description of our extensions to the Java language. Section 3 sketches how to implement the language extensions using the standard virtual machine. It also shows how these extensions are converted into our extended bytecode specification and how the extended bytecodes are verified and run. Finally, it presents some performance results. Section 4 discusses ways that other aspects of Java could be changed to take advantage of parametric polymorphism. We conclude in Section 5 with a discussion of what we have accomplished. The appendices contain detailed specifications of our language and virtual machine extensions.