|
|
| Line 1: |
Line 1: |
| Many [[programming language]] [[type system]]s support [[subtyping]]. For instance, if {{C sharp|Cat}} is subtype of {{C sharp|Animal}}, then an expression of type {{C sharp|Cat}} can be used whenever an expression of type {{C sharp|Animal}} could. '''Variance''' refers to how subtyping between more complex types (list of {{C sharp|Cat}}s versus list of {{C sharp|Animal}}s, function returning {{C sharp|Cat}} versus function returning {{C sharp|Animal}}, ...) relates to subtyping between their components. Depending on the variance of the [[type constructor]], the subtyping relation may be either preserved, reversed, or ignored. For example, in [[C Sharp (programming language)|C#]] :
| | Nice to meet you, my title is Refugia. Her spouse and her live in Puerto Rico but she will have to transfer 1 working day or an additional. My working day occupation is a librarian. Doing ceramics is what my family members and I enjoy.<br><br>My webpage; diet meal delivery ([http://url.b17.my/dietdelivery10007 simply click the up coming internet page]) |
| | |
| * {{C sharp|IEnumerable<Cat>}} is a subtype of {{C sharp|IEnumerable<Animal>}}, because the {{C sharp|IEnumerable<T>}} type constructor is '''covariant'''. Note how original subtyping of the interface's type argument is preserved.
| |
| | |
| * {{C sharp|Action<Cat>}} is a supertype of {{C sharp|Action<Animal>}}, because the {{C sharp|Action<T>}} type constructor is '''contravariant''' (An {{C sharp|Action<T>}} represents a first-class function expecting an argument of type {{C sharp|T}} or {{C sharp|sub-T}}). Note how the subtyping of {{C sharp|T}} is reversed while encapsulated by an {{C sharp|Action}}, but preserved once supplied as an argument to the underlying function.
| |
| | |
| * Neither {{C sharp|IList<Cat>}} or {{C sharp|IList<Animal>}} is a subtype of the other, because the {{C sharp|IList<T>}} type constructor is '''invariant'''.
| |
| | |
| A programming language designer will consider variance when devising typing rules for e.g. arrays, inheritance, and generic datatypes. By making type constructors covariant or contravariant instead of invariant, more programs will be accepted as well-typed. On the other hand, programmers often find contravariance unintuitive, and accurately tracking variance to avoid runtime type errors can lead to complex typing rules. In order to keep the type system simple and allow useful programs, a language may treat a type constructor as invariant even if it would be safe to consider it variant, or treat it as covariant even when that can violate type safety.
| |
| | |
| ==Formal definition==
| |
| | |
| Within the [[type system]] of a [[programming language]], a typing rule or a type constructor is:
| |
| | |
| * '''covariant''' if it preserves the [[subtype|ordering, ≤, of types]], which orders types from more specific to more generic;
| |
| * '''contravariant''' if it reverses this ordering;
| |
| * '''invariant''' if neither of these applies.
| |
| | |
| In the rest of the article, we will consider how this applies to some common type constructors.
| |
| | |
| ==Arrays==
| |
| | |
| First consider the [[array data type|array type]] constructor: from the type {{java|Animal}} we can make the type {{java|Animal[]}} ("array of animals"). Should we treat this as
| |
| * Covariant: a {{java|Cat[]}} is a {{java|Animal[]}}
| |
| * Contravariant: a {{java|Animal[]}} is a {{java|Cat[]}}
| |
| * or neither (invariant)?
| |
| | |
| If we wish to avoid type errors, and the array supports both reading and writing elements, then only the third choice is safe. Clearly, not every {{java|Animal[]}} can be treated as if it were a {{java|Cat[]}}, since a client reading from the array will expect a {{java|Cat}}, but an {{java|Animal[]}} may contain e.g. a {{java|Dog}}. So the contravariant rule is not safe.
| |
| | |
| Conversely, a {{java|Cat[]}} can not be treated as a {{java|Animal[]}}. It should always be possible to put a {{java|Dog}} into a {{java|Animal[]}}. With covariant arrays this can not be guaranteed to be safe, since the backing store might actually be an array of cats. So the covariant rule is also not safe—the array constructor should be '''invariant'''. Note that this is only an issue for mutable arrays; the covariant rule is safe for immutable (read-only) arrays.
| |
| | |
| This illustrates a general phenomenon. Read-only data types (sources) can be covariant; write-only data types (sinks) can be contravariant. Mutable data types which act as both sources and sinks should be invariant.
| |
| | |
| ===Covariant arrays in Java and C#===
| |
| | |
| Early versions of Java and C# did not include generics (a.k.a. parametric polymorphism). In such a setting, making arrays invariant rules out useful polymorphic programs.
| |
| | |
| For example, consider writing a function to shuffle an array, or a function that tests two arrays for equality using the {{Javadoc:SE|java/lang|Object}}.{{java|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
| |
| <source lang="java">
| |
| boolean equalArrays (Object[] a1, Object[] a2);
| |
| void shuffleArray(Object[] a);
| |
| </source>
| |
| However, if array types were treated as invariant, it would only be possible to call these functions on an array of exactly the type {{java|Object[]}}. One could not, for example, shuffle an array of strings.
| |
| | |
| Therefore, both Java and C# treat array types covariantly.
| |
| For instance, in C# {{C sharp|string[]}} is a subtype of <code>object[]</code>, and in Java {{java|String[]}} is a subtype of {{java|Object[]}}.
| |
| | |
| As discussed above, covariant arrays leads to problem with writes into the array. Java and C# deals with this by marking each array object with a type when it is created. Each time a value is stored into an array, the compiler inserts a check that the run-time type of the value is equal to the run-time type of the array. If there is a mismatch, an {{java|ArrayStoreException}} (or {{C sharp|ArrayTypeMismatchException}} in C#) is thrown:
| |
| | |
| <source lang="java">
| |
| // a is a single-element array of String
| |
| String[] a = new String[1];
| |
| | |
| // b is an array of Object
| |
| Object[] b = a;
| |
| | |
| // Assign an Integer to b. This would be possible if b really were
| |
| // an array of Object, but since it really is an array of String,
| |
| // we will get a java.lang.ArrayStoreException.
| |
| b[0] = 1;
| |
| </source>
| |
| | |
| In the above example you can '''read''' from b safely. It is only trying to '''write''' to the array that can lead to trouble.
| |
| | |
| One drawback of this approach is that it leaves the possibility of a run-time error which a stricter type system could have caught at compile-time. Also, it hurts performance because each write into an array requires an additional runtime check.
| |
| | |
| With the addition of generics, Java and C# now offer type safe ways to write this kind of polymorphic functions. The array comparison and shuffling functions can be given the parameterized types
| |
| <source lang="java">
| |
| <T> boolean equalArrays (T[] a1, T[] a2);
| |
| <T> void shuffleArray(T[] a);
| |
| </source>
| |
| Alternatively, to enforce that a C# method accesses a collection in a read-only way, one can use the interface {{C sharp|IEnumerable<object>}} instead of passing it an array {{C sharp|object[]}}.
| |
| | |
| ==Function types==
| |
| | |
| Languages with [[first-class functions]] have [[function type]]s like "a function expecting a Cat and returning an Animal" (written {{OCaml|Cat -> Animal}} in [[OCaml]] syntax or {{Csharp|Func<Cat,Animal>}} in [[C Sharp (programming language)|C#]] syntax).
| |
| | |
| Those languages also need to specify when one function type is a subtype of another—that is, when it is safe to use a function of one type in a context that expects a function of a different type.
| |
| A moment's thought shows that it is safe to substitute a function ''f'' instead of a function ''g'' if ''f'' accepts a more general type of arguments and returns a more specific type than ''g''.
| |
| For example, a function of type {{OCaml|Cat->Cat}} can safely be used wherever a {{OCaml|Cat->Animal}} was expected, and likewise a function of type {{OCaml|Animal->Animal}} can be used wherever a {{OCaml|Cat->Animal}} was expected. The general rule is
| |
| | |
| <blockquote>
| |
| S<sub>1</sub> → S<sub>2</sub> ≤ T<sub>1</sub> → T<sub>2</sub> if T<sub>1</sub> ≤ S<sub>1</sub> and S<sub>2</sub> ≤ T<sub>2</sub>.
| |
| </blockquote>
| |
| | |
| In other words, the → type constructor is '''contravariant in the input type''' and '''covariant in the output type'''. This rule was first stated formally by Luca Cardelli.<ref>
| |
| {{cite conference|author=Luca Cardelli |title=A semantics of multiple inheritance |conference=Semantics of Data Types (International Symposium Sophia-Antipolis, France, June 27 – 29, 1984) |year=1984 |url=http://lucacardelli.name/Papers/Inheritance%20(Semantics%20of%20Data%20Types).pdf |series=Lecture Notes in Computer Science |volume=173 |publisher=Springer |doi=10.1007/3-540-13346-1_2}}(Longer version in Information and Computation, 76(2/3): 138-164, February 1988.)</ref>
| |
| | |
| When dealing with [[higher-order function|functions that take functions as arguments]], this rule can be applied several times. For example, by applying the rule twice, we see that (A'→B)→B ≤ (A→B)→B if A'≤A. In other words, the type (A→B)→B is ''covariant'' in the A position. For complicated types it can be confusing to mentally trace why a given type specialization is or isn't type-safe, but it is easy to calculate which positions are co- and contravariant: a position is covariant if it is on the left side of an even number of arrows.
| |
| | |
| == Inheritance in object oriented languages ==
| |
| | |
| When a subclass [[Method overriding|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, 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 (argument type contravariance).
| |
| | |
| For the following examples, suppose that {{java|Cat}} is a subclass of {{java|Animal}}, and that we have a base class (using Java syntax)
| |
| | |
| <source lang="java">
| |
| class AnimalShelter {
| |
| Animal getAnimalForAdoption() {
| |
| ...
| |
| }
| |
|
| |
| void putAnimal(Animal animal) {
| |
| ...
| |
| }
| |
| }
| |
| </source>
| |
| | |
| Now the question is: if we subclass {{java|AnimalShelter}}, what types are we allowed to give to {{java|getAnimalForAdoption}} and {{java|putAnimal}}?
| |
| | |
| ===Covariant method return type===
| |
| | |
| In a language which allows covariant return types, a derived class can override the {{java|getAnimalForAdoption}} method to return a more specific type:
| |
| | |
| <source lang="java">
| |
| class CatShelter extends AnimalShelter {
| |
| Cat getAnimalForAdoption() {
| |
| return new Cat();
| |
| }
| |
| }
| |
| </source>
| |
| | |
| Among mainstream OO languages, [[Java (Programming language)|Java]] and [[C++]] support covariant return types, while [[C Sharp (programming language)|C#]] does not. Adding the covariant return type was one of the first modifications of the C++ language approved by the standards committee in 1998.<ref>{{cite news |last=Allison |first=Chuck |url=http://www.drdobbs.com/184403580 |title=What's New in Standard C++?}}</ref> [[Scala (programming language)|Scala]] and [[D (programming language)|D]] also support covariant return types.
| |
| | |
| ===Contravariant method argument type===
| |
| | |
| Similarly, it is type safe to allow an overriding method to accept a more general argument than the method in the base class:
| |
| | |
| <source lang="java">
| |
| class CatShelter extends AnimalShelter {
| |
| void putAnimal(Object animal) {
| |
| ...
| |
| }
| |
| }
| |
| </source>
| |
| | |
| Not many object oriented languages actually allow this—C++ and Java would interpret this as an unrelated method with an [[Function overloading|overloaded]] name.
| |
| | |
| However, [[Sather]] supports both covariance and contravariance. Calling convention for overridden methods are covariant with ''out'' arguments and return values, and contravariant with normal arguments (with the mode ''in'').
| |
| | |
| ===Covariant method argument type===
| |
| | |
| Uniquely among mainstream languages, [[Eiffel (programming language)|Eiffel]] allows the arguments of an overriding method to have a ''more'' specific type than the method in the superclass (argument type covariance). Thus, the Eiffel version of the following code would type check, with {{java|putAnimal}} overriding the method in the base class:
| |
| | |
| <source lang="java">
| |
| class CatShelter extends AnimalShelter {
| |
| void putAnimal(Cat animal) {
| |
| ...
| |
| }
| |
| }
| |
| </source>
| |
| | |
| This is not type safe. By up-casting a {{java|CatShelter}} to an {{java|AnimalShelter}}, one can place a dog in a cat shelter. The lack of type safety (known as the "catcall problem" in the Eiffel community) 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 <ref>{{cite conference|title=Static Typing |author=Bertrand Meyer |booktitle=OOPSLA 95 (Object-Oriented Programming, Systems, Languages and Applications), Atlanta, 1995. |month=October |year=1995 |url=http://se.ethz.ch/~meyer/publications/acm/typing.pdf}}</ref>
| |
| ,<ref name="competentCompilers">{{cite web|title=Type-safe covariance: Competent compilers can catch all catcalls |first1=Mark |last1=Howard |first2=Eric |last2=Bezault |first3=Bertrand |last3=Meyer |first4=Dominique |last4=Colnet |first5=Emmanuel |last5=Stapf |first6=Karine |last6=Arnout |first7=Markus |last7=Keller |date=April 2003 |accessdate=23 May 2013 |url=http://se.ethz.ch/~meyer/ongoing/covariance/recast.pdf}}</ref> and these have been implemented in some Eiffel compilers.
| |
| | |
| Despite the type safety problem, the Eiffel designers consider covariant argument types crucial for modeling real world requirements.<ref name="competentCompilers"/> 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 argument 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.
| |
| | |
| Another example where covariant arguments seem helpful is so-called binary methods, i.e. methods where the argument is expected to be of the same type as the object the method is called on. An example is the {{java|compareTo}} method: {{java|a.compareTo(b)}} checks whether {{java|a}} comes before or after {{java|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 {{java|Comparable}}:
| |
| | |
| <source lang="java">
| |
| interface Comparable {
| |
| int compareTo(Object o);
| |
| }
| |
| </source>
| |
| | |
| The drawback of this is that the method is specified to take an argument of type {{java|Object}}. A typical implementation would first down-cast this argument (throwing an error if it is not of the expected type):
| |
| | |
| <source lang="java">
| |
| class RationalNumber implements Comparable {
| |
| int numerator;
| |
| int denominator;
| |
|
| |
| ...
| |
|
| |
| public int compareTo(Object other) {
| |
| RationalNumber otherNum = (RationalNumber)other;
| |
| return Integer.compare(numerator*otherNum.denominator,
| |
| otherNum.numerator*denominator);
| |
| }
| |
| }
| |
| </source>
| |
| | |
| In a language with covariant arguments, the argument to compareTo could be directly given the desired type {{java|RationalNumber}}, hiding the typecast. (Of course, this would still give a runtime error if {{java|compareTo}} was then called on e.g. a {{java|String}}).
| |
| | |
| === Avoiding the need for covariant argument types ===
| |
| | |
| It is possible to use other language features to compensate for lacking covariant arguments.
| |
| | |
| In a language with '''generics''' (a.k.a. [[parametric polymorphism]]) and [[bounded quantification]], the previous examples can be written in a type-safe way
| |
| <ref>{{cite conference|title=Getting Class Correctness and System Correctness Equivalent - How to Get Covariance Right |author=Franz Weber |year=1992 |booktitle=TOOLS 8 (8th conference on Technology of Object-Oriented Languages and Systems), Dortmund, 1992 |url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.52.7872}}</ref>
| |
| . Instead of defining {{java|AnimalShelter}}, we define a parameterized class {{java|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).
| |
| | |
| <source lang="java">
| |
| class Shelter<T extends Animal> {
| |
| T getAnimalForAdoption() {
| |
| ...
| |
| }
| |
|
| |
| void putAnimal(T animal) {
| |
| ...
| |
| }
| |
| }
| |
|
| |
|
| |
| class CatShelter extends Shelter<Cat> {
| |
| Cat getAnimalForAdoption() {
| |
| ...
| |
| }
| |
|
| |
| void putAnimal(Cat animal) {
| |
| ...
| |
| }
| |
| }
| |
| </source>
| |
| | |
| Similarly, in recent versions of Java the {{java|Comparable}} interface has been parameterized, which allows the downcast to be omitted in a type-safe way:
| |
| | |
| <source lang="java">
| |
| class RationalNumber implements Comparable<RationalNumber> {
| |
| int numerator;
| |
| int denominator;
| |
|
| |
| ...
| |
|
| |
| public int compareTo(RationalNumber otherNum) {
| |
| return Integer.compare(numerator*otherNum.denominator,
| |
| otherNum.numerator*denominator);
| |
| }
| |
| }
| |
| </source>
| |
| | |
| Another language feature that can help is '''multiple dispatch'''.
| |
| One reason that binary methods are awkward to write is that in a call like {{java|a.compareTo(b)}}, selecting the correct implementation of {{java|compareTo}} really depends on the type of both {{java|a}} and {{java|b}}, but in a conventional OO language only the type of {{java|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<ref>Giuseppe Castagna, [http://portal.acm.org/citation.cfm?id=203096&dl=ACM&coll=&CFID=15151515&CFTOKEN=6184618 Covariance and contravariance: conflict without a cause], ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 17, Issue 3, May 1995, pages 431-447.</ref> observed that in a typed language with multiple dispatch, a generic function can have some arguments which control dispatch and some "left-over" arguments 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 arguments. On the other hand, to ensure type safety the language still must require the left-over arguments 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: there only one argument is used for method selection (the receiver object, passed along to a method as the hidden argument {{java|this}}), and indeed the type of {{java|this}} is more specialized inside overriding methods than in the superclass.
| |
| | |
| Castagna suggests that examples where you want covariant argument types, in particular binary methods, should be handled using multiple dispatch which is naturally covariant.
| |
| Unfortunately, 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.
| |
| | |
| {| class="wikitable" border="1"
| |
| |-
| |
| ! !! Argument type !! Return type
| |
| |-
| |
| | [[C++ (programming language)|C++]] (since 1998), [[Java (programming language)|Java]] (since [[Java Platform, Standard Edition|J2SE 5.0]]), [[Scala (programming language)|Scala]], [[D (programming language)|D]] || Invariant || Covariant
| |
| |-
| |
| | [[C Sharp (programming language)|C#]] || Invariant || Invariant
| |
| |-
| |
| | [[Sather]] || Contravariant || Covariant
| |
| |-
| |
| | [[Eiffel (programming language)|Eiffel]] || Covariant || Covariant
| |
| |}
| |
| | |
| == 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 {{C sharp|IList<T>}} makes it possible to construct new types like {{C sharp|IList<Animal>}} or {{C sharp|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 Sharp (programming language)|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 (programming language)|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 Sharp (programming language)|C#]] (using the keywords {{C sharp|out}} and {{C sharp|in}}),
| |
| and [[Scala (programming language)|Scala]] and [[OCaml]] (using the keywords {{OCaml|+}} and {{OCaml|-}}).
| |
| C# only allows variance annotations for interface types, while Scala and OCaml allows them for both interface types and concrete data types.
| |
| | |
| ==== Interfaces ====
| |
| | |
| In C#, each type parameter of a generic interface can be marked covariant ({{C sharp|out}}), contravariant ({{C sharp|in}}), or invariant (no annotation). For example, we can define an interface {{C sharp|IEnumerator<T>}} of read-only iterators, and declare it to be covariant (out) in its type parameter.
| |
| <source lang="csharp">
| |
| interface IEnumerator<out T>
| |
| {
| |
| T Current { get; }
| |
| bool MoveNext();
| |
| }
| |
| </source>
| |
| With this declaration, {{C sharp|IEnumerator}} will be treated as covariant in its type argument, e.g. {{C sharp|IEnumerator<Cat>}} is a subtype of {{C sharp|IEnumerator<Animal>}}.
| |
| | |
| The typechecker enforces that each method declaration in an interface only mentions the type parameters in a way consistent with the {{C sharp|in}}/{{C sharp|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<ref>{{cite web|author=Eric Lippert |title=Exact rules for variance validity |date=3 December 2009 |accessdate=July 2013 |url=http://blogs.msdn.com/b/ericlippert/archive/2009/12/03/exact-rules-for-variance-validity.aspx}}</ref><ref>Section II.9.7 in <cite>ECMA International Standard ECMA-335 Common Language Infrastructure (CLI) 6th edition (June 2012)</cite>; [http://www.ecma-international.org/publications/standards/Ecma-335.htm available online]</ref> is that the return types of all methods in the interface must be ''valid covariantly'' and all the method argument 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 argument {{C sharp|T}} is valid covariantly if it was not marked {{C sharp|in}}, and valid contravariantly if it was not marked {{C sharp|out}}
| |
| * An array type {{C sharp|A[]}} is valid S-ly if {{C sharp|A}} is. (This is because C# has covariant arrays).
| |
| * An generic type {{C sharp|G<A1,A2,...,An>}} is valid S-ly if for each argument {{C sharp|Ai}},
| |
| ** Ai is valid S-ly, and the ''i''th parameter to {{C sharp|G}} is declared covariant, or
| |
| ** Ai is valid (not S)-ly, and the ''i''th parameter to {{C sharp|G}} is declared contravariant, or
| |
| ** Ai is valid both covariantly and contravariantly, and the ''i''th parameter to {{C sharp|G}} is declared invariant.
| |
| | |
| As an example of how these rules apply, consider the {{C sharp|IList<T>}} interface.
| |
| <source lang="csharp">
| |
| interface IList<T>
| |
| {
| |
| void Insert(int index, T item);
| |
| IEnumerator<T> GetEnumerator();
| |
| }
| |
| </source>
| |
| The argument type {{C sharp|T}} of {{C sharp|Insert}} must be valid contravariantly, i.e. the type parameter {{C sharp|T}} must not be tagged {{C sharp|out}}. Similarly, the result type {{C sharp|IEnumerator<T>}} of {{C sharp|GetEnumerator}} must be valid covariantly, i.e. (since {{C sharp|IEnumerator}} is a covariant interface) the type {{C sharp|T}} must be valid covariantly, i.e. the type parameter {{C sharp|T}} must not be tagged {{C sharp|in}}. This shows that the interface {{C sharp|IList}} is not allowed to be marked either co- or contravariant.
| |
| | |
| In the common case of a generic data structure such as {{C sharp|IList}}, these restrictions mean that an {{C sharp|out}} parameter can only be used for methods getting data out of the structure, and an {{C sharp|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, both in [[Scala (programming language)|Scala]] and [[OCaml]] the immutable list type is covariant: <source lang=scala enclose=none>List[Cat]</source> is a subtype of <source lang=scala enclose=none>List[Animal]</source>.
| |
| | |
| 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 <source lang=scala enclose=none>List[A]</source> class.
| |
| | |
| <source lang="scala">
| |
| sealed abstract class List[+A] extends AbstractSeq[A] {
| |
| def head: A
| |
| def tail: List[A]
| |
| | |
| /** Adds an element at the beginning of this list. */
| |
| def ::[B >: A] (x: B): List[B] =
| |
| new scala.collection.immutable.::(x, this)
| |
| | |
| ...
| |
| }
| |
| </source>
| |
| | |
| First, class members that have a variant type must be immutable. Here, <source lang=scala enclose=none>head</source> has the type <source lang=scala enclose=none>A</source>, which was declared covariant (<source lang=scala enclose=none>+</source>), and indeed <source lang=scala enclose=none>head</source> was declared as a method (<source lang=scala enclose=none>def</source>). Trying to declare it as a mutable field (<source lang=scala enclose=none>var</source>) 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 <source lang=scala enclose=none>::</source> which adds an element to the front of a list. (The implementation works by creating a new object of the similarly-named ''class'' <source lang=scala enclose=none>::</source>, the class of nonempty lists). The most obvious type to give it would be
| |
| <source lang=scala>
| |
| def :: (x: A): List[A]
| |
| </source>
| |
| However, this would be a type error, because the covariant parameter <source lang=scala enclose=none>A</source> appears in a contravariant position (as a function argument). But there is a trick to get around this problem. We give <source lang=scala enclose=none>::</source> a more general type, which allows adding an element of any type <source lang=scala enclose=none>B</source>
| |
| as long as <source lang=scala enclose=none>B</source> is a supertype of <source lang=scala enclose=none>A</source>. Note that this relies on <source lang=scala enclose=none>List</source> being covariant, since
| |
| <source lang=scala enclose=none>this</source> has type <source lang=scala enclose=none>List[A]</source> and we treat it as having type <source lang=scala enclose=none>List[B]</source>. 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.<ref name="tamingCombining">{{cite conference|author1=John Altidor |author2=Huang Shan Shan |author3=Yannis Smaragdakis |title=Taming the wildcards: combining definition- and use-site variance |booktitle=Proceedings of the 32nd ACM SIGPLAN conference on Programming language design and implementation (PLDI'11) |year=2011 |url=http://www.cs.umass.edu/~jaltidor/variance_pldi11.pdf}}</ref> However, the analysis can get complex for several reasons. First, the analysis is nonlocal since the variance of an interface {{java|I}} depends the variance of all interfaces that {{java|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<ref>{{cite web|title=Covariance and Contravariance in C# Part Seven: Why Do We Need A Syntax At All? |author1= Eric Lippert |date=October 29, 2007 |accessdate=October 2013
| |
| |url=http://blogs.msdn.com/ericlippert/archive/2007/10/29/covariance-and-contravariance-in-c-part-seven-why-do-we-need-a-syntax-at-all.aspx}}</ref> 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 {{OCaml|T}} which wraps a function
| |
| <source lang="ocaml">
| |
| type ('a, 'b) t = T of ('a -> 'b)
| |
| </source>
| |
| The compiler will automatically infer that {{OCaml|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:
| |
| <source lang="ocaml">
| |
| type (-'a, +'b) t = T of ('a -> 'b)
| |
| </source>
| |
| | |
| Explicit annotations in OCaml become useful when specifying interfaces. For example, the standard library interface {{OCaml|Map.S}} for association tables include an annotation saying that the map type constructor is covariant in the result type.
| |
| <source lang="ocaml">
| |
| module type S =
| |
| sig
| |
| type key
| |
| type (+'a) t
| |
| val empty: 'a t
| |
| val mem: key -> 'a t -> bool
| |
| ...
| |
| end
| |
| </source>
| |
| This ensures that e.g. {{OCaml|IntMap.t cat}} is a subtype of {{OCaml|IntMap.t animal}}.
| |
| | |
| === 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 {{C sharp|IList}} needed to be invariant, because it contained both {{C sharp|Insert}} and {{C sharp|GetEnumerator}}. In order to expose more variance, the API designer could provide additional interfaces which provide subsets of the available methods (eg. an "insert-only list" which only provides {{C sharp|Insert}}). However this quickly becomes unwieldy.
| |
| | |
| Use-site variance annotations aim to give users of a class more opportunities for subtyping without requiring the designer of the class to define multiple interfaces with different variance. Instead, each time a class or interface is used in a type declaration, the programmer can indicate that only a subset of the methods will be used. In effect, each definition of a class also makes available interfaces for the covariant and contravariant "parts" of that class. Therefore the designer of the class no longer needs to take variance into account, increasing re-usability.
| |
| | |
| Java provides use-site variance annotations through [[Wildcard (Java)|wildcards]], a restricted form of [[bounded quantification|bounded]] [[existential type]]s. A parameterized type can be instantiated by a wildcard {{java|?}} together with an upper or lower bound, e.g. {{java|List<? extends Animal>}} or {{java|List<? super Animal>}}. (A an unbounded wildcard like {{java|List<?>}} is equivalent to {{java|List<? extends Object>}}). Such a type represents {{java|List<X>}} for some unknown type {{java|X}} which satisfies the bound. For example, if {{java|l}} has type {{java|List<? extends Animal>}}, then the typechecker will accept
| |
| <source lang="java">
| |
| Animal a = l.get(3);
| |
| </source>
| |
| because the type {{java|X}} is known to be a subtype of {{java|Animal}}, but
| |
| <source lang="java">
| |
| l.add(new Animal())
| |
| </source>
| |
| will be rejected as a type error since an {{java|Animal}} is not necessarily an {{java|X}}. In general, given some interface {{java|I<T>}}, a reference to a {{java|I<? extends A>}} forbids using methods from the interface where {{java|T}} occurs contravariantly in the type of the method. Conversely, if {{java|l}} had type {{java|List<? super Animal>}} one could call {{java|l.add}} but not {{java|l.get}}.
| |
| | |
| [[File:Java wildcard subtyping.svg|thumb|right|350px|Wildcard subtyping in Java can be visualized as a cube.]]
| |
| | |
| While plain generic types in Java are invariant (e.g. there is no subtyping relationship between {{java|List<Cat>}} and {{java|List<Animal>}}), wildcard types can be made more specific by specifying a tighter bound, for example {{java|List<? extends Cat>}} is a subtype of {{java|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 {{java|C<? extends T>}}, there are three ways to form a subtype: by specializing the class {{java|C}}, by specifying a tighter bound {{java|T}}, or by replacing the wildcard {{java|?}} by a specific type (see figure).
| |
| | |
| By combining two steps of subtyping, it is therefore possible to e.g. pass an argument of type {{java|List<Cat>}} to a method expecting a {{java|List<? extends Animal>}}. This is exactly the kind of programs that covariant interface types allow. The type {{java|List<? extends Animal>}} acts as an interface type containing only the covariant methods of {{java|List<T>}}, but the implementer of {{java|List<T>}} did not have to define it ahead of time. This is use-site variance.
| |
| | |
| In the common case of a generic data structure {{C sharp|IList}}, covariant parameters are used for methods getting data out of the structure, and contravariant parameters for methods putting data into the structure. The mnemonics PECS (Producer Extends, Consumer Super) 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 {{Javadoc:SE|java/lang|Comparable}} interface. Suppose we want to write a function that finds the biggest element in a collection. The elements need to implement the {{java|compareTo}} method, so a first try might be
| |
| <source lang="java">
| |
| <T extends Comparable<T>> T max(Collection<T> coll);
| |
| </source>
| |
| However, this type is not general enough—one can find the max of a {{java|Collection<Calendar>}}, but not a {{java|Collection<GregorianCalendar>}}. The problem is that {{Javadoc:SE|java/util|GregorianCalendar}} does not implement {{java|Comparable<GregorianCalendar>}}, but instead the (better) interface {{java|Comparable<Calendar>}}. In Java, unlike in C#, {{java|Comparable<Calendar>}} is not considered a subtype of {{java|Comparable<GregorianCalendar>}}. Instead the type of {{java|max}} has to be modified:
| |
| <source lang="java">
| |
| <T extends Comparable<? super T>> T max(Collection<T> coll);
| |
| </source>
| |
| The bounded wildcard {{java|? super T}} conveys the information that {{java|max}} calls only contravariant methods from the {{java|Comparable}} interface. This particular example is frustrating because ''all'' the methods in {{java|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 {{java|Comparable}}.
| |
| | |
| === 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<ref name="tamingCombining" /> found that 39% of wildcard annotations could have been directly replaced by a declaration-site annotations. Thus the remaining 61% is an indication on 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 versions of each interface: a base interface which is invariant but does not export any mutating methods, a mutable version which adds side-effecting methods, and an immutable version which does not add any methods but (usually) marks the type parameter as covariant.<ref>{{cite web|title=The Scala 2.8 Collections API |author1=Marin Odersky |author2=Lex Spoon |date=September 7, 2010 |accessdate=May 2013 |url=http://www.scala-lang.org/docu/files/collections-api/collections.html}}</ref> 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<ref>{{cite web|author=Joshua Bloch |title=The Closures Controversy [video] |date=November 2007 |place=Presentation at Javapolis'07 |url=http://parleys.com/play/514892250364bc17fc56bb15/chapter0/about |accessdate=May 2013}}</ref> [[Joshua Bloch]] criticized them as being too hard to understand and use, stating that when adding support for [[Closure (computer science)|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.<ref>{{cite conference |author1=Martin Odersky |author2=Matthias Zenger |title=Scalable component abstractions |booktitle=Proceedings of the 20th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications (OOPSLA '05) |year=2005 |url=http://lampwww.epfl.ch/~odersky/papers/ScalableComponent.pdf}}</ref> 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.<ref>{{cite web|title=The Purpose of Scala's Type System: A Conversation with Martin Odersky, Part III |author=Bill Venners and Frank Sommers |date=May 18, 2009 |accessdate=May 2013 |url=http://www.artima.com/scalazine/articles/scalas_type_system.html}}</ref>
| |
| | |
| Ross Tate argues<ref name="MixedSiteVariance">{{cite conference |author1=Ross Tate |title=Mixed-Site Variance |booktitle=FOOL '13: Informal Proceedings of the 20th International Workshop on Foundations of Object-Oriented Languages |year=2013 |url=http://www.cs.cornell.edu/~ross/publications/mixedsite/index.html}}</ref> 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<ref>
| |
| {{cite conference|author1=Atsushi Igarashi |author2=Mirko Viroli |title=On Variance-Based Subtyping for Parametric Types |booktitle=Proceedings of the 16th European Conference on Object-Oriented Programming (ECOOP '02) |year=2002 |url=http://www.sato.kuis.kyoto-u.ac.jp/~igarashi/papers/pdf/variance.ecoop02.pdf}}</ref>
| |
| <ref>{{cite conference|author1=Kresten Krab Thorup |author2=Mads Torgersen |title=Unifying Genericity: Combining the Benefits of Virtual Types and Parameterized Classes |booktitle=Object-Oriented Programming (ECOOP '99) |year=1999 |url=http://www.daimi.au.dk/~madst/tool/papers/unifying.pdf}}</ref> used special-purpose syntax for variance annotations, writing {{java|List<+Animal>}} instead of Java's more verbose {{java|List<? extends Animal>}}.
| |
| | |
| Since wildcards are a form of existential types they can be used for more things than just variance. A type like {{java|List<?>}} ("some type of list") lets objects be passed to methods or stored in fields without exactly specifying their type parameters. This is particularly valuable for classes such as {{Javadoc:SE|java/lang|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.<ref>{{cite conference|title=Taming wildcards in Java's type system |first1=Ross |last1=Tate |first2=Alan |last2=Leung |first3=Sorin |last3=Lerner |booktitle=Proceedings of the 32nd ACM SIGPLAN conference on Programming language design and implementation (PLDI '11) |year=2011 |url=http://www.cs.cornell.edu/~ross/publications/tamewild/}}</ref> For the programmer, it leads to complicated type error messages. Java typechecks 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 {{java|Cat}} to a {{java|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 system provide both.<ref name=tamingCombining /><ref name="MixedSiteVariance" />
| |
| | |
| ===Covariant generics in Dart===
| |
| | |
| The [[Dart (programming language)|Dart]] programming language does not track variance, and instead treats all parameterized types as covariant. The language specification<ref>{{cite web|title=The Dart Programming Language Specification |date=May 6, 2013 |accessdate=May 2013 |url=http://www.dartlang.org/docs/spec/}}</ref> states
| |
| <blockquote>
| |
| The type system is unsound, due to the covariance of generic types. This is a deliberate choice (and undoubtedly controversial). Experience has shown that sound type rules for generics fly in the face of programmer intuition. It is easy for tools to provide a sound type analysis if they choose, which may be useful for tasks like refactoring.
| |
| </blockquote>
| |
| | |
| ==Origin of the term "covariance" ==
| |
| | |
| These terms come from the notion of [[covariance and contravariance of functors|covariant and contravariant functors]] in [[category theory]]. Consider the category <math>C</math> 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 <math>C^2</math> to objects in <math>C</math>. By the subtyping rule for function types this operation reverses ≤ for the first argument and preserves it for the second, so it is a contravariant functor in the first argument and a covariant functor in the second.
| |
| | |
| ==See also==
| |
| | |
| * [[Polymorphism (computer science)]]
| |
| * [[Inheritance (computer science)]]
| |
| | |
| == References ==
| |
| <references/>
| |
| | |
| ==External links==
| |
| * [http://blogs.msdn.com/ericlippert/archive/tags/Covariance+and+Contravariance/default.aspx Fabulous Adventures in Coding]: An article series about implementation concerns surrounding co/contravariance in C#
| |
| * [http://c2.com/cgi/wiki?ContraVsCoVariance Contra Vs Co Variance] (note this article is not updated about C++)
| |
| * [http://www.javac.info/closures-v05.html Closures for the Java 7 Programming Language (v0.5)]
| |
| | |
| {{DEFAULTSORT:Covariance And Contravariance (Computer Science)}}
| |
| [[Category:Object-oriented programming]]
| |
| [[Category:Type theory]]
| |
| [[Category:Polymorphism (computer science)]]
| |