Efficient implementation of run-time generic types for Java

One of the most significant limitations of the Java Programming Language is its lack of support for generic types. This thesis describes an efficient compiler and run-time type system for NextGen, a compatible extension of Java that supports generic types, including type dependent operations. The NextGen compiler is implemented as an extension to the existing compiler for GJ, a limited generic extension of Java that does not support run-time generic types. Our implementation is homogeneous, with one major exception: Instantiations of generic classes are constructed on demand. This exception is necessary to support polymorphic recursion. The NextGen compiler generates templates for such instantiation classes and relies on a customized class loader to construct instantiations at run-time. A suite of benchmarks on the Java, GJ, and NextGen compilers shows that the additional code required to support run-time generic types has little or no overhead compared to ordinary Java and GJ.