Alternate Constraint Mechanisms



next up previous
Next: Virtual Machine Extensions Up: Language Extensions Previous: Optional Methods

Alternate Constraint Mechanisms

 

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].

Procedures

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.

Interfaces

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);
    }
The problem with this approach is that it cannot express constraints (such as 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.

Parameterized Interfaces

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);
    }
With this interface, any type 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.



next up previous
Next: Virtual Machine Extensions Up: Language Extensions Previous: Optional Methods

Andrew C. Myers, Joseph A. Bank, Barbara Liskov
Copyright © 1996 Association for Computing Machinery