Contra Vs Co Variance

To summarize the concept
When inheriting from a class and over-riding one of its methods, how should you constrain the types accepted as arguments and returned as results according to the method being over-ridden?


Say you have a class Foo, which has a method bar(). Method bar() takes an argument of type middle_type, and returns a value of type middle_type.

Now you make a subclass of Foo called SubFoo, and you override bar(). What types can the new bar() take? What types can it return?

Look at return types first: we want to be able to substitute SubFoo where existing code expects Foo, so it needs to return things of type middle_type, or of some subtype (e.g. sub_type). This should be pretty obvious.

As for what types our new bar() can take: One answer is: bar() can take only things of type middle_type. You can't declare it to take sub_type, and you can't declare it to take super_type. This is called invariance.

Another answer: bar() can only be declared to take things that are a subtype of middle_type - so middle_type is OK, and sub_type is OK, but super_type is out. This is called covariance.

Finally, the third answer: bar() can only be declared to take things that are a supertype of middle_type - so any of middle_type, and super_type may be passed to bar(), but sub-type is not allowed. This is called contravariance.

Covariance seems to jibe with our notion that subclasses are more specialized, less general than their superclasses. So you might have a Collection class which takes and returns Objects; you could subclass it to make a FooCollection class which takes and returns Foos (where Foo is a subclass of Object).

Contravariance sounds kind of counterintuitive at first, but it's actually just analogous to the famous advice about implementing protocols: "Be liberal in what you accept, and conservative in what you send." So just as you have to return a subtype of the original bar()'s return type, you have to accept any supertype of whatever the original bar() accepts.

If your type system enforces contravariance of parameters, then it can tell at compile time whether your code is typesafe (cf. SatherLanguage, ObjectiveCaml). If it enforces covariance (Cf. cf. EiffelLanguage, CeePlusPlus), it can't really do that, but it can make some good guesses (cf. EiffelLanguage) - though Eiffel are known to crash when it guesses wrong.


 Covariance and contravariance : conflict without a cause
 Castagna, Giuseppe 
 ACM Transactions on Programming Languages and Systems
 Vol.17, No. 3 (May 1995), pp. 431-447 

From the Abstract: (http://citeseer.ist.psu.edu/castagna94covariance.html) (Full text is on http://www.cs.trinity.edu/~mlewis/CSCI3294-F01/Papers/p431-castagna.pdf.)

In type-theoretic research on object-oriented programming, the issue of "covariance versus contravariance" is a topic of continuing debate. In this short note we argue that covariance and contravariance appropriately characterize two distinct and independent mechanisms. The so-called contravariance rule correctly captures the subtyping relation (that relation which establishes which sets of functions can replace another given set in every context). A covariant relation, instead, characterizes the specialization of code (i.e., the definition of new code which replaces old definitions in some particular cases). Therefore, covariance and contravariance are not opposing views, but distinct concepts that each have their place in object-oriented systems. Both can (and should) be integrated in a type-safe manner in object-oriented languages.

We also show that the independence of the two mechanisms is not characteristic of a particular model but is valid in general, since covariant specialization is present in record-based models, although it is hidden by a deficiency of all existing calculi that realize this model. As an aside, we show that the lambda-calculus can be taken as the basic calculus for both an overloading-based and a record-based model. Using this approach, one not only obtains a more uniform vision of object-oriented type theories, but in the case of the record-based approach, one also gains multiple dispatching, a feature that existing record-based models do not capture.

The resulting type system is similar to that of CecilLanguage.

This has some parallel with the example of bounded wildcards for Java generics, from Joshua Bloch's 2006 JavaOne presentation:

 public interface Shop<T> {
	T buy();
	void sell(T item);
	void sell(Collection<? extends T> lot);
	void buy(int numItems, Collection<? super T> myStuff);
 }

// You can buy a bunch of models from the train shop modelTrainShop.buy(5, myModels);

// You can sell your train set to the model shop modelShop.sell(myTrains);

Basic rule:

See http://www.icsi.berkeley.edu/~sather/Documentation/EclecticTutorial/node5.html.


Contravariance and Covariance are also used to describe Tensors (such as in MetricTensor) see
CoVariance ContraVariance ContraVsCoVariance CovariantReturnTypes NoCovariantReturnTypes WhatIsCovariance


CategoryComparisons CategoryTypeTheory

EditText of this page (last edited May 4, 2007) or FindPage with title or text search