Although we chose where clauses as the mechanism for constraining parameterized types, other choices are possible. We briefly examine some of these choices to show why they do not work well for extending Java. Further discussion of constraint mechanisms is available in an earlier paper [DGLM95].
One simple approach is to avoid constraints and instead pass the needed routines explicitly when objects are created (as arguments to constructors - and the procedures would be stored in instance variables so that they would be accessible to the methods).
Even assuming that first-class procedures exist, passing procedures
to constructors is not a good solution, since
it doesn't properly reflect the semantics. For example,
the meaning of a map depends very directly on the equality
test used for Key. Two maps that use different notions of key equality
are not really of the same type.
Finally, explicitly passing procedures prevents optimization (e.g., inlining) and uses space in each object to store the procedure.
Since where clauses resemble interfaces, it might seem that an interface could be used as the constraint; that is, the parameter would represent any type that is a subtype of the interface. The virtue of this approach is that some constraints can be expressed using the subtype notion that already exists; several languages have taken this approach [S+86][MMPN93][Mey88].
For example, we might try to write
interface SortedList[T] where T extends Ordered {
. . .
}
interface Ordered {
boolean lt(Ordered x);
}
lt) that mention the type
parameter [DGLM95]. Because ``lt'' is a binary method,
contravariance of arguments prevents most types from being subtypes of
Ordered.
Note also that interfaces cannot express constructor and static method constraints, which are both possible with where clauses.
To address some weaknesses of interfaces, parameterized interfaces can be
used instead. This approach, related to F-bounded polymorphism [CCH+89],
is used by some other statically-typed
programming languages [Omo93][OL92][KLMM94].
In these schemes, the
contravariance problem is avoided by adding parameters
to the constraint interface. For example, the SortedList example would
look as follows:
interface SortedList[T] where T extends Ordered[T] {
. . .
}
interface Ordered[X] {
boolean lt (X x);
boolean equals (X x);
}
T whose method signatures are compatible
with Ordered[T] will also satisfy the constraint in its where clause form.
However, using parameterized interfaces as constraints does not work
well in a language like Java, which has explicitly declared subtype
relationships. For a type to be usable as a parameter argument to
SortedList_Member, it must declare its relationship to Ordered
and every other appropriate constraining interface. There will be many
interfaces such as Ordered, each with its own combination of
methods. In a large system, there may even be duplicate interfaces used
as constraints. Every class will have to declare a
multitude of interfaces that it satisfies.
Further, the need for a constraint may only
be known later, because new parameterized classes (and constraints) can
be added to the system. Existing types cannot
be used as parameters because they do not declare their satisfaction
of the new constraint. Sather [Omo93]
addresses this problem by allowing
new subtype declarations to be added to the system at any time.
For example, after SortedList_Member is written,
any users who wish to use SortedList_Member[Num]
could add the following additional declaration:
class Num implements Ordered[Num];
This additional language extension seems likely to be
problematic in a dynamically-loaded system like Java, where the
full type hierarchy is not available.
If parameterized interfaces are used to constrain parameters, the subtype hierarchy is apt to become extremely complex as the system grows. The extra subtype relations do not serve any ordinary object-oriented purpose, since the constraint types are unlikely to be used other than as constraints. The number of subtype relations will be roughly proportional to the number of parameterized types and to the total number of types in the system. In most implementations of object-oriented systems, the resulting complex type hierarchy has a significant performance impact.
We might consider removing the requirement for an explicit subtype declaration. In this approach, the parameter matches the interfaces if its method signatures are compatible with the interface. In this case, a constraint interface no longer functions as an real interface, as there is probably no object providing the interface. Essentially, it becomes a clumsy way of bundling where clauses together.
A separate interface to constrain parameters might seem to offer economy of expression in some cases: one interface can be used to constrain several different parameterized definitions, rather than restating the where clauses for each definition. CLU [L+81] has a construct called a typeset that was provided for just this purpose. Yet, our experience with CLU is that typesets are almost never used - primarily because most constraints are very short (just one or two methods). Defining a separate interface just isn't worth the time.