Combining parametric polymorphism with matching

  In this section we illustrate the extra flexibility obtained by supporting a form of parametric polymorphism that is similar to that provided in CLU's parameterized clusters and Ada's generic packages. Polymorphism is very important for clean programming of a variety of problems, especially those involving data structures called ``container classes''. Container classes are those classes representing collections of objects, usually of the same or related types.

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 ${\it { List}}$, 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 ${\it {List(Int)}}$ represents the type of a list of integers, while ${\it {List(Window)}}$ represents the type of a list of windows.

  

Figure 14: List type function.

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, ${\it {Comparable}}$, 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, ${\it {BinarySearchTree}}$, is applied?

  

Figure 15: The type ${\it {Comparable}}$.

We might expect that any type that is a subtype of ${\it {Comparable}}$would be acceptable. However, because ${\it {Comparable}}$contains method types that include contravariant occurrences of MyType (i.e., binary methods), no non-trivial subtypes of ${\it {Comparable}}$ exist.

Interestingly, matching allows us to express exactly the types that we are interested in. If ${\it {T {\rm \, <\!\!\!\char93 \, }Comparable}}$, then ${\it {T}}$ must have ${\it {equal}}$, ${\it {greaterThan}}$, and ${\it {lessThan}}$ 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 ${\it {BinSearchTreeType}}$ and ${\it { BinTreeNodeType}}$ in Figure 16 provide examples of the use of match-bounded polymorphism in the definition of a function from types to types. The type ${\it {Top}}$ which serves as the upper bound for the type parameter in ${\it { BinTreeNodeType}}$ is a built-in type which is greater than every other type in the matching ordering. The corresponding class provides methods like ${\it {ShallowClone}}$ and ${\it {equal}}$ 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 ${\it {T}}$ in ${\it {BinSearchTree}}$ is illustrated by the expression ${\it {elt.equal(current.getValue())}}$. Because ${\it {T {\rm \, <\!\!\!\char93 \, }Comparable}}$ and ${\it {elt}}$ has type ${\it {T}}$, ${\it {elt}}$ is guaranteed to have a method ${\it {equal}}$ with the necessary typing.

  

Figure 16: Binary search tree type functions.

  

Figure 17: BinSearchTree classes.

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 ${\it {Comparable}}$) and by the type of node it is composed of, a type that is required to match ${\it {NodeType}}$ (the type of objects generated by the ${\it {Node}}$ 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 ${\it {NodeType}}$ 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 ${\it {DoubleNodeType}}$ 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 ${\it {BinSearchTreeType}}$ as

$${\tt TypeFunction\ BinSearchTreeType(T {\rm \ <: \ }CompFcn(T))}$$

Notice that the bounded variable, ${\it {T}}$, occurs in the upper bound, ${\it {CompFcn(T)}}$.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.