Subtype

In computer science, a subtype is a datatype that is generally related to another datatype (the supertype) by some notion of "substitutability", meaning that computer programs written to operate on elements of the supertype can also operate on elements of the subtype. More specifically, the supertype-subtype relation is often taken to be the one defined by the Liskov substitution principle; however, any given programming language may define its own notion of subtyping, or none at all.

Example

A simple practical example of subtypes is shown in the diagram, right. The generic object "bird" (or, supertype) gives rise to three derived objects (or, subtypes) "duck", "cuckoo" and "ostrich". Each of these varies the basic "bird" concept in its own way, but still inherits many "bird" characteristics. A data object may be declared as any one of the four types. 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.

In most class-based object-oriented languages, subclasses give rise to subtypes: if "A" is a subclass of "B", then an instance of class "A" may be used in any context where an instance of type "B" is expected; thus we say "A" is a subtype of "B". A consequence of this is that any variable or parameter declared as having type "B" might, at run time, hold a value of class "A"; in this situation many object-oriented programmers would say that "B" is the variable's "static type" and "A" is its "dynamic type". Exceptions to this rule include private inheritance in C++ (which does not create subtypes), and certain operations on derived types in Eiffel, wherein features inherited from a base class can be removed or modified in a way which violates the subtyping rule.

As another example, a language might allow integer values to be used wherever floating-point values are expected, or it might define a type number containing both the integers and the reals. In the first instance, the integer type would be a subtype of the floating-point type; in the second, those two types might be unrelated to each other by subtyping but both would be subtypes of number.

Programmers may take advantage of subtyping to write code in a more abstract manner than would be possible without it. Consider the following example:

function max (x as number, y as number) is if x < y then return y else return x end

If integer and real are both subtypes of number, then values of either type can be passed to this function. Because of this, subtyping is often considered a form of polymorphism. The above example can also be compared to the template feature of C++.

In type theory, the subtype relation is often written &lt;:, so that "A"&lt;:"B" means that "A" is a subtype of "B". Subtyping in type theory is characterized by the fact that any expression of type "A" may also be given type "B" if "A"&lt;:"B"; the formal typing rule that codifies this is known as the "subsumption" rule.

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. 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"&lt;:"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"&lt;:"A" for any type "A") and transitive (meaning that if "A"&lt;:"B" and "B"&lt;:"C" then "A"&lt;:"C"). This makes it a preorder on types.

See also

* A derived type is a type given a new type but structurally the same as the original type. It may or may not be a subtype depending on the type system.
* Contravariance in Covariance and contravariance (computer science)
* The circle-ellipse problem for the perils of subtyping variable-types on the same basis as value-types
* class-based programming for an example of a problem when one confuses subtyping with subclassing.
*Top type
*superclass and subclass

External links

* "Object-Oriented Software Construction" by Bertrand Meyer