There are two reasonable ways to implement parameterized types in Java without extending the virtual machine. We will briefly sketch these approaches, though we did not implement them because of their performance problems.
The most obvious implementation is to treat each instantiation of a parameterized class or interface as producing a separate class or interface. Each instantiation of a parameterized class has its own ".class" file that must be separately loaded into the interpreter and verified for correctness. In essence, the parameterized code is recompiled for each distinct set of parameters. This technique is similar to the template implementation used by most C++ compilers, which leads to substantial code blowup. It differs from the C++ approach in that the where clauses guarantee successful recompilation.
An alternative strategy produces code that is generic across all instantiations:
the compiler can generate bytecodes for parameterized classes
as though all parameters are of class Object. When compiling code
that uses a parameterized class, the compiler generates runtime casts
as appropriate. Because the compiler has type checked the code, all
the runtime casts necessarily succeed, but the performance is the same
as for old-style Java code that manipulates variables of type Object
and performs explicit casts.
In this scheme, invocation of where-routines is complex. Each object of a parameterized class contains a pointer to a separate object that bundles up the appropriate where-routines for the instantiation, presenting them as methods. The compiler translates a where-routine invocation to an invocation of the corresponding method of this where-routine object. The where-routine object is installed in the object of a parameterized class by passing it as a hidden, extra argument to class constructors. The advantage of this technique over the previous one is that only the code of these where-routine objects is duplicated for each instantiation; most of the code of a parameterized class is shared for all instantiations.
This approach takes extra space in each object to point to the where-routine objects, and also adds the overhead of runtime casts. Gratuitous runtime casts occur at calls to methods of the parameterized class, and also within the methods of the where-routine objects. In addition, the already-noticeable cost of runtime casts can be expected to increase as more sophisticated interpreters and native code compilers are used. Native code compilation seems likely to improve simple operations like arithmetic and method invocation more than runtime casts, so the casts will become relatively more expensive. Therefore, in our implementation, we extended the bytecodes to express parameterization directly.