Type variance · Lablypedia

If the type Cat is a subtype of Animal, then an expression of type Cat should be substitutable wherever an expression of type Animal is used. Depending on the variance of the type constructor, the subtyping relation of the simple types may be either preserved, reversed, or ignored for the respective complex types. In many programming languages, for example, "list of Cat" will be a subtype of "list of Animal", because the list type constructor is covariant. This means that the subtyping relation of the simple types is preserved for the complex types. On the other hand, "function from Animal to String" is a subtype of "function from Cat to String" because the function type constructor is contravariant in the parameter type. Here, the subtyping relation of the simple types is reversed for the complex types.

A programming language designer will consider variance when devising typing rules for language features such as 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 though that could violate type safety.

Etymology

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 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 parameter and preserves it for the second, so it is a contravariant functor in the first parameter and a covariant functor in the second.

5 more chapters are free with a Lably account.

Formal definition

Suppose A and B are types, and I<U> denotes application of a type constructor I with type argument U. Within the type system of a programming language, a typing rule for a type constructor I is:

covariant if it preserves the ordering of types (≤), which orders types from more specific to more generic: If A ≤ B, then I<A> ≤ I<B>;
contravariant if it reverses this ordering: If A ≤ B, then I<B> ≤ I<A>;
bivariant if both of these apply (i.e., if A ≤ B, then I<A> ≡ I<B>);
variant if covariant, contravariant or bivariant;
invariant or nonvariant if not variant.

The article considers how this applies to some common type constructors.

C# examples

For example, in C#, if Cat is a subtype of Animal, then:

IEnumerable<Cat> is a subtype of IEnumerable<Animal>. The subtyping is preserved because IEnumerable<T> is covariant on T.
Action<Animal> is a subtype of Action<Cat>. The subtyping is reversed because Action<T> is contravariant on T.
Neither IList<Cat> nor IList<Animal> is a subtype of the other, because IList<T> is invariant on T.

The variance of a C# generic interface is declared by placing the out (covariant) or in (contravariant) attribute on (zero or more of) its type parameters. The above interfaces are declared as IEnumerable<out T>, Action<in T>, and IList<T>. Types with more than one type parameter may specify different variances on each type parameter. For example, the delegate type Func<in T, out TResult> represents a function with a contravariant input parameter of type T and a covariant return value of type TResult. The compiler checks that all types are defined and used consistently with their annotations, and otherwise signals a compilation error.

The typing rules for interface variance ensure type safety. For example, an Action<T> represents a first-class function expecting an argument of type T, and a function that can handle any type of animal can always be used instead of one that can only handle cats.

Arrays

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. To illustrate this general phenomenon, consider the array type. For the type Animal we can make the type Animal[] , which is an "array of animals". For the purposes of this example, this array supports both reading and writing elements.

We have the option to treat this as either:

covariant: a Cat[] is an Animal[] ;
contravariant: an Animal[] is a Cat[] ;
invariant: an Animal[] is not a Cat[] and a Cat[] is not an Animal[] .

If we wish to avoid type errors, 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[] cannot be treated as an Animal[] . It should always be possible to put a Dog into an Animal[] . With covariant arrays this cannot 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 an issue for mutable arrays; the covariant rule is safe for immutable (read-only) arrays. Likewise, the contravariant rule would be safe for write-only arrays.

Covariant arrays in Java and C#

Early versions of Java and C# did not include generics, also termed 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:

<span id="mwAWs"></span><span class="kt" id="mwAWw">boolean</span><span class="w" id="mwAW0"> </span><span class="nf" id="mwAW4">equalArrays</span><span class="p" id="mwAW8">(</span><span class="n" id="mwAXA">Object</span><span class="o" id="mwAXE">[]</span><span class="w" id="mwAXI"> </span><span class="n" id="mwAXM">a1</span><span class="p" id="mwAXQ">,</span><span class="w" id="mwAXU"> </span><span class="n" id="mwAXY">Object</span><span class="o" id="mwAXc">[]</span><span class="w" id="mwAXg"> </span><span class="n" id="mwAXk">a2</span><span class="p" id="mwAXo">);</span> <span class="kt" id="mwAXs">void</span><span class="w" id="mwAXw"> </span><span class="nf" id="mwAX0">shuffleArray</span><span class="p" id="mwAX4">(</span><span class="n" id="mwAX8">Object</span><span class="o" id="mwAYA">[]</span><span class="w" id="mwAYE"> </span><span class="n" id="mwAYI">a</span><span class="p" id="mwAYM">);</span>

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 Java String[] is a subtype of Object[] , and in C# string[] is a subtype of object[].

As discussed above, covariant arrays lead to problems with writes into the array. Java and C# deal with this by marking each array object with a type when it is created. Each time a value is stored into an array, the execution environment will 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 (Java) or ArrayTypeMismatchException (C#) is thrown:

<span id="mwAa0"></span><span class="c1" id="mwAa4">// a is a single-element array of String</span> <span class="n" id="mwAa8">String</span><span class="o" id="mwAbA">[]</span><span class="w" id="mwAbE"> </span><span class="n" id="mwAbI">a</span><span class="w" id="mwAbM"> </span><span class="o" id="mwAbQ">=</span><span class="w" id="mwAbU"> </span><span class="k" id="mwAbY">new</span><span class="w" id="mwAbc"> </span><span class="n" id="mwAbg">String</span><span class="o" id="mwAbk">[</span><span class="mi" id="mwAbo">1</span><span class="o" id="mwAbs">]</span><span class="p" id="mwAbw">;</span> <span class="c1" id="mwAb0">// b is an array of Object</span> <span class="n" id="mwAb4">Object</span><span class="o" id="mwAb8">[]</span><span class="w" id="mwAcA"> </span><span class="n" id="mwAcE">b</span><span class="w" id="mwAcI"> </span><span class="o" id="mwAcM">=</span><span class="w" id="mwAcQ"> </span><span class="n" id="mwAcU">a</span><span class="p" id="mwAcY">;</span> <span class="c1" id="mwAcc">// Assign an Integer (int) to b. This would be possible if b were actually</span> <span class="c1" id="mwAcg">// an array of Object, but since it really is an array of String,</span> <span class="c1" id="mwAck">// we will get a java.lang.ArrayStoreException at runtime.</span> <span class="n" id="mwAco">b</span><span class="o" id="mwAcs">[</span><span class="mi" id="mwAcw">0</span><span class="o" id="mwAc0">]</span><span class="w" id="mwAc4"> </span><span class="o" id="mwAc8">=</span><span class="w" id="mwAdA"> </span><span class="mi" id="mwAdE">1</span><span class="p" id="mwAdI">;</span>

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

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

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

