Covariance and contravariance (computer science): Difference between revisions

Revision as of 14:24, 18 March 2025

Latest revision as of 07:58, 19 August 2025

(6 intermediate revisions by 3 users not shown)

Line 1:

{{Short description|Programming language concept}}{{Lead rewrite|date=March 2025}}
{{Type systems}}

Many [[programming language]] [[type system]]s support [[subtyping]]. For instance, if the [[type (computer science)|type]] {{C sharp|Cat}} is a subtype of {{C sharp|Animal}}, then an [[expression (computer science)|expression]] of type {{C sharp|Cat}} [[Liskov_substitution_principle|should be substitutable]] wherever an expression of type {{C sharp|Animal}} is used.

'''Variance''' is howthe subtypingcategory of possible relationships between more [[composite type|complex types]] relates to subtyping betweenand their components' subtypes. ForA examplelanguage's chosen variance determines the relationship between, howfor shouldexample, a [[list (programming)|list]] of {{C sharp|Cat}}s relate toand a list of {{C sharp|Animal}}s? Or how, shouldor a [[Function (computer science)|function]] that [[return value|return]]sing {{C sharp|Cat}} relate toand a function that returnsreturning {{C sharp|Animal}}?.

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 the [[OCaml]] programming language, for example, "list of Cat" is 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.

Line 18 ⟶ 19:

* ''covariant'' if it preserves the [[subtyping|ordering of types (≤)]], which orders types from more specific to more generic: If <code>A ≤ B</code>, then <code>I<nowiki><A> ≤ I<B></nowiki></code>;

* ''contravariant'' if it reverses this ordering: If <code>A ≤ B</code>, then <code>I<nowiki><B> ≤ I<A></nowiki></code>;

* ''bivariant'' if both of these apply (i.e., if <code>A ≤ B</code>, then <code>I<nowiki><A> ≡ I<B></nowiki></code>);<ref>{{notetag|1=This only happens in a pathological case. For example, <code>I<T> = int</code>: any type can be put in for <code>T</code> and the result is still <code>int</code>.</ref>}}

* ''variant'' if covariant, contravariant or bivariant;

* ''invariant'' or ''nonvariant'' if not variant.

Line 475 ⟶ 476:

On the other hand, Java wildcards are themselves complex. In a conference presentation<ref>{{cite web |first=Joshua |last=Bloch |title=The Closures Controversy [video] |date=November 2007 |place=Presentation at Javapolis'07 |url=http://parleys.com/play/514892250364bc17fc56bb15/chapter0/about |url-status=dead |archive-url=https://web.archive.org/web/20140202190630/http://parleys.com/play/514892250364bc17fc56bb15/chapter0/about |archive-date=2014-02-02 }}</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 |first1=Martin |last1=Odersky |first2=Matthias |last2=Zenger |title=Scalable component abstractions |book-title=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 |publisher=ACM |isbn=1595930310 |pages=41–57 |doi=10.1145/1094811.1094815 |citeseerx=10.1.1.176.5313}}</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 |first1=Bill |last1=Venners |first2=Frank |last2=Sommers |date=May 18, 2009 |access-date=16 August 2016 |url=http://www.artima.com/scalazine/articles/scalas_type_system.html}}</ref>

Ross Tate argues<ref name="MixedSiteVariance">{{cite conference |first=Ross |last=Tate |title=Mixed-Site Variance |book-title=FOOL '13: Informal Proceedings of the 20th International Workshop on Foundations of Object-Oriented Languages |year=2013 |url=httphttps://www.cs.cornell.edu/~ross/publications/mixedsite/index.html |citeseerx=10.1.1.353.4691}}</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 |first1=Atsushi |last1=Igarashi |first2=Mirko |last2=Viroli |title=On Variance-Based Subtyping for Parametric Types |book-title=Proceedings of the 16th European Conference on Object-Oriented Programming (ECOOP '02) |year=2002 |isbn=3-540-47993-7 |pages=441–469 |doi=10.1007/3-540-47993-7_19 |series=Lecture Notes in Computer Science |volume=2374 |citeseerx=10.1.1.66.450}}</ref><ref>{{cite conference |first1=Kresten Krab |last1=Thorup |first2=Mads |last2=Torgersen |title=Unifying Genericity: Combining the Benefits of Virtual Types and Parameterized Classes |book-title=Object-Oriented Programming (ECOOP '99) |publisher=Springer |date=1999 |isbn=3-540-48743-3 |pages=186–204 |doi=10.1007/3-540-48743-3_9 |series=Lecture Notes in Computer Science |volume=1628 |citeseerx=10.1.1.91.9795 }}</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<?>}} ("a list of unknown type"<ref>{{cite web |url=https://docs.oracle.com/javase/tutorial/java/generics/unboundedWildcards.html |title=The Java™ Tutorials, Generics (Updated), Unbounded Wildcards |access-date=July 17, 2020}}</ref>) 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 |book-title=Proceedings of the 32nd ACM SIGPLAN conference on Programming language design and implementation (PLDI '11) |year=2011 |url=httphttps://www.cs.cornell.edu/~ross/publications/tamewild/ |pages=614–627 <!-- |doi=1145/1993498.1993570 --> |isbn=9781450306638 |citeseerx=10.1.1.739.5439}}</ref> In general it is [[Undecidable problem|undecidable]] whether a Java program using generics is well-typed or not,<ref>{{cite conference |first=Radu |last=Grigore | title=Java generics are turing complete | book-title=Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages (POPL'17) | year=2017 | arxiv=1605.05274 | bibcode=2016arXiv160505274G |isbn=9781450346603 |pages=73–85 <!-- |doi=10.1145/3009837.3009871 --> }}</ref> 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 {{java|Cat}} to a {{java|List<? extends Animal>}} will give an error like

method List.add (capture#1) is not applicable

Line 496 ⟶ 497:

* [[Inheritance (object-oriented programming)]]

* [[Liskov substitution principle]]

== Notes ==

{{notefoot}}

== References ==