COVARIANCE AND CONTRAVARIANCE (COMPUTER SCIENCE)

A 'covariant type operator' in a type system preserves the ordering ≤ of types. A 'contravariant operator' reverses ≤. If neither of these apply, the operator is ''invariant''. These terms come from category theory.
Typical examples:

★ The array type is usually covariant on the base type: as ''String'' ≤ ''Object'' then ''ArrayOf(String)'' ≤ ''ArrayOf(Object)''. Note that this is only correct (i.e. type safe) if the array is immutable; if insert and remove operators are permitted, then the insert operator is covariant (e.g. one can insert a ''String'' into an ''ArrayOf(Object)'') and the remove operator is contravariant (e.g. one can remove an ''Object'' from an ''ArrayOf(String)''). Since the mutators have conflicting variance, arrays should be ''invariant'' on the base type.

★ A function with a parameter of type ''T'' (defined as ''fun f'' (''T x'') : ''Integer'') can be replaced by a function ''g'' (defined as ''fun g'' (''S x'') : ''Integer'') if ''T'' ≤ ''S''. In other words, if ''g'' ''cares less'' about the type of its parameter, then it can replace ''f'' anywhere, since both return an ''Integer''. So, in a language accepting function arguments, ''g'' ≤ ''f'' and the type of the parameter to ''f'' is said to be contravariant.

★ In the general case, the type of the result is covariant.
In object-oriented programming, substitution is also implicitly invoked by ''overriding'' methods in subclasses: the new method can be used where the old method was invoked in the original code. Programming languages vary widely on their allowed forms of overriding, and on the variance of overridden methods' types.

Contents

Origin of the terms

The controversy in object oriented languages

Overview of covariance/contravariance in some programming languages

C++

C#

Eiffel

Java

REALbasic

Scala

Sather

See also

External links

Origin of the terms

The origin of these terms is in category theory. Here we see the types in the type system as forming a category ''C'', with arrows representing the subtype relationship. The subtype relationship supposedly reflects the ''substitution principle'': that any expression of type ''t'' can be substituted by an expression of type ''s'' if ''s'' ≤ ''t''.
Defining a function that accepts type ''p'' and returns type ''r'' creates a new type ''p'' → ''r'' in the type system which the new method name is associated with. This ''function definition'' operator is actually a functor ''F'' : ''C'' × ''C'' → ''C'' that creates the type as just said. From the substitution principle above, this functor must be contravariant in the first argument and covariant in the second (see Luca Cardelli).

The controversy in object oriented languages

The problem arises as different object oriented languages have different strategies to select the actual code used in a particular contexts and the first parameter is the object itself (which is ''not'' contravariant).
However, it was shown by Castagna (1995) that all depends on the method fetching algorithm: types used to select the method are contravariant; types not used to select the method are covariant. It's immaterial if the fetching occurs at run-time or at compile time.
These terms are also used in the context of modern programming languages that offer other ''functors'' to create new types with type variables, as in generic programming or parametric polymorphism, and exception handling where method definitions are enriched with annotations that indicate possible failures.

Overview of covariance/contravariance in some programming languages

How types are built from basic types, thus defining the sub-type relationship, and how new methods are defined and override or not existing methods depends on the language and sometimes not necessarily follow the substitution principle above adding runtime checking instead.
Here a simple comparison of how overriding methods behave in some programming languages.

C++

C++ supports covariant return types in overridden virtual functions. Adding the covariant return type was the first modification of the C++ language approved by the standards committee in 1998. See What's New in Standard C++? Chuck Allison
With generic programming, C++ allows for what amounts to covariance in argument as well as return type.
For example, the argument and return types of member functions of the <T> class vary with T. The push_back method takes a const T&, so one pushes an int onto a vector<int> but a onto a vector<string>. This is done at compile time (staticly) and, strictly speaking, is parametric polymorphism.

C#

Arrays of reference-types are covariant: string[] is a subtype of object[], although with some caveats:

// a is a single-element array of System.String

string[] a = new string[1];

// b is an array of System.Object

object[] b = a;

// Assign an integer to b. This would be possible if b really were

// an array of objects, but since it really is an array of strings,

// we will get an ArrayTypeMismatchException with the following message:

// "Attempted to store an element of the incorrect type into the array".

b[0] = 1;

'Note': In the above case you can 'read' from b without problem. It is only when trying to 'write' to the array that you must know its real type.
Arrays of value-types are invariant: int[] is not a subtype of double[].
In the C# programming language, support for both return-type covariance and parameter contravariance for delegates was added in version 2.0 of the language. Neither covariance nor contravariance are supported for method overriding.

Eiffel

Eiffel allows covariant return and parameter types in overriding methods. This is possible because Eiffel does not require subclasses to be substitutable for superclasses — that is, subclasses are not necessarily subtypes.
However, this can lead to surprises if subclasses with such covariant parameter types are operated upon as though they were a more general class (polymorphism), leading to the possibility of compiler errors.

Java

Arrays of objects are covariant: [] is a subtype of [], although with some caveats:

// a is a single-element array of String

String[] a = new String[1];

// b is an array of Object

Object[] b = a;

// Assign an Integer to b. This would be possible if b really were

// an array of Object, but since it really is an array of String,

// we will get a java.lang.ArrayStoreException.

b[0] = new Integer (1);

'Note': In the above case you can 'read' from b without problem. It is only when trying to 'write' to the array that you must know its real type.
Arrays of primitive types are invariant: int[] is not a subtype of long[], although int is in some sense a subtype of long.
Exception covariance has been supported since the introduction of the language. Return type covariance is implemented in the Java programming language version J2SE 5.0. Parameter types have to be exactly the same (invariant) for method overriding, otherwise the method is overloaded with a parallel definition instead.

REALbasic

REALbasic added support for return type covariance in version 5.5. As with Java, the parameter types of the overriding method must be the same.

Scala

Scala supports both covariance and contravariance.

Sather

Sather supports both covariance and contravariance.

See also

★ Polymorphism (computer science)

★ Inheritance (computer science)

External links

★ Covariance and contravariance: conflict without a cause by G. Castagna

★ Contra Vs Co Variance (note this article is not updated about C++)

★ Closures for the Java 7 Programming Language (v0.5)