Solving covariance problems with match-bounded polymorphism

We prefer systems which catch type errors at compile time, rather than postponing their discovery until link time or run time. Cook, in [Coo89], presented several suggestions on how to fix the problems with Eiffel. An important part of these suggestions is the use of bounded quantification to replace the uses of covariance in instance variable and parameter types, in particular, those occurrences arising from uses of Eiffel's ${\it {like\ x}}$ construct.

In section 5, we provided a solution to the problem of covariant changes to parameter and instance variable types for the cases when the types involved can be represented using MyType. In those cases the type represented by MyType changes automatically in subclasses. Our assumptions on the meaning of MyType in type checking methods ensure that this implicit covariant change to parameter types causes no type problems. In the rest of this section we show how to use match-bounded polymorphism to replace the apparent need for covariant changes when types other than MyType are required to change.

We revisit the ${\it {Circle}}$ / ${\it {ColorCircle}}$ example discussed in section 4, and presented in Figure 9, in order to see how to use match-bounded polymorphism to model this in a type-safe way. Recall that ${\it {Circle}}$ has a ${\it {getCenter}}$ method that returns a point, while we wished the same method to return a color point in the subclass, ${\it {ColorCircle}}$. Subtyping allowed us to change the return type as desired, but we later ran into difficulty because we were not allowed to change the instance variable, ${\it {center}}$, from type ${\it {PointType}}$ to ${\it {ColorPointType}}$ in the subclass.

Using match-bounded polymorphism, we can work around this by adding a type parameter that is required to match ${\it {PointType}}$. This type parameter represents the type of the center of the circle. See the class ${\it { PCircle}}$ in Figure 18. Now any subclass of ${\it { PCircle}}$ can instantiate the type variable by any type that matches ${\it {PointType}}$, solving our problem, though at the cost of requiring the programmer to plan ahead for subsequent changes in subclasses.

  

Figure 18: Polymorphic Circle classes.

A new color circle can be created by evaluating ${\it {new\ PColorCircle(ColorPointType,cpt)}}$ where ${\it {cpt}}$ is a color point that is to be the location of the center of the circle. Thus the addition of match-bounded polymorphism has allowed us to get around the difficulties caused by the restrictions on changing instance variable types. Because the bodies of the methods of ${\it { PCircle}}$ are type checked under the assumption that ${\it {CenterType {\rm \, <\!\!\!\char93 \, } PointType}}$, they are guaranteed to work when the subclass is instantiated with ${\it {ColorPointType}}$.

Our second example, due to Shang [Sha91], is presented in Figure 19. It is typical of those given to illustrate the need for covariant subtyping on parameter types in subclasses. In this example, an ${\it {Animal}}$ can eat any kind of food, while an ${\it {Herbivore}}$ eats only plants.

  

Figure 19: Animal and herbivore classes

Because the parameter of ${\it {eat}}$ changes in a covariant way, this is an illegal subclass according to the typing rules with which we have been working. In fact, it is easy to code up an example using these definitions that would type check correctly according to the Eiffel rules, yet be unsafe, if ${\it {Herbivore}}$were allowed to be a subclass of ${\it {Animal}}$.Nevertheless this seems like an obvious change in parameters for the subclass because we clearly wish to place more restricts on the parameter in the subclass. This covariant change in parameters is characteristic of many desired subclass relationships in object-oriented programming languages.

To solve this problem we need to analyze more carefully the modeling which is reflected in this class. While for each item of type ${\it {FoodType}}$ there may be a kind of animal that can eat that food, virtually all kinds of animals have some dietary restrictions. Cows eat grass and hay, but do not eat meat. Humans eat a variety of plants and animals, but do not typically eat either grass or hay. Thus while it is proper to conclude that any item of ${\it {FoodType}}$ is potentially edible by some animal, it would be incorrect to conclude that any, let alone all, food items will be edible by all animals. As a result, the ${\it {Animal}}$ class definition, particularly with the functionality assigned to ${\it {eat}}$, does not really accurately reflect the situation to be modeled. A more realistic model of the class would allow us to change the parameter type for the ${\it {eat}}$ method for each particular kind of animal.

The polymorphic ${\it {PAnimal}}$ class in Figure 20 is parameterized over the type of food eaten by the animal. Match-bounded polymorphism has been used to impose a bound of ${\it {FoodType}}$ on the type parameter, where ${\it {FoodType}}$ might include methods returning the weight and number of calories that would be extracted if the item is consumed. Notice that in the (parameterized) subclass, ${\it {PHerbivore}}$,we have replaced the upper bound of ${\it {FoodType}}$ by ${\it {PlantType}}$, where ${\it {PlantType}}$ is an object type that must match ${\it {FoodType}}$. The requirement that ${\it {PlantType}}$ match ${\it {FoodType}}$ comes from the fact that ${\it {PHerbivore(MyFoodType)}}$ is defined to be a subclass of ${\it {PAnimal(MyFoodType)}}$. But ${\it {PAnimal(MyFoodType)}}$ is only well-defined if ${\it {MyFoodType {\rm \, <\!\!\!\char93 \, }FoodType}}$. If ${\it {PlantType {\rm \, <\!\!\!\char93 \, }FoodType}}$ and ${\it {MyFoodType {\rm \, <\!\!\!\char93 \, } PlantType}}$ then transitivity implies that ${\it {MyFoodType {\rm \, <\!\!\!\char93 \, }FoodType}}$.

  

Figure 20: Polymorphic animal and herbivore classes

As an example, suppose there is an object type ${\it {Vegetable {\rm \, <\!\!\!\char93 \, } PlantType}}$. Then we can create the class ${\it {PHerbivore(Vegetable)}}$which generates objects that can eat only vegetables. Note that ${\it {PHerbivore(Vegetable)}}$ is a legal subclass of ${\it {PAnimal(Vegetable)}}$,since the corresponding methods have exactly the same types, though the types of the objects they generate are not in the subtype relation. On the other hand, ${\it {PHerbivore(PlantType)}}$ is not a subclass of ${\it {PAnimal(FoodType)}}$.

The method ${\it {eat}}$ of the parameterized ${\it {PAnimal}}$ class will be type checked under the assumption that ${\it {MyFoodType {\rm \, <\!\!\!\char93 \, }FoodType}}$, since that is all that is known about the parameter type from its declaration. Notice that this is exactly the same kind of assumption as we make about MyType when type checking methods in classes. What we have done here with parameterized classes is to hand-code the same kind of flexibility that we get for free with self and MyType. While this takes more work on the programmer's part, we get the effect of covariance while retaining type safety - clearly something of value!