Lecture
Introduction to inheritance
Interesting systems are rarely built from scratch. Almost always, new programs are extensions of earlier developments; the best way to create something new is to imitate earlier models, refining and combining them. Traditional design methods largely paid no attention to this aspect of development. In OO technology, it is highly significant.
Software development involves creating a large number of classes, many of which are variants of previously created classes. Managing the potential complexity of such a system requires a classification mechanism known as inheritance. Class A is an heir of class B if it incorporates (inherits) the components of class B in addition to its own. A descendant is a direct or indirect heir; the reverse notion is an ancestor.
It must be possible to declare a class as the heir of another class.
Inheritance is one of the central concepts of the OO method; it has a major influence on the process of software development.
It is often necessary to combine different abstractions. Consider a class modeling the concept of "infant". It can be viewed as a "person" class with the components associated with that class. It can also be viewed more prosaically - as a "taxable item" class, entitled to tax deductions. Inheritance is justified in both cases. Multiple inheritance is the guarantee that a class can be the heir not just of one class, but of several, whenever this is conceptually justified.
Multiple inheritance raises several technical problems, such as resolving name clashes (components inherited from different classes sharing the same name). Any notation offering multiple inheritance must provide an adequate solution to these problems.
A class must be able to be the heir of several classes.
Name clashes arising from inheritance are resolved by an adequate mechanism.
for example, by renaming the conflicting components in the heir class.
With multiple inheritance, a situation of repeated inheritance arises, where a class becomes the heir of the same class more than once, through different inheritance branches:
Fig. 2.1. Repeated inheritance
In this case, the language must provide precise rules defining what happens to components inherited repeatedly from a common ancestor (A in the figure). In some cases it is desirable for the component from A to produce only one component in D (sharing), while in others it should produce two (replication). Developers must have flexible means allowing them to prescribe one of these options independently for each component.
Under repeated inheritance, the fate of components must be governed by precisely defined rules that let developers choose, for each such component, either sharing or replication.
The techniques studied so far are clearly insufficient. Classes, of course, provide a way of achieving good decomposition into modules and possess many of the qualities expected of reusable components: they are uniform, consistent modules; in accordance with the Information Hiding principle, interfaces can easily be separated from implementations; genericity gives them a certain flexibility, and thanks to assertions, their semantics can be precisely specified. But something more is needed to achieve reusability and extendibility.
Any comprehensive approach that provides for reuse must confront the problem of repetition and variation, analyzed in one of the previous lectures (see Lecture 4). To eliminate the repeated rewriting of the same code - which wastes time and leads to inconsistencies and errors - methods are needed that capture the striking commonality shared by many groups of structurally similar constructs: all text editors, all tables, all file-processing programs - while still accounting for the many differences in the characteristics of specific cases.
In providing extendibility, the advantage of the type system described above lies in guaranteed compile-time consistency, but it prohibits many entirely legitimate combinations of elements. For example, it is not possible to declare an array containing geometric objects of different compatible types, such as POINT (the point) and SEGMENT (the segment).
To make progress in reuse or extendibility, one must take advantage of the conceptual relations between classes: one class may be an extension, a specialization, or a combination of other classes. The method and the language must support expressing and using these relations. This support is provided by inheritance.
The central and delightful component of object technology - the inheritance relation - will require several lectures to master fully. This lecture covers the fundamental concepts. The next three describe more specialized aspects: multiple inheritance, renaming, subcontracting, and the impact on the type system. Lecture 6 of the course "Fundamentals of Object-Oriented Design" will supplement these technical discussions by considering the methodological perspective: how to use inheritance and how to avoid misusing it.
To explain the basic concepts, let us consider a simple example. What follows is more of a sketch of this example than a complete version of it, but it illustrates all the essential ideas well.
Suppose we need to build a graphics library. Its classes will describe geometric abstractions: points, segments, vectors, circles, ellipses, polygons, triangles, rectangles, squares, and so on.
Let us first consider a class describing polygons. Its operations will include computing the perimeter, translation, and rotation. This class might look as follows:
indexing
description: "Polygons with an arbitrary number of vertices"
class POLYGON creation
...
feature -- Access
count: INTEGER
-- Number of vertices
perimeter: REAL is
-- Perimeter length
do ... end
feature -- Transformation
display is
-- Displays the polygon on the screen.
do ... end
rotate (center: POINT; angle: REAL) is
-- Rotation by the angle angle around the point center.
do
... see below ...
end
translate (a, b: REAL) is
-- Shift by a horizontally, by b vertically.
do ... end
... Declarations of other components ...
feature {NONE} -- Implementation
vertices: LINKED_LIST [POINT]
-- List of the polygon's vertices
invariant
same_count_as_implementation: count = vertices.count
at_least_three: count >= 3
-- A polygon has at least three vertices (see exercise E14.2)
end
The attribute vertices specifies the list of vertices; the choice of a linked list is just one of the possible representations (an array might turn out to be better).
Let us give the implementation of a typical procedure, rotate. This procedure performs a rotation by a given angle around a given center of rotation. To rotate a polygon, it suffices to rotate each of its vertices in turn.
rotate (center: POINT; angle: REAL) is
-- Rotation around the point center by the angle angle.
do
from
vertices.start
until
vertices.after
loop
vertices.item.rotate (center, angle)
vertices.forth
end
end
To understand this procedure, note that the component item of LINKED_LIST returns the value of the current element of the list. Since vertices is of type LINKED_LIST [POINT], vertices.item denotes a point, to which the rotation procedure rotate, defined for class POINT in the previous lecture, can be applied. It is entirely correct, and fairly common practice, to give the same name (in this case, rotate) to components of different classes, since the resulting set for each of them has its own explicitly defined type. (This is the OO form of overloading.)
More important for our purposes is the procedure that computes the perimeter of a polygon. The only way to compute the perimeter of a polygon is to loop over all of its vertices and sum the lengths of all the edges. Here is a possible implementation of the procedure perimeter:
perimeter: REAL is
-- Sum of the edge lengths
local
this, previous: POINT
do
from
vertices.start; this := vertices.item
check not vertices.after end -- A consequence of the at_least_three condition
until
vertices.is_last
loop
previous := this
vertices.forth
this := vertices.item
Result := Result + this.distance (previous)
end
Result := Result + this.distance (vertices.first)
end
In this loop, the distances between adjacent vertices are simply summed one after another. The function distance was defined in class POINT. The value Result returned by this function is initialized to 0. From class LINKED_LIST the following components are used: first gives the first element of the list, start moves the cursor to this first element, forth advances it to the next one, item yields the value of the element under the cursor, is_last determines whether the current element is the last one, after tells whether the cursor has moved past the last element. As indicated by the check instruction, the invariant at_least_three guarantees a correct start and end to the loop. It starts in the state not after, in which the element vertices.item is defined. It is valid to apply forth one or more times, which will eventually lead to a state satisfying the loop-exit condition is_last.
Suppose now that we need a new class representing rectangles. We could start designing it from scratch. But rectangles are a special kind of polygon, and they share many common components: they too can be translated, rotated, and displayed on the screen. On the other hand, they have a number of specific components (for example, diagonals), specific properties (the number of vertices equals four, and the angles are right angles), and specific variants are possible for some operations (computing the perimeter can be arranged more simply than in the algorithm given above).
The advantages of such a mix of common and specific components can be exploited by defining class RECTANGLE as the heir of class POLYGON. All the components of class POLYGON, called the parent of class RECTANGLE, will then by default also be applicable to the heir class. To achieve this, it suffices to include in RECTANGLE an inheritance clause:
class RECTANGLE inherit
POLYGON
feature
... Components specific to rectangles ...
end
In the feature clause of the heir class, the parent's components are not repeated: they are automatically available thanks to the inheritance clause. Only the components specific to the heir will be listed there. These may be new components, such as diagonal, as well as redefined inherited components.
The second option is useful for a component that already existed in the parent but must be described differently in the heir. Consider the perimeter perimeter. For rectangles it can be computed more efficiently: there is no need to compute all four side lengths - it suffices to double the sum of the lengths of two sides. An heir that redefines a component of the parent must declare this in the inheritance clause, by including a redefine clause:
class RECTANGLE inherit
POLYGON
redefine perimeter end
feature
...
end
This makes it possible to include, in the feature clause of class RECTANGLE, a new version of the component perimeter, which will replace its version from class POLYGON. If the redefine declaration is not included, then the new declaration of the component perimeter among the other components of class RECTANGLE will cause an error, since RECTANGLE already has a component perimeter inherited from POLYGON, meaning that component would end up with two definitions.
Class RECTANGLE looks as follows:
indexing
description: "Rectangles - a special case of polygons"
class RECTANGLE inherit
POLYGON
redefine perimeter end
creation
make
feature -- Initialization
make (center: POINT; s1, s2, angle: REAL) is
-- Set the center of the rectangle to center, the side lengths
-- to s1 and s2, and the orientation to angle.
do ... end
feature -- Access
side1, side2: REAL
-- Lengths of the two sides
diagonal: REAL
-- Length of the diagonal
perimeter: REAL is
-- Sum of the side lengths
-- (Redefinition of the version from POLYGON)
do
Result := 2 * (side1 + side2)
end
invariant
four_sides: count = 4
first_side: (vertices.i_th (1)).distance (vertices.i_th (2)) = side1
second_side: (vertices.i_th (2)).distance (vertices.i_th (3)) = side2
third_side: (vertices.i_th (3)).distance (vertices.i_th (4)) = side1
fourth_side: (vertices.i_th (4)).distance (vertices.i_th (1)) = side2
end
| For a list, i_th(i) gives the element at position i (the i-th element, hence the name of the query). |
Since RECTANGLE is an heir of class POLYGON, all the components of the parent class are also applicable to the new class: vertices, rotate, translate, perimeter (in its redefined form), and all the rest. There is no need to repeat them in the definition of the new class.
This process is transitive: any class that is an heir of RECTANGLE, for example SQUARE, also possesses all the components of class POLYGON.
Besides the terms "heir" and "parent", the following terms will be useful:
Inheritance terminology
Descendant of class C is any class that inherits from C, directly or indirectly, including class C itself. (Formally, this is either C, or, recursively, a descendant of some heir of C.)
Proper descendant of class C is a descendant other than C itself.
Ancestor of C is a class A such that C is a descendant of it. Proper ancestor of C is a class A such that C is a proper descendant of it.
The literature also uses the terms "subclass" and "superclass", but we will not use them because of their ambiguity.
There is also terminology for the components of a class: a component is either inherited (passed down from some proper ancestor) or immediate (introduced in the given class).
In graphical representations of OO software structures, in which classes are depicted as ellipses, inheritance relationships are shown as single arrows. This distinguishes them from "client" relationships, which are represented by double arrows.
Fig. 14.1. Inheritance relation
A redefined component is marked with ++ (this is the convention adopted in the Business Object Notation (B.O.N.)).
The arrow points upward from the heir to the parent. This convention is easy to remember - it represents the relation "inherit from". The literature also shows such arrows in the opposite direction. Although the choice of graphical representation is usually a matter of taste, in this case one of them is clearly better than the other, since one suggests the correct relation, while the other can lead to confusion. An arrow is not just an arbitrary pictogram - it indicates a one-way relation between its two ends. In this case:
[x]. Every instance of the heir can be regarded as an instance of the parent, but the converse is not true.
[x]. The text of the heir always mentions its parent, but not the other way around. This is, in fact, an important property of the OO method, stemming from the Open-Closed principle, according to which a class does not "know" the list of its heirs or other proper descendants.
Although we have no strict rule determining, for sufficiently complex systems, the placement of classes in inheritance diagrams, we will, whenever possible, place a class above its heir.
We would like to specify an invariant for class RECTANGLE stating that the number of sides of the rectangle equals four and that the side lengths are, in order, side1, side2, side1 and side2.
Class POLYGON also has an invariant, which is applicable to its heir as well:
Invariant inheritance rule
The invariant of a class is the conjunction of the assertions from its invariant clause and the invariant properties of its parents (if any).
Since the parents of a class may themselves have parents, this rule is recursive: as a result, the complete invariant of a class is obtained as the conjunction of its own invariant and the invariants of the classes of all its ancestors.
This rule reflects one of the important characteristics of inheritance: to say that B inherits from A is to assert that every instance of B is also an instance of A. As a consequence, any integrity constraint expressed by an invariant, applicable to instances of A, will also be applicable to instances of B.
In our example, the second clause (at_least_three) of the invariant of POLYGON states that the number of sides must be at least three; it follows from the clause four_sides in the invariant of class RECTANGLE, which requires that there be exactly four sides.
The creation procedure (constructor) for class POLYGON, not shown earlier, might look as follows
make_polygon (vl: LINKED_LIST [POINT]) is
-- Creation from the vertices in vl.
require
vl.count >= 3
do
...Initialize the representation of the polygon from the elements of vl ...
ensure
-- vertices and vl consist of the same elements (this can be expressed
formally)
end
This procedure takes a list of points containing at least three elements, and uses it to create the polygon.
| It is given its own name, make_polygon, in order to avoid a name clash when it is inherited by class RECTANGLE, which has its own creation procedure make. We do not recommend doing this in general; in the next lecture it will be shown how to give the creation procedure of class POLYGON the standard name make, and then use renaming in the inheritance clause of class RECTANGLE to prevent the name collision. |
The creation procedure for class RECTANGLE given above has four arguments: a point serving as the center, the lengths of two sides, and the orientation. Note that the component vertices is applicable to rectangles, so the creation procedure for RECTANGLE builds the list of vertices vertices (the four corners are computed from the center, the side lengths, and the orientation).
The general creation procedure for polygons is inconvenient for rectangles, since only lists of four elements satisfying the invariant of class RECTANGLE are acceptable. The creation procedure for rectangles, in turn, is not suitable for arbitrary polygons. This is a common situation: the parent's creation procedure does not fit the heir. There is no guarantee that it will satisfy the heir's new invariant.
For example, if the heir has new attributes, the creation procedure will need to initialize them, which will require additional arguments. Hence the general rule:
Constructor inheritance rule
Under inheritance, a procedure's property of being a constructor is not preserved.
An inherited creation procedure is still available in the heir, like any other component of the parent, but it does not retain constructor status. Only the procedures listed in the heir's creation clause have this status.
In some cases, the parent's constructor is also suitable for the heir. Then it simply needs to be listed in the creation clause:
class B inherit
A
creation
make
feature
...
where the procedure make is inherited unchanged from class A, where it is likewise listed in the creation clause.
To conclude this discussion, it is useful to consider the POLYGON-RECTANGLE example in the context of a more general hierarchy of geometric figure types.
Fig. 14.2. Hierarchy of figure types
Figures are divided into closed and open ones. Besides the polygon, another example of a closed figure is the ellipse, and a special case of the ellipse is the circle.
Next to the classes, their various components are indicated. The symbol "++" means "redefined", while the symbols "+" and "*" will be explained later.
Earlier, for simplicity, RECTANGLE was an heir of class POLYGON. Since the classification given is based on the number of vertices, it seems reasonable to introduce an intermediate class QUADRANGLE for quadrilaterals at the same level as the classes TRIANGLE, PENTAGON, and so on. Then the component diagonal (the diagonal) can be moved up to the level of class QUADRANGLE.
Note that class SQUARE, an heir of class RECTANGLE, is characterized by the invariant side1 = side2. Similarly, an ellipse has two foci, while for a circle they merge into one, which defines the invariant of class CIRCLE: equal (focus1 = focus2).
Inheritance hierarchies make it possible to work with objects with considerable flexibility while retaining the reliability of static typing. The methods that support this - polymorphism and dynamic binding - are among the most fundamental aspects of the software architecture discussed in this book. Let us begin with polymorphism.
"Polymorphism" means the ability to take several forms. In OO development, several forms are taken by entities (elements of data structures) that are capable, at run time, of becoming attached to objects of different types, subject to control by static declarations.
Suppose that for the inheritance structure in the figure above, the following entities are declared:
p: POLYGON; r: RECTANGLE; t: TRIANGLE
Then the following assignments are valid:
p := r
p := t
These instructions assign, as the value of the entity denoting a polygon, the entity denoting a rectangle in the first case, and the entity denoting a triangle in the second.
Such assignments, in which the type of the source (the right-hand side) differs from the type of the target (the left-hand side), are called polymorphic assignments. An entity that appears on the left of a polymorphic assignment (in the example, this is p) is called a polymorphic entity.
Before the introduction of inheritance, all assignments were monomorphic (not polymorphic): one could assign a point to a point, a book to a book, an account to an account. With the advent of polymorphism, more actions become possible.
The polymorphic assignments given in the example are legitimate because the inheritance structure allows an instance of class RECTANGLE or TRIANGLE to be regarded as an instance of class POLYGON. In such a case, we say that the type of the source is compatible with the type of the target. An assignment in the opposite direction is not allowed, i.e. it is incorrect to write r := p. This important rule will soon be examined in more detail.
Besides assignment, polymorphism also occurs when passing arguments, for example in calls of the form f (r) or f (t), provided the component f is declared as:
f (p: POLYGON) is do ... end
Recall that assignment and argument passing have the same semantics, and both are called attachment. When the source and the target have different types, we can speak of polymorphic attachment.
All the entities that appear in the previous examples of polymorphic assignments have reference type: the possible values of p, r and t are not objects but references to objects. Therefore the result of the assignment p := r is simply a new reference attachment.
Fig. 14.3. Polymorphic reference attachment
Despite its name, polymorphism should not be pictured as some kind of transmutation of objects at run time. Once created, an object never changes its type. Only references can do that, since they can point to objects of different types. It also follows that polymorphism need not be paid for with a loss of efficiency: redirecting a reference is a very fast operation, whose cost does not depend on the objects involved in it.
Polymorphic attachment is allowed only for targets of reference type, and never for expanded types. Since a descendant class may have new attributes, its corresponding instances may have more fields. In Fig. 14.3 we can see that an object of class RECTANGLE is larger than an object of class POLYGON. Such a difference in object sizes causes no problems as long as everything that gets newly attached has reference type. But if p is not a reference but has an expanded type (for example, declared as expanded POLYGON), then the value of p is directly some object, and any assignment to p will change the contents of that object. In this case, no polymorphism is possible.
Consider an array of polygons:
poly_arr: ARRAY [POLYGON]
When some value x is assigned to an element of this array, as in the call
poly_arr.put (x, some_index)
(for some valid value of the index some_index), the specification of class ARRAY indicates that the type of the assigned value must be compatible with the type of the actual generic parameter:
class ARRAY [G] creation
...
feature - Changing an element
put (v: G; i: INTEGER) is
-- Assign v to the element with index i
...
end
Since the type of the formal argument v, corresponding to x, is defined in the class as G, and the actual generic parameter corresponding to G in the call poly_arr is POLYGON, the type of x must be compatible with it. As we have seen, for this x need not have type POLYGON - any descendant of type POLYGON will do.
Therefore, if the bounds of the array are 1 and 4, we can declare some entities:
p: POLYGON; r: RECTANGLE; s: SQUARE; t: TRIANGLE
and, having created the corresponding objects, we can perform the operations
poly_arr.put (p, 1)
poly_arr.put (r, 2)
poly_arr.put (s, 3)
poly_arr.put (t, 4)
which will assign to the array's elements references to objects of different types.
Fig. 14.4. Polymorphic array
| In this figure, graphical objects are represented by the corresponding geometric shapes, rather than by ordinary object diagrams with a set of their fields. |
Such data structures, containing objects of different types that have a common ancestor, are called polymorphic data structures. Numerous examples of such structures will be examined further on. Arrays are only one possibility; any container structure can be polymorphic: lists, stacks, and so on.
Polymorphic data structures realize the goal formulated at the beginning of the lecture: combining generation and inheritance to achieve maximum flexibility and reliability. It is worth recalling Fig. 10.1, which illustrates this idea:
Fig. 14.5. Dimensions of generalization
The types that in Fig. 10.1 were informally called SET_OF_BOOKS and so on have been replaced by types derived from a generic universal type - SET [BOOK].
Such a combination of genericity and inheritance is a very powerful tool. It makes it possible to describe the structure of objects with the desired degree of generality. For example,
LIST [RECTANGLE]: can contain squares, but not triangles.
LIST [POLYGON]: can contain squares, rectangles, triangles, but not circles.
LIST [FIGURE]: can contain instances of any type from the FIGURE hierarchy, but not books or bank accounts.
LIST [ANY]: can contain objects of any type.
In the last case, the class ANY is used, which we agree to regard as the ancestor of every class (it will be examined in more detail later).
By varying the position, within the hierarchy, of the class chosen as the actual generic parameter, one can precisely set the bounds on the types of objects allowed in the container being defined.
The remarkable flexibility provided by inheritance does not come at the cost of reliability, since static type checking is used, guaranteeing at compile time the absence of incorrect type combinations at run time.
Inheritance is consistent with the type system. The basic rules are easy to explain using the example given above. Suppose that the following declarations exist:
p: POLYGON
r: RECTANGLE
Let us pick out the relevant fragment in the hierarchy given above (Fig. 14.6).
Then the following expressions are legal:
[x]. p.perimeter: no problem, since perimeter is defined for polygons;
[x]. p.vertices, p.translate (...), p.rotate (...) with correct arguments;
[x]. r.diagonal, r.side1, r.side2: these three components are declared at the level of RECTANGLE or QUADRANGLE;
[x]. r.vertices, r.translate (...), r.rotate (...): these components are declared at the level of POLYGON or higher, and are therefore applicable to rectangles, which inherit all the components of polygons;
[x]. r.perimeter: the same as in the previous case. But the function called here has a new definition in class RECTANGLE, so it differs from the function with the same name in class POLYGON.
Fig. 14.6. Fragment of the geometric figure hierarchy
But the following component calls are illegal, since these components are not available at the level of a polygon:
p.side1
p.side2
p.diagonal
This discussion is based on the first fundamental rule of typing:
Component Call Rule
If the type of entity x is based on class C, then in the component call x.f the component f itself must be defined in one of the ancestors of C.
Recall that a class C is its own ancestor. The phrase "the type of entity x is based on class C" is a reminder that, for classes derived from generic ones, the type may include more than just the class name: LINKED_LIST [INTEGER]. But the base class for the type is LINKED_LIST, so the generic parameter plays no part in our rule.
Like all the other correctness rules considered in this book, the Component Call Rule is static - it can be checked from the text of the system, rather than as it executes. The compiler (which, as a rule, performs this check) will reject classes containing incorrect component calls. If the checking of the typing rules is successfully implemented, there is no risk that the compiled system will ever, at run time, apply some component to an object of an unsuitable type.
Static typing is one of the main resources of OO technology for achieving the goal stated in Lecture 1 - the reliability of software.
| It has already been noted that not all approaches to building OO software have static typing. The best-known representative of languages with dynamic typing is Smalltalk, in which the static call rule does not apply, but a computation is allowed to terminate abnormally when an error occurs: "message not understood". The lecture devoted to typing will give a comparison of the different approaches. |
Unrestricted polymorphism would be incompatible with the static notion of type. The admissibility of polymorphic operations is determined by inheritance.
All the examples of polymorphic assignment, such as p := r and p := t, use descendants of the target class as the source type. We say that in such a case the type of the source is compatible with the class of the target. For example, SQUARE is compatible with RECTANGLE and with POLYGON, but not with TRIANGLE. To make this notion more precise, let us give a formal definition:
Definition: conformance
Type U conforms to type T only if the base class for U is a descendant of the base class for T; in addition, for generically derived types, each actual parameter of U must (recursively) conform to the corresponding formal parameter of T.
Why is the notion of descendant not sufficient in this definition? The reason, again, is that derivation from generic classes is allowed, so types and classes must be distinguished. For every type there is a base class, which, in the absence of derivation, coincides with the type itself (for example, POLYGON is its own base). For a generically derived class, however, the base is the generic class with its generic parameters omitted. For example, for class LIST [POLYGON] the base will be class LIST. The second part of the definition states that B [Y] will conform to A [X] if B is a descendant of A, and Y is a descendant of X.
Note that since every class is its own descendant, every type conforms to itself.
With this generalization of the notion of descendant, we obtain the second important rule of typing:
Type Conformance Rule
The attachment of target x to source y (that is, the assignment x:=y, or the use of y as the actual parameter in a procedure call with the corresponding formal parameter x) is admissible only when the type of y conforms to the type of x.
The Type Conformance Rule expresses the fact that the specialized can be assigned to the general, but not the other way around. Hence the assignment p := r is admissible, while r := p is not.
| This rule can be illustrated as follows. Suppose I am so deranged that I sent the company Pets-By-Mail an order for "Animal" ("the animal"). In that case, whatever I receive - a dog, a ladybug, or a killer whale - I will have no right to complain. (It is assumed that DOG and all the others are descendants of class ANIMAL.) But if I ordered a dog, and the mailman brought me, one morning, a box labeled ANIMAL, or, say, MAMMAL, then I have the right to return it to the sender, even if unmistakable barking and yapping can be heard coming from it. Since my order was not fulfilled according to specification, I owe the firm Pets-By-Mail nothing. |
With the introduction of polymorphism, we need to refine the terminology related to instances. Informally, instances of a class are run-time objects built according to the class's definition. But now we must also regard, in this role, objects built for proper descendants of the class. Here is a more precise definition:
Definition: direct instance, instance
A direct instance of class C is an object created in accordance with the exact definition of C, by means of the creation instruction create x ..., in which the target x has type C (or, recursively, by cloning a direct instance of C).
An instance of C is a direct instance of a descendant of C.
From the last part of this definition it follows that a direct instance of class C is also an instance of C, since a class is included among its own descendants.
Thus, executing the fragment:
p1, p2: POLYGON; r: RECTANGLE
...
create p1 ...; create r ...; p2 := r
will create two instances of class POLYGON, but only one direct instance (the one attached to p1). The other object, pointed to by p2 and r, is a direct instance of class RECTANGLE, and hence an instance of both classes POLYGON and RECTANGLE.
Although the notions of direct instance and instance were defined above for classes, they extend naturally to any type (with a base class and possible generic parameters).
Polymorphism means that an element of some type can be attached not only to direct instances of that type, but also to its other instances. We can regard the role of the Type Conformance Rule as ensuring the following property:
Static-dynamic type consistency
An entity of type T may, at run time, become attached only to instances of class T.
The name of the last property presupposes a distinction between "static type" and "dynamic type". The type used when declaring some element is the static type of the corresponding reference. If, at run time, this reference becomes attached to an object of some type, that type becomes the dynamic type of the reference.
Thus, given the declaration p: POLYGON, the static type of the reference denoted by p is POLYGON; after executing create p, the dynamic type of this reference is also POLYGON; and after the assignment p := r, where r has type RECTANGLE and is not void, the dynamic type becomes RECTANGLE.
The Type Conformance Rule states that the dynamic type must always conform to the static type.
To avoid confusion, let us recall that we are dealing with three levels: an entity is a certain identifier in the text of a class; at run time, its value is a reference (except in the expanded case); a reference may be attached to an object.
An object has only a dynamic type, which it acquired at the moment of its creation. This type does not change during the object's lifetime.
At every moment during execution, a reference has a dynamic type - the type of the object to which it is currently attached (or the special type NONE, if the reference is void). The dynamic type may change as a result of reattachment operations.
Only an entity has both a static and a dynamic type. Its static type is the type with which it was declared: if the declaration has the form x: T, then this type is T. Its dynamic type, at every moment of execution, is the type of the value of this reference, i.e. of the object to which it is attached.
|
In the expanded case there is no reference; the value of x is an object of type T, and T is both the static type and the only possible dynamic type for x.
|
The typing rules given above may sometimes seem too strict. For example, the second instruction in both of the following cases is statically rejected:
1 p:= r; r := p
2 p := r; x := p.diagonal
In (1), it is forbidden to assign a polygon to a rectangle-entity, even though at run time it happens that this polygon is a rectangle (similar to how one might refuse to accept a dog because the cage is labeled "animal"). In (2), the component diagonal turns out not to be applicable to p, despite the fact that at run time it is, in fact, present.
But a more careful analysis shows that our rules are entirely justified. If a reference is to be attached to an object, it is better to avoid future problems by making sure that their types conform. And if one wants to apply some rectangle operation, why not simply declare the target as a rectangle in the first place?
In practice, cases like (1) and (2) are unlikely. Assignments of the form p:= r are usually found inside some control structures that depend on conditions determined at run time, for example, on input from the user. A more realistic polymorphic scheme might look like this:
create r.make (...); ...
screen.display_icons -- Displays icons for the various polygons
screen.wait_for_mouse_click -- Waits for a mouse click
x := screen.mouse_position -- Determines where the button was pressed
chosen_icon := screen.icon_where_is (x) -- Determines the icon
-- under which the mouse pointer is located
if chosen_icon = rectangle_icon then
p := r
elseif ...
p := "A polygon of another type" ...
end
... Use of p, for example, p.display, p.rotate, ...
In the last line, p may denote any polygon, so only the general components from class POLYGON can be applied to it. It is clear that operations suited to rectangles, such as diagonal, must be applied only to r (for example, in the first branch of the if). If p has to be used in the instructions following the if instruction, then only operations applicable to all kinds of polygons can be applied to it.
In another typical case, p is simply the formal parameter of a routine:
some_routine (p: POLYGON) is ...
and you can make the call some_routine (r), which is correct according to the type conformance rule. But when the routine is written, nothing is yet known about this particular call. In fact, the call some_routine (t) for t of type TRIANGLE, or of any other descendant of class POLYGON, will also be correct, so we may consider that p represents some kind of polygon - any of its kinds. Then it is only reasonable that p should have access to nothing but the components of class POLYGON.
Thus, whenever it is not possible to predict the exact type of the attached object, polymorphic entities (such as p) are extremely useful.
Since the concepts just introduced play an important role in what follows, it is worth restating a few of the last points once more. (In fact, this short section will contain nothing new, but it will help you better understand the basic concepts and prepare you for the introduction of new ones.)
If you are still uncomfortable with the impossibility of writing p.diagonal after the assignment p :=r (in case (2)), you are not alone. This comes as a shock to many people when they first encounter these concepts. We know that p is a rectangle, so why don't we have access to its diagonal? Because it would be useless. After a polymorphic assignment, as shown in the following excerpt from the earlier figure, one and the same object of type RECTANGLE has two names: the polygon name p and the rectangle name r.
Figure 14.7. After a polymorphic assignment
In this case, since we know that object O2 is a rectangle and is accessible through the rectangle name r, why would we try to access its diagonal through the operation p.diagonal? That makes no sense, since we can simply write r.diagonal, using the rectangle's official name and removing any doubt as to whether its operations may legitimately be applied. Using the polygon name p, which could just as well denote a triangle, gains nothing and only leads to uncertainty.
Indeed, polymorphism does lose information: when, as a result of the assignment p :=r, it becomes possible to refer to rectangle O2 through the polygon name p, something important is lost - the ability to use the rectangle's specific components. What benefit is there then? In this particular case, none. As already noted, the interest arises when it is not known in advance what kind of polygon p will be after executing the instruction if some_condition then p:= r else p := something_else ..., or when p is a formal argument of a routine and the type of the actual argument is not known. But in these cases it would be incorrect and dangerous to apply to p anything other than the components of class POLYGON.
|
Continuing with the animal theme, imagine that someone asks: "Do you have a pet?" and you answer: "Yes, a cat!". This is similar to a polymorphic assignment - one object is known under two names of different types: "my_pet" and "my_cat" now denote the same animal. But they do not serve the same purpose; the first name is less informative than the second. You can use either name equally well when calling the absent-owners department of the Pets-By-Mail company ("I am going on vacation, how much will it cost to have my_pet (or: my_cat) looked after for two weeks?") But when calling another department with the question: "May I bring my pet in on Tuesday to have its claws trimmed?", you will not be able to make an appointment until you specify that you meant your cat. |
In some cases it is necessary to perform an assignment that does not conform to the inheritance structure, and to accept that the result may not necessarily be an object. This does not usually happen when the OO method is applied to objects internal to some program. But it can happen, for example, when an object is obtained over a network together with its declared type, and since there is no way to control the origin of that object, static type declarations guarantee nothing, and before using the object it is necessary to check its type.
| On receiving a box labeled "Animal" instead of the expected label "Dog", you might be tempted to open it anyway, knowing that if a dog is not inside, you will lose the right to return the package and, depending on what emerges from it, you may even lose the ability to tell the story afterward. |
In such cases a new mechanism is needed - assignment attempt, which will allow writing an instruction of the form r ?= p (where ?= denotes the assignment attempt symbol, as opposed to := for ordinary assignment), meaning "perform the assignment if the type of the object conforms to r, otherwise make r void". But we are not yet ready to understand how such an instruction fits with the OO method, so we will return to this question in later lectures. (Until then, consider that you have read nothing about it.)
The introduction of inheritance and polymorphism leads to a small extension of the object creation mechanism, which will allow objects of descendant types to be created directly.
Recall that creation instructions (creation procedures) take one of the following forms:
create x
create x.make (...)
where the second form implies and requires that the base class for the type T attached to x contain a creation clause in which make is listed as one of the creation procedures. (Of course, the creation procedure may have any name - make is simply the recommended default.) The result of executing the first instruction is the creation of a new object of type T, its initialization with default values, and its attachment to x. When the second instruction is executed, make will be called with the given arguments to create and initialize the object.
Suppose that T has a proper descendant U. We might want to use x polymorphically and attach it directly to an instance of U rather than of T. One possible solution uses a local entity of type U.
some_routine (...) is
local
u_temp: U
do
...; create u_temp.make (...); x := u_temp; ...
end
This works, but it is too cumbersome, especially in the context of a multi-branch choice, where we might want to attach x to an instance of one of several possible descendant types. Local entities (u_temp in our example) play only a temporary role, and their declarations and assignments clutter the program text. Hence the need for special variants of the creation instructions:
create {U} x
create {U} x.make (...)
The result should be the same as for the create constructs shown above, except that the created object must be a direct instance of U rather than of T. This variant must satisfy an obvious constraint: the type U must conform to the type T, and in the second form make must be defined as a creation procedure in the class that is the base class for U; and if that class has one or more creation procedures, then only the second form is applicable. Note that it does not matter here whether class T itself has creation procedures - everything depends only on U.
A typical use is related to creating an instance of one of several possible types:
f: FIGURE
...
"Display the figure icons"
if chosen_icon = rectangle_icon then
create {RECTANGLE} f
elseif chosen_icon = circle_icon then
create {CIRCLE} f
else
...
end
This new kind of object creation construct leads us to introduce the notion of generating type, denoting the type of the object being created at the moment it is created by the constructor:
For the implicit-type form create x ..., the generating type is the type of x.
For the explicit-type form create {U} x ..., the generating type is U.
Dynamic binding will complement redefinition, polymorphism and static typing, forming the basic tetralogy of inheritance.
Operations defined for all kinds of polygons can be implemented differently. For example, perimeter (the perimeter) has different versions for general polygons and for rectangles; let us call these versions perimeterPOL and perimeterRECT. Class SQUARE will also have its own version (the side length multiplied by 4). This naturally raises an important question: what happens if a program having several versions is applied to a polymorphic entity?
In the fragment
create p.make (...); x := p.perimeter
it is clear that version perimeterPOL will be used. Similarly, in the fragment
create r.make (...); x := r.perimeter
version perimeterRECT will be used. But what if the polymorphic entity p is statically declared as a polygon, but dynamically refers to a rectangle? Suppose we need to execute the fragment:
create r.make (...)
p := r
x := p.perimeter
The rule of dynamic binding states that the version of the applied operation is determined by the dynamic form of the object. In this case it will be perimeterRECT.
Of course, a more interesting case arises when it is not possible to tell from the program text what dynamic type p will have at run time. For example, what will happen in the fragment
-- Compute the perimeter of the figure chosen by the user
p: POLYGON
...
if chosen_icon = rectangle_icon then
create {RECTANGLE} p.make (...)
elseif chosen_icon = triangle_icon then
create {TRIANGLE} p.make (...)
elseif
...
end
...
x := p.perimeter
or after the conditional polymorphic assignment if ... then p := r elseif ... then p := t ..., ; or if p is an element of a polymorphic array of polygons, or if p is a formal argument with declared type POLYGON of some routine, to which the calling routine has passed an actual argument of a conforming type?
Then, depending on how the computation proceeds, the dynamic type of p will be RECTANGLE, or TRIANGLE,
продолжение следует...
Часть 1 14. Inheritance in OOP: Kinds of Inheritance
Часть 2 Redefinition and Assertions - 14. Inheritance in OOP: Kinds of
Часть 3 Programs with holes - 14. Inheritance in OOP: Kinds of
Comments