Origins
The notion of subtyping in programming languages dates back to the 1960s; it was introduced inExamples
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. The UML 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 type Number as a common supertype of integers and the reals. In this second case, we only have Integer
<: Number
and Float
<: Number
, but Integer
and Float
are not subtypes of each other.
Programmers may take advantage of subtyping to write code in a more abstract manner than would be possible without it. Consider the following example:
Number
, 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 requires bounded polymorphism.
Subtyping enables a given type to be substituted for another type or abstraction. Subtyping is said to establish an is-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.
C++
The following C++ code establishes an explicit inheritance relationship between classes B and A, where B is both a subclass and a subtype of A, and can be used as an A wherever a B is specified (via a reference, a pointer or the object itself).Python
The following python code establishes an explicit inheritance relationship between classes and , where is both a subclass and a subtype of , and can be used as an wherever a is required.Java
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 and implements clauses. Using the classes, implements , and extends . So is a subtype of , which is a subtype of . The subtyping relationship is preserved between the types automatically. When defining an interface, , that associates an optional value of generic type P with each element, its declaration might look like:Subsumption
In type theory the concept of ''subsumption''Benjamin C. Pierce, ''Types and Programming Languages'', MIT Press, 2002, 15.1 "Subsumption", p. 181-182 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 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: . 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". * A type T ''subsumes'' S if the set of values which it defines, is a superset of the set , so that every member of is also a member of . * A type may be subsumed by more than one type: the supertypes of S intersect at . * If S <: T (and therefore ), then T, the predicate which circumscribes the set , must be part of the predicate S (over the same domain) which defines . * 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) . 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 type T, and which applies additional criteria for the type S, then sets for the two types can be defined: : : The predicate is applied alongside as part of the compound predicate S defining . The two predicates are ''conjoined'', so both must be true for a value to be selected. The predicate subsumes the predicate T, so 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. : : 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, . If T subsumes S (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 type T, because . In the example above, we could expect the function ''ofSubfamily'' to be applicable to values of all three types Felidae, Felinae and Felis.Subtyping schemes
Type theorists make a distinction between nominal subtyping, in which only types declared in a certain way may be subtypes of each other, and structural 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 type ''A'' can handle all of the messages that objects of type ''B'' can handle (that is, if they define all the same methods), then ''A'' is a subtype of ''B'' regardless of whether either inherits from the other. This so-called '' duck typing'' is common in dynamically typed object-oriented languages. Sound structural subtyping rules for types other than object types are also well known. Implementations of programming languages with subtyping fall into two general classes: ''inclusive'' implementations, in which the representation of any value of type ''A'' also represents the same value at type ''B'' if ''A'' <: ''B'', and ''coercive'' implementations, in which a value of type ''A'' can be ''automatically converted'' into one of type ''B''. 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 (meaning ''A'' <: ''A'' for any type ''A'') and transitive (meaning that if ''A'' <: ''B'' and ''B'' <: ''C'' then ''A'' <: ''C''). This makes it a preorder on types.Record types
Width and depth subtyping
Types of records give rise to the concepts of ''width'' and ''depth'' 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, called ''width 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, called ''depth 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 (seeFunction types
If is a function type, then a subtype of it is any function type with the property that and This can be summarised using the followingRelationship with inheritance
Subtyping and inheritance are independent (orthogonal) relationships. They may coincide, but none is a special case of the other. In other words, between two types ''S'' and ''T'', all combinations of subtyping and inheritance are possible: # ''S'' is neither a subtype nor a derived type of ''T'' # ''S'' is a subtype but is not a derived type of ''T'' # ''S'' is not a subtype but is a derived type of ''T'' # ''S'' is both a subtype and a derived type of ''T'' The first case is illustrated by independent types, such asBoolean
and Float
.
The second case can be illustrated by the relationship between Int32
and Int64
. In most object oriented programming languages, Int64
are unrelated by inheritance to Int32
. However Int32
can be considered a subtype of Int64
since any 32 bit integer value can be promoted into a 64 bit integer value.
The third case is a consequence of function subtyping input contravariance. Assume a super class of type ''T'' having a method ''m'' returning an object of the same type (''i.e.'' the type of ''m'' is ''T'' → ''T'', also note that the first parameter of ''m'' is this/self) and a derived class type ''S'' from ''T''. By inheritance, the type of ''m'' in ''S'' is ''S'' → ''S''. In order for ''S'' to be a subtype of ''T'' the type of ''m'' in ''S'' must be a subtype of the type of ''m'' in ''T'' , in other words: ''S'' → ''S'' ≤: ''T'' → ''T''. By bottom-up application of the function subtyping rule, this means: ''S'' ≤: ''T'' and ''T'' ≤: ''S'', which is only possible if ''S'' and ''T'' are the same. Since inheritance is an irreflexive relation, ''S'' can't be a subtype of ''T''.
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 .
Coercions
In coercive subtyping systems, subtypes are defined by explicit type conversion functions from subtype to supertype. For each subtyping relationship (''S'' <: ''T''), a coercion function ''coerce'': ''S'' → ''T'' is provided, and any object ''s'' of type ''S'' is regarded as the object ''coerce''''S'' → ''T''(''s'') of type ''T''. A coercion function may be defined by composition: if ''S'' <: ''T'' and ''T'' <: ''U'' then ''s'' may be regarded as an object of type ''u'' under the compound coercion (''coerce''''T'' → ''U'' ∘ ''coerce''''S'' → ''T''). The type coercion from a type to itself ''coerce''''T'' → ''T'' is the identity function ''id''T. Coercion functions for records and disjoint 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 by ''f(''t'') = ''coerce''''S''2 → ''T''2(''f''(''coerce''''T''1 → ''S''1(''t''))), reflecting the contravariance of parameter values and covariance of return values. The coercion function is uniquely determined given the subtype and supertype. 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 coercion ''coerce''''float'' → ''float'' given by ''coerce''''int'' → ''float'' ∘ ''coerce''''float'' → ''int'' would then be distinct from the identity coercion ''id''''float''.See also
* Covariance and contravariance * The circle-ellipse problem (for the perils of subtyping variable-types on the same basis as value-types) * Class-based programming * Top type * Refinement type * Behavioral subtypingNotes
References
Textbooks * Benjamin C. Pierce, ''Types and programming languages'', MIT Press, 2002, , chapter 15 (subtyping of record types), 19.3 (nominal vs. structural types and subtyping), and 23.2 (varieties of polymorphism) * C. Szyperski, D. Gruntz, S. Murer, ''Component software: beyond object-oriented programming'', 2nd ed., Pearson Education, 2002, , pp. 93–95 (a high-level presentation aimed at programming language users) Papers * Reynolds, John C. Using category theory to design implicit conversions and generic operators. In N. D. Jones, editor, Proceedings of the Aarhus Workshop on Semantics-Directed Compiler Generation, number 94 in Lecture Notes in Computer Science. Springer-Verlag, January 1980. Also in Carl A. Gunter and John C. Mitchell, editors, Theoretical Aspects of Object-Oriented Programming: Types, Semantics, and Language Design (MIT Press, 1994).Further reading
* John C. Reynolds, ''Theories of programming languages'', Cambridge University Press, 1998, , chapter 16. * Martín Abadi, Luca Cardelli, ''A theory of objects'', Springer, 1996, . Section 8.6 contrast the subtyping of records and objects. {{DEFAULTSORT:Subtype Polymorphism Data types Polymorphism (computer science) Type theory Object-oriented programming