Lecture
Variance is discussed independently of any particular programming language. The examples in the practice section are written in pseudocode and therefore need not compile with any compiler.
In documentation, technical literature and other sources you may have come across various names for the phenomena of variance.
The terms covariance and contravariance were introduced by Sylvester in 1853 for research on the algebraic theory of invariants.
The terms covariance and covariancy are equivalent (at least in programming). Moreover, the terms contravariance and contravariancy are also equivalent. For example, the terms covariance and contravariance are used on Wikipedia and by Troelsen (in translation).
Covariance and contravariance in programming — ways of transferring the inheritance of types onto types derived from them — containers, generic types, delegates and so on. The terms originate from the analogous notions of category theory, the “covariant” and “contravariant functor”.
The terms covariance and contravariance are also found, for instance, on MSDN and in Skeet (in translation).
Variance — the transfer of the inheritance of source types onto types derived from them. By derived types we mean containers, delegates, generics, not types related by an "ancestor–descendant" relationship. The various kinds of variance are covariance, contravariance and invariance.
Covariance (covariance)— the transfer of the inheritance of source types onto types derived from them in direct order.
Contravariance (contravariance)— the transfer of the inheritance of source types onto types derived from them in reverse order.
Invariance — the situation where the inheritance of source types is not transferred onto derived types.
Covariance is the preservation of the inheritance hierarchy of source types in derived types in the same order. Thus, if class Cat inherits from class Animal, then it is natural to expect that the enumeration IEnumerable<Cat> will be a descendant of the enumeration IEnumerable<Animal>. Indeed, a “list of five cats” is a special case of a “list of five animals”. In such a case the type (in this instance the generic interface) IEnumerable<T> is said to be covariant in its type parameter T.
Contravariance is the reversal of the hierarchy of source types into the opposite one in derived types. Thus, if class String inherits from class Object, and the delegate Action<T> is defined as a method taking an object of type T, then Action<Object> inherits from the delegate Action<String>, and not the other way around. Indeed, if “every string is an object”, then “any method operating on arbitrary objects can perform an operation on a string”, but not vice versa. In such a case the type (in this instance the generic delegate) Action<T> is said to be contravariant in its type parameter T.
The absence of inheritance between derived types is called invariance.
Perhaps a more accurate definition of variance is the one proposed by Eric Lippert.
Assignment compatibility, assignment compatibility — the possibility of assigning a value of a more specific type to a compatible variable of a more general type.
Variance — the preservation of assignment compatibility of source types in derived types.
Covariance — the preservation of assignment compatibility of source types in derived types in direct order.
Contravariance — the preservation of assignment compatibility of source types in derived types in reverse order.
Covariance and contravariance — concepts used in mathematics (linear algebra, differential geometry, tensor analysis) and in physics that characterize how tensors (scalars, vectors, operators, bilinear forms, etc.) change under basis transformations in the corresponding spaces or manifolds. Contravariant components are the «ordinary» components that, when the basis of the space changes, transform using the transformation inverse to the basis transformation. Covariant components are those that transform in the same way as the basis.
The relationship between the covariant and contravariant coordinates of a tensor is only possible in spaces where a metric tensor is defined (not to be confused with a metric space).
The terms covariance and contravariance were introduced by Sylvester in 1853 for research on the algebraic theory of invariants.
Contravariance allows the type to be correctly established when creating subtypes (subtyping), that is, it establishes a set of functions that can replace another set of functions in any context. Covariance, in turn, characterizes the specialization of code, that is, the replacement of old code with new code in certain cases. Thus, covariance and contravariance are independent type-safety mechanisms that do not exclude one another, and can and should be applied in object-oriented programming languages.
Covariance is the preservation of the inheritance hierarchy of source types in derived types in the same order. Thus, if class Cat inherits from class Animal, then it is natural to expect that the enumeration IEnumerable<Cat> will be a descendant of the enumeration IEnumerable<Animal>. Indeed, a “list of five cats” is a special case of a “list of five animals”. In such a case the type (in this instance the generic interface) IEnumerable<T> is covariant in its type parameter T.
Contravariance is the reversal of the hierarchy of source types into the opposite one in derived types. Thus, if class String inherits from class Object, and the delegate Action<T> is defined as a method taking an object of type T, then Action<object> inherits from the delegate Action<string>, and not the other way around. Indeed, if «every string is an object», then «any method operating on arbitrary objects can perform an operation on a string», but not vice versa. In such a case the type (in this instance the generic delegate) Action<T> is contravariant in its type parameter T.
The absence of inheritance between derived types is called invariance.
Contravariance allows the type to be correctly established when creating subtypes (subtyping), that is, it establishes a set of functions that can replace another set of functions in any context. Covariance, in turn, characterizes code specialization, that is, the replacement of old code with new code in certain cases. Thus, covariance and contravariance are independent type-safety mechanisms that do not exclude one another, and can and should be applied in object-oriented programming languages .
A good visualization of the concepts of variance is the following figure:
If derived types exhibit covariance, they are said to be covariant with the source type. If derived types exhibit contravariance, they are said to be contravariant with the source type. If derived types exhibit neither, they are said to be invariant.
Let us consider specific examples.
What is the purpose of this?
The whole point of variance lies in using the advantages of inheritance in derived types. It is known that if two types are related by an "ancestor–descendant" relationship, then an object of the descendant can be stored in a variable of the ancestor's type. In practice, this means we can use descendant objects instead of ancestor objects for certain operations. This lets us write more flexible and shorter code for actions supported by different descendants with a common ancestor.
The source hierarchy and derived types
To begin with, let's describe the type hierarchy we'll be working with. At the top of the hierarchy we have Device, whose descendants are Mouse and Keyboard. Mouse, in turn, also has descendants — WiredMouse and WirelessMouse.
Everyone loves containers. They make it easiest to explain what is meant by derived types. If we talk about lists as derived types, then for the type Device the derived type will be
List (a list of devices). Similarly, for the type Keyboard the derived type will be List (a list of keyboards). I think if there were any doubts, there are none now.
Classic covariance
Covariance is also easier to study using the example of containers. To do this, let's single out a part of the hierarchy (a branch) — Keyboard : Device (a keyboard is a device, a keyboard is a special case of a device). Let's again take lists and build a covariant derived branch — List : List (a list of keyboards is a special case of a list of devices). As we can see, the inheritance was carried over in direct order.
Let's look at a code example. There is a function that takes a list of devices, List, and performs some manipulations on them. As you've probably guessed, you can pass a list of keyboards, List, into this function:
void DoSmthWithDevices(List<Device> devices) { /* actions on the list elements */ }
...
List<Keyboard> keyboards = new List<Keyboard> { /* populate the list */ };
DoSmthWithDevices(keyboards);
Classic contravariance
The canonical way to study contravariance is to look at it using delegates. Suppose we have a generic delegate:
delegate void Action<T>(T something);
For the source type Device the derived type will be Action, and for Keyboard — Action. The resulting delegates can represent functions that perform some action on a device or on a mouse respectively. For the branch Keyboard : Device let's build a derived contravariant branch — Action : Action (an action on a device is a special case of an action on a keyboard — that sounds strange, but that's how it is). If you can press a key on a keyboard, that doesn't mean you can press it on a device (the device may have no notion of what a key is). But if you can plug in a device, then you can plug in a keyboard using that same method (function). As we can see, the inheritance was carried over in reverse order.
From what was said above, it logically follows that if a function can do something to a device, then it can do the same to a keyboard. This means we can pass an Action delegate object into a function that takes an Action delegate object. Let's look at this in code:
void DoSmthWithKeyboard(Action<Keyboard> actionWithKeyboard) { /* execute actionWithKeyboard on the keyboard */ }
...
Action<Device> actionWithDevice = device => device.PlugIn();
DoSmthWithKeyboard(actionWithDevice);
A bit of invariance
If derived types are invariant with respect to source types, then for the branch Keyboard : Device neither a covariant branch (List : List) nor a contravariant branch (Action : Action) is formed. This means there is no relationship at all between the derived types. As we can see, inheritance is not carried over.
But what if?
Non-obvious covariance
Delegates of type Action can be covariant. This means that for the branch Keyboard : Device a covariant branch is formed — Action : Action. Thus, into a function that accepts an Action delegate object, an Action delegate object can be passed.
void DoSmthWithDevice(Action<Device> actionWithDevice) { /* execute actionWithDevice on the device */ }
...
Action<Keyboard> actionWithKeyboard = keyboard => ((Device)keyboard).PlugIn();
DoSmthWithDevice(actionWithKeyboard);
Non-obvious contravariance
Containers can be contravariant. This means that for the branch Keyboard : Device a contravariant branch is formed — List : List. Thus, into a function that accepts a List, a List can be passed:
void FillListWithKeyboards(List<Keyboard> keyboards) { /* populate the list of keyboards */ }
...
List<Device> devices = new List<Device>();
FillListWithKeyboards(devices);
The exotic kinds of variance examined above have, at best, only academic value. It's hard to come up with a real-world task that is easier to solve thanks to capabilities of this kind. It's worth remembering that covariance and contravariance can cause runtime errors. Eliminating them requires introducing certain restrictions. Compilers, as a rule, do not introduce such restrictions.
Safety for containers
If a derived type is covariant, then to ensure safety the container must be read only. Otherwise, it remains possible to write an object of the wrong type (Device, Mouse and others) into List by casting to List:
List<Keyboard> devices = new List<Keyboard>(); devices.Add(new Device()); // runtime error
If a derived type is contravariant, then to ensure safety the container must be write only. Otherwise, it remains possible to read from List an object of the wrong type (Keyboard, Mouse and others) by casting to the corresponding list (List, List and others):
List<Device> keyboards = new List<Device>(); keyboards.Add(new Keyboard()); keyboards .PressSpace(); // runtime error
Double standards for delegates
For delegates, it is reasonable to have covariance for the return value and contravariance for input parameters (excluding pass-by-reference). When these conditions are observed, no runtime errors occur.
Debriefing
The examples presented are enough to understand the principles of how variance works. Look up information about its support by the various types of your favorite language in the corresponding specification.
In containers that allow writing objects, covariance is considered undesirable, since it allows bypassing type checking. Indeed, let's consider covariant arrays. Suppose classes Cat and Dog inherit from class Animal (in particular, a variable of type Animal can be assigned a variable of type Cat or Dog). Let's create an array Cat[]. Thanks to type checking, only objects of type Cat and its descendants can be written into this array. Then let's assign a reference to this array to a variable of type Animal[] (array covariance allows this). Now, into this array, already known as Animal[], let's write a variable of type Dog. Thus, into the array Cat[] we have written a Dog, bypassing type checking. That's why containers that allow writing are best made invariant. Also, containers that allow writing can implement two independent interfaces, the covariant Producer<T> and the contravariant Consumer<T>; in that case, the type-checking bypass described above cannot be achieved.
Since type checking can only be violated when writing an element into a container, covariance is safe and even useful for immutable collections and iterators. For example, thanks to this, in C# any method accepting an argument of type IEnumerable<object> can be passed any collection of any type, for instance IEnumerable<string> or even List<string>.
If, on the contrary, in this context the container is used only for writing into it, with no reading, then it can be contravariant. Thus, if there is a hypothetical type WriteOnlyList<T>, inheriting from List<T> and forbidding read operations on it, and a function with a parameter WriteOnlyList<Cat>, into which it writes objects of type Cat, then it is safe to pass it a List<Animal> or a List<object> — it will write nothing into it except objects of the descendant class, and it will not attempt to read other objects.
In languages with first-class functions there exist generic function types and delegate variables. For generic function types, covariance in return types and contravariance in arguments are useful. Thus, if a delegate is defined as “a function that takes a String and returns an Object”, then a function that takes an Object and returns a String can also be assigned to it: if a function can accept any object, it can also accept a string; and from the fact that a function's result is a string, it follows that the function returns an object.
When a subclass overrides a method in a superclass, the compiler must check that the overriding method has the correct type. While some languages require the type to exactly match the type in the superclass (invariance), it is also type-safe to allow the replacing method to have a “better” type. By the usual subtyping rule for function types, this means that the overriding method must return a more specific type (covariance of the return type) and accept a more general argument (contravariance of the parameter type). In UML notation, the possibilities are as follows:
Variant and method overriding: an overview
Subtype of the method's parameter / return type.
Invariance . The signature of the replacing method has not changed.
Covariant return type . The subtype relationship is in the same direction as the relationship between ClassA and ClassB.
Contravariant parameter type . The subtype relationship is the opposite of the relationship between ClassA and ClassB.
Covariant type parameter . Not type-safe. As a concrete example, suppose we are writing a class to model an animal shelter. We assume that Cat is a subclass of Animal, and that we have a base class (using Java syntax)
Now the question arises: if we create a subclass AnimalShelter, what types are we allowed to give out in getAnimalForAdoption and putAnimal?
In a language that allows covariant return types, a derived class can override the getAnimalForAdoption method to return a more specific type:
Among the major object-oriented languages, Java, C++ and C# (starting with version 9.0 ) support covariant return types. Adding covariant return types was one of the first modifications to the C++ language approved by the standards committee, in 1998. Scala and D also support covariant return types.
In exactly the same way, it is type-safe to allow the overriding method to accept a more general argument than the method in the base class:
Only a few object-oriented languages actually allow this (for example, Python when type-checked with mypy). C++, Java and most other languages that support overloading and/or shadowing interpret this as a method with an overloaded or shadowed name.
However, Sather supported both covariance and contravariance. The calling convention for overridden methods was covariant in out parameters and return values, and contravariant in normal parameters (with in mode).
A couple of major languages, Eiffel and Dart , allow the parameters of a replacing method to have a more specific type than the method in the superclass (parameter type covariance). Thus, the following Dart code will type-check with a putAnimal method override in the base class:
class CatShelter extends AnimalShelter {
void putAnimal ( covariant Cat animal ) {
// ...
}
}
This is not type-safe. Upcasting a CatShelter to an AnimalShelter, one could try to put a dog into the cat shelter. This does not conform to CatShelter's parameter constraints and will result in a runtime error. This lack of type safety (known as the “catcall problem” in the Eiffel community, where “cat” or “CAT” stands for changed availability or type) has been a long-standing issue. Over the years, various combinations of global static analysis, local static analysis and new language features have been proposed to fix this problem , and they have been implemented in some Eiffel compilers.
Despite the type-safety problem, Eiffel developers consider covariant parameter types crucial for modeling real-world requirements. A cat shelter illustrates a general phenomenon: it is a kind of shelter for animals, but with additional constraints, and it seems reasonable to use inheritance and constrained parameter types to model this. By proposing this use of inheritance, Eiffel developers reject the Liskov substitution principle, which states that objects of a subclass should always be less constrained than objects of their superclass.
Another example of a major language that allows covariance in method parameters is PHP, with respect to class constructors. In the following example, the __construct() method is accepted even though the method's parameter is covariant with the parent method's parameter. If this method were anything other than __construct(), an error would occur:
Another example where covariant parameters seem useful is so-called binary methods, that is, methods in which the parameter must have the same type as the object on which the method is called. An example is the compareTo method: it checks whether it comes before or after in some ordering, but the way of comparing, say, two rational numbers will differ from the way of comparing two strings. Other common examples of binary methods include equality testing, arithmetic operations, and set operations such as subset and union. a.compareTo(b)ab
In older versions of Java, the comparison method was specified as the Comparable interface:
interface Comparable {
int compareTo ( Object o );
}
The drawback of this is that the method is defined as accepting an argument of type Object. In a typical implementation, this argument will first be downcast (an error is raised if it doesn't match the expected type):
In a language with covariant parameters, the argument of compareTo can be directly given the desired type RationalNumber, hiding the type cast. (Of course, this will still result in a runtime error if compareTo is then called with, for example, a String.)
Other language features can provide the apparent benefits of covariant parameters while preserving Liskov substitutability.
In a language with generic templates (also known as parametric polymorphism) and bounded quantification, the earlier examples can be written in a type-safe way.[10] Instead of defining AnimalShelter, we define a parameterized class. (One drawback of this is that the base class's designer must anticipate which types will need to be specialized in subclasses.) Shelter<T>
Similarly, in recent versions of Java the Comparable interface was parameterized, which allows the downcast to be omitted in a type-safe way:
Another language feature that can help is multiple dispatch. One reason binary methods are awkward to write is that in such calls, selecting the correct implementation really depends on the runtime type of both operands, but in a conventional object-oriented language only the runtime type of the receiver is taken into account. In a language with multiple dispatch in the style of the Common Lisp Object System (CLOS), the comparison method can be written as a generic function in which both arguments are used to select the method. a.compareTo(b)compareToaba
Giuseppe Castagna[11] observed that in a statically typed language with multiple dispatch, a generic function can have some parameters that control dispatch, and some «remaining» parameters that do not. Since the method-selection rule chooses the most specific applicable method, if a method overrides another method, then the overriding method will have more specific types for the controlling parameters. On the other hand, to ensure type safety, the language must still require that the remaining parameters be at least as general. Using the earlier terminology, the types used to select the method at runtime are covariant, while the types not used to select the method at runtime are contravariant. Traditional single-dispatch languages such as Java also obey this rule: only one argument is used to select the method (the receiver object, this), and indeed, the type of this is more specialized inside overriding methods than in the superclass.
Castagna suggests that examples where covariant parameter types excel (binary methods in particular) should be handled using multiple dispatch, which is naturally covariant. However, most programming languages do not support multiple dispatch.
The following table shows the method-overriding rules for the languages discussed above.
| Parameter type | Return type | |
|---|---|---|
| C++ (since 1998), Java (since J2SE 5.0), D | Invariant | Covariant |
| C# | Invariant | Covariant (starting with C# 9 - previously invariant) |
| Scala, Sather | Contravariant | Covariant |
| Eiffel | Covariant | Covariant |
In containers that allow writing objects, covariance is considered undesirable, since it allows bypassing type checking. Indeed, let's consider covariant arrays. Suppose classes Cat and Dog inherit from class Animal (in particular, a variable of type Animal can be assigned a variable of type Cat or Dog). Let's create an array Cat[]. Thanks to type checking, only objects of type Cat and its descendants can be written into this array. Then let's assign a reference to this array to a variable of type Animal[] (array covariance allows this). Now, into this array, already known as Animal[], let's write a variable of type Dog. Thus, into the array Cat[] we have written a Dog, bypassing type checking. That's why containers that allow writing are best made invariant. Also, containers that allow writing can implement two independent interfaces, the covariant Producer<T> and the contravariant Consumer<T>, in which case the type-checking bypass described above cannot be achieved.
Since type checking can only be violated when writing an element into a container, covariance is safe and even useful for immutable collections and iterators. For example, thanks to this, in C# any method accepting an argument of type IEnumerable<Object>, can be passed any collection of any type, for instance IEnumerable<String> or even List<String>.
If, on the contrary, in this context the container is used only for writing into it, with no reading, then it can be contravariant. Thus, if there is a hypothetical type WriteOnlyList<T>, inheriting from List<T> and forbidding read operations on it, and a function with a parameter WriteOnlyList<Cat>, into which it writes objects of type Cat, then it is safe to pass it a List<Animal> or a List<Object> — it will write nothing into it except objects of the descendant class, and it will not attempt to read other objects.
In languages with first-class functions there exist generic function types and delegate variables. For generic function types, covariance in return types and contravariance in arguments are useful. Thus, if a delegate is defined as «a function that takes a String and returns an Object», then a function that takes an Object and returns a String can also be assigned to it: if a function can accept any object, it can also accept a string; and from the fact that a function's result is a string, it follows that the function returns an object.
C++, starting with the 1998 standard, supports covariant return types in overridden virtual functions:
class X {}; class A { public: virtual X* f() { return new X; } }; class Y : public X {}; class B : public A { public: virtual Y* f() { return new Y; } // covariance allows a refined return type to be specified in the overriding method };
Pointers in C++ are covariant: for example, a pointer to a derived class can be assigned to a pointer of the base class.
C++ templates, generally speaking, are invariant; the inheritance relationships of the parameter classes are not carried over to the templates. For example, a covariant container vector<T> would allow type checking to be violated. However, using parameterized copy constructors and assignment operators, one can create a smart pointer that is covariant in its type parameter .
Covariance of method return types has been implemented in Java since J2SE 5.0. There is no covariance in method parameters: to override a virtual method, its parameter types must match the definition in the parent class, otherwise, instead of an override, a new overloaded method with those parameters will be defined.
Arrays in Java have been covariant since the very first version, when the language did not yet have generic types. (If this were not the case, then to use, for example, a library method that accepts an array of objects Object[], in order to work with an array of strings String[], it would first have to be copied into a new Object[] array.) Since, as mentioned above, writing an element into such an array can bypass type checking, the JVM has additional runtime checking that throws an exception when an incorrect element is written.
Generic types in Java are invariant, since instead of creating a universal method that works with Objects, it can be parameterized, turning it into a generic method while preserving type checking.
At the same time, in Java one can implement a kind of co- and contravariance of generic types by using the wildcard character and bounding specifiers: List will be covariant in the substituted type, while List will be contravariant.
In C#, starting from its very first version, arrays are covariant. This was done for compatibility with the Java language . When attempting to write an element of the wrong type into an array, a runtime exception is thrown.
Generic classes and interfaces, introduced in C# 2.0, became, just as in Java, invariant in their type parameter.
With the introduction of generic delegates (parameterized by argument types and return types), the language allowed automatic conversion of ordinary methods to generic delegates, with covariance in return types and contravariance in argument types. Because of this, code of the following form became possible in C# 2.0:
void ProcessString(String s) { /* ... */} void ProcessAnyObject(Object o) { /* ... */ } String GetString() { /* ... */ } Object GetAnyObject() { /* ... */ } //... Action<string> process = ProcessAnyObject; process(myString); // this is legal Func<object> getter = GetString; Object obj = getter(); // this is legal
however the code Action<object>process = ProcessString; is incorrect and produces a compilation error, otherwise this delegate could later be called as process(5), passing an Int32 into ProcessString.
In C# 2.0 and 3.0, this mechanism only allowed assigning simple methods to generic delegates and could not perform automatic conversion of one generic delegate into another. In other words, the code
Func<string> f1 = GetString; Func<object> f2 = f1;
did not compile in these versions of the language. Thus, generic delegates in C# 2.0 and 3.0 were still invariant.
In C# 4.0 this restriction was lifted, and starting with this version the code f2 = f1 in the example above began to work.
In addition, in 4.0 it became possible to explicitly specify the variance of the parameters of generic interfaces and delegates. For this, the keywords out and in are used, respectively. Since the actual use of the type parameter within a generic type is known only to its author, and moreover it can change during development, this solution provides the greatest flexibility without compromising the reliability of type checking.
Some library interfaces and delegates were redefined in C# 4.0 using these capabilities. For example, the interface IEnumerable<T> is now defined as IEnumerable<out T>, the interface IComparable<T> — as IComparable<in T>, the delegate Action<T> — as Action<in T>, and so on.
Comments