intro,
inheritance,
subtypes,
polymorphism,
types,
hiding,
self-reference,
summary,
Q/A,
literature
Our interest in the subtype relation is primarily
directed towards objects.
However, since real objects involve self-reference
and possibly recursively defined methods,
we will first study the subtyping relation for
objects as (simple) records.
Our notion of objects as records
is based on the views expressed in [Ca84].
Objects may be regarded as records (where a record
is understood as a finite association of values to
labels), provided we allow functions to occur
as the value of a record field.
The basic operation with records is field selection
which, when the value of the field accessed is a function,
may be applied for method invocation.
The typing rule for records follows the
construction of the record: the type of a record
is simply the record type composed of the types
of the record's components.
See slide 9-objects.
In the previous section we have already characterized
the subtyping relation between records.
This characterization is repeated in slide 9-ex-objects.
The following is meant to justify this characterization.
Let us first look at a number of examples that
illustrate how the subtype relation fits into
the mechanism of derivation by inheritance.
Subtyping -- examples
type any = { }
type entity = { age : int }
type vehicle = { age : int, speed : int }
type machine = { age : int, fuel : string }
type car = { age : int, speed : int, fuel : string }
Suppose we define the type any as the record type
having no fields.
In our view of types as constraints, the empty record
may be regarded as imposing no constraints.
This is in agreement with our formal characterization
of subtyping, since according to the record subtyping rule
the record type any is a supertype of any other
record type.
Subtyping in the sense of refinement means adding constraints,
that is information that constrains the set of possible
elements associated with the type.
The record type entity, which assumes a field age,
is a subtype of any, adding the information
that age is a relevant property for an entity.
Following the same line of reasoning, we may regard the types
vehicle and machine as subtypes
of the type entity.
Clearly, we may have derived the respective types by
applying inheritance.
For example, we may derive vehicle from entity
by adding the field speed, and machine from entity
by adding the field fuel.
Similarly, we may apply multiple inheritance to derive the
type car from vehicle and machine,
where we assume that the common field age (ultimately
inherited from entity) only occurs once.
Obviously, the type car is a subtype of both vehicle
and machine.
Each of the successive types listed above
adds information that constrains the
possible applicability of the type
as a descriptive device.
The other way around, however, we may regard each object
of a particular (sub)type to be an instance of its supertype
simply by ignoring the information that specifically
belongs to the subtype.
Mathematically, we may explain this as a projection onto
the fields of the supertype.
Put differently, a subtype allows us to make
finer distinctions. For example,
from the perspective of the supertype
two entities are the same
whenever they have identical ages but they may be different when
regarded as vehicles (by allowing different speeds).
Conformance
The importance of subtyping for practical software
development comes from the conformance
requirement (or substitutability property) stating
that any instance of a subtype may be used
when an instance of a supertype is expected.
This property allows the programmer to express the
functionality of a program in a maximally abstract
way, while simultaneously allowing for
the refinement of these abstract types needed
to arrive at an acceptable implementation.
For objects as records, the refinement relation concerns
both attributes and functions (as members of the object record).
For attributes, refinement means providing more information.
Syntactically, with respect to the (signature) type
of the attribute, this means a restriction of its range.
In other words, the possible values an attribute
may take may only be restricted.
Alternatively, the refinement relation may be characterized
as restricting the non-determinism contained
in the specification of the supertype,
by making a more specific choice.
For example, if we specify the speed range of a vehicle
initially as
record = finite association of values to labels
(a = 3, b = true ).a ≡ 3
then we may restrict
the speed range of a car safely to
record = finite association of values to labels
(a = 3, b = true ).a ≡ 3
.
However, to stay within the regime of subtyping
we may not subsequently enlarge this range
by defining a subtype racing car with a speed
range of
0..400 .
Intuitively, subtyping means enforcing determinism,
the restriction of possible choices.
Our (syntactic) characterization of the subtyping relation
between object types does not yet allow for data hiding,
generics or self-reference.
These issues will be treated in sections existential and self-reference.
However, before that, let us look at the characterization
of the subtyping relation between object types as
defined (for example) for the language Emerald.
The characterization given in slide 9-emerald
is taken from [DT88].
Subtyping in Emerald -- S conforms to T
S provides at least the operations of T
for each operation in T, the corresponding operation in S
has the same number of arguments
the type of the result of operations of S
conform to those of the operations of T
the types of arguments of operations of T conform
to those of the operations of S
The object subtyping relation in Emerald is characterized
in terms of conformance.
The rules given above specify when an object
type S conforms to an object (super) type T.
These rules are in agreement with the subtyping
rules given previously, including the contravariance
required for the argument types of operations.
Taken as a guideline, the rules specify what restrictions
to obey (minimally) when specifying a subtype by inheritance.
However, as we will discuss in the next section,
polymorphism and subtyping is not restricted to
object types only.
Nor are the restrictions mentioned a sufficient criterion
for a semantically safe use of inheritance.