| Polymorphism |
|---|
| Ad hoc polymorphism |
| Parametric polymorphism |
| Subtyping |
Inprogramming language theory,subtyping (also calledsubtype polymorphism orinclusion polymorphism) is a form oftype polymorphism. Asubtype is adatatype that is related to another datatype (thesupertype) by some notion ofsubstitutability, meaning that program elements (typicallysubroutines 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 subtypingrelation (written asS <:T, S ⊑T,[1] or S ≤:T ) means that any term of type S cansafely be used inany 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 giventype formalism orprogramming language. Thetype system of a programming language essentially defines its own subtyping relation, which may well betrivial, 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. Inobject-oriented programming the term 'polymorphism' is commonly used to refer solely to thissubtype polymorphism, while the techniques ofparametric polymorphism would be consideredgeneric programming.
Functional programming languages often allow the subtyping ofrecords. Consequently,simply typed lambda calculus extended with record types is perhaps the simplest theoretical setting in which a useful notion of subtyping may be defined and studied.[2] Because the resulting calculus allows terms to have more than one type, it is no longer a "simple"type theory. Since functional programming languages, by definition, supportfunction literals, 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 issystem F<:. 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 ofhyponymy andholonymy. It is also related to the concept ofbounded quantification in mathematical logic (seeOrder-sorted logic). Subtyping should not be confused with the notion of (class or object)inheritance from object-oriented languages;[3] 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 calledinterface inheritance, with inheritance referred to asimplementation inheritance.
The notion of subtyping in programming languages dates back to the 1960s; it was introduced inSimula derivatives. The first formal treatments of subtyping were given byJohn C. Reynolds in 1980 who usedcategory theory to formalizeimplicit conversions, andLuca Cardelli (1985).[4]
The concept of subtyping has gained visibility (and synonymy with polymorphism in some circles) with the mainstream adoption of object-oriented programming. In this context, the principle of safe substitution is often called theLiskov substitution principle, afterBarbara Liskov who popularized it in akeynote address at a conference on object-oriented programming in 1987. Because it must consider mutable objects, the ideal notion of subtyping defined by Liskov andJeannette Wing, calledbehavioral subtyping is considerably stronger than what can be implemented in atype checker. (See§ Function types below for details.)
A simple practical example of subtypes is shown in the diagram. The type "bird" has three subtypes "duck", "cuckoo" and "ostrich". Conceptually, each of these is a variety of the basic type "bird" that inherits many "bird" characteristics but has some specific differences. TheUML notation is used in this diagram, with open-headed arrows showing the direction and type of the relationship between the supertype and its subtypes.
As a more practical example, a language might allow integer values to be used wherever floating point values are expected (Integer <:Float), or it might define a generic typeNumber as a common supertype of integers and the reals. In this second case, we only haveInteger <:Number andFloat <:Number, butInteger andFloat are not subtypes of each other.
Programmers may take advantage of subtypingto write code in a more abstract manner than would be possible without it. Consider the following example:
functionmax(xasNumber,yasNumber)isifx<ythenreturnyelsereturnxend
If integer and real are both subtypes ofNumber, and an operator of comparison with an arbitrary Number is defined for both types, then values of either type can be passed to this function. However, the very possibility of implementing such an operator highly constrains the Number type (for example, one can't compare an integer with a complex number), and actually only comparing integers with integers, and reals with reals, makes sense. Rewriting this function so that it would only accept 'x' and 'y' of the same type requiresbounded polymorphism.
Subtyping enables a given type to be substituted for another type or abstraction. Subtyping is said to establish anis-a relationship between the subtype and some existing abstraction, either implicitly or explicitly, depending on language support. The relationship can be expressed explicitly via inheritance in languages that support inheritance as a subtyping mechanism.
The following C++ code establishes an explicit inheritance relationship between classesB andA, whereB is both a subclass and a subtype ofA, and can be used as anA wherever aB is specified (via a reference, a pointer or the object itself).
classA{public:voidmethodOfA()const{// ...}};classB:publicA{public:voidmethodOfB()const{// ...}};voidfunctionOnA(constA&a){a.methodOfA();}intmain(){Bb;functionOnA(b);// b can be substituted for an A.}
The following python code establishes an explicit inheritance relationship between classesB andA, whereB is both a subclass and a subtype ofA, and can be used as anA wherever aB is required.
classA:defmethod_of_a(self)->None:passclassB(A):defmethod_of_b(self)->None:passdeffunction_on_a(a:A)->None:a.method_of_a()if__name__=="__main__":b:B=B()function_on_a(b)# b can be substituted for an A.
The following example,type(a) is a "regular" type, andtype(type(a)) is a metatype. While as distributed all types have the same metatype (PyType_Type, which is also its own metatype), this is not a requirement. The type of classic classes, known astypes.ClassType, can also be considered a distinct metatype.[6]
a = 0print(type(a))# prints: <type 'int'>print(type(type(a)))# prints: <type 'type'>print(type(type(type(a))))# prints: <type 'type'>print(type(type(type(type(a)))))# prints: <type 'type'>
In Java,is-a relation between the type parameters of one class or interface and the type parameters of another are determined by the extends andimplements clauses.
Using theCollections classes,ArrayList<E> implementsList<E>, andList<E> extendsCollection<E>. SoArrayList<String> is a subtype ofList<String>, which is a subtype ofCollection<String>. The subtyping relationship is preserved between the types automatically. When defining an interface,PayloadList, that associates an optional value ofgeneric type P with each element, its declaration might look like:
interfacePayloadList<E,P>extendsList<E>{voidsetPayload(intindex,Pval);...}
The following parameterizations of PayloadList are subtypes ofList<String>:
PayloadList<String,String>PayloadList<String,Integer>PayloadList<String,Exception>
In type theory the concept ofsubsumption[7] is used to define or evaluate whether a typeS is a subtype of typeT.
A type is a set of values. The set can be describedextensionally by listing all the values, or it can be describedintensionally 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 types 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: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]
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, orrelevance 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 theprevalence 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 usingSet-builder notation, which uses a predicate to define a set. Predicates can be defined over a domain (set of possible values)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, which applies selection criteria for the typeT, and which applies additional criteria for the typeS, then sets for the two types can be defined:
The predicate is applied alongside as part of the compound predicateS definingS. The two predicates areconjoined, so both must be true for a value to be selected. The predicate subsumes the predicateT, soS <: T.
For example: there is a subfamily of cat species calledFelinae, which is part of the familyFelidae. The genusFelis, to which the domestic cat speciesFelis catus belongs, is part of that subfamily.
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,Felis <: Felinae <: Felidae.
IfT subsumesS (T :> S) then a procedure, function or expression given a value as an operand (parameter value or term) will therefore be able to operate over that value as one of typeT, because. In the example above, we could expect the functionofSubfamily to be applicable to values of all three typesFelidae,Felinae andFelis.
Type theorists make a distinction betweennominal subtyping, in which only types declared in a certain way may be subtypes of each other, andstructural subtyping, in which the structure of two types determines whether or not one is a subtype of the other. The class-based object-oriented subtyping described above is nominal; a structural subtyping rule for an object-oriented language might say that if objects of typeA can handle all of the messages that objects of typeB can handle (that is, if they define all the samemethods), thenA is a subtype ofB regardless of whether eitherinherits from the other. This so-calledduck typing is common in dynamically typed object-oriented languages. Sound structural subtyping rules for types other than object types are also well known.[citation needed]
Implementations of programming languages with subtyping fall into two general classes:inclusive implementations, in which the representation of any value of typeA also represents the same value at typeB ifA <: B, andcoercive implementations, in which a value of typeA can beautomatically converted into one of typeB. The subtyping induced by subclassing in an object-oriented language is usually inclusive; subtyping relations that relate integers and floating-point numbers, which are represented differently, are usually coercive.
In almost all type systems that define a subtyping relation, it is reflexive (meaningA <: A for any typeA) and transitive (meaning that ifA <: B andB <: C thenA <: C). This makes it apreorder on types.
Types ofrecords give rise to the concepts ofwidth anddepth subtyping. These express two different ways of obtaining a new type of record that allows the same operations as the original record type.
Recall that a record is a collection of (named) fields. Since a subtype is a type which allows all operations allowed on the original type, a record subtype should support the same operations on the fields as the original type supported.
One kind of way to achieve such support, calledwidth subtyping, adds more fields to the record. More formally, every (named) field appearing in the width supertype will appear in the width subtype. Thus, any operation feasible on the supertype will be supported by the subtype.
The second method, calleddepth subtyping, replaces the various fields with their subtypes. That is, the fields of the subtype are subtypes of the fields of the supertype. Since any operation supported for a field in the supertype is supported for its subtype, any operation feasible on the record supertype is supported by the record subtype. Depth subtyping only makes sense for immutable records: for example, you can assign 1.5 to the 'x' field of a real point (a record with two real fields), but you can't do the same to the 'x' field of an integer point (which, however, is a deep subtype of the real point type) because 1.5 is not an integer (seeVariance).
Subtyping of records can be defined inSystem F<:, which combinesparametric polymorphism with subtyping of record types and is a theoretical basis for manyfunctional programming languages that support both features.
Some systems also support subtyping of labeleddisjoint union types (such asalgebraic data types). The rule for width subtyping is reversed: every tag appearing in the width subtype must appear in the width supertype.
IfT1 →T2 is afunction type, then a subtype of it is any function typeS1 →S2 with the property thatT1 <:S1 andS2 <:T2. This can be summarised using the followingtyping rule:
The parameter type ofS1 →S2 is said to becontravariant because the subtyping relation is reversed for it, whereas the return type iscovariant. 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 inScala: an-ary function is internally a class that inherits thetrait (which can be seen as a generalinterface inJava-like languages), where are the parameter types, and 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 onbehavioral subtyping, which besides the type system safety discussed in this article also requires that subtypes preserve allinvariants guaranteed by the supertypes in somecontract.[8] This definition of subtyping is generallyundecidable, so it cannot be verified by atype checker.
The subtyping ofmutable references is similar to the treatment of parameter values and return values. Write-only references (orsinks) are contravariant, like parameter values; read-only references (orsources) are covariant, like return values. Mutable references which act as both sources and sinks are invariant.
Subtyping and inheritance are independent (orthogonal) relationships. They may coincide, but none is a special case of the other. In other words, between two typesS andT, all combinations of subtyping and inheritance are possible:
The first case is illustrated by independent types, such asBoolean andFloat.
The second case can be illustrated by the relationship betweenInt32 andInt64. In most object oriented programming languages,Int64 are unrelated by inheritance toInt32. HoweverInt32 can be considered a subtype ofInt64 since any 32 bit integer value can be promoted into a 64 bit integer value.
 | This articlepossibly containsoriginal research. Pleaseimprove it byverifying the claims made and addinginline citations. Statements consisting only of original research should be removed.(July 2022) (Learn how and when to remove this message) |
The third case is a consequence offunction subtyping input contravariance. Assume a super class of typeT having a methodm returning an object of the same type (i.e. the type ofm isT →T, also note that the first parameter ofm is this/self) and a derived class typeS fromT. By inheritance, the type ofm inS isS →S.[citation needed] In order forS to be a subtype ofT the type ofm inS must be a subtype of the type ofm inT[citation needed], in other words:S →S ≤:T →T. By bottom-up application of the function subtyping rule, this means:S ≤:T andT ≤:S, which is only possible ifS andT are the same. Since inheritance is an irreflexive relation,S can't be a subtype ofT.
Subtyping and inheritance are compatible when all inherited fields and methods of the derived type have types which are subtypes of the corresponding fields and methods from the inherited type .[3]
In coercive subtyping systems, subtypes are defined by explicittype conversion functions from subtype to supertype. For each subtyping relationship (S <:T), a coercion functioncoerce:S →T is provided, and any objects of typeS is regarded as the objectcoerceS →T(s) of typeT. A coercion function may be defined by composition: ifS <:T andT <:U thens may be regarded as an object of typeu under the compound coercion (coerceT →U ∘coerceS →T). Thetype coercion from a type to itselfcoerceT →T is theidentity functionidT.
Coercion functions for records anddisjoint union subtypes may be defined componentwise; in the case of width-extended records, type coercion simply discards any components which are not defined in the supertype. The type coercion for function types may be given byf'(t) =coerceS2 →T2(f(coerceT1 →S1(t))), reflecting thecontravariance of parameter values and covariance of return values.
The coercion function is uniquely determined given the subtype andsupertype. Thus, when multiple subtyping relationships are defined, one must be careful to guarantee that all type coercions are coherent. For instance, if an integer such as 2 :int can be coerced to a floating point number (say, 2.0 :float), then it is not admissible to coerce 2.1 :float to 2 :int, because the compound coercioncoercefloat →float given bycoerceint →float ∘coercefloat →int would then be distinct from the identity coercionidfloat.
Textbooks
Papers