Covariance and contravariance (computer science)

Many programming language type systems support subtyping. For instance, if Cat is subtype of Animal, then an expression of type Cat can be used whenever an expression of type Animal could. Variance refers to how subtyping between more complex types (list of Cats versus list of Animals, function returning Cat versus function returning Animal, ...) relates to subtyping between their components. Depending on the variance of the type constructor, the subtyping relation may be either preserved, reversed, or ignored. For example, in C# :

• IEnumerable<Cat> is a subtype of IEnumerable<Animal>, because the IEnumerable<T> type constructor is covariant.

• Action<Animal> is a subtype of Action<Cat>, because the Action<T> type constructor is contravariant. (An Action represents a method that expects a single argument and does not return a value). Note how the subtyping is "reversed".

• Neither IList<Cat> or IList<Animal> is a subtype of the other, because the IList<T> type constructor is invariant.

A programming language designer will consider variance when devising typing rules for e.g. arrays, inheritance, and generic datatypes. By making type constructors covariant or contravariant instead of invariant, more programs will be accepted as well-typed. On the other hand, programmers often find contravariance unintuitive, and accurately tracking variance to avoid runtime type errors can lead to complex typing rules. In order to keep the type system simple and allow useful programs, a language may treat a type constructor as invariant even if it would be safe to consider it variant, or treat it as covariant even when that can violate type safety.

Formal definition

Within the type system of a programming language, a typing rule or a type constructor is:

• covariant if it preserves the ordering, ≤, of types, which orders types from more specific to more generic;
• contravariant if it reverses this ordering;
• invariant if neither of these applies.

This distinction is important in considering argument and return types of methods in class hierarchies. In object-oriented languages such as Python, if class B is a subtype of class A, then all member functions of B must return the same or narrower set of types as A; the return type is said to be covariant. On the other hand, if the member functions of B take the same or broader set of arguments compared with the member functions of A, the argument type is said to be contravariant. The problem for instances of B is how to be perfectly substitutable for instances of A. The only way to guarantee type safety and substitutability is to be equally or more liberal than A on inputs, and to be equally or more strict than A on outputs. Note that not all programming languages guarantee both properties in every context, and that some are unnecessarily strict; they are said not to support covariance or contravariance in a given context; the behavior of some programming languages is discussed below.

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.

Arrays

First consider the array type constructor: from the type Animal we can make the type Animal[] ("array of animals"). Should we treat this as

• Covariant: a Cat[] is a Animal[]
• Contravariant: a Animal[] is a Cat[]
• or neither (invariant)?

If we wish to avoid type errors, and the array supports both reading and writing elements, then only the third choice is safe. Clearly, not every Animal[] can be treated as if it were a Cat[], since a client reading from the array will expect a Cat, but an Animal[] may contain e.g. a Dog. So the contravariant rule is not safe.

Conversely, a Cat[] can not be treated as a Animal[]. It should always be possible to put a Dog into a Animal[]. With covariant arrays this can not be guaranteed to be safe, since the backing store might actually be an array of cats. So the covariant rule is also not safe—the array constructor should be invariant. Note that this is only a issue for mutable arrays; the covariant rule is safe for immutable (read-only) arrays.

This illustrates a general phenomenon. Read-only data types (sources) can be covariant; write-only data types (sinks) can be contravariant. Mutable data types which act as both sources and sinks should be invariant.

Covariant arrays in Java and C#

Early versions of Java and C# did not include generics (a.k.a. parametric polymorphism). In such a setting, making arrays invariant rules out useful polymorphic programs.

For example, consider writing a function to shuffle an array, or a function that tests two arrays for equality using the Object.equals method on the elements. The implementation does not depend on the exact type of element stored in the array, so it should be possible to write a single function that works on all types of arrays. It is easy to implement functions of type

    boolean equalArrays (Object[] a1, Object[] a2);
    void shuffleArray(Object[] a);

However, if array types were treated as invariant, it would only be possible to call these functions on an array of exactly the type Object[]. One could not, for example, shuffle an array of strings.

Therefore, both Java and C# treat array types covariantly. For instance, in C# string[] is a subtype of object[], and in Java String[] is a subtype of Object[].

