Lecture
Это продолжение увлекательной статьи про наследование в ооп.
...
or something else. We have no way of knowing in advance which of these cases will occur. But thanks to dynamic binding, we do not need to know: whatever happens to p, the correct version of component perimeter will be executed when it is called.
This ability of operations to automatically adapt to the objects to which they are applied is one of the principal features of OO systems, directly related to the software quality issues discussed at the beginning of the book. Its consequences will be examined in more detail later in this lecture.
Dynamic binding lets us complete the discussion, begun above, of the aspects connected with the loss of information under polymorphism. It should now be clear why it is not dangerous to lose information about an object: after the assignment p := q, or the call some_routine (q) in which p was the formal argument, specific information about the type of q is lost, but if the operation p.polygon_feature is applied, and polygon_feature has a special version applicable to q, then it is precisely that version which will be executed.
|
It is quite acceptable to send your pets to the absent-owners department that serves all species, provided you know for certain that, when feeding time comes, your cat will get cat food and your dog will get dog food.
|
If a client of class POLYGON calls p.perimeter, it expects to obtain the value of the perimeter of p, as defined by the specification of function perimeter in the definition of that class. But now, thanks to dynamic binding, the client may actually invoke a different routine, redefined in some descendant class. In class RECTANGLE, the redefinition improves efficiency and does not change the result, but what would prevent someone from redefining the perimeter so that the new version computes, say, the area?
This goes against the spirit of redefinition. Redefinition should change the implementation of a routine, not its semantics. Fortunately, assertions make it possible to constrain the semantics of routines. Informally, the basic rule for controlling redefinition and dynamic binding can be stated simply: the precondition and postcondition of a routine must apply to any of its redefinitions, and, as we have already seen, a class invariant must automatically extend to all its descendants.
The precise rules will be given below. But we can already note that redefinition is not arbitrary: only semantics-preserving redefinitions are permitted. It is the responsibility of the program's author to express its semantics precisely enough, while still leaving freedom for future implementors.
One might fear that dynamic binding is an expensive mechanism, requiring a search through the inheritance graph at run time, and hence overhead that grows with the depth of that graph.
Fortunately, this is not the case for a well-designed (and statically typed) OO language. This will be discussed in more detail at the end of the lecture, but we can already reassure ourselves that the consequences of dynamic binding will not be significant for efficiency when working in a suitable environment.
Polymorphism and dynamic binding mean that in the process of designing software you can rely on abstractions, confident that at run time the appropriate implementation will be selected. But before execution, everything must be fully implemented.
A complete implementation, however, is not always necessary. Partially implemented or unimplemented abstract software elements are helpful in solving many problems: analyzing a problem and designing a system's architecture (in which case they can be kept in the final product to record the course of the analysis and design), fixing agreements between implementors, and describing intermediate points in a classification.
Deferred features and classes provide the necessary abstraction mechanism.
To understand the need for deferred routines and classes, let us again consider the figure hierarchy
FIGURE.
Figure 14.8. The FIGURE hierarchy again
The most general notion here is FIGURE. Based on the mechanisms of polymorphism and dynamic binding, we can try to apply the general scheme described earlier:
transform (f: FIGURE) is
-- Apply the specific transformation to f.
do
f.rotate (...)
f.translate (...)
end
with appropriate values for the omitted arguments. Then all of the following calls are correct:
transform (r) -- for r: RECTANGLE
transform (c) -- for c: CIRCLE
transform (figarray.item (i)) -- for an array of figures: ARRAY [POLYGON]
In other words, we need to apply the transformations rotate and translate to a figure f, and let the dynamic binding mechanism select the appropriate version (different for classes RECTANGLE and CIRCLE), depending on the current kind of figure f, which will be determined at run time.
This really works, and is a typical example of the elegant style made possible by polymorphism and dynamic binding, a style based on the Single Choice principle. All that is required is to redefine rotate and translate for the various classes involved in the computation.
But there is nothing to redefine! Class FIGURE is a very general notion, covering all kinds of two-dimensional figures. It is clear that it is impossible to write a version of routines rotate and translate suitable for figures "in general", without more specific information about their kind.
Thus we have a situation in which routine transform will execute correctly, thanks to dynamic binding, but is statically illegal, since rotate and translate are not components of class FIGURE. Type checking will detect errors in the calls f.rotate and f.translate.
One could, of course, introduce at the level of class FIGURE a routine rotate that does nothing. But this is a dangerous path: the component rotate (center, angle) has an intuitively well-understood semantics, and "doing nothing" is not a reasonable implementation of it.
Thus, we need a way to specify the components rotate and translate at the level of class FIGURE, which would place the responsibility for their actual implementation on the descendants of this class. This is achieved by declaring these components as "deferred". In this case the entire body of the routine's instructions is replaced by the keyword deferred. In class FIGURE there will be the declaration:
rotate (center: POINT; angle: REAL) is
-- Rotate by angle angle around point center.
deferred
end
and component translate will be declared similarly. This means that this component is known in the class where such a declaration appears, but its implementations reside in classes that are its proper descendants. In this case, a call of the form f.rotate in routine transform becomes legal.
A component declared in this way is called a deferred component. A component that is not deferred - one that has an implementation (for example, any of the components we have encountered so far) - is called effective.
In some proper descendants of class FIGURE it will be necessary to replace the deferred version with an effective one. For example,
class POLYGON inherit
CLOSED_FIGURE
feature
rotate (center: POINT; angle: REAL) is
-- Rotate by angle angle around point center.
do
... Instructions to rotate all the vertices ...
end
...
end
Note that POLYGON inherits the components of class FIGURE not directly, but through class CLOSED_FIGURE, in which routine rotate remains deferred.
This process of providing an implementation for a deferred component is called effecting. (An effective component is a component equipped with an implementation.)
There is no need to list, in the redefine clause of some class, deferred components that are given an implementation, since they had no real definition at the point of declaration. In this class, one simply places the definitions of such components, type-compatible with their original declarations, as for example in the case of component rotate.
Providing an implementation for a component is, of course, close to redefining it and, apart from being listed in a redefine clause, obeys the same rules. Hence a general term is needed.
Definition: redeclaration
A redeclaration of a component means defining or redefining its implementation.
The difference between these two forms of redeclaration is well illustrated by the examples given when they were introduced:
[x]. Going from POLYGON to RECTANGLE, the component perimeter is already implemented by the parent, and we want to provide a new implementation for it in class RECTANGLE. This is a redefinition. Note that this component is redefined once more in class SQUARE.
[x]. Going from FIGURE to POLYGON, the parent has no implementation of component rotate, and we want to implement it in class POLYGON. This is effecting. Proper descendants of POLYGON may, of course, redefine this effective version.
A need may arise to change some parameters of an inherited deferred component, after which it still remains deferred. These changes may affect the component's signature - the types of its arguments and result - and its assertions (the precise constraints will be given in the next lecture). Unlike the transition from a deferred component to an effective one, such a transition from deferred to deferred is regarded as a redefinition and requires a redefine clause. Here is a summary of the four possible cases of a new declaration:
| REDECLARATION OF COMPONENT TO | REDECLARATION OF COMPONENT FROM | |
|---|---|---|
| DEFERRED | EFFECTIVE | |
| DEFERRED | Redefinition | Undefinition |
| EFFECTIVE | Effecting | Redefinition |
Table 14.1.Effects of redeclaration
This table contains one case not yet discussed: undefinition - the transition from an effective component to a deferred one. Here the original implementation is cancelled and a new life begins.
As we have seen, a component can be deferred or effective. The same applies to classes.
Definition: deferred class, effective class
A class is deferred if it has a deferred component.
Otherwise, the class is effective.
Thus, for a class to be effective, all of its components must be effective. One or more deferred components make the class deferred. In this case, the class must carry a special label:
Deferred class declaration rule
The declaration of a deferred class must include the consecutive keywords deferred class (as opposed to the single keyword class for effective classes).
So class FIGURE will be declared as follows:
deferred class FIGURE feature
rotate (...) is
... Declarations of deferred components ...
... Declarations of other components ...
end
Conversely, if a class is marked as deferred, then it must have at least one deferred component. In this case, a class can be deferred even if it does not itself declare any deferred component, since it may have a deferred parent from which it inherited a deferred component that it did not make effective. In our example, class OPEN_FIGURE will most likely leave deferred the components display, rotate, and many others inherited from class FIGURE, since the notion of an open figure is not specific enough to support standard implementations of these operations. This class is therefore deferred and will be declared as
deferred class OPEN_FIGURE inherit
FIGURE
...
even if it does not itself introduce a single deferred component.
A descendant of a deferred class is an effective class if all the deferred components of its parents have effective definitions in it, and it does not introduce any deferred components of its own. Effective classes, such as POLYGON and ELLIPSE, must provide implementations for the deferred components display and rotate.
For convenience, we will call a type deferred if its base class is deferred. Thus, class FIGURE, viewed as a type, is deferred. If the generic class LIST is deferred (as it should be, if it represents the notion of a list independent of any particular implementation), then the type LIST [INTEGER] is deferred. Only the base class matters: C [X] will be effective if class C is effective, and deferred if C is deferred, regardless of the status of X.
We can now fully explain the graphical symbols used in Figure 14.8. An asterisk marks deferred components or classes:
FIGURE*
display*
perimeter* -- At the level of class OPEN_FIGURE in Figure 14.8
A plus sign means "effective" and marks the effecting of a component:
perimeter+ -- At the level of POLYGON in Figure 14.8
To indicate that a class is effective, it can be marked with the sign +. By default, an unmarked class is considered effective, just as, in textual form, the declaration class C without the keyword deferred means that the class is effective.
A single plus sign can be attached to a component to indicate that it has become effective. For example, the component perimeter appears as deferred and, hence, has the form perimeter* in class CLOSED_FIGURE. Then, at the level of POLYGON, an implementation is given for this component, and it is marked in this class as perimeter+.
Finally, two plus signs mark a redefinition:
perimeter++ -- At the level of RECTANGLE and SQUARE in Figure 14.8
The presence of deferred elements in a system raises the question: "what will happen if component rotate is applied to an object of type FIGURE?", or in general terms - "can a deferred component be applied to a direct instance of a deferred class?" The answer may be disconcerting: there is no such thing as an object of type FIGURE - there are no direct instances of deferred classes.
No instances of deferred classes rule
The generating type in a creation instruction may not be deferred.
Recall that the generating type is the type of x, for the form create x, and U for the form create {U} x. A type is considered deferred if its base class is deferred.
Hence the constructor call create f is incorrect and will be rejected by the compiler if the type of f is one of the deferred classes: FIGURE, OPEN_FIGURE, CLOSED_FIGURE. This rule eliminates the danger of erroneous component calls.
| Note, however, that even if the type of entity f is deferred, the explicit form of the creation instruction is still permitted - create{RECTANGLE} f, since here the generating type is an effective descendant of FIGURE - class RECTANGLE. We have already seen how this technique is used in the multi-branch creation instruction for objects of class FIGURE, which, depending on the context, will be instances of the effective classes RECTANGLE, CIRCLE, and others. |
It might seem that this rule limits the usefulness of deferred classes, making them just a syntactic trick for fooling the static type system. This would be true were it not for polymorphism and dynamic binding. You cannot create an object of type FIGURE, but you can declare a polymorphic entity of this type, and then use it without knowing exactly what type of object it is attached to in a particular computation:
f: FIGURE
...
f := "Some expression of an effective type, such as CIRCLE or POLYGON"
...
f.rotate (some_point, some_angle)
f.display
...
Such examples are the combination and culmination of the unique abstraction mechanisms of the OO method, such as classes, information hiding, Single Choice, inheritance, polymorphism, dynamic binding, deferred classes (and, as we shall see further on, assertions). You manipulate objects without knowing their exact types, supplying only the minimum information necessary for the required operations. Having the reliable seal of the type checker, certifying that calls to these operations are consistent with their declarations, you can count on a greater power - dynamic binding - which lets you apply the correct version of each operation without knowing exactly which version it is.
Although a deferred component has no implementation, and a deferred class either has no implementation or is only partially implemented, it is often necessary to specify their abstract semantic properties. Assertions can be used for this purpose.
Like other classes, a deferred class may have an invariant, and a deferred component may have a precondition, a postcondition, or both of these assertions.
Consider the example of linear lists, described independently of any particular implementation. As with many other structures of this kind, it is convenient to associate with each list a cursor, pointing to the current active element.
Figure 14.9. A list with a cursor
This class is deferred:
indexing
description: "Linear lists"
deferred class
LIST [G]
feature -- Access
count: INTEGER is
-- Number of elements
deferred
end
index: INTEGER is
-- Cursor position
deferred
end
item: G is
-- Element at cursor position
deferred
end
feature - Status report
after: BOOLEAN is
-- Is the cursor after the last element?
deferred
end
before: BOOLEAN is
-- Is the cursor before the first element?
deferred
end
feature - Cursor movement
forth is
-- Move the cursor forward one position.
require
not after
deferred
ensure
index = old index + 1
end
... Other components ...
invariant
non_negative_count: count >= 0
offleft_by_at_most_one: index >= 0
offright_by_at_most_one: index <= count + 1
after_definition: after = (index = count + 1)
before_definition: before = (index = 0)
end
Here the invariant expresses relations between the different queries. The first two clauses state that the cursor may go beyond the bounds of the set of elements by no more than one position on the left or on the right.
Figure 14.10. Cursor positions
| The last two clauses of the invariant could also be expressed as postconditions: ensure Result = (index = count + 1) for after and ensure Result = (index = 0) for before. Such a choice always arises when expressing properties that involve only argument-free queries. I prefer to use invariant clauses, viewing such properties as global properties of the class rather than attaching them to a particular component. |
The assertions on forth express precisely what this routine must do: move the cursor by one position. Since the cursor must stay within the bounds of the list of elements plus two "marker" positions on the left and right, applying forth requires that the condition not after hold, and the result, as stated in the postcondition, will be that index increases by one.
Here is another example - our old friend the stack. Our library will need a general class STACK [G], which will be deferred, since it must cover all possible implementations. Its proper descendants, such as FIXED_STACK and LINKED_STACK, will describe specific implementations. One of the deferred routines of class STACK is put:
put (x: G) is
-- Push x onto the top.
require
not full
deferred
ensure
not_empty: not empty
pushed_is_top: item = x
one_more: count = old count + 1
end
The boolean functions empty and full (also deferred at the level of STACK) express the stack's property of being empty and full.
It is only through assertions that deferred classes achieve their full power. As already noted (although the details will come in two lectures' time), preconditions and postconditions apply to all redefinitions of a routine. This is especially important in the deferred case: there, such assertions will constrain all admissible implementations. Thus, the specification given above constrains every version of put in the descendants of class STACK.
Through the use of assertions, deferred classes can be made sufficiently informative and semantically rich, despite lacking implementations.
At the end of this lecture we will return to deferred classes and examine more deeply their role in the process of OO analysis, design and implementation.
The ability to change the declaration of a component - to redefine it or to provide its implementation - provides flexibility and supports a consistent development process. There are two more techniques that reinforce these qualities:
[x]. The ability to change the declaration of a function into an attribute.
[x]. A simple way to refer to the original version from within the body of a new definition.
Redeclarations make it possible to actively apply one of the central principles of modularity - the principle of Uniform Access.
Recall (see lecture 3) that this principle states (originally in less technical terms, but we can now afford to be more precise) that, from the client's viewpoint, there should be no significant difference between an attribute and an argument-free function. In both cases the component is a query, and the only thing that distinguishes them is their internal representation.
The first example of this was the class describing bank accounts, in which the component balance could be implemented either as a function that adds deposits and subtracts withdrawals, or as an attribute, updated whenever necessary to reflect the current balance. To the client, this made no difference (except, perhaps, in efficiency).
With the introduction of inheritance, we can go further and allow an inherited function to be redefined as an attribute in a class.
Our earlier example is well suited to illustrate this. Suppose we have a class ACCOUNT1:
class ACCOUNT1 feature
balance: INTEGER is
-- Current balance
do
Result := list_of_deposits.total - list_of_withdrawals.total
end
...
End
Then, in a descendant, the second implementation from our original example may be chosen, redefining balance as an attribute:
class ACCOUNT2 inherit
ACCOUNT1
redefine balance end
feature
balance: INTEGER
-- Current balance
...
end
Presumably, class ACCOUNT2 will need to redefine certain routines, such as withdraw and deposit, so that, among their other duties, they also modify balance appropriately, maintaining as an invariant the property: balance = list_of_deposits.total - list_of_withdrawals.total.
In this example, the new declaration is a redefinition. Its result may also be the transformation of a deferred component into an attribute. For example, suppose that in the deferred class LIST there is a component
count: INTEGER is
-- Number of inserted elements
deferred
end
Then, in an implementation of the list, this component might be implemented as an attribute:
count: INTEGER
| If we are asked to apply this classification to split components into attributes and routines, we shall agree to regard a deferred component as a routine, even though for a deferred component with a result and no arguments, the very notion of being deferred means that we have not yet made the choice of how to implement it - as a function or as an attribute. The phrase "deferred component" conveys this indeterminacy and is preferable to the phrase "deferred routine". |
Redeclaring a function as an attribute, combined with polymorphism and dynamic binding, leads to the full realization of the Uniform Access principle. It is now possible not only to implement a client request of the form a.service either through storage or through computation, but the very same request may, during the course of a single computation, in some cases trigger access to some field, and in others invoke some function. This may happen, in particular, during the execution of one and the same call a.balance, if in the course of the computation a becomes polymorphically attached to objects of different classes.
One might expect that the reverse redefinition - of an attribute into an argument-free function - would also be allowed. But no. Assignment, an operation applicable to attributes, becomes meaningless for functions. Suppose that a is an attribute of class C, and some routine contains the instruction
a := some_expression
If a descendant of C redefines a as a function, then this function would not be applicable, since a function cannot be used on the left-hand side of an assignment.
This lack of symmetry (it is permitted to change the declaration of a function into that of an attribute, but not the other way around) is unfortunate, but unavoidable, and in practice it is not a serious obstacle. It means that declaring some component as an attribute is a final and irreversible choice, whereas declaring it as a function still leaves room for later implementations through storage, rather than through computation.
Consider some class that redefines a routine inherited from its parent. The usual pattern of redefinition consists of doing everything that the original version does, while adding some special actions either before or after it.
For example, class BUTTON, a descendant of class WINDOW, might redefine the component display that draws the button, so that the window is drawn first and then a border appears:
class BUTTON inherit
WINDOW
redefine display end
feature -- Output
display is
-- Display as a button.
do
"Display as a normal window"; -- See below
draw_border
end
... Other components ...
end
where draw_border is a routine of the new class. In order to "Display as a normal window", we must call the original version of display, technically known as the precursor of routine draw_border.
This is a sufficiently general case, and it is desirable to introduce a special notation for it. The construct
Precursor
can be used as the name of a component, but only within the body of the redefining routine. A call to this component, with arguments if needed, is a call to the parent's version of this routine (the precursor).
Hence, in the last example, the part "Display as a normal window" can simply be written as
Precursor
This will mean calling the original version of this routine from class WINDOW, which is permitted when the routine is redefined by the descendant class WINDOW. Precursor is a reserved entity name, just like Result or Current, and it is likewise written in italics with an initial capital letter.
In this example, the redefined component is a procedure, and hence the call to the construct Precursor is an instruction. This same call may also appear, when redefining a function, within an expression:
some_query (n: INTEGER): INTEGER is
-- The value returned by the parent's version, if it is
-- positive, zero otherwise
do
Result := (Precursor (n)).max (0)
end
|
In the case of multiple inheritance, discussed in the next lecture, a routine may have several precursors, which makes it possible to combine several inherited routines into one. To remove the resulting ambiguity, it will then be necessary to specify the parent, for example, Precursor {WINDOW}. Note that using the Precursor construct does not make the precursor component a component of the current class; only its redefined version is a component. (In particular, the precursor version may not satisfy the new invariant.) The purpose of the construct is to facilitate redefinition in cases where the new version includes the old one.
|
In a more complex case, where, in particular, both the precursor and the new versions need to be used as components of the class, one can make use of repeated inheritance, in which the parent's component is, in effect, duplicated, so that the heir ends up with two complete components. This will be discussed in detail when we examine repeated inheritance.
We have already examined the principal ways of using inheritance. Much still remains to be studied, in particular multiple inheritance and the details of what happens to assertions in the context of inheritance (the notion of subcontracting).
But first we should reflect on these fundamental notions and determine their significance for the question of software quality and for the software development process.
It is probably nowhere that the dual role of classes - as modules on the one hand, and as types on the other - shows up as clearly as in the study of inheritance. Viewed as a module, a descendant class describes an extension of the parent module; viewed as a type, it describes a subtype of the parent type.
Although some aspects of inheritance relate more to the view of a class as a type, most of them are useful under both approaches, as shown by the sample classification given here (which also reflects a few aspects not yet studied: renaming, descendant hiding, multiple and repeated inheritance). None of the aspects considered belongs exclusively to the view of a class as a module.
Figure 14.11. Inheritance mechanisms and their role
These two perspectives complement each other, giving inheritance its power and flexibility. This power may even seem frightening, which tempts some to propose splitting the mechanism in two: the ability to extend modules, and a mechanism for deriving subtypes. But once we look more deeply into the issue (in the lecture on inheritance methodology), we will find that such a split has many drawbacks and no clear advantages. Inheritance is a unifying principle; like many other unifying ideas in science, it brings together phenomena previously regarded as distinct.
From this perspective, inheritance is especially effective as a technique for reuse.
A module is a set of services offered to the outside world. Without inheritance, every new module would have to define on its own all the services it provides. Of course, the implementations of these services may rely on services provided by other modules: that is precisely the purpose of the "client" relation. But the only way to define a new module would be to add new services to previously defined modules.
Inheritance provides this possibility. If B is a descendant of A, then all the services (features) of A are automatically available in B, and there is no need to define them explicitly there. In line with its own purposes, B may add new features. Further flexibility is provided by redefinition, which lets B make different use of the implementations offered by A: some remain unchanged, while others are reworked into versions more suitable for this class.
This leads to a style of software development in which, instead of trying to solve every new problem from scratch, the solution is encouraged to build on earlier achievements and extend their results. Its rationale lies in economy - why repeat what has already been done once? - and in modesty, in the spirit of Newton's well-known remark that he was able to reach such heights only because he stood on the shoulders of giants.
The full benefit of this approach is best understood in terms of the Open-Closed principle, introduced in one of the earlier lectures. (It would be worth rereading that section in light of the concepts just introduced.) This principle states that a good module structure must be both closed and open.
[x]. Closed, because clients need the module's services to carry out their own development and, once fixed in some version of it, these services must not change when new services are introduced that the client does not need.
[x]. Open, since there is no guarantee that all the services potentially needed by some client were included in the module from the very start.
These two requirements pose a dilemma, and the classical module structure offers no key to resolving it. But inheritance solves this problem. A class is closed in that it can be compiled, stored in a library, and used by client classes. But it is also open, since any new class can use it as a parent, adding new features and changing the declarations of some inherited features, without any need to modify the original class or disturb its clients. This is a fundamental property in applying inheritance to the construction of reusable, extendible software.
|
If this idea were carried to the extreme, every class would simply add one feature to its parents! Of course, this is not recommended. The decision to finish a class should not be taken lightly; it should be based on a deliberate conclusion that the class, in its current state, already provides a logically consistent set of services - a coherent data abstraction - for potential clients. It should be remembered that the Open-Closed principle does not rule out the subsequent reworking of inadequate services. If a poor result was the consequence of an incorrect component specification, then we will not be able to modify the class without this affecting its clients. However, thanks to redefinition, the Open-Closed principle is still applicable if the change being introduced is consistent with the declared specification.
|
One of the most difficult questions in designing reusable module structures was the need to take advantage of the considerable commonality that can exist among different groups of similar data abstractions - among all hash tables, all sequential tables, and so on. By using class structures linked through inheritance, one can gain by knowing the logical relations between different implementations. Below, the diagram shows a rough and partial sketch of a possible structure for a library dealing with tables. This scheme naturally makes use of multiple inheritance, which will be discussed in detail in the next lecture.
Figure 14.12. A sketch of the structure of a table library
| This inheritance diagram represents only a sketch, although it shows the inheritance links typical of these structures. For a systematic classification of tables and other containers based on inheritance, see [M 1994a]. |
From this perspective, the requirement of reuse can be expressed quite precisely: the idea is to move the definition of each feature as high as possible in the inheritance hierarchy, so that it can be inherited by the largest possible number of descendant classes. One can picture this process as the reuse game, played on a board representing inheritance hierarchies (such as the one in figure 14.12), with pieces representing features. The winner is whoever, by discovering higher-level abstractions, manages to move as many features as possible as high as possible, and along the way, through the discovery of common properties, manages to merge the greatest number of pieces.
From the type perspective, inheritance addresses both reuse and extendibility, in particular what was called continuity in the earlier discussion. Here the key is dynamic binding.
A type is a set of objects characterized (as we know from ADT theory) by certain operations. INTEGER describes the set of integers with arithmetic operations, POLYGON is the set of objects with the operations vertices, perimeter, and others.
For types, inheritance represents the "is a" relation, as in the phrases "every dog is a mammal", "every mammal is an animal". Likewise, a rectangle is a polygon.
What does this relation mean?
[x]. If we consider the values of each type, this relation is simply set inclusion: dogs form a subset of the set of animals, instances of class RECTANGLE form a subset of the instances of class POLYGON. (This follows from the definition of "instance" given at the beginning of this lecture; note that a direct instance of class RECTANGLE is not a direct instance of class POLYGON.)
[x]. If we consider the operations applicable to each type, then saying that B is an A means that every operation applicable to A is also applicable to instances of B. (However, through redefinition, B may create its own implementation, which for instances of B will replace the implementation provided by A.)
Using this relation, one can describe "is a" schemes representing many variants of types, for example all the variants of class FIGURE. Each new version of routines such as rotate and display is defined in the class that specifies the corresponding type variant. In the case of tables, for example, each class in the graph provides its own implementation of the operations search, insert, delete, except of course when its parent's implementation is suitable for it.
A caution about the use of the "is a" ("is a") relation. Beginners - though I suppose not one of the readers
Having dynamic binding, one can create decentralized software architectures, needed to achieve the goals of reuse and extendibility. Let us compare the OO approach, in which self-contained classes provide their own sets of operation variants, with classical approaches. In Pascal or Ada, one can use a variant record type
type FIGURE =
record
"Common fields"
case figtype: (polygon, rectangle, triangle, circle,...) of
polygon: (vertices: LIST_OF_POINTS; count: INTEGER);
rectangle: (side1, side2: REAL;...);
...
end
to define the various kinds of figures. But this means that any program that must work with figures (rotating them, and so on) must carry out a case analysis:
case f.figure_type of
polygon: ...
circle: ...
...
end
In the case of tables, the search procedure would have to use the same structure. The trouble is that these procedures must possess excessive knowledge about the future of the whole system: they must know exactly which types of figures are permitted in it. Any addition of a new type, or change to an existing one, will affect every procedure.
Ne sutor ultra crepidam, (a cobbler should stick to his last) - this is a principle of software design: the rotation procedure does not need to know the full list of figure types. It needs only enough information to do its own job: rotating certain kinds of figures.
Distributing information among an excessive number of procedures is the main source of inflexibility in classical approaches to software development. The main difficulties of software modification can be traced back to this problem. It also partly explains why it is so hard to manage software projects, when quite small changes have far-reaching consequences, forcing developers to rework modules that seemed to have been successfully completed.
OO methods also face this problem. Changing the implementation of an operation affects only the class in which that implementation is used. Adding a new variant of some type will, in most cases, not affect other classes. The reason is decentralization: classes take care of their own implementations and do not meddle in each other's affairs. Applied to people, this would sound like Voltaire's Cultivez votre jardin - tend your own garden. Applied to modules, what matters is the requirement of obtaining decentralized structures that lend themselves gracefully to extension, modification, combination, and reuse.
Dynamic binding is connected with one of the key aspects of reuse: representation independence, that is, the ability to request the execution of some operation that has several variants without specifying which of them will be applied. In the earlier lecture, when this notion was discussed, the example of the call
present := has (x, t)
was used, which must apply the appropriate search algorithm depending on the kind of t at run time. If t is declared as a table but may be attached to an instance of a binary search tree, a hash table, and so on (assuming all the necessary classes are available), then with dynamic binding the call
present := t.has (x)
will find, at run time, the appropriate version of the procedure has. Dynamic binding achieves what was impossible to obtain through overloading and genericity: the client can request some operation, and the language support system will automatically find its corresponding implementation.
Thus, the combination of classes, inheritance, redefinition, polymorphism, and dynamic binding provides excellent answers to the questions posed at the beginning of this book: the requirements of reuse, and the criteria, principles, and rules of modularity.
Inheritance is sometimes viewed as extension, and sometimes as specialization. Although these two interpretations seem to contradict each other, both are true - but from different points of view.
Everything again depends on whether we view the class as a type or as a module. In the first case, inheritance, representing the "is a" relation, is specialization: "dog" is a more specialized notion than "animal", and "rectangle" than "polygon". As already noted, this corresponds to the inclusion of a subset in a set: if B is a descendant of A, then the set of objects representing B at run time is a subset of the corresponding set for A.
But from the module point of view, in which a class is regarded as a supplier of services, B implements the services of A plus its own. A small number of objects are often allowed to have more features, since this leads to an increase in information. Moving from arbitrary animals to dogs, we can add the property specific to them, "bark", and moving from polygons to rectangles we can add the feature "diagonal". Therefore, with respect to implemented features, the inclusion relation points in the other direction: the features applicable to instances of A are a subset of the features applicable to instances of B.
| >Here we are talking about implemented features, not about services offered (to clients), because when information hiding is combined with inheritance, as we shall see, B may hide from its clients some of the features that A exported to its own clients. |
Thus, inheritance is specialization from the type point of view and extension from the module point of view. This is precisely the extension-specialization paradox: the more features that are applicable, the fewer the objects to which they apply.
The extension-specialization paradox is one of the reasons for abandoning the term "subclass", which suggests the notion of "subset". Another reason, already noted, is the confusing use, found in the literature, of the term "subclass" to denote both direct and indirect inheritance. These problems do not arise when precisely defined terms are used: heir, descendant, and proper descendant, and their duals: parent, ancestor, and proper ancestor.
Deferred classes are one of the most important inheritance-related mechanisms intended to solve the software construction problems described at the beginning of the book.
Deferred classes richly endowed with assertions are well suited to representing ADTs. An excellent example is the deferred class for stacks. We have already described the procedure put; let us now give a possible version of the full description of this class.
indexing
description:
"Stacks (Last-in, First-out storage structures), %
%independent of the choice of representation"
deferred class
STACK [G]
feature -- Access
count: INTEGER is
-- Number of elements.
deferred
end
item: G is
-- Last inserted element.
require
not_empty: not empty
deferred
end
feature - Status report
empty: BOOLEAN is
-- Is the stack empty?
do
Result := (count = 0)
end
full: BOOLEAN is
-- Is the stack full?
deferred
end
feature - Element change
put (x: G) is
-- Push x onto the top.
require
not full
deferred
ensure
not_empty: not empty
pushed_is_top: item = x
one_more: count = old count + 1
end
remove is
-- Remove the top element.
require
not empty
deferred
ensure
not_full: not full
one_less: count = old count - 1
end
change_top (x: T) is
-- Replace the top element with x
require
not_empty: not empty
do
remove; put (x)
ensure
not_empty: not empty
new_top: item = x
same_number_of_items: count = old count
end
wipe_out is
-- Remove all elements.
deferred
ensure
no_more_elements: empty
end
invariant
non_negative_count: count >= 0
empty_count: empty = (count = 0)
end
This class shows how an effective procedure can be implemented using deferred ones: for example, the procedure change_top is implemented as successive calls to the procedures remove and put. (Such an implementation may not be the best for some representations, for example arrays, but efficient descendants of class STACK can redefine it.)
If we compare class STACK with the specification of the corresponding ADT given in lecture 6, a striking resemblance emerges. Let us stress, in particular, the correspondence between the ADT's functions and the class's features, and between the PRECONDITIONS clause and the procedures' preconditions. The axioms are represented in the procedures' postconditions and in the class invariant.
The addition of the operations change_top, count, and wipe_out is inessential here, since they could easily be included in the ADT specification (see exercise E6.8). The absence of an explicit equivalent of the ADT's new function is also inessential, since object creation will be handled by creation procedures in the efficient descendants of this class. Three essential differences remain.
The first is the introduction of the function full, intended for implementations with a bounded number of stack elements, for example an array-based implementation. This is a typical example of a restriction that is inessential at the specification level but necessary for developing practical systems. Note, however, that this difference between the ADT and the deferred class can easily be removed by including in the ADT specification the means to cover bounded stacks. Generality is not lost in doing so, since some implementations (for example, using lists) can implement full with trivial procedures that always return false.
The second difference, noted when discussing design by contract, is that the ADT specification is fully applicative (functional): it consists of functions with no side effects. A deferred class, despite its abstractness, is imperative (procedural); for example put is defined as a procedure that changes the stack, rather than as a function that takes one stack as an argument and returns another.
Finally, as has also already been noted, the assertion mechanism is not expressive enough for some ADT axioms. Of the four stack axioms
For all x: G, s: STACK [G],
1 item (put (s, x)) = x
2 remove (put (s, x)) = s
3 empty (new)
4 not empty (put (s, x))
all except (2) have direct equivalents among the assertions. (We assume that for (3) the creation procedures of the descendants will ensure that the empty condition holds.) The reasons for such limitations have already been explained, and possible ways of overcoming them have been outlined - formal specification languages such as IFL.
Not all deferred classes are as close to an ADT as STACK. Between a fully abstract class such as STACK, in which all the essential features are deferred, and an effective class such as FIXED_STACK, describing a single implementation of an ADT, there is room for ADT implementations with varying degrees of completeness.
A typical example is the hierarchy of table implementations, which helped us understand the role of partial commonality when studying reuse. The original figure showing the relations between variants can now be redrawn as an inheritance diagram.
Figure 14.13. Variants of the notion of "table"
The most general class, TABLE, is fully or almost fully deferred, since at this level we can declare several features but cannot offer any substantial implementation of them. Among the variants is the class SEQUENTIAL_TABLE, representing tables into which elements are inserted sequentially. Examples of such tables are arrays, linked lists, and sequential files. The corresponding classes at the bottom of the figure are effective.
Classes such as SEQUENTIAL_TABLE are of particular interest. This class is still deferred, but its status lies midway between the fully deferred status of a class such as TABLE and the fully effective status of a class such as ARRAY_TABLE. It has enough information to allow itself the implementation of certain specific algorithms; for example, it can fully implement sequential search:
has (x: G): BOOLEAN is
-- Is x present in the table?
do
from start until after or else equal (item, x) loop
forth
end
Result := not after
end
This function is effective, although its algorithm uses deferred features. The features start (place the cursor at the first position), forth (move the cursor one position forward), item (the value of the element at the cursor position), and after (is the cursor past the last element?) are deferred in class SEQUENTIAL_TABLE, and each of the descendants of this class shown in the figure implements them differently.
These implementations were given earlier in the discussion of reuse. For example, class ARRAY_TABLE may represent the cursor by a number i, so that the procedure start is implemented as i := 1, and item as t @ i, and so on.
Note the importance of including a precondition and postcondition for the feature forth, as well as an invariant for the enclosing class, to guarantee that all future implementations will satisfy the same basic specification. These assertions were given earlier in this lecture (in a somewhat different context, for class LIST, but they apply directly here as well).
This discussion fully illustrates the correspondence between classes and ADTs:
[x]. A fully deferred class, such as TABLE, corresponds to an ADT.
[x]. A fully effective class, such as ARRAY_TABLE, corresponds to an implementation of an ADT.
[x]. A partially deferred class, such as SEQUENTIAL_TABLE, corresponds to a family of implementations (or, equivalently, a partial implementation) of an ADT.
A class such as SEQUENTIAL_TABLE, which accumulates traits common to several variants of an ADT, can be called a behavior class. Behavior classes provide important patterns for building OO software.
Class SEQUENTIAL_TABLE gives an idea of how OO technology, through the notion of a behavior class, answers the question of "Factoring out common behaviors", left open at the end of lecture 4.
Particularly interesting is the possibility of defining, in a behavior class, an effective procedure whose implementation uses deferred procedures. This possibility is illustrated above by the procedure has. It shows how partially deferred classes can be used to capture the common behavior of several variants. The deferred class describes only what is common to all of them, leaving the description of the variations to the descendants.
A
продолжение следует...
Часть 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