A good example of a container class is a list of elements. The code for a particular list implementation is essentially the same, no matter what type of element is held in the list. Similarly the interfaces vary only in the type of the element held in the list. As a result we can represent the type of lists with , a function from types to types. (See Figure 14.) We can create type expressions representing lists of various types by simply applying the type function to the intended type of the elements. Thus represents the type of a list of integers, while represents the type of a list of windows.
Some of these container classes, however, require the types of elements contained in the data structure to support certain operations. For instance, a binary search tree will only work with elements whose types support comparisons between elements. As another example, a data structure representing a collection of objects on a computer screen may require each element to have a bounding rectangle. How can we express this dependency in order to assure that type functions only get applied to the appropriate types?
Let us look at the case of binary search trees in order to get more insight into the problem. In order to insert and find an element in a binary search tree we must be able to compare that element with other elements of the type. In Figure 15 we present an object type, , which supports the necessary comparison operations. Any type of element that can be stored in a binary search tree must support at least these operations. How can we use this to restrict the types to which the type function, , is applied?
We might expect that any type that is a subtype of would be acceptable. However, because contains method types that include contravariant occurrences of MyType (i.e., binary methods), no non-trivial subtypes of exist.
Interestingly, matching allows us to express exactly the types that we are interested in. If , then must have , , and methods, each with function types that expect an argument of the same type as the receiver, and return Booleans. This is exactly what we want. This mechanism of restricting type parameters using matching is called match-bounded polymorphism or bounded matching .
The definitions of the type functions and in Figure 16 provide examples of the use of match-bounded polymorphism in the definition of a function from types to types. The type which serves as the upper bound for the type parameter in is a built-in type which is greater than every other type in the matching ordering. The corresponding class provides methods like and which are implicitly inherited by every other class of the language.
Figure 17 shows part of the definitions of a node class and binary search tree class, both of which are parameterized by the types of elements they contain. (The node class is also parameterized by an initial value for the node value. This can be treated as syntactic sugar for a function returning a class.) The need for the constraint on the type parameter in is illustrated by the expression . Because and has type , is guaranteed to have a method with the necessary typing.
A more complicated example can be constructed of an ordered linked list, which is parameterized both by the type of value it contains (which is required to match ) and by the type of node it is composed of, a type that is required to match (the type of objects generated by the class from the previous section). For instance, the user can instantiate the ordered list with an object type supporting integers with the usual order and with type in order to obtain a singly-linked list of integers. Alternatively, one can instantiate it with an object type representing strings and with the type in order to obtain a doubly-linked list of strings. (See [BSvG95] for details of the example.)
Bounded polymorphism (using subtyping rather than matching) was introduced in [CW85]. That paper also included a very extensive discussion of types and subtypes in object-oriented languages. The failure of bounded polymorphism using subtyping to capture the constraints needed in examples like our binary search tree example above was first pointed out in [CCH+89]. In that paper, the authors invented a generalization of bounded polymorphism, called F-bounded quantification, which provided the correct constraints on polymorphism. F-bounded quantification is a generalization of bounded quantification using subtyping in which the bounded variable is allowed to appear in the bound. Using this in languages supporting recursive types in place of MyType provides the same functionality as match-bounded polymorphism.
For example we can define
TypeFunction CompFcn(T) = ObjectType function equal(T): Boolean; function greaterThan(T): Boolean; function lessThan(T): Boolean; end ObjectType;Then, using F-bounded quantification, we can rewrite the bound on as
Notice that the bounded variable, , occurs in the upper bound, .Unfolding rules of recursive types can then be used to show that the expected (recursive) object types satisfy the constraint.
The notion of matching given here and match-bounded polymorphism were introduced in [Bru94] as a simpler way of expressing the constraints of F-bounded quantification in order to specify the semantics of typed object-oriented languages. That paper also pointed out the usefulness of matching in type checking classes and subclasses. As pointed out in [AC95], a somewhat better encoding for matching can be obtained through the use of higher-order subtyping [PS95].
A concept similar to match-bounded polymorphism seems to have been invented independently by several language designers. The term matching was introduced in [BH91], though with a definition relating types to type functions, rather than types to types. Modulo this change, the definition is very similar to that of F-bounded quantification. This construct is used in the distributed language Emerald [BHJL86,BHJ+87,Hut87]. The language School ([RIR93]) also constrains polymorphism with a mechanism similar to F-bounded quantification.
Interestingly, the type restrictions obtained by match-bounded polymorphism are equivalent to those obtained by mechanisms for restricting type parameters in imperative languages supporting polymorphism, like CLU and Ada. In Ada, for instance, one would write:
generic T with function equal(T,T): Boolean; function lessThan(T,T): Boolean; function greaterThan(T,T): Boolean; package BinSearchTree ... end BinSearchTree;
While the functions are written as functions of two parameters here (rather than the single parameter for the object-oriented style), the restrictions on the admissible types are equivalent. This provides further evidence that matching is a very natural notion in object-oriented languages. In fact the object-oriented language Theta [DGLM95,DGLM94] uses a similar notation to express restrictions on type parameters that are equivalent to match-bounded polymorphism.