As discussed above, covariant arrays leads to problem with writes into the array. Java and C# deals with this by marking each array object with a type when it is created. Each time a value is stored into an array, the compiler inserts a check that the run-time type of the value is equal to the run-time type of the array. If there is a mismatch, an ArrayStoreException (or ArrayTypeMismatchException in C#) is thrown:

    // 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] = 1;

In the above example you can read from b safely. It is only trying to write to the array that can lead to trouble.

One drawback of this approach is that it leaves the possibility of a run-time error which a stricter type system could have caught at compile-time. Also, it hurts performance because each write into an array requires an additional runtime check.

With the addition of generics, Java and C# now offer type safe ways to write this kind of polymorphic functions. The array comparison and shuffling functions can be given the parameterized types

    <T> boolean equalArrays (T[] a1, T[] a2);
    <T> void shuffleArray(T[] a);

Alternatively, to enforce that a C# method accesses a collection in a read-only way, one can use the interface IEnumerable<object> instead of passing it an array object[].

Function types

Languages with first-class functions have function types like "a function expecting a Cat and returning an Animal" (written Cat -> Animal in OCaml syntax or Func<Cat,Animal> in C# syntax).

Those languages also need to specify when one function type is a subtype of another—that is, when it is safe to use a function of one type in a context that expects a function of a different type. A moment's thought shows that it is safe to substitute a function f instead of a function g if f accepts a more general type of arguments and returns a more specific type than g. For example, a function of type Cat->Cat can safely be used wherever a Cat->Animal was expected, and likewise a function of type Animal->Animal can be used wherever a Cat->Animal was expected. The general rule is

S₁ → S₂ ≤ T₁ → T₂ if T₁ ≤ S₁ and S₂ ≤ T₂.

In other words, the → type constructor is contravariant in the input type and covariant in the output type. This rule was first stated formally by Luca Cardelli.

When dealing with functions that take functions as arguments, this rule can be applied several times. For example, by applying the rule twice, we see that (A'→B)→B ≤ (A→B)→B if A'≤A. In other words, the type (A→B)→B is covariant in the A position. For complicated types it can be confusing to mentally trace why a given type specialization is or isn't type-safe, but it is easy to calculate which positions are co- and contravariant: a position is covariant if it is on the left side of an even number of arrows.

Origin of the terms

These terms come from the notion of covariant and contravariant functors in category theory. Consider the category $C$ whose objects are types and whose morphisms represent the subtype relationship ≤. (This is a an example of how any partially ordered set can be considered as a category). Then for example the function type constructor takes two types p and r and creates a new type p → r; so it takes objects in $C^2$ to objects in $C$. By the subtyping rule for function types this operation reverses ≤ for the first argument and preserves it for the second, so it is a contravariant functor in the first argument and a covariant functor in the second.

Need for covariant argument types?

In many strictly typed languages (with the notable exception of Eiffel, see below), subclassing must allow for substitution. That is, a child class instance can always stand in for a parent class instance; this is known as the Liskov Substitution Principle. This places restrictions on the sorts of relationships that subclassing can represent. In particular, it means that arguments to member functions can only be contravariant and return types can only be covariant, as explained in previous section.

This creates problems in some situations, where argument types should be covariant to model real-life requirements. Suppose you have a class representing a person. A person can see the doctor, so this class might have a method virtual void Person::see(Doctor d). Now suppose you want to make a subclass of the Person class, Child. That is, a Child is a Person. One might then like to make a subclass of Doctor, Pediatrician. If children only visit pediatricians, we would like to enforce that in the type system. However, a naive implementation fails: because a Child is a Person, Child::see(d) must take any Doctor, not just a Pediatrician.

We could try moving the see() method to the Doctor class hierarchy, but we would have the same problem: If a Doctor could see a Person and a Child is a Person, then there is still no way to enforce that a Child must see a Pediatrician and that a Person who is not a Child cannot see a Pediatrician and must see another Doctor.

In this case, the visitor pattern could be used to enforce this relationship. Another way to solve the problems, in C++, is using generic programming (see below).

Avoiding the need for covariant argument types

The need for covariant argument types arises from strategies in object oriented languages for context-sensitive selection of the code used in method calls. This does not include the first parameter of a method call, which is the object itself, which is not contravariant.

Giuseppe Castagna showed that types used for runtime selection of the method are covariant, while types not used for runtime selection of the method are contravariant. In Castagna's work, examples which would suggest the usage of covariance for parameter types are treated with the usage of multiple dispatch, i.e. overriding where the right method is selected also based on the type of some arguments; applying the rule, covariance is allowed for those argument types. However, this solution cannot be applied to most programming languages, since they do not support multiple dispatch.

Note that for (static) overload resolution, the opposite rule applies: types used for compile-time method selection (i.e. parameter types) are contravariant; types not used to select the method are covariant.

These terms are also used in the context of modern programming languages that offer other functors to create new types with type variables, e.g., 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

Both the subtype and method overriding concepts are defined differently between programming languages. They do not necessarily follow the substitution principle above, sometimes adding runtime checking instead. What follows is a simple comparison of how overriding methods behave in some common 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 Allison, Chuck. "What's New in Standard C++?". 

C#

In C# it is possible to store an object which is an instance of an equal or smaller type in that storage location.

object str = "string";

Ever since C# 1.0, arrays where the element type is a reference type are covariant.

object[] strings = new string[1];

Method group to delegate conversions are covariant in return types, and contravariant in argument types.

Generic delegate types are always invariant in C# 3.0.

A variant interface which inherits from another variant interface must do so in a manner which does not introduce problems in the type system.

C# 4.0 allows declaration of covariance and contravariance on parameterized interface and delegate types.

D

The D Programming Language supports covariance for method overriding:

interface IFactory {
    Object Create();
}

class X { }

class XFactory : IFactory {
    // This method implements IFactory.Create
    X Create() {
        return new X();
    }
}

Java

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.

Generics were introduced in Java 5.0 to allow type-safe generic programming. Unlike arrays, generic classes are neither covariant nor contravariant. For example, neither List<String> nor List<Object> is a subtype of the other:

// a is a single-element List of String
List<String> a = new ArrayList<String>();
a.add("foo");
 
// b is a List of Object
List<Object> b = a; // This is a compile-time error

However, generic type parameters can contain wildcards (a shortcut for an extra type parameter that is only used once). Example: Given a requirement for a method which operates on Lists, of any object, then the only operations that can be performed on the object are those for which the type relationships can be guaranteed to be safe.

// a is a single-element List of String
List<String> a = new ArrayList<String>();
a.add("foo");
 
// b is a List of anything
List<?> b = a;
 
// retrieve the first element
Object c = b.get(0);
// This is legal, because we can guarantee
// that the return type "?" is a subtype of Object
 
// Add an Integer to b.
b.add(new Integer (1)); 
// This is a compile-time error; 
// we cannot guarantee that Integer is
// a subtype of the parameter type "?"

Wildcards can also be bound, e.g. ? extends Foo or ? super Foo for upper and lower bounds, respectively. This allows to refine permitted performance. Example: given a List<? extends Foo>, then an element can be retrieved and safely assigned to a Foo type (covariance). Given a List<? super Foo>, then a Foo object can be safely added as an element (contravariance).

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 presuming they were a more general class (polymorphism), leading to the possibility of compiler errors.

Sather

Sather supports both covariance and contravariance. Calling convention for overridden methods are covariant with out arguments and return values, and contravariant with normal arguments (with the mode in).

Scala

The Scala programming language supports declaration-site variance annotations.

Scala originally supported use-site declarations of covariance and contravariance, but it turned out to be difficult to achieve consistency of usage-site type annotations, so that type errors were not uncommon. Because declaration-site annotations provide excellent guidance on which methods should be generalized with lower bounds, Scala later adopted them. Though usage-site variance annotations allow a single class to have covariant as well as non-variant fragments, Scala's mixin composition makes it relatively easy to explicitly factor classes into covariant and non-variant fragments.

See also

• Polymorphism (computer science)
• Inheritance (computer science)

External links

• Fabulous Adventures in Coding: An article series about implementation concerns surrounding co/contravariance in C#
• Contra Vs Co Variance (note this article is not updated about C++)
• Closures for the Java 7 Programming Language (v0.5)
• Concise explanation of Covariance and Contravariance in C#