Subtyping

In <a href="/facts/Programming_language_theory/MfecfTFI">programming language theory</a>, subtyping (also called subtype polymorphism or inclusion polymorphism) is a form of <a href="/facts/Polymorphism_(computer_science)/S3cCKsVT">type polymorphism</a>. A subtype is a <a href="/facts/Datatype/fcx5hgVL">datatype</a> that is related to another datatype (the supertype) by some notion of <a href="/facts/Substitutability/r2vHVwa5">substitutability</a>, meaning that program elements (typically <a href="/facts/Subroutines/9vFJrg0A">subroutines</a> or functions), written to operate on elements of the supertype, can also operate on elements of the subtype. 
If S is a subtype of T, the subtyping <a href="/facts/Binary_relation/r9BwGgaK">relation</a> (written as S <: T,  S ⊑ T, or  S ≤: T ) means that any term of type S can safely be used in any context where a term of type T is expected. The precise semantics of subtyping here crucially depends on the particulars of how "safely be used" and "any context" are defined by a given <a href="/facts/Formal_language/crDTyP8q">type formalism</a> or <a href="/facts/Programming_language/cWTYbgWa">programming language</a>. The <a href="/facts/Type_system/Tz0bAMS9">type system</a> of a programming language essentially defines its own subtyping relation, which may well be <a href="/facts/Identity_relation/wh0QoWzS">trivial</a>, should the language support no (or very little) conversion mechanisms.
Due to the subtyping relation, a term may belong to more than one type. Subtyping is therefore a form of type polymorphism. In <a href="/facts/Object-oriented_programming/TxNMEcao">object-oriented programming</a> the term 'polymorphism' is commonly used to refer solely to this subtype polymorphism, while the techniques of <a href="/facts/Parametric_polymorphism/ETb0G1zd">parametric polymorphism</a> would be considered <a href="/facts/Generic_programming/kqtqJk7p">generic programming</a>.
<a href="/facts/Functional_programming_languages/cdxqPEIM">Functional programming languages</a> often allow the subtyping of <a href="/facts/Record_(computer_science)/1fvSgenB">records</a>. Consequently, <a href="/facts/Simply_typed_lambda_calculus/5RQlXLjy">simply typed lambda calculus</a> extended with record types is perhaps the simplest theoretical setting in which a useful notion of subtyping may be defined and studied. Because the resulting calculus allows terms to have more than one type, it is no longer a "simple" <a href="/facts/Type_theory/xj0xzVqI">type theory</a>. Since functional programming languages, by definition, support <a href="/facts/Function_literals/2vdyE4zL">function literals</a>, which can also be stored in records, records types with subtyping provide some of the features of object-oriented programming. Typically, functional programming languages also provide some, usually restricted, form of parametric polymorphism. In a theoretical setting, it is desirable to study the interaction of the two features; a common theoretical setting is <a href="/facts/System_F-sub/sJ73ej8w">system F<:</a>. Various calculi that attempt to capture the theoretical properties of object-oriented programming may be derived from system F<:.
The concept of subtyping is related to the linguistic notions of <a href="/facts/Hyponymy/bjxUuoRb">hyponymy</a> and <a href="/facts/Holonymy/Vgl30GYl">holonymy</a>. It is also related to the concept of <a href="/facts/Bounded_quantification/ah38uAab">bounded quantification</a> in mathematical logic (see <a href="/facts/Order-sorted_logic/GBbEnWqG">Order-sorted logic</a>). Subtyping should not be confused with the notion of (class or object) <a href="/facts/Inheritance_(object-oriented_programming)/a7R1xv8n">inheritance</a> from object-oriented languages; subtyping is a relation between types (interfaces in object-oriented parlance) whereas inheritance is a relation between implementations stemming from a language feature that allows new objects to be created from existing ones. In a number of object-oriented languages, subtyping is called interface inheritance, with inheritance referred to as implementation inheritance.

Subtyping open-in-new

Subtyping