CSE 505 Lecture Notes:
Types in Object-Oriented Languages
November 19, 1997
Some choices:
- static or dynamic typing?
- type declarations?
- separate or combined type and inheritance hierarchies?
- contravariance or covariance?
In Smalltalk-80, all type checking is done dynamically.
Object-oriented languages with static type checking: Emerald, Simula,
Trellis/Owl, Eiffel
Cecil: optional type declarations and static checking
- Types in an object-oriented language:
-
A collection of operation signatures, where each signature
consists of the operation name, the types of the arguments, and the
type of the result(s)
We will say that an object is of an abstract type if it has the properties
defined by that type. Abstract types can allow us to do static type
checking in an object-oriented language, while preserving the dynamic
binding of names to operations. For example, we can statically check that
some object will understand a message m, even though we don't know exactly
which method will be invoked.
Another definition sometimes used in type inference systems: a type is a
set of classes (see e.g. Palsberg and Schwartzbach)
Contravariance vs. covariance
The contravariant rule for subtyping is used in Emerald, Cecil,
Trellis/Owl, etc. (It is also the rule used in Cardelli's paper "A
Semantics of Multiple Inheritance".)
Covariant rule is used in Eiffel.
Contravariant rule:
S is a subtype of T if:
- S provides all the operations that T does (and maybe some more)
- For each operation in T, the corresponding operation in S has the same
number of arguments and results
- The types of the results of S's operations are subtypes of the types of
the corresponding results of T's operations
- The types of the arguments of T's operations are subtypes of the types
of the corresponding arguments of S's operations
(note the reversal of T and S here)
N.B. If S=T, then S is a subtype of T.
Covariant rule:
same as above, except for 4:
- The types of the arguments of S's operations are subtypes of the types
of the corresponding arguments of T's operations
Example
Type Color
Type GrayScaleColor (a subtype of Color)
Type Number
Type Integer, Float (both subtypes of Number)
Type Point
x(): Number
y(): Number
Type ColoredPoint
x(): Number
y(): Number
mycolor() : Color
Type GrayScalePoint
x(): Number
y(): Number
mycolor() : GrayScaleColor
ColoredPoint is a subtype of Point -- anywhere a Point is
needed, we can use a ColoredPoint.
Also GrayScalePoint is a subtype of ColoredPoint, and GrayScalePoint is a
subtype of Point.
p : ColoredPoint;
c : Color
p := GrayScalePoint.new;
c := p.mycolor;
q , r : Point;
a : Number;
q := ColoredPoint.new;
r := GrayScalePoint.new;
a := q.x + r.x;
now add a message with an argument:
Type ColoredPoint
x(): Number
y(): Number
mycolor() : Color
setDotSize(c : Integer);
Type GrayScalePoint
x(): Number
y(): Number
mycolor() : GrayScaleColor
setDotSize(c : Number);
The contravariant rule says that GrayScalePoint is still a subtype of
ColoredPoint.
c, d : ColoredPoint;
c := ColoredPoint.new;
d := GrayScalePoint.new;
c.setDotSize(3);
d.setDotSize(4);
However, the following statements would give compile-time errors:
c.setDotSize(3.5);
d.setDotSize(3.5);
Now consider:
Type ColoredPoint
x(): Number
y(): Number
mycolor() : Color
setcolor(c : Color);
Type GrayScalePoint
x(): Number
y(): Number
mycolor() : GrayScaleColor
setcolor(c : GrayScaleColor);
Under the contravariant rule there is no longer a subtype relation between
ColoredPoint and GrayScalePoint. Example:
c : ColoredPoint;
c := GrayScalePoint.new; /* not permitted */
c.setcolor(yellow); /* an error would occur if we tried this */
However, under the covariant rule GrayScalePoint would still be a subtype
of ColoredPoint, and the above program would type check correctly.
Multiple Inheritance
A type can be a subtype of several other types -- 'multiple inheritance'
for abstract types introduces no additional complications (unlike multiple
implementation inheritance).
Parameterized types
What is the type of array? We want to be able to get reasonable type
information for the element access and set messages.
Statically-typed object-oriented languages usually have some notion of
parameterized types to handle this.
a : Array[Integer]
n : Integer;
...
a[1] := 4;
n := a[1];
For a type Array, we can have something like:
Type Array[T]
at(n : Integer) : T
put(n : Integer, x : T)
Question:What is the type relation between Array[Number]
and Array[Integer]?
Answer: under the contravariant rule, none.
Design Decision: should abstract type and concrete
implementation inheritance be separate or combined? (This question
only makes sense if there are type declarations.)
Reasons for separating them:
- they are different concepts
- allows additional flexibility (for example, multiple implementations of
the same abstract type)
Reasons against:
- it makes the language more complicated
- they usually go together anyway
Example of multiple implementations (two concrete classes with one abstract
type):
abstract type Stack
implementation classes ListStack, ArrayStack
both would conform to the abstract type Stack
Example of inheriting implementation but not abstract type:
Stack inherits from Deque (just masks off extra operations like front)