<span id="mwAd8"></span><span class="o" id="mwAeA"><</span><span class="n" id="mwAeE">T</span><span class="o" id="mwAeI">></span><span class="w" id="mwAeM"> </span><span class="kt" id="mwAeQ">boolean</span><span class="w" id="mwAeU"> </span><span class="nf" id="mwAeY">equalArrays</span><span class="p" id="mwAec">(</span><span class="n" id="mwAeg">T</span><span class="o" id="mwAek">[]</span><span class="w" id="mwAeo"> </span><span class="n" id="mwAes">a1</span><span class="p" id="mwAew">,</span><span class="w" id="mwAe0"> </span><span class="n" id="mwAe4">T</span><span class="o" id="mwAe8">[]</span><span class="w" id="mwAfA"> </span><span class="n" id="mwAfE">a2</span><span class="p" id="mwAfI">);</span> <span class="o" id="mwAfM"><</span><span class="n" id="mwAfQ">T</span><span class="o" id="mwAfU">></span><span class="w" id="mwAfY"> </span><span class="kt" id="mwAfc">void</span><span class="w" id="mwAfg"> </span><span class="nf" id="mwAfk">shuffleArray</span><span class="p" id="mwAfo">(</span><span class="n" id="mwAfs">T</span><span class="o" id="mwAfw">[]</span><span class="w" id="mwAf0"> </span><span class="n" id="mwAf4">a</span><span class="p" id="mwAf8">);</span>

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. It is safe to substitute a function f for a function g if f accepts a more general type of argument and returns a more specific type than g. For example, functions of type animal -> cat, cat -> cat, and animal -> animal can be used wherever a cat -> animal was expected. (One can compare this to the robustness principle of communication: "be liberal in what you accept and conservative in what you produce.") The general rule is:

(P_{1} \to R_{1}) \leq (P_{2} \to R_{2})

P_{1} \geq P_{2}

and

R_{1} \leq R_{2}

Using inference rule notation the same rule can be written as:

\frac{P_{1} \geq P_{2} R_{1} \leq R_{2}}{(P_{1} \to R_{1}) \leq (P_{2} \to R_{2})}

In other words, the → type constructor is contravariant in the parameter (input) type and covariant in the return (output) type. This rule was first stated formally by John C. Reynolds, and further popularized in a paper 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 $((P_{1} \to R) \to R) \leq ((P_{2} \to R) \to R)$ if $P_{1} \leq P_{2}$ . In other words, the type $((A \to B) \to C)$ is covariant in the position of $A$ . 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 applying to it.

Inheritance in object-oriented languages

In an object-oriented programming (OOP) language, when a subclass overrides a method in a superclass, the compiler must check that the overriding method has the right type. While some languages require that the type exactly matches the type in the superclass (invariance), it is also type safe to allow the overriding method to have a "better" type. By the usual subtyping rule for function types, this means that the overriding method should return a more specific type (return type covariance) and accept a more general argument (parameter type contravariance). In Unified Modeling Language (UML) notation, the possibilities are as follows (where Class B is the subclass that extends Class A which is the superclass):

For 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)

