Java offers the real possibility that most programs can be written in a type-safe language. However, for Java to be broadly useful, it needs to have more expressive power than it does at present.
This paper addresses one of the areas where more power is needed. It extends Java with a mechanism for parametric polymorphism, which allows the definition and implementation of generic abstractions. The paper gives a complete design for the extended language. The proposed extension is small and conservative and the paper discusses the rationale for many of our decisions. The extension does have some impact on other parts of Java, especially Java arrays, and the Java class library.
The paper also explains how to implement the extensions. We first sketched two designs that do not change the JVM, but sacrifice some space or time performance. Our implementation avoids these performance problems. We had three main goals: to allow all instantiations to share the same bytecodes (avoiding code blowup), to have good performance when using parameterized code, and to have little impact on the performance of code that does not use parameterization.
The implementation discussed in Section 3 meets these goals. In that section, we described some small extensions to the virtual machine specification that are needed to support parameterized abstractions; we also described the designs of the bytecode verifier and interpreter, and the runtime structures they rely on.
Preliminary performance results from our implementation of the extended bytecode interpreter show roughly a 2% penalty for the presence of parameterized code, but a speedup for parameterized code of 17%, by eliminating runtime checks. We expect that some simple performance tuning can improve these results.
The appendices that follow present a more detailed specification of our extensions to the Java language and to the Java virtual machine.
Parameterized abstractions are not the only extension needed to make Java into a convenient general purpose programming language. First-class procedures and iterators would also be valuable extensions to the language. However, we believe that parameterized types are the most important feature currently missing from Java.