Covariance and Contravariance

Some further implications of substitutability

In the last installment, I introduced a concept called result covariance. Just to remind you, result covariance means, loosely, that if operator Op is defined to have a result of declared type T, then the actual result of an invocation of Op can be of any subtype of type T. I used the following example (among others) to illustrate the point:

OPERATOR MOVE ( E ELLIPSE, S SQUARE ) RETURNS ELLIPSE 
VERSION ES_MOVE ;
... ;
END OPERATOR ;
OPERATOR MOVE ( C CIRCLE, S SQUARE ) RETURNS CIRCLE 
VERSION CS_MOVE ;
... ;
END OPERATOR ;

Operator MOVE "moves" its first argument so that it's centered on the center of its second argument (more precisely, it returns a result just like the first argument except that it's centered on the center of the second argument). If the first argument is of type CIRCLE, the version called CS_MOVE is invoked (and the result is of type CIRCLE); if the first argument is only of type ELLIPSE, the version called ES_MOVE is invoked (and the result is only of type ELLIPSE). Thus, the type of the result "covaries" with the type of the first argument.

Let me also remind you that:

• Although the covariance has been made explicit in this example (that is, I've explicitly defined two separate versions of the MOVE operator, one for circles and one for "just ellipses"), it does not need to be made explicit in this manner, in general. The COPY example discussed last month illustrates this point.
• Furthermore, the EORC example, also discussed last month, shows that "covariance" can occur even without any variation in argument type at all.
• The explicit specialization of MOVE to circles (version CS_MOVE) might be unnecessary in practice (I made this claim last month but didn't justify it -- and I'm still not in a position to do so, either; that justification will have to wait for a future installment).

In the present installment, I want to introduce a related concept called argument contravariance, and then revisit -- and reinterpret -- both concepts.

Continuing the Example

Here again is the coding example involving MOVE, repeated from last month's column:

VAR S SQUARE ;
VAR E ELLIPSE ;
VAR F ELLIPSE ;
VAR C CIRCLE ;
C := CIRCLE (...) ;	/* initialize C to some circle	*/
E := C ;	/* MST(E) is now CIRCLE	*/
F := MOVE ( E, S ) ;	/* MST(F) is now CIRCLE also	*/

The final assignment here has the effect it does because of the run-time binding process, of course. That is, the system discovers at run time that the current most specific type of E is CIRCLE and therefore invokes the version of MOVE that applies to circles (namely, version CS_MOVE). That invocation returns a result of most specific type CIRCLE, and that result is then assigned to F.

Observe now that the second argument to that MOVE invocation is of type SQUARE. It follows that -- read this sentence carefully! -- the declared type of the second parameter to version CS_MOVE of the MOVE operator could be any supertype of SQUARE, and the type checking (both compile-time and run-time) would still succeed. For example, we could replace the explicit specialization CS_MOVE by the following version (version CR_MOVE) instead:

OPERATOR MOVE ( C CIRCLE, R RECTANGLE ) RETURNS CIRCLE 
VERSION CR_MOVE ;
... ;
END OPERATOR ;

Thus, the notion of substitutability has the further implication that if operator Op is defined to have a parameter P1 of declared type T1, and Op is invoked with a corresponding argument A1 of some subtype of T1, then the other arguments A2, ..., An to that invocation of Op can be of any supertypes of the declared types T2, ..., Tn of the corresponding parameters P2, ..., Pn of the "P1 is of type T1" version of Op. (Any supertype that makes sense, that is. In the MOVE example, the second argument must be of a type for which the concept of having a center makes sense.)

This property -- that if the declared type of one parameter to operator Op (in some version of Op) is further specialized, then the declared type of another parameter (in that same version of Op) can be further generalized -- is sometimes called argument contravariance, on the grounds (presumably, and very loosely!) that the most specific type of one argument "contravaries" with that of another. Note carefully that, unlike "result covariance," "argument contravariance" must be made explicit (by defining explicit specializations of the operator in question), because it refers to the declared types of parameters to such specializations.

What's Really Going On Here?

Now, you might be finding these two concepts, "result covariance" and (especially) "argument contravariance," a little hard to get your head around, and if so then I don't think I'd blame you. Let me see if I can do something to make matters a little clearer.

First of all, I have to say I think both terms are extremely ill chosen (why is the computing community so bad at choosing apt terminology?). Let's consider "result covariance" first. As I said last month, result covariance is presumably so called on the grounds that the most specific type of the result "covaries" with the most specific type of the argument. But if this supposition is correct, then note that:

• There seems to be a tacit assumption that there's just one argument! In our MOVE example, by contrast, there are two arguments; the type of the result covaries with the type of the first but not with that of the second.
• In any case, the type of the result can "covary" even if the argument type remains fixed (remember the EORC example from the last installment), or even if there are no explicit arguments at all (imagine an operator that returns a circle on weekdays but just an ellipse at weekends).

Our inheritance model therefore makes no mention of the term "result " at all. Instead, we simply point out that it's a logical consequence of The Principle of Value Substitutability -- which is to say, a logical consequence of the very concept of inheritance in the first place -- that, in general, an invocation of a given operator might return a result whose most specific type is some proper subtype of the applicable declared type. That is, if you have inheritance, you must have "result covariance," otherwise you don't have inheritance!

What about "argument contravariance"? In my opinion, this term is even less apt than "result covariance," for at least the following two reasons:

• In the first place, it's really parameters that "contravary," not arguments (in the MOVE example, it's the first parameter whose type is "varied down" from ELLIPSE to CIRCLE and the second parameter whose type is "varied up" from SQUARE to RECTANGLE).
• Second, there seems to be a tacit assumption that there are just two arguments! (Or parameters, rather). MOVE does have two parameters, which "contravary" -- but what if it had three or more?

In any case, I think there's a much better way to look at this whole business of "argument contravariance." In fact, I think it would be much clearer to talk, not in terms of "argument contravariance" (as such) at all, but rather in terms of restrictions on argument type combinations, as I now explain.

Consider the MOVE example once again. Presumably what the person who defined the MOVE operator will do is tell the user that MOVE is an operator that takes two arguments, of types ELLIPSE and RECTANGLE respectively, and returns a result of type ELLIPSE (after all, remember that to the user there's just one MOVE operator). Then, because of substitutability, the user knows that the arguments to any given MOVE invocation can be of any subtypes of ELLIPSE and RECTANGLE, respectively (and the result can be of any subtype of ELLIPSE -- though it must be of the same most specific type as the first argument, because of the semantics of the operation).

So far, so good. However, there's a fly in the ointment: Certain combinations of most specific argument types are illegal (and the user must be aware of this fact). To be precise, the combination ELLIPSE-SQUARE (which gives a result of most specific type ELLIPSE) is legal, and so is the combination CIRCLE-RECTANGLE (which gives a result of most specific type CIRCLE), but the combination ELLIPSE-RECTANGLE is not.

So the obvious question is: Why on earth did the MOVE definer impose such a strange restriction in the first place? Isn't it a violation of substitutability? (After all, ELLIPSE is a subtype of ELLIPSE and RECTANGLE is a subtype of RECTANGLE, so we should surely be able to invoke the operator and pass it an ellipse per se and a rectangle per se.) In fact, the restriction might be regarded as a violation of orthogonality too, because there's an unpleasant -- and unjustified -- interdependence between the two arguments to any given invocation.

For such reasons, we reject the "argument contravariance" concept in our inheritance model. In its place, we insist simply that operators must be defined in such a way as to allow the most specific type of any given argument to be the same as the declared type of the corresponding parameter. Indeed, it seems perverse to us to do otherwise. And if this prescription is adhered to, then the notion of "argument contravariance" can simply be ignored.

Concluding Remarks

What I'm generally trying to do in this series is explain the basic concepts of type inheritance, using our own inheritance model as a vehicle for those explanations. At the same time, of course, I'm trying to describe our own model specifically, in the hope that I can thereby draw attention to what we believe could be a useful and fruitful candidate for adoption by the community at large. In this installment, however, I've been talking about two concepts I don't really believe in (as it were), concepts that don't show up -- at least, not directly -- in our own inheritance model. The trouble is, they're certainly concepts that show up in the literature, and I think it's better to face up to them and try to explain them (or explain them away, perhaps), rather than just sweep them under the rug -- especially since they're not all that easy to understand anyway! By way of illustration of this latter point, here are the relevant definitions from one book on object databases (Object-Oriented Database Systems: Concepts and Architectures, Addison-Wesley, 1993):

"A type t is a subtype of a type s if:

1. The properties of s are a subset of those of t .
2. For each method ms of s , there is a corresponding method mt of t , such that
1. ms and mt have the same name;
2. ms and mt have the same number of arguments;
3. The ith argument type of ms is a subtype of the ith argument type of mt (rule of contravariance in arguments);
4. Both ms and mt have a result, or neither of the two has a result;
5. If there is a result, then the type of the result of mt is a subtype of the type of the result of ms (rule of covariance in results)."

I don't know about you, but to me the real meaning of these definitions doesn't exactly leap off the page. In fact, I have some problems with them. First of all, they seem to be circular (the concept of some type being a subtype of another relies on the concept of some type being a subtype of another). Second, they seem to be saying that t is a subtype of s if substitutability applies, whereas I would have said the opposite (viz., that substitutability applies if t is a subtype of s ).

One final point (a point, in fact, that I've touched on a couple of times already): It seems to me that many of the concepts I've been discussing at such length in this series so far -- specifically, inclusion polymorphism, value substitutability, result covariance, argument contravariance, explicit specialization (operator versions), code reuse, and run-time binding -- aren't really components of the model, as such, at all (despite the fact that you do need to understand them in order to appreciate what inheritance and subtyping are really all about). The only relevant concept that's truly part of the model is this: "To say that T' is a subtype of T means, by definition, that operators that apply to values of type T apply to values of type T' also" -- and the rest follows.

C. J. Date is an independent author, lecturer, researcher, and consultant, specializing in relational database systems (a field he helped pioneer). His most recent books are Foundation for Future Database Systems: The Third Manifesto (2nd edition, co-authored with Hugh Darwen); The Database Relational Model: A Retrospective Review and Analysis; WHAT Not HOW: The Business Rules Approach to Application Development; and An Introduction to Database Systems (7th edition), all of them published by Addison-Wesley in 2000.