<span id="mwApA"></span><span class="kd" id="mwApE">class</span> <span class="nc" id="mwApI">AnimalShelter</span><span class="w" id="mwApM"> </span><span class="p" id="mwApQ">{</span> <span class="w" id="mwApU"> </span><span class="n" id="mwApY">Animal</span><span class="w" id="mwApc"> </span><span class="nf" id="mwApg">getAnimalForAdoption</span><span class="p" id="mwApk">()</span><span class="w" id="mwApo"> </span><span class="p" id="mwAps">{</span> <span class="w" id="mwApw"> </span><span class="c1" id="mwAp0">// ...</span> <span class="w" id="mwAp4"> </span><span class="p" id="mwAp8">}</span> <span class="w" id="mwAqA"> </span> <span class="w" id="mwAqE"> </span><span class="kt" id="mwAqI">void</span><span class="w" id="mwAqM"> </span><span class="nf" id="mwAqQ">putAnimal</span><span class="p" id="mwAqU">(</span><span class="n" id="mwAqY">Animal</span><span class="w" id="mwAqc"> </span><span class="n" id="mwAqg">animal</span><span class="p" id="mwAqk">)</span><span class="w" id="mwAqo"> </span><span class="p" id="mwAqs">{</span> <span class="w" id="mwAqw"> </span><span class="c1" id="mwAq0">//...</span> <span class="w" id="mwAq4"> </span><span class="p" id="mwAq8">}</span> <span class="p" id="mwArA">}</span>

Now the question is: if we subclass AnimalShelter , what types are we allowed to give to getAnimalForAdoption and putAnimal ?

Covariant method return type

In a language which allows covariant return types, a derived class can override the getAnimalForAdoption method to return a more specific type:

<span id="mwAsg"></span><span class="kd" id="mwAsk">class</span> <span class="nc" id="mwAso">CatShelter</span><span class="w" id="mwAss"> </span><span class="kd" id="mwAsw">extends</span><span class="w" id="mwAs0"> </span><span class="n" id="mwAs4">AnimalShelter</span><span class="w" id="mwAs8"> </span><span class="p" id="mwAtA">{</span> <span class="w" id="mwAtE"> </span><span class="n" id="mwAtI">Cat</span><span class="w" id="mwAtM"> </span><span class="nf" id="mwAtQ">getAnimalForAdoption</span><span class="p" id="mwAtU">()</span><span class="w" id="mwAtY"> </span><span class="p" id="mwAtc">{</span> <span class="w" id="mwAtg"> </span><span class="k" id="mwAtk">return</span><span class="w" id="mwAto"> </span><span class="k" id="mwAts">new</span><span class="w" id="mwAtw"> </span><span class="n" id="mwAt0">Cat</span><span class="p" id="mwAt4">();</span> <span class="w" id="mwAt8"> </span><span class="p" id="mwAuA">}</span> <span class="p" id="mwAuE">}</span>

Among mainstream OOP languages, Java, C++ and C# (as of version 9.0 ) support covariant return types. Adding the covariant return type was one of the first modifications of the C++ language approved by the standards committee in 1998. Scala and D also support covariant return types.

Contravariant method parameter type

Similarly, it is type safe to allow an overriding method to accept a more general argument than the method in the base class:

<span id="mwAvk"></span><span class="kd" id="mwAvo">class</span> <span class="nc" id="mwAvs">CatShelter</span><span class="w" id="mwAvw"> </span><span class="kd" id="mwAv0">extends</span><span class="w" id="mwAv4"> </span><span class="n" id="mwAv8">AnimalShelter</span><span class="w" id="mwAwA"> </span><span class="p" id="mwAwE">{</span> <span class="w" id="mwAwI"> </span><span class="kt" id="mwAwM">void</span><span class="w" id="mwAwQ"> </span><span class="nf" id="mwAwU">putAnimal</span><span class="p" id="mwAwY">(</span><span class="n" id="mwAwc">Object</span><span class="w" id="mwAwg"> </span><span class="n" id="mwAwk">animal</span><span class="p" id="mwAwo">)</span><span class="w" id="mwAws"> </span><span class="p" id="mwAww">{</span> <span class="w" id="mwAw0"> </span><span class="c1" id="mwAw4">// ...</span> <span class="w" id="mwAw8"> </span><span class="p" id="mwAxA">}</span> <span class="p" id="mwAxE">}</span>

Only a few object-oriented languages actually allow this (for example, Python when typechecked with mypy). C++, Java and most other languages that support overloading and/or shadowing would interpret this as a method with an overloaded or shadowed name.

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

Covariant method parameter type

A couple of mainstream languages, Eiffel and Dart allow the parameters of an overriding method to have a more specific type than the method in the superclass (parameter type covariance). Thus, the following Dart code would type check, with putAnimal overriding the method in the base class:

<span id="mwAy4"></span><span class="kd" id="mwAy8">class</span><span class="w" id="mwAzA"> </span><span class="nc" id="mwAzE">CatShelter</span><span class="w" id="mwAzI"> </span><span class="kd" id="mwAzM">extends</span><span class="w" id="mwAzQ"> </span><span class="n" id="mwAzU">AnimalShelter</span><span class="w" id="mwAzY"> </span><span class="p" id="mwAzc">{</span> <span class="w" id="mwAzg"> </span><span class="kt" id="mwAzk">void</span><span class="w" id="mwAzo"> </span><span class="n" id="mwAzs">putAnimal</span><span class="p" id="mwAzw">(</span><span class="kd" id="mwAz0">covariant</span><span class="w" id="mwAz4"> </span><span class="n" id="mwAz8">Cat</span><span class="w" id="mwA0A"> </span><span class="n" id="mwA0E">animal</span><span class="p" id="mwA0I">)</span><span class="w" id="mwA0M"> </span><span class="p" id="mwA0Q">{</span> <span class="w" id="mwA0U"> </span><span class="c1" id="mwA0Y">// ...</span> <span class="w" id="mwA0c"> </span><span class="p" id="mwA0g">}</span> <span class="p" id="mwA0k">}</span>

This is not type safe. By up-casting a CatShelter to an AnimalShelter , one can try to place a dog in a cat shelter. That does not meet CatShelter parameter restrictions and will result in a runtime error. The lack of type safety (known as the "catcall problem" in the Eiffel community, where "cat" or "CAT" is a 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 remedy it, and these have been implemented in some Eiffel compilers.

Despite the type safety problem, the Eiffel designers consider covariant parameter types crucial for modeling real world requirements. The cat shelter illustrates a common phenomenon: it is a kind of animal shelter but has additional restrictions, and it seems reasonable to use inheritance and restricted parameter types to model this. In proposing this use of inheritance, the Eiffel designers reject the Liskov substitution principle, which states that objects of subclasses should always be less restricted than objects of their superclass.

One other instance of a mainstream language allowing covariance in method parameters is PHP in regards to class constructors. In the following example, the __construct() method is accepted, despite the method parameter being covariant to the parent's method parameter. Were this method anything other than __construct(), an error would occur:

<span id="mwA2c"></span><span class="k" id="mwA2g">interface</span> <span class="nx" id="mwA2k">AnimalInterface</span> <span class="p" id="mwA2o">{}</span> <span class="k" id="mwA2s">interface</span> <span class="nx" id="mwA2w">DogInterface</span> <span class="k" id="mwA20">extends</span> <span class="nx" id="mwA24">AnimalInterface</span> <span class="p" id="mwA28">{}</span> <span class="k" id="mwA3A">class</span> <span class="nc" id="mwA3E">Dog</span> <span class="k" id="mwA3I">implements</span> <span class="nx" id="mwA3M">DogInterface</span> <span class="p" id="mwA3Q">{}</span> <span class="k" id="mwA3U">class</span> <span class="nc" id="mwA3Y">Pet</span> <span class="p" id="mwA3c">{</span> <span class="k" id="mwA3g">public</span> <span class="k" id="mwA3k">function</span> <span class="fm" id="mwA3o">__construct</span><span class="p" id="mwA3s">(</span><span class="nx" id="mwA3w">AnimalInterface</span> <span class="nv" id="mwA30">$animal</span><span class="p" id="mwA34">)</span> <span class="p" id="mwA38">{}</span> <span class="p" id="mwA4A">}</span> <span class="k" id="mwA4E">class</span> <span class="nc" id="mwA4I">PetDog</span> <span class="k" id="mwA4M">extends</span> <span class="nx" id="mwA4Q">Pet</span> <span class="p" id="mwA4U">{</span> <span class="k" id="mwA4Y">public</span> <span class="k" id="mwA4c">function</span> <span class="fm" id="mwA4g">__construct</span><span class="p" id="mwA4k">(</span><span class="nx" id="mwA4o">DogInterface</span> <span class="nv" id="mwA4s">$dog</span><span class="p" id="mwA4w">)</span> <span class="p" id="mwA40">{</span> <span class="k" id="mwA44">parent</span><span class="o" id="mwA48">::</span><span class="na" id="mwA5A">__construct</span><span class="p" id="mwA5E">(</span><span class="nv" id="mwA5I">$dog</span><span class="p" id="mwA5M">);</span> <span class="p" id="mwA5Q">}</span> <span class="p" id="mwA5U">}</span>

Another example where covariant parameters seem helpful is so-called binary methods, i.e. methods where the parameter is expected to be of the same type as the object the method is called on. An example is the compareTo method: a.compareTo(b) checks whether a comes before or after b in some ordering, but the way to compare, say, two rational numbers will be different from the way to compare two strings. Other common examples of binary methods include equality tests, arithmetic operations, and set operations like subset and union.

In older versions of Java, the comparison method was specified as an interface Comparable :

<span id="mwA64"></span><span class="kd" id="mwA68">interface</span> <span class="nc" id="mwA7A">Comparable</span><span class="w" id="mwA7E"> </span><span class="p" id="mwA7I">{</span> <span class="w" id="mwA7M"> </span><span class="kt" id="mwA7Q">int</span><span class="w" id="mwA7U"> </span><span class="nf" id="mwA7Y">compareTo</span><span class="p" id="mwA7c">(</span><span class="n" id="mwA7g">Object</span><span class="w" id="mwA7k"> </span><span class="n" id="mwA7o">o</span><span class="p" id="mwA7s">);</span> <span class="p" id="mwA7w">}</span>

The drawback of this is that the method is specified to take an argument of type Object . A typical implementation would first down-cast this argument (throwing an error if it is not of the expected type):

<span id="mwA8M"></span><span class="kd" id="mwA8Q">class</span> <span class="nc" id="mwA8U">RationalNumber</span><span class="w" id="mwA8Y"> </span><span class="kd" id="mwA8c">implements</span><span class="w" id="mwA8g"> </span><span class="n" id="mwA8k">Comparable</span><span class="w" id="mwA8o"> </span><span class="p" id="mwA8s">{</span> <span class="w" id="mwA8w"> </span><span class="kt" id="mwA80">int</span><span class="w" id="mwA84"> </span><span class="n" id="mwA88">numerator</span><span class="p" id="mwA9A">;</span> <span class="w" id="mwA9E"> </span><span class="kt" id="mwA9I">int</span><span class="w" id="mwA9M"> </span><span class="n" id="mwA9Q">denominator</span><span class="p" id="mwA9U">;</span> <span class="w" id="mwA9Y"> </span><span class="c1" id="mwA9c">// ...</span> <span class="w" id="mwA9g"> </span> <span class="w" id="mwA9k"> </span><span class="kd" id="mwA9o">public</span><span class="w" id="mwA9s"> </span><span class="kt" id="mwA9w">int</span><span class="w" id="mwA90"> </span><span class="nf" id="mwA94">compareTo</span><span class="p" id="mwA98">(</span><span class="n" id="mwA-A">Object</span><span class="w" id="mwA-E"> </span><span class="n" id="mwA-I">other</span><span class="p" id="mwA-M">)</span><span class="w" id="mwA-Q"> </span><span class="p" id="mwA-U">{</span> <span class="w" id="mwA-Y"> </span><span class="n" id="mwA-c">RationalNumber</span><span class="w" id="mwA-g"> </span><span class="n" id="mwA-k">otherNum</span><span class="w" id="mwA-o"> </span><span class="o" id="mwA-s">=</span><span class="w" id="mwA-w"> </span><span class="p" id="mwA-0">(</span><span class="n" id="mwA-4">RationalNumber</span><span class="p" id="mwA-8">)</span><span class="n" id="mwA_A">other</span><span class="p" id="mwA_E">;</span> <span class="w" id="mwA_I"> </span><span class="k" id="mwA_M">return</span><span class="w" id="mwA_Q"> </span><span class="n" id="mwA_U">Integer</span><span class="p" id="mwA_Y">.</span><span class="na" id="mwA_c">compare</span><span class="p" id="mwA_g">(</span><span class="n" id="mwA_k">numerator</span><span class="w" id="mwA_o"> </span><span class="o" id="mwA_s">*</span><span class="w" id="mwA_w"> </span><span class="n" id="mwA_0">otherNum</span><span class="p" id="mwA_4">.</span><span class="na" id="mwA_8">denominator</span><span class="p" id="mwBAA">,</span> <span class="w" id="mwBAE"> </span><span class="n" id="mwBAI">otherNum</span><span class="p" id="mwBAM">.</span><span class="na" id="mwBAQ">numerator</span><span class="w" id="mwBAU"> </span><span class="o" id="mwBAY">*</span><span class="w" id="mwBAc"> </span><span class="n" id="mwBAg">denominator</span><span class="p" id="mwBAk">);</span> <span class="w" id="mwBAo"> </span><span class="p" id="mwBAs">}</span> <span class="p" id="mwBAw">}</span>

In a language with covariant parameters, the argument to compareTo could be directly given the desired type RationalNumber , hiding the typecast. (Of course, this would still give a runtime error if compareTo was then called on e.g. a String .)

Avoiding the need for covariant parameter types

Other language features can provide the apparent benefits of covariant parameters while preserving Liskov substitutability.

In a language with generics (a.k.a. parametric polymorphism) and bounded quantification, the previous examples can be written in a type-safe way. Instead of defining AnimalShelter , we define a parameterized class Shelter<T> . (One drawback of this is that the implementer of the base class needs to foresee which types will need to be specialized in the subclasses.)

<span id="mwBC8"></span><span class="kd" id="mwBDA">class</span> <span class="nc" id="mwBDE">Shelter</span><span class="o" id="mwBDI"><</span><span class="n" id="mwBDM">T</span><span class="w" id="mwBDQ"> </span><span class="kd" id="mwBDU">extends</span><span class="w" id="mwBDY"> </span><span class="n" id="mwBDc">Animal</span><span class="o" id="mwBDg">></span><span class="w" id="mwBDk"> </span><span class="p" id="mwBDo">{</span> <span class="w" id="mwBDs"> </span><span class="n" id="mwBDw">T</span><span class="w" id="mwBD0"> </span><span class="nf" id="mwBD4">getAnimalForAdoption</span><span class="p" id="mwBD8">()</span><span class="w" id="mwBEA"> </span><span class="p" id="mwBEE">{</span> <span class="w" id="mwBEI"> </span><span class="c1" id="mwBEM">// ...</span> <span class="w" id="mwBEQ"> </span><span class="p" id="mwBEU">}</span> <span class="w" id="mwBEY"> </span><span class="kt" id="mwBEc">void</span><span class="w" id="mwBEg"> </span><span class="nf" id="mwBEk">putAnimal</span><span class="p" id="mwBEo">(</span><span class="n" id="mwBEs">T</span><span class="w" id="mwBEw"> </span><span class="n" id="mwBE0">animal</span><span class="p" id="mwBE4">)</span><span class="w" id="mwBE8"> </span><span class="p" id="mwBFA">{</span> <span class="w" id="mwBFE"> </span><span class="c1" id="mwBFI">// ...</span> <span class="w" id="mwBFM"> </span><span class="p" id="mwBFQ">}</span> <span class="p" id="mwBFU">}</span> <span class="w" id="mwBFY"> </span> <span class="kd" id="mwBFc">class</span> <span class="nc" id="mwBFg">CatShelter</span><span class="w" id="mwBFk"> </span><span class="kd" id="mwBFo">extends</span><span class="w" id="mwBFs"> </span><span class="n" id="mwBFw">Shelter</span><span class="o" id="mwBF0"><</span><span class="n" id="mwBF4">Cat</span><span class="o" id="mwBF8">></span><span class="w" id="mwBGA"> </span><span class="p" id="mwBGE">{</span> <span class="w" id="mwBGI"> </span><span class="n" id="mwBGM">Cat</span><span class="w" id="mwBGQ"> </span><span class="nf" id="mwBGU">getAnimalForAdoption</span><span class="p" id="mwBGY">()</span><span class="w" id="mwBGc"> </span><span class="p" id="mwBGg">{</span> <span class="w" id="mwBGk"> </span><span class="c1" id="mwBGo">// ...</span> <span class="w" id="mwBGs"> </span><span class="p" id="mwBGw">}</span> <span class="w" id="mwBG0"> </span><span class="kt" id="mwBG4">void</span><span class="w" id="mwBG8"> </span><span class="nf" id="mwBHA">putAnimal</span><span class="p" id="mwBHE">(</span><span class="n" id="mwBHI">Cat</span><span class="w" id="mwBHM"> </span><span class="n" id="mwBHQ">animal</span><span class="p" id="mwBHU">)</span><span class="w" id="mwBHY"> </span><span class="p" id="mwBHc">{</span> <span class="w" id="mwBHg"> </span><span class="c1" id="mwBHk">// ...</span> <span class="w" id="mwBHo"> </span><span class="p" id="mwBHs">}</span> <span class="p" id="mwBHw">}</span>

Similarly, in recent versions of Java the Comparable interface has been parameterized, which allows the downcast to be omitted in a type-safe way:

<span id="mwBIM"></span><span class="kd" id="mwBIQ">class</span> <span class="nc" id="mwBIU">RationalNumber</span><span class="w" id="mwBIY"> </span><span class="kd" id="mwBIc">implements</span><span class="w" id="mwBIg"> </span><span class="n" id="mwBIk">Comparable</span><span class="o" id="mwBIo"><</span><span class="n" id="mwBIs">RationalNumber</span><span class="o" id="mwBIw">></span><span class="w" id="mwBI0"> </span><span class="p" id="mwBI4">{</span> <span class="w" id="mwBI8"> </span><span class="kt" id="mwBJA">int</span><span class="w" id="mwBJE"> </span><span class="n" id="mwBJI">numerator</span><span class="p" id="mwBJM">;</span> <span class="w" id="mwBJQ"> </span><span class="kt" id="mwBJU">int</span><span class="w" id="mwBJY"> </span><span class="n" id="mwBJc">denominator</span><span class="p" id="mwBJg">;</span> <span class="w" id="mwBJk"> </span><span class="c1" id="mwBJo">// ...</span> <span class="w" id="mwBJs"> </span> <span class="w" id="mwBJw"> </span><span class="kd" id="mwBJ0">public</span><span class="w" id="mwBJ4"> </span><span class="kt" id="mwBJ8">int</span><span class="w" id="mwBKA"> </span><span class="nf" id="mwBKE">compareTo</span><span class="p" id="mwBKI">(</span><span class="n" id="mwBKM">RationalNumber</span><span class="w" id="mwBKQ"> </span><span class="n" id="mwBKU">otherNum</span><span class="p" id="mwBKY">)</span><span class="w" id="mwBKc"> </span><span class="p" id="mwBKg">{</span> <span class="w" id="mwBKk"> </span><span class="k" id="mwBKo">return</span><span class="w" id="mwBKs"> </span><span class="n" id="mwBKw">Integer</span><span class="p" id="mwBK0">.</span><span class="na" id="mwBK4">compare</span><span class="p" id="mwBK8">(</span><span class="n" id="mwBLA">numerator</span><span class="w" id="mwBLE"> </span><span class="o" id="mwBLI">*</span><span class="w" id="mwBLM"> </span><span class="n" id="mwBLQ">otherNum</span><span class="p" id="mwBLU">.</span><span class="na" id="mwBLY">denominator</span><span class="p" id="mwBLc">,</span><span class="w" id="mwBLg"> </span> <span class="w" id="mwBLk"> </span><span class="n" id="mwBLo">otherNum</span><span class="p" id="mwBLs">.</span><span class="na" id="mwBLw">numerator</span><span class="w" id="mwBL0"> </span><span class="o" id="mwBL4">*</span><span class="w" id="mwBL8"> </span><span class="n" id="mwBMA">denominator</span><span class="p" id="mwBME">);</span> <span class="w" id="mwBMI"> </span><span class="p" id="mwBMM">}</span> <span class="p" id="mwBMQ">}</span>

Another language feature that can help is multiple dispatch. One reason that binary methods are awkward to write is that in a call like a.compareTo(b) , selecting the correct implementation of compareTo really depends on the runtime type of both a and b , but in a conventional OO language only the runtime type of a is taken into account. In a language with Common Lisp Object System (CLOS)-style multiple dispatch, the comparison method could be written as a generic function where both arguments are used for method selection.

Giuseppe Castagna observed that in a typed language with multiple dispatch, a generic function can have some parameters which control dispatch and some "left-over" parameters which do not. Because 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 still must require the left-over parameters to be at least as general. Using the previous terminology, types used for runtime method selection are covariant while types not used for runtime method selection of the method are contravariant. Conventional single-dispatch languages like Java also obey this rule: only one argument is used for method selection (the receiver object, passed along to a method as the hidden argument 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 are superior (particularly, binary methods) should be handled using multiple dispatch; which is naturally covariant. However, most programming languages do not support multiple dispatch.

Summary of variance and inheritance

The following table summarizes the rules for overriding methods in the languages discussed above.

Generic types

In programming languages that support generics (a.k.a. parametric polymorphism), the programmer can extend the type system with new constructors. For example, a C# interface like IList<T> makes it possible to construct new types like IList<Animal> or IList<Cat>. The question then arises what the variance of these type constructors should be.

There are two main approaches. In languages with declaration-site variance annotations (e.g., C#), the programmer annotates the definition of a generic type with the intended variance of its type parameters. With use-site variance annotations (e.g., Java), the programmer instead annotates the places where a generic type is instantiated.

Declaration-site variance annotations

The most popular languages with declaration-site variance annotations are C# and Kotlin (using the keywords out and in), and Scala and OCaml (using the keywords + and -). C# only allows variance annotations for interface types, while Kotlin, Scala and OCaml allow them for both interface types and concrete data types.

Interfaces

In C#, each type parameter of a generic interface can be marked covariant (out), contravariant (in), or invariant (no annotation). For example, we can define an interface IEnumerator<T> of read-only iterators, and declare it to be covariant (out) in its type parameter.

<span id="mwBUc"></span><span class="k" id="mwBUg">interface</span><span class="w" id="mwBUk"> </span><span class="n" id="mwBUo">IEnumerator</span><span class="o" id="mwBUs"><</span><span class="k" id="mwBUw">out</span><span class="w" id="mwBU0"> </span><span class="n" id="mwBU4">T</span><span class="o" id="mwBU8">></span> <span class="p" id="mwBVA">{</span> <span class="w" id="mwBVE"> </span><span class="n" id="mwBVI">T</span><span class="w" id="mwBVM"> </span><span class="n" id="mwBVQ">Current</span><span class="w" id="mwBVU"> </span><span class="p" id="mwBVY">{</span><span class="w" id="mwBVc"> </span><span class="k" id="mwBVg">get</span><span class="p" id="mwBVk">;</span><span class="w" id="mwBVo"> </span><span class="p" id="mwBVs">}</span> <span class="w" id="mwBVw"> </span><span class="kt" id="mwBV0">bool</span><span class="w" id="mwBV4"> </span><span class="nf" id="mwBV8">MoveNext</span><span class="p" id="mwBWA">();</span> <span class="p" id="mwBWE">}</span>

With this declaration, IEnumerator will be treated as covariant in its type parameter, e.g. IEnumerator<Cat> is a subtype of IEnumerator<Animal>.

The type checker enforces that each method declaration in an interface only mentions the type parameters in a way consistent with the in/out annotations. That is, a parameter that was declared covariant must not occur in any contravariant positions (where a position is contravariant if it occurs under an odd number of contravariant type constructors). The precise rule is that the return types of all methods in the interface must be valid covariantly and all the method parameter types must be valid contravariantly, where valid S-ly is defined as follows:

Non-generic types (classes, structs, enums, etc.) are valid both co- and contravariantly.
A type parameter T is valid covariantly if it was not marked in, and valid contravariantly if it was not marked out.
An array type A[] is valid S-ly if A is. (This is because C# has covariant arrays.)
A generic type G<A1, A2, ..., An> is valid S-ly if for each parameter Ai,
- Ai is valid S-ly, and the ith parameter to G is declared covariant, or
- Ai is valid (not S)-ly, and the ith parameter to G is declared contravariant, or
- Ai is valid both covariantly and contravariantly, and the ith parameter to G is declared invariant.

As an example of how these rules apply, consider the IList<T> interface.

<span id="mwBcM"></span><span class="k" id="mwBcQ">interface</span><span class="w" id="mwBcU"> </span><span class="n" id="mwBcY">IList</span><span class="o" id="mwBcc"><</span><span class="n" id="mwBcg">T</span><span class="o" id="mwBck">></span> <span class="p" id="mwBco">{</span> <span class="w" id="mwBcs"> </span><span class="k" id="mwBcw">void</span><span class="w" id="mwBc0"> </span><span class="nf" id="mwBc4">Insert</span><span class="p" id="mwBc8">(</span><span class="kt" id="mwBdA">int</span><span class="w" id="mwBdE"> </span><span class="n" id="mwBdI">index</span><span class="p" id="mwBdM">,</span><span class="w" id="mwBdQ"> </span><span class="n" id="mwBdU">T</span><span class="w" id="mwBdY"> </span><span class="n" id="mwBdc">item</span><span class="p" id="mwBdg">);</span> <span class="w" id="mwBdk"> </span><span class="n" id="mwBdo">IEnumerator</span><span class="o" id="mwBds"><</span><span class="n" id="mwBdw">T</span><span class="o" id="mwBd0">></span><span class="w" id="mwBd4"> </span><span class="n" id="mwBd8">GetEnumerator</span><span class="p" id="mwBeA">();</span> <span class="p" id="mwBeE">}</span>

The parameter type T of Insert must be valid contravariantly, i.e. the type parameter T must not be tagged out. Similarly, the result type IEnumerator<T> of GetEnumerator must be valid covariantly, i.e. (since IEnumerator is a covariant interface) the type T must be valid covariantly, i.e. the type parameter T must not be tagged in. This shows that the interface IList is not allowed to be marked either co- or contravariant.

In the common case of a generic data structure such as IList, these restrictions mean that an out parameter can only be used for methods getting data out of the structure, and an in parameter can only be used for methods putting data into the structure, hence the choice of keywords.

Data

C# allows variance annotations on the parameters of interfaces, but not the parameters of classes. Because fields in C# classes are always mutable, variantly parameterized classes in C# would not be very useful. But languages which emphasize immutable data can make good use of covariant data types. For example, in all of Scala, Kotlin and OCaml the immutable list type is covariant: List[Cat] is a subtype of List[Animal].

Scala's rules for checking variance annotations are essentially the same as C#'s. However, there are some idioms that apply to immutable datastructures in particular. They are illustrated by the following (excerpt from the) definition of the List[A] class.

<span id="mwBik"></span><span class="k" id="mwBio">sealed</span><span class="w" id="mwBis"> </span><span class="k" id="mwBiw">abstract</span><span class="w" id="mwBi0"> </span><span class="k" id="mwBi4">class</span><span class="w" id="mwBi8"> </span><span class="nc" id="mwBjA">List</span><span class="p" id="mwBjE">[</span><span class="o" id="mwBjI">+</span><span class="nc" id="mwBjM">A</span><span class="p" id="mwBjQ">]</span><span class="w" id="mwBjU"> </span><span class="k" id="mwBjY">extends</span><span class="w" id="mwBjc"> </span><span class="nc" id="mwBjg">AbstractSeq</span><span class="p" id="mwBjk">[</span><span class="nc" id="mwBjo">A</span><span class="p" id="mwBjs">]</span><span class="w" id="mwBjw"> </span><span class="p" id="mwBj0">{</span> <span class="w" id="mwBj4"> </span><span class="k" id="mwBj8">def</span><span class="w" id="mwBkA"> </span><span class="nf" id="mwBkE">head</span><span class="p" id="mwBkI">:</span><span class="w" id="mwBkM"> </span><span class="nc" id="mwBkQ">A</span> <span class="w" id="mwBkU"> </span><span class="k" id="mwBkY">def</span><span class="w" id="mwBkc"> </span><span class="nf" id="mwBkg">tail</span><span class="p" id="mwBkk">:</span><span class="w" id="mwBko"> </span><span class="nc" id="mwBks">List</span><span class="p" id="mwBkw">[</span><span class="nc" id="mwBk0">A</span><span class="p" id="mwBk4">]</span> <span class="w" id="mwBk8"> </span><span class="cm" id="mwBlA">/** Adds an element at the beginning of this list. */</span> <span class="w" id="mwBlE"> </span><span class="k" id="mwBlI">def</span><span class="w" id="mwBlM"> </span><span class="nf" id="mwBlQ">::</span><span class="p" id="mwBlU">[</span><span class="nc" id="mwBlY">B</span><span class="w" id="mwBlc"> </span><span class="o" id="mwBlg">>:</span><span class="w" id="mwBlk"> </span><span class="nc" id="mwBlo">A</span><span class="p" id="mwBls">]</span><span class="w" id="mwBlw"> </span><span class="p" id="mwBl0">(</span><span class="n" id="mwBl4">x</span><span class="p" id="mwBl8">:</span><span class="w" id="mwBmA"> </span><span class="nc" id="mwBmE">B</span><span class="p" id="mwBmI">):</span><span class="w" id="mwBmM"> </span><span class="nc" id="mwBmQ">List</span><span class="p" id="mwBmU">[</span><span class="nc" id="mwBmY">B</span><span class="p" id="mwBmc">]</span><span class="w" id="mwBmg"> </span><span class="o" id="mwBmk">=</span> <span class="w" id="mwBmo"> </span><span class="k" id="mwBms">new</span><span class="w" id="mwBmw"> </span><span class="n" id="mwBm0">scala</span><span class="p" id="mwBm4">.</span><span class="n" id="mwBm8">collection</span><span class="p" id="mwBnA">.</span><span class="n" id="mwBnE">immutable</span><span class="p" id="mwBnI">.</span><span class="n" id="mwBnM">::</span><span class="p" id="mwBnQ">(</span><span class="n" id="mwBnU">x</span><span class="p" id="mwBnY">,</span><span class="w" id="mwBnc"> </span><span class="bp" id="mwBng">this</span><span class="p" id="mwBnk">)</span> <span class="w" id="mwBno"> </span><span class="cm" id="mwBns">/** ... */</span> <span class="p" id="mwBnw">}</span>

First, class members that have a variant type must be immutable. Here, head has the type A, which was declared covariant (+), and indeed head was declared as a method (def). Trying to declare it as a mutable field (var) would be rejected as type error.

Second, even if a data structure is immutable, it will often have methods where the parameter type occurs contravariantly. For example, consider the method :: which adds an element to the front of a list. (The implementation works by creating a new object of the similarly named class ::, the class of nonempty lists.) The most obvious type to give it would be

<span id="mwBpI"></span><span class="k" id="mwBpM">def</span><span class="w" id="mwBpQ"> </span><span class="nf" id="mwBpU">::</span><span class="w" id="mwBpY"> </span><span class="p" id="mwBpc">(</span><span class="n" id="mwBpg">x</span><span class="p" id="mwBpk">:</span><span class="w" id="mwBpo"> </span><span class="nc" id="mwBps">A</span><span class="p" id="mwBpw">):</span><span class="w" id="mwBp0"> </span><span class="nc" id="mwBp4">List</span><span class="p" id="mwBp8">[</span><span class="nc" id="mwBqA">A</span><span class="p" id="mwBqE">]</span>

However, this would be a type error, because the covariant parameter A appears in a contravariant position (as a function parameter). But there is a trick to get around this problem. We give :: a more general type, which allows adding an element of any type B as long as B is a supertype of A. Note that this relies on List being covariant, since this has type List[A] and we treat it as having type List[B]. At first glance it may not be obvious that the generalized type is sound, but if the programmer starts out with the simpler type declaration, the type errors will point out the place that needs to be generalized.

Inferring variance

It is possible to design a type system where the compiler automatically infers the best possible variance annotations for all datatype parameters. However, the analysis can get complex for several reasons. First, the analysis is nonlocal since the variance of an interface I depends on the variance of all interfaces that I mentions. Second, in order to get unique best solutions the type system must allow bivariant parameters (which are simultaneously co- and contravariant). And finally, the variance of type parameters should arguably be a deliberate choice by the designer of an interface, not something that just happens.

For these reasons most languages do very little variance inference. C# and Scala do not infer any variance annotations at all. OCaml can infer the variance of parameterized concrete datatypes, but the programmer must explicitly specify the variance of abstract types (interfaces).

For example, consider an OCaml datatype T which wraps a function

<span id="mwBtM"></span><span class="k" id="mwBtQ">type</span> <span class="o" id="mwBtU">(</span><span class="k" id="mwBtY">'</span><span class="n" id="mwBtc">a</span><span class="o" id="mwBtg">,</span> <span class="k" id="mwBtk">'</span><span class="n" id="mwBto">b</span><span class="o" id="mwBts">)</span> <span class="n" id="mwBtw">t</span> <span class="o" id="mwBt0">=</span> <span class="nc" id="mwBt4">T</span> <span class="k" id="mwBt8">of</span> <span class="o" id="mwBuA">(</span><span class="k" id="mwBuE">'</span><span class="n" id="mwBuI">a</span> <span class="o" id="mwBuM">-></span> <span class="k" id="mwBuQ">'</span><span class="n" id="mwBuU">b</span><span class="o" id="mwBuY">)</span>

The compiler will automatically infer that T is contravariant in the first parameter, and covariant in the second. The programmer can also provide explicit annotations, which the compiler will check are satisfied. Thus the following declaration is equivalent to the previous one:

<span id="mwBu0"></span><span class="k" id="mwBu4">type</span> <span class="o" id="mwBu8">(-</span><span class="k" id="mwBvA">'</span><span class="n" id="mwBvE">a</span><span class="o" id="mwBvI">,</span> <span class="o" id="mwBvM">+</span><span class="k" id="mwBvQ">'</span><span class="n" id="mwBvU">b</span><span class="o" id="mwBvY">)</span> <span class="n" id="mwBvc">t</span> <span class="o" id="mwBvg">=</span> <span class="nc" id="mwBvk">T</span> <span class="k" id="mwBvo">of</span> <span class="o" id="mwBvs">(</span><span class="k" id="mwBvw">'</span><span class="n" id="mwBv0">a</span> <span class="o" id="mwBv4">-></span> <span class="k" id="mwBv8">'</span><span class="n" id="mwBwA">b</span><span class="o" id="mwBwE">)</span>

Explicit annotations in OCaml become useful when specifying interfaces. For example, the standard library interface Map.S for association tables include an annotation saying that the map type constructor is covariant in the result type.

<span id="mwBwo"></span><span class="k" id="mwBws">module</span> <span class="k" id="mwBww">type</span> <span class="nc" id="mwBw0">S</span> <span class="o" id="mwBw4">=</span> <span class="k" id="mwBw8">sig</span> <span class="k" id="mwBxA">type</span> <span class="n" id="mwBxE">key</span> <span class="k" id="mwBxI">type</span> <span class="o" id="mwBxM">(+</span><span class="k" id="mwBxQ">'</span><span class="n" id="mwBxU">a</span><span class="o" id="mwBxY">)</span> <span class="n" id="mwBxc">t</span> <span class="k" id="mwBxg">val</span> <span class="n" id="mwBxk">empty</span><span class="o" id="mwBxo">:</span> <span class="k" id="mwBxs">'</span><span class="n" id="mwBxw">a</span> <span class="n" id="mwBx0">t</span> <span class="k" id="mwBx4">val</span> <span class="n" id="mwBx8">mem</span><span class="o" id="mwByA">:</span> <span class="n" id="mwByE">key</span> <span class="o" id="mwByI">-></span> <span class="k" id="mwByM">'</span><span class="n" id="mwByQ">a</span> <span class="n" id="mwByU">t</span> <span class="o" id="mwByY">-></span> <span class="kt" id="mwByc">bool</span> <span class="o" id="mwByg">...</span> <span class="k" id="mwByk">end</span>

This ensures that e.g. cat IntMap.t is a subtype of animal IntMap.t.

Use-site variance annotations (wildcards)

One drawback of the declaration-site approach is that many interface types must be made invariant. For example, we saw above that IList needed to be invariant, because it contained both Insert and GetEnumerator. In order to expose more variance, the API designer could provide additional interfaces which provide subsets of the available methods (e.g. an "insert-only list" which only provides Insert). However this quickly becomes unwieldy.

Use-site variance means the desired variance is indicated with an annotation at the specific site in the code where the type will be used. This gives users of a class more opportunities for subtyping without requiring the designer of the class to define multiple interfaces with different variance. Instead, at the point a generic type is instantiated to an actual parameterized type, the programmer can indicate that only a subset of its methods will be used. In effect, each definition of a generic class also makes available interfaces for the covariant and contravariant parts of that class.

Java provides use-site variance annotations through wildcards, a restricted form of bounded existential types. A parameterized type can be instantiated by a wildcard ? together with an upper or lower bound, e.g. List<? extends Animal> or List<? super Animal> . An unbounded wildcard like List<?> is equivalent to List<? extends Object> . Such a type represents List<X> for some unknown type X which satisfies the bound. For example, if l has type List<? extends Animal> , then the type checker will accept

<span id="mwB4k"></span><span class="n" id="mwB4o">Animal</span><span class="w" id="mwB4s"> </span><span class="n" id="mwB4w">a</span><span class="w" id="mwB40"> </span><span class="o" id="mwB44">=</span><span class="w" id="mwB48"> </span><span class="n" id="mwB5A">l</span><span class="p" id="mwB5E">.</span><span class="na" id="mwB5I">get</span><span class="p" id="mwB5M">(</span><span class="mi" id="mwB5Q">3</span><span class="p" id="mwB5U">);</span>

because the type X is known to be a subtype of Animal , but

<span id="mwB58"></span><span class="n" id="mwB6A">l</span><span class="p" id="mwB6E">.</span><span class="na" id="mwB6I">add</span><span class="p" id="mwB6M">(</span><span class="k" id="mwB6Q">new</span><span class="w" id="mwB6U"> </span><span class="n" id="mwB6Y">Animal</span><span class="p" id="mwB6c">());</span>

will be rejected as a type error since an Animal is not necessarily an X . In general, given some interface I<T> , a reference to an I<? extends T> forbids using methods from the interface where T occurs contravariantly in the type of the method. Conversely, if l had type List<? super Animal> one could call l.add but not l.get .

While non-wildcard parameterized types in Java are invariant (e.g. there is no subtyping relationship between List<Cat> and List<Animal> ), wildcard types can be made more specific by specifying a tighter bound. For example, List<? extends Cat> is a subtype of List<? extends Animal> . This shows that wildcard types are covariant in their upper bounds (and also contravariant in their lower bounds). In total, given a wildcard type like C<? extends T> , there are three ways to form a subtype: by specializing the class C , by specifying a tighter bound T , or by replacing the wildcard ? with a specific type (see figure).

By applying two of the above three forms of subtyping, it becomes possible to, for example, pass an argument of type List<Cat> to a method expecting a List<? extends Animal> . This is the kind of expressiveness that results from covariant interface types. The type List<? extends Animal> acts as an interface type containing only the covariant methods of List<T> , but the implementer of List<T> did not have to define it ahead of time.

In the common case of a generic data structure IList, covariant parameters are used for methods getting data out of the structure, and contravariant parameters for methods putting data into the structure. The mnemonic for Producer Extends, Consumer Super (PECS), from the book Effective Java by Joshua Bloch gives an easy way to remember when to use covariance and contravariance.

Wildcards are flexible, but there is a drawback. While use-site variance means that API designers need not consider variance of type parameters to interfaces, they must often instead use more complicated method signatures. A common example involves the Comparable interface. Suppose we want to write a function that finds the biggest element in a collection. The elements need to implement the compareTo method, so a first try might be

<span id="mwCFU"></span><span class="o" id="mwCFY"><</span><span class="n" id="mwCFc">T</span><span class="w" id="mwCFg"> </span><span class="kd" id="mwCFk">extends</span><span class="w" id="mwCFo"> </span><span class="n" id="mwCFs">Comparable</span><span class="o" id="mwCFw"><</span><span class="n" id="mwCF0">T</span><span class="o" id="mwCF4">>></span><span class="w" id="mwCF8"> </span><span class="n" id="mwCGA">T</span><span class="w" id="mwCGE"> </span><span class="nf" id="mwCGI">max</span><span class="p" id="mwCGM">(</span><span class="n" id="mwCGQ">Collection</span><span class="o" id="mwCGU"><</span><span class="n" id="mwCGY">T</span><span class="o" id="mwCGc">></span><span class="w" id="mwCGg"> </span><span class="n" id="mwCGk">coll</span><span class="p" id="mwCGo">);</span>

However, this type is not general enough—one can find the max of a Collection<Calendar> , but not a Collection<GregorianCalendar> . The problem is that GregorianCalendar does not implement Comparable<GregorianCalendar> , but instead the (better) interface Comparable<Calendar> . In Java, unlike in C#, Comparable<Calendar> is not considered a subtype of Comparable<GregorianCalendar> . Instead the type of max has to be modified:

<span id="mwCJc"></span><span class="o" id="mwCJg"><</span><span class="n" id="mwCJk">T</span><span class="w" id="mwCJo"> </span><span class="kd" id="mwCJs">extends</span><span class="w" id="mwCJw"> </span><span class="n" id="mwCJ0">Comparable</span><span class="o" id="mwCJ4"><?</span><span class="w" id="mwCJ8"> </span><span class="kd" id="mwCKA">super</span><span class="w" id="mwCKE"> </span><span class="n" id="mwCKI">T</span><span class="o" id="mwCKM">>></span><span class="w" id="mwCKQ"> </span><span class="n" id="mwCKU">T</span><span class="w" id="mwCKY"> </span><span class="nf" id="mwCKc">max</span><span class="p" id="mwCKg">(</span><span class="n" id="mwCKk">Collection</span><span class="o" id="mwCKo"><</span><span class="n" id="mwCKs">T</span><span class="o" id="mwCKw">></span><span class="w" id="mwCK0"> </span><span class="n" id="mwCK4">coll</span><span class="p" id="mwCK8">);</span>

The bounded wildcard ? super T conveys the information that max calls only contravariant methods from the Comparable interface. This particular example is frustrating because all the methods in Comparable are contravariant, so that condition is trivially true. A declaration-site system could handle this example with less clutter by annotating only the definition of Comparable .

The max method can be changed even further by using an upper bounded wildcard for the method parameter:

<span id="mwCM8"></span><span class="o" id="mwCNA"><</span><span class="n" id="mwCNE">T</span><span class="w" id="mwCNI"> </span><span class="kd" id="mwCNM">extends</span><span class="w" id="mwCNQ"> </span><span class="n" id="mwCNU">Comparable</span><span class="o" id="mwCNY"><?</span><span class="w" id="mwCNc"> </span><span class="kd" id="mwCNg">super</span><span class="w" id="mwCNk"> </span><span class="n" id="mwCNo">T</span><span class="o" id="mwCNs">>></span><span class="w" id="mwCNw"> </span><span class="n" id="mwCN0">T</span><span class="w" id="mwCN4"> </span><span class="nf" id="mwCN8">max</span><span class="p" id="mwCOA">(</span><span class="n" id="mwCOE">Collection</span><span class="o" id="mwCOI"><?</span><span class="w" id="mwCOM"> </span><span class="kd" id="mwCOQ">extends</span><span class="w" id="mwCOU"> </span><span class="n" id="mwCOY">T</span><span class="o" id="mwCOc">></span><span class="w" id="mwCOg"> </span><span class="n" id="mwCOk">coll</span><span class="p" id="mwCOo">);</span>

Comparing declaration-site and use-site annotations

Use-site variance annotations provide additional flexibility, allowing more programs to type check. However, they have been criticized for the complexity they add to the language, leading to complicated type signatures and error messages.

One way to assess whether the extra flexibility is useful is to see if it is used in existing programs. A survey of a large set of Java libraries found that 39% of wildcard annotations could have been directly replaced by declaration-site annotations. Thus the remaining 61% is an indication of places where Java benefits from having the use-site system available.

In a declaration-site language, libraries must either expose less variance, or define more interfaces. For example, the Scala Collections library defines three separate interfaces for classes which employ covariance: a covariant base interface containing common methods, an invariant mutable version which adds side-effecting methods, and a covariant immutable version which may specialize the inherited implementations to exploit structural sharing. This design works well with declaration-site annotations, but the large number of interfaces carry a complexity cost for clients of the library. And modifying the library interface may not be an option—in particular, one goal when adding generics to Java was to maintain binary backwards compatibility.

On the other hand, Java wildcards are themselves complex. In a conference presentation Joshua Bloch criticized them as being too hard to understand and use, stating that when adding support for closures "we simply cannot afford another wildcards". Early versions of Scala used use-site variance annotations but programmers found them difficult to use in practice, while declaration-site annotations were found to be very helpful when designing classes. Later versions of Scala added Java-style existential types and wildcards; however, according to Martin Odersky, if there were no need for interoperability with Java then these would probably not have been included.

Ross Tate argues that part of the complexity of Java wildcards is due to the decision to encode use-site variance using a form of existential types. The original proposals used special-purpose syntax for variance annotations, writing List<+Animal> instead of Java's more verbose List<? extends Animal> .

Since wildcards are a form of existential types they can be used for more things than just variance. A type like List<?> ("a list of unknown type") lets objects be passed to methods or stored in fields without exactly specifying their type parameters. This is particularly valuable for classes such as Class where most of the methods do not mention the type parameter.

However, type inference for existential types is a difficult problem. For the compiler implementer, Java wildcards raise issues with type checker termination, type argument inference, and ambiguous programs. In general it is undecidable whether a Java program using generics is well-typed or not, so any type checker will have to go into an infinite loop or time out for some programs. For the programmer, it leads to complicated type error messages. Java type checks wildcard types by replacing the wildcards with fresh type variables (so-called capture conversion). This can make error messages harder to read, because they refer to type variables that the programmer did not directly write. For example, trying to add a Cat to a List<? extends Animal> will give an error like

method List.add (capture#1) is not applicable (actual argument Cat cannot be converted to capture#1 by method invocation conversion) where capture#1 is a fresh type-variable: capture#1 extends Animal from capture of ? extends Animal

Since both declaration-site and use-site annotations can be useful, some type systems provide both.