Editing Subtyping (section)

== Subsumption ==

In type theory the concept of ''subsumption''<ref>Benjamin C. Pierce, ''Types and Programming Languages'', MIT Press, 2002, 15.1 "Subsumption", p. 181-182</ref>  is used to define or evaluate whether a type '''S''' is a subtype of type '''T'''.

A type is a set of values. The set can be described ''extensionally'' by listing all the values, or it can be described ''intensionally'' by stating the membership of the set by a predicate over a domain of possible values. In common programming languages enumeration types are defined extensionally by listing values. [[User-defined type]]s like records (structs, interfaces) or classes are defined intensionally by an explicit type declaration or by using an existing value, which encodes type information, as a prototype to be copied or extended.

In discussing the concept of subsumption, the set of values of a type is indicated by writing its name in mathematical italics: {{mvar|T}}. The type, viewed as a predicate over a domain, is indicated by writing its name in bold: '''T'''. The conventional symbol '''<:''' means "is a subtype of", and ''':>''' means "is a supertype of".{{Citation needed|reason=Are &lt;: and &gt;: from the Julia language? Older usage? I don't see these symbols in Unicode or Latex|date=March 2024}}

* A type '''T''' ''subsumes'' '''S''' if the set of values {{mvar|T}} which it defines, is a superset of the set {{mvar|S}}, so that every member of {{mvar|S}} is also a member of {{mvar|T}}. 
* A type may be subsumed by more than one type: the supertypes of '''S''' intersect at {{mvar|S}}.
* If '''S <: T''' (and therefore {{math|''S'' ⊆ ''T'' }}), then '''T''', the predicate which circumscribes the set {{mvar|T}}, must be part of the predicate '''S''' (over the same domain) which defines {{mvar|S}}. 
* If '''S''' subsumes '''T''', and '''T''' subsumes '''S''', then the two types are equal (although they may not be the same type if the type system distinguishes types by name).

In terms of information specificity, a subtype is considered more specific than any one of its supertypes, because it holds at least as much information as each of them. This may increase the applicability, or ''relevance'' of the subtype (the number of situations where it can be accepted or introduced), as compared to its "more general" supertypes. The disadvantage of having this more detailed information is that it represents incorporated choices which reduce the ''prevalence'' of the subtype (the number of situations which are able to generate or produce it).

In the context of subsumption, the type definitions can be expressed using [[Set-builder notation]], which uses a predicate to define a set. Predicates can be defined over a domain (set of possible values) {{mvar|D}}. Predicates are partial functions that compare values to selection criteria. For example: "is an integer value greater than or equal to 100 and less than 200?". If a value matches the criteria then the function returns the value. If not, the value is not selected, and nothing is returned. (List comprehensions are a form of this pattern used in many programming languages.)

If there are two predicates, <math>P_T</math> which applies selection criteria for the type '''T''', and <math>P_s</math> which applies additional criteria for the type '''S''', then sets for the two types can be defined:

:<math>T = \{v \in D  \mid \ P_T(v)\}</math>

:<math>S =\{v \in D  \mid \ P_T(v)\text{ and }P_s(v)\}</math>
  
The predicate <math>\mathbf T = P_T</math> is applied alongside <math>P_s</math> as part of the compound predicate '''S''' defining {{mvar|S}}. The two predicates are ''conjoined'', so both must be true for a value to be selected. The predicate <math>\mathbf S = \mathbf T \land P_s = P_T \land P_s</math> subsumes the predicate '''T''', so {{nowrap|'''S <: T'''.}}

For example: there is a subfamily of cat species called ''Felinae'', which is part of the family ''Felidae''. The genus ''Felis'', to which the domestic cat species ''Felis catus'' belongs, is part of that subfamily.

:<math>\mathit{Felinae = \{cat \in Felidae  \mid \ ofSubfamily(cat, felinaeSubfamilyName)\}}</math>

:<math>\mathit{Felis =\{cat \in Felinae \mid \ ofGenus(cat, felisGenusName)\}}</math>

The conjunction of predicates has been expressed here through application of the second predicate over the domain of values conforming to the first predicate. Viewed as types, {{nowrap|'''Felis <: Felinae <: Felidae'''}}.

If '''T''' subsumes '''S''' ('''T :> S''') then a procedure, function or expression given a value <math>s \in S</math> as an operand (parameter value or term) will therefore be able to operate over that value as one of type '''T''', because <math>s \in T</math>. In the example above, we could expect the function ''ofSubfamily'' to be applicable to values of all three types '''Felidae''', '''Felinae''' and '''Felis'''.