Editing Subtyping (section)

==Function types==

If {{math|1=''T''<sub>1</sub> → ''T''<sub>2</sub>}} is a function type, then a subtype of it is any function type {{math|1=''S''<sub>1</sub> → ''S''<sub>2</sub>}} with the property that {{math|1=''T''<sub>1</sub> <: ''S''<sub>1</sub>}} and {{math|1=''S''<sub>2</sub> <: ''T''<sub>2</sub>.}} This can be summarised using the following [[typing rule]]:

<math display="block">{T_1 \leq: S_1 \quad S_2 \leq: T_2}
\over
{S_1 \rightarrow S_2 \leq: T_1 \rightarrow T_2}
</math>

The parameter type of {{math|1=''S''<sub>1</sub> → ''S''<sub>2</sub>}} is said to be [[Covariance and contravariance (computer science)|contravariant]] because the subtyping relation is reversed for it, whereas the return type is [[Covariance and contravariance (computer science)|covariant]]. Informally, this reversal occurs because the refined type is "more liberal" in the types it accepts and "more conservative" in the type it returns. This is what exactly works in [[Scala (programming language)|Scala]]: a ''n''-ary function is internally a class that inherits the <math>\mathtt{ Function_N({-A_1}, {-A_2}, \dots, {-A_n}, {+B})}</math> [[Trait (computer programming)|trait]] (which can be seen as a general [[Application programming interface|interface]] in [[Java (programming language)|Java]]-like languages), where <math>\mathtt{A_1, A_2, \dots, A_n}</math> are the parameter types, and <math>\mathtt{B}</math> is its return type; "−" before the type means the type is contravariant while "+" means covariant.

In languages that allow side effects, like most object-oriented languages, subtyping is generally not sufficient to guarantee that a function can be safely used in the context of another. Liskov's work in this area focused on [[behavioral subtyping]], which besides the type system safety discussed in this article also requires that subtypes preserve all [[Invariant (computer science)|invariants]] guaranteed by the supertypes in some [[Design by Contract|contract]].<ref name="LSP">Barbara Liskov, Jeannette Wing, ''[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.1223 A behavioral notion of subtyping]'', ACM Transactions on Programming Languages and Systems, Volume 16, Issue 6 (November 1994), pp. 1811–1841. An updated version appeared as CMU technical report: {{cite web|url=http://reports-archive.adm.cs.cmu.edu/anon/1999/CMU-CS-99-156.ps|title=Behavioral Subtyping Using Invariants and Constraints|last=Liskov|first=Barbara|author-link=Barbara Liskov|author2=Wing, Jeannette |author-link2=Jeannette Wing |date=July 1999|format=[[PostScript|PS]]|access-date=2006-10-05}}</ref> This definition of subtyping is generally [[undecidable problem|undecidable]], so it cannot be verified by a [[type checker]].

The subtyping of [[Immutable object|mutable reference]]s is similar to the treatment of parameter values and return values. Write-only references (or ''sinks'') are contravariant, like parameter values; read-only references (or ''sources'') are covariant, like return values. Mutable references which act as both sources and sinks are invariant.