PARAMETRIC POLYMORPHISM

A polymorphic function f (t x) takes some parameter x of type t, where t can be instantiated at different actual types. In an explicit style of parametric polymorphism, we pass the type as an argument to the function, so we write something like f <t>(t x), and a function call might look like f <int>(3) or f <string>("three"). In a language with implicit parametric polymorphism, we simply write the definition as f (x), and the call as f (3) or f ("three") - the type parameter t is unstated. Reasonable coding languages can be designed either way. In this chapter we will present Generic Java (GJ for short), a polymorphic extension of Java (polymorphic functions have also been called generic functions in the literature of coding languages). In GJ, classes and methods are polymorphic: Each class and method can take type parameters in triangle brackets:

 ClassDecl → Class id TyParams Ext { VarDecl* MethodDecl* }
 Ext → extends Type
 →
MethodDecl → public TyParams Type id ( FormalList )
 { VarDecl* Statement* return Exp ;}
 TyParams → < id Ext TyParRest* >
 →
 TyParRest → , id Ext

In addition to the int and boolean types (and so on), a Type used in declaring variables can now take arguments that are themselves types:

 Type → id < Type TypeRest* >
TypeRest → , Type

Finally, class constructors can also take type arguments:

Exp → new id < Type TypeRest* >()

GJ uses a combination of explicit and implicit polymorphism: The programmer must always write the formal type parameters (at class declarations), but actual type parameters (when calling a class constructor) can often be omitted. In this chapter we'll present only a fully explicit GJ. Using polymorphism, we can make a generic List class with which we can make a list of integers, or a list of strings, but which prevents the unintended mistaking of one for the other:

abstract class List<X> {
 List<X> append(List<X> more);
}
class Cons<X> extends List<X> {
 X head; List<X> tail;
 Cons (X head, List<X> tail) {this.head=head; this.tail=tail;}
 List<X> append(List<X> more) {
 return new Cons<X>(head, tail.append(more));
 }
}
class Null<X> extends List<X> {
 Null () {}
 List<X> append(List<X> more) {
 return more;
 }
}

Using this class declaration, we could create a list of the integers (3,4) with the expression,

List<Integer> list34 =
 new Cons<Integer>(new Integer(3),
 new Cons<Integer>(new Integer(4),
 new Null<Integer>));

We can even build a list of int-lists:

List<List<Integer>> lislis =
 new Cons<List<Integer>>(list34,
 new Null<List<Integer>>();

In GJ we can also bound a formal type parameter by specifying that it must be a subclass of a particular base class. Suppose, for example, that we have a class Printable:

abstract class Printable { void print_me(); }

with some subclasses, some of which are declared here and some of which are yet to be declared:

class PrintableInt extends Printable {
 int x;
 void print_me() {... print x ...}
}
class PrintableBool extends Printable {
 boolean b;
 void print_me() {... print b ...}
}

In ordinary Java we could make a pair-of-printables, as follows:

class Pair {
 Printable a;
 Printable b;
 void print_me() { a.print_me(); b.print_me(); }
}

and this will work well, as long as we don't mind that in any particular Pair, the a and b components might belong to different subclasses of Printable. But if we want to make "coherent" pairs-of-printables, where both components must belong to the same subclass, we can use bounded polymorphism in GJ, as follows:

class GPair<X extends Printable> {
 X a;
 X b;
 void print_me() { a.print_me(); b.print_me(); }
}

Now every object of type GPair<PrintableInt> has a and b components that are both instances of PrintableInt, and correspondingly for GPair<PrintableBool>, and for other subclasses of Printable that may be declared in the future. We say that Printable is the bound of type parameter X. Subtyping in GJ In Java, if we make class Triple extends Pair, then Triple is a subtype of Pair, and any Triple object can be passed as a parameter to any method that expects a Pair. In GJ, we can make class GTriple<X extends Printable> extends GPair<X>, and then GTriple<PrintableInt> is a subtype of GPair<PrintableInt>. But if class MyInt extends PrintableInt, then it's not the case that GTriple<MyInt> is a subtype of GPair<PrintableInt>. And it's especially not the case that GTriple is a subtype of GPair, because these are not types, they're type constructors, which become types only when applied to arguments.