Covariance and contravariance (computer science): Difference between revisions

Revision as of 20:09, 27 May 2025

Latest revision as of 07:58, 19 August 2025

(2 intermediate revisions by one other user not shown)

Line 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 109:

== 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 (bivarianceinvariance), 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):

<gallery perrow="5" heights="190" caption="Variance and method overriding: overview">

Image:Vererbung T.svg|Subtyping of the parameter/return type of the method.

Image:Inheritance_invariant.svg|''BivarianceInvariance''. The signature of the overriding method is unchanged.

Image:Inheritance_covariant_return.svg|''Covariant return type''. The subtyping relation is in the same direction as the relation between ClassA and ClassB.

Image:Inheritance_contravariant_argument.svg|''Contravariant parameter type''. The subtyping relation is in the opposite direction to the relation between ClassA and ClassB.

Line 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 497:

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

* [[Liskov substitution principle]]

== Notes ==

{{notefoot}}

== References ==