In this section we discuss the implementation issues that arise in adding parameterized types to Java. We largely ignore the issue of compiling the extended Java language described in Section 2, since there are many languages with parametric polymorphism [S+86][LCD+94][MTH90]. Instead, we focus on what is new: extensions to the bytecodes of the Java Virtual Machine (JVM) that support parametric polymorphism, and the effect of these extensions on both the bytecode verifier and interpreter.
Extensions to the JVM are not required. Without JVM extensions, however, there are two options for implementation, both of which have some performance problems, as discussed in Section 3.1. For this reason, we have chosen to extend the virtual machine.
The Java compiler generates ".class" files, containing code in a bytecode format, along with other information needed to interpret and verify the code. The format of a ".class" file is described by the JVM specification [LY96]. We extended the JVM in a backwards-compatible way, as described in Section 3.2, so existing binaries can run without modification. The extended virtual machine supports not only the extended Java described in Section 2, but also could be used as a target architecture for other languages with subtyping or parametric polymorphism.
We show how to verify the extended bytecodes in Section 3.3 and how to interpret them in Section 3.4. Our implementation technique requires little duplication of information for each instantiation; in particular, bytecodes and global constants are not duplicated.
The extended bytecode interpreter has been implemented, showing that parametric polymorphism can be easily added to Java while preserving verification and speeding up some code. Code that does not use parametric polymorphism suffers little performance penalty. Performance results are given in Section 3.5.