11.4 Parameterized Types

Parameterized types are found in a diverse set of languages, from Eiffel (one of the first object-oriented languages) and Haskell (a purely functional language without any side effects) to C++. In C++, parameterized types are called templates.

A parameterized type allows the programmer to write programs without specifying all the types that are used. A parameterized type is often used to define a collection of objects. For example, here is code for a binary tree, written in Eiffel:

 class BINARY_TREE[T -> COMPARABLE] feature    left : BINARY_TREE[T]    right : BINARY_TREE[T]    value : T    insert(node : T) is        -- Insert the node into the tree        -- This code can use < on node and value, since they        -- are both COMPARABLEs    end; end 

All the values in the binary tree described must be of type T, and each of the sub-trees must also be binary trees that store T. Different trees may use a different type for T. T is called a type variable.

The notation T -> COMPARABLE means that T must be a descendant of the COMPARABLE class. This is called constrained genericity. The symbol < is a feature of all classes that are descendants of COMPARABLE. A feature is like a method in Java: it is called to produce a value. The symbol < is used to compare elements. All descendants of COMPARABLE support the < feature.

You can create a binary tree of some particular type by substituting that type for T. For example, to create a binary tree of real numbers, write

 real_tree : BINARY_TREE[REAL]     -- Create a tree of reals 

A programmer might add to the system a new class that supports the COMPARABLE features, such as this definition of a dictionary entry:

 class DICTIONARY_ENTRY    inherit COMPARABLE feature    -- provide definitions for the COMPARABLE features end; 

This code defines a class DICTIONARY_ENTRY that inherits the definitions from the class COMPARABLE. The Eiffel inherit clause is similar to the Java super clause in a class declaration, except that Eiffel permits multiple inheritance.

The programmer can use this definition to create a dictionary that is a binary tree of dictionary entries:

 dictionary : BINARY_TREE[DICTIONARY_ENTRY] 

If the programmer attempts to enter a DICTIONARY_ENTRY into real_tree or a REAL into the dictionary, then the compiler signals a type violation.

There are two basic ways to implement type parameters in the Java virtual machine. One is to create one generic class. The other is to create new classes for all possible values of the type parameters.

11.4.1 Implementing Parameterized Types with a Generic Class

The following code implements BINARY_TREE in bytecodes using a single generic class:

 .class BINARY_TREE .field left LBINARY_TREE; .field right LBINARY_TREE; .field value LCOMPARABLE; .method insert(LCOMPARABLE;)V ;; Code for the method, making no assumptions about the argument ;; except that it is a COMPARABLE .end method 

Since the type of value is constrained to being a descendent of COMPARABLE, it may be treated as a COMPARABLE. If there were no constraint provided, you could substitute java/lang/Object for COMPARABLE, since java/lang/Object is the superclass of all classes.

To properly implement Eiffel programs this way we have to provide classes for basic types like REAL and INT. REAL and INT would implement the COMPARABLE interface, allowing the programmer to use the BINARY_TREE class to create trees of numerical values as well as objects.

One difficulty with implementing binary trees this way is that it does not force all elements of the binary tree to be of the same type. If you created an instance of this class, then you could insert either a REAL or a DICTIONARY_ENTRY into it. In fact, you could insert entries of both at different times.

This is not necessarily a problem. The class BINARY_TREE is not intended to be used from other JVM programs. It is created by the Eiffel compiler, and it should not be used except by other classes generated by the Eiffel compiler. Eiffel does compile-time checking to ensure that the programmer does not try to insert a DICTIONARY_ENTRY into a BINARY_TREE[REAL] or vice versa. The JVM does not need to further check that the types are compatible.

11.4.2 Implementing Parameterized Types as Templates

A different way of implementing parameterized types in the JVM is to create a new class for each instantiation of the parameter template that is used in the program. This is the approach C++ compilers use to implement templates.

For BINARY_TREE[REAL] and BINARY_TREE[DICTIONARY_ENTRY], two new classes are generated, one for binary trees of REALs and another for binary trees of DICTIONARY_ENTRYs. The names are mangled to ensure that they don't conflict with existing types. The definitions of these classes follow.

 .class BINARY_TREE$REAL .field left LBINARY_TREE$REAL; .field right LBINARY_TREE$REAL; .field value LREAL; .method insert(LREAL;)V ;; Code for the insert method, specialized using ;; a REAL as the argument .end method .class BINARY_TREE$DICTIONARY_ENTRY .field left LBINARY_TREE$DICTIONARY_ENTRY; .field right LBINARY_TREE$DICTIONARY_ENTRY; .field value DICTIONARY_ENTRY; .method insert(LDICTIONARY_ENTRY;)V ;; Code for the insert method, specialized using a   ;; DICTIONARY_ENTRY as the argument .end method 

One reason to use this technique of implementing parameterized types is that the JVM does additional type checking for you. Even if the Eiffel compiler were to permit you to generate JVM code that tried to insert a REAL into a BINARY_TREE[DICTIONARY_ENTRY], the JVM would catch it.

Another advantage is that the compiler can optimize the code to use unwrapped, native JVM implementations of the numeric types. Instead of wrapping the numbers in an object such as REAL, which implements the COMPARABLE interface, the class BINARY_TREE$REAL can use floats. The implementation could be specialized to use the single instruction fcmpg to compare floats, instead of looking in COMPARABLE for the method that corresponds to the < operator in Eiffel.

The problem with this technique is that it requires extensive analysis of the code at compile time to determine which classes may be used. If the programmer uses many different kinds of binary trees, many different classes will be created. Adding new classes or changing the implementation of BINARY_TREE may cause substantial recompilation.