Rambles around computer science

Diverting trains of thought, wasting precious time

Tue, 22 Feb 2011

Explaining covariance and contravariance by data flow

A few years ago when I was pressed by my students to give them a good explanation of Java's wildcard types, like Stack<? super Circle> or List<? extends Ellipse>, I came up with a simple code example concerning the direction of data flow. The idea seems both to be more general than I first thought, and to apply to more wide-ranging problems with subtyping relations than the case of Java wildcards. Since I've never seen it written down anywhere else, here it is.

In a nutshell, the idea is that direction of data flow is key. (If that was obvious to you already, you can probably stop reading now!) In object-oriented programming, all interactions across object interfaces can be seen as sending messages. In a procedural language like Java, each interaction will in general involve two messages---the call and the return value. In a parametrically polymorphic type system like modern Java's, one of the key roles of the type system is to check (conservatively, as always) that any invocation will not try to send the wrong kind of data, in either direction.

Suppose I have some code that works by pulling objects out of a queue. To work correctly, these objects have to be of class Circle or some subclass thereof. So, we need a queue whose designated element type is Circle or some subtype of Circle, i.e. ? extends Circle. We say that the type of the queue here is covariant in its element type, meaning the subtyping relationships go “the same way”.

Meanwhile, suppose the same code, after it processes the Circle, wants to push the object onto another queue for some other code to deal with. We want to ensure that this queue can accept the objects we give it, which might be Circles or instances of any subclass. So we need a guarantee that it can take any such objects. So, a queue of UnitCircle, say, would not be good enough---if we gave it a plain Circle this would be a type error. So our output queue has to have element type Circle or any supertype thereof, that is, element type ? super Circle. Here the type of the queue is contravariant in the element type, meaning the subtyping relationships go opposite ways.

I won't claim that this explanation covers all sane use-cases of wildcard types. On the other hand, if you know of any that aren't in some way similar, I'd like to hear about them. The idea is certainly more general than just code which processes items in queues, or just code that pushes data from one data structure to another.

This is also a neat way of considering a classic problem in typed object-oriented programming, called the “Circle--Ellipse problem”. The question is simple. We wish to define two mutable data types: Circle for representing circles and Ellipse for representing ellipses. Which way, if any, should the subtyping relation be between Circle and Ellipse?

The trick is to remember that a mutable object is not just a value: it is a container for a value that can be retrieved and replaced. In other words, we can put data in and get data out. The presence of these two distinct directions is the source of the problem. Put simply: when used in the “out” direction, for reading the parameters of the circle, Circle is a subtype of Ellipse (every valuation of a circle also represents an ellipse); but in the “in” direction, for updating the parameters stored in the object, Ellipse is a subtype of Circle, since we can give an ellipse any set of parameters that we might give a circle, whereas the converse is not true--circles cannot be updated with the parameters of ellipses having unequal minor and major radii.

An even simpler case which illustrates the in/out distinction is the usual subtyping rule for functions, which I will illustrate formal-style just because I can:

       s1 <= t1        t2 <= s2
    ------------------------------
          t1->t2  <=  s1->s2 

In English: a function expression's type t1->t2 is a subtype of another function expression's type s1->s2 if t2 (denoting the set of result values) is a subtype of its counterpart s2, and the type t1 (denoting the set of argument values) is a supertype of its counterpart s1. Intuitively (or Liskovly), this holds because to be a subtype, any term typed t1->t2 must be substitutable into any context where a term of type s1->s2 could be used, meaning the full range of argument values denoted by s1 must be acceptable as the call's content (and, optionally, other values may also be permitted), and the full range of return values denoted by t2 must be acceptable to the call context (and, optionally, (and possibly other argument values could be allowed also). I said “if” but turning the rule upside down is also valid, so “iff” would have been correct (but a stronger statement than the inference rule itself).

I'd like to add that this is the first time I've written down an inference rule in any of my writing.

None of this says anything about how Circle and Ellipse should be implemented. Abstractly, they share a lot, so in any sane implementation we would want to share whatever code we could. In many object-oriented programming languages, inheritance is provided as a code-sharing mechanism. Which way should the inheritance relationship go? It doesn't matter, as long we treat this as separate from the subtyping relationship.

Here is the real problem. Some languages, particularly Java, make this difficult for us by assuming that these two relationships should be the same. Most people who know a little about object-oriented programming will know that inheritance and subtyping are distinct concepts, although are often conflated. Historically, C++ can probably be blamed for this conflation, in that it popularised the overloading of a single mechanism (class derivation) for both. However, in C++'s defence, the fact that class inheritance is private by default is this way precisely because of this distinction. Sadly, most texts which teach the language use public inheritance nearly everywhere without ever explaining why this can be a bad idea. Java made public inheritance the default, so is far more culpable in my opinion.

Many people take this as an opportunity to lambast implementation inheritance. I won't do this. Inheritance is a useful language feature for capturing commonality of implementation. It's great that I can write a class C which shares a lot of implementation with a pre-existing class B, simply by describing what is different. It's very handy that there is no need to write forwarding functions to the code in B that can be used directly in C. It makes for readable code and discourages copy-and-paste code cloning.

Subtyping is more subtle, because it is a semantic property. It relates to the meaning of code, not the raw code itself. Things like direction of data flow don't turn up in the more syntactic matter of code re-use (inheritance's territory) but, as we saw, very much do in the semantic world of types.

I said I've never seen this explanation written down by anyone else. but actually, a bit of Googling reveals another blogger has covered similar ground. You can decide whose explanation you like best!

[/teaching] permanent link contact


Powered by blosxom

validate this page