Covariance and contravariance (computer science): Difference between revisions

Revision as of 18:10, 17 October 2022

Revision as of 21:44, 5 November 2022

Line 298:

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 runtime type of both {{java|a}} and {{java|b}}, but in a conventional OO language only the runtime 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>{{cite journal |first=Giuseppe |last=Castagna |title=Covariance and contravariance: conflict without a cause |journal=ACM Transactions on Programming Languages and Systems |volume=17 |issue=3 |pages=431–447 |date=May 1995 |doi=10.1145/203095.203096 |citeseerx=10.1.1.115.5992|s2cid=15402223 }}</ref> 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 {{java|this}}), and indeed the type of {{java|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.

Line 391:

==== 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 |firstfirst1=John |lastlast1=Altidor |first2=Huang Shan |last2=Shan |first3=Yannis |last3=Smaragdakis |title=Taming the wildcards: combining definition- and use-site variance |book-title=Proceedings of the 32nd ACM SIGPLAN conference on Programming language design and implementation (PLDI'11) |year=2011 |publisher=ACM |date=2011 |isbn=9781450306638 |pages=602–613 |doi=10.1145/1993316.1993569 |citeseerx=10.1.1.225.8265 }}</ref> However, the analysis can get complex for several reasons. First, the analysis is nonlocal since the variance of an interface {{java|I}} depends on 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? |first=Eric |last=Lippert |date=October 29, 2007 |access-date=16 August 2016

Line 471:

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.<ref>{{cite web|title=The Scala 2.8 Collections API |first1=Marin |last1=Odersky |first2=Lex |last2=Spoon |date=September 7, 2010 |access-date=16 August 2016 |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&mdash;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 |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 |firstfirst1=Bill |lastlast1=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=http://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 |firstfirst1=Atsushi |lastlast1=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 |firstfirst1=Kresten Krab |lastlast1=Thorup |first2=Mads |last2=Torgersen |title=Unifying Genericity: Combining the Benefits of Virtual Types and Parameterized Classes |book-title=Object-Oriented Programming (ECOOP '99) |year=1999 |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.