574 INHERITANCE TECHNIQUES $16.1 Of course I can only compute an approximation of the inverse of a matrix.I am prepared to guarantee a certain precision of the result,but since I am not very good at numerical analysis,I shall only accept requests for a precision not better than 10-6.The resulting routine will look like this: invert (epsilon:REAL)is --Inverse of current matrix,with precision epsilon require epsilon>=10A(-6) do “Computation of inverse” ensure ((Current inverse)One)<=epsilon end The postcondition assumes that the class has a function infix "-"such that m/m2 is m/-m2,the norm of the matrix difference of m/and m2,and a function infix "* which yields the product of two matrices;One is assumed to denote the identity matrix. I am not too proud of myself,so for the summer I hire a bright young programmer- numerician who rewrites my imert routine using a much better algorithm,which approximates the result more closely and accepts a smaller epsilon: require Warning:syntacti- cally not valid as a epsilon>=10(-20) redefinition.See next. ensure ((Current inverse)One)<=(epsilon 2) The author of this new version is far too clever to rewrite a full MATRIY class;only a few routines need adaptation.They will be included in a descendant of MATRIY,say NEW MATRIX. If the new assertions are in a redefinition,they must use a different syntax than shown above.The rule will be given shortly. The change of assertions satisfies the Assertion Redeclaration rule:the new precondition epsilon>10(-20)is weaker than (that is to say,implied by)the original epsilon >=10^(-6);and the new postcondition is stronger than the original. This is how it should be.A client of the original MATRIX may be requesting a matrix inversion but,through dynamic binding,actually calling the NEW MATRIX variant.The client could contain a routine some client routine (ml:MATRIX;precision:REAL)is do ...ml.invert (precision),.. --May use either the MATRIX or the NEW MATRIX version end to which one of its own clients passes a first argument of type NEW MATRIY
574 INHERITANCE TECHNIQUES §16.1 Of course I can only compute an approximation of the inverse of a matrix. I am prepared to guarantee a certain precision of the result, but since I am not very good at numerical analysis, I shall only accept requests for a precision not better than 10–6. The resulting routine will look like this: invert (epsilon: REAL) is -- Inverse of current matrix, with precision epsilon require epsilon >= 10 ^ (–6) do “Computation of inverse” ensure ((Current ∗ inverse) |–| One) <= epsilon end The postcondition assumes that the class has a function infix "|–|" such that m1 |–| m2 is |m1 — m2|, the norm of the matrix difference of m1 and m2, and a function infix "∗" which yields the product of two matrices; One is assumed to denote the identity matrix. I am not too proud of myself, so for the summer I hire a bright young programmernumerician who rewrites my invert routine using a much better algorithm, which approximates the result more closely and accepts a smaller epsilon: require epsilon >= 10 ^ (–20) … ensure ((Current ∗ inverse) |–| One) <= (epsilon / 2) The author of this new version is far too clever to rewrite a full MATRIX class; only a few routines need adaptation. They will be included in a descendant of MATRIX, say NEW_MATRIX. If the new assertions are in a redefinition, they must use a different syntax than shown above. The rule will be given shortly. The change of assertions satisfies the Assertion Redeclaration rule: the new precondition epsilon >= 10 ^ (–20) is weaker than (that is to say, implied by) the original epsilon >= 10 ^ (–6); and the new postcondition is stronger than the original. This is how it should be. A client of the original MATRIX may be requesting a matrix inversion but, through dynamic binding, actually calling the NEW_MATRIX variant. The client could contain a routine some_client_routine (m1: MATRIX; precision: REAL) is do … ; m1 ● invert (precision); … -- May use either the MATRIX or the NEW_MATRIX version end to which one of its own clients passes a first argument of type NEW_MATRIX. Warning: syntactically not valid as a redefinition. See next
$16.1 INHERITANCE AND ASSERTIONS 575 NEW MATRIY must be able to accept and handle correctly any call that MATRIY would accept.If we made the precondition of the new invert stronger than the original (as in epsilon>=(-5)),calls which are correct for MATRIX would now be incorrect;if we made the postcondition weaker,the result returned would not be as good as guaranteed by MATRIY.By using a weaker precondition and a stronger postcondition we correctly treat all calls from clients of MATRIY,while offering a better deal to our own clients. Cutting out the middleman The last comment points to an interesting consequence of the Assertion Redeclaration rule.In our general scheme ris The routine, require the client and 0 the sub- ensure contractor B end r++is require Y ensure 6 end the assertions of the redeclared version,y and 8,if different from a and B,are more favorable to the clients,in the sense explained earlier (weaker precondition,stronger postcondition).But a client of 4 which uses 4'through polymorphism and dynamic binding cannot make good use of this improved contract,since its only contract is with 4. Only by becoming a direct client of'(the shaded link with a question mark on the last figure)can you take advantage of the new contract,as in al:A' if al.y then al.r end check al.δend --i.e.the postcondition holds But then of course you have specialized al to be of type A,not the general 4;you have lost the polymorphic generality of going through 4. The tradeoff is clear.A client of MATRIY must satisfy the original (stronger) precondition,and may only expect the original (weaker)postcondition;even if its request gets served dynamically by NEW MATRIX it has no way of benefiting from the broader tolerance of inputs and tighter precision of results.To get this improved specification it must declare the matrix to be of type NEW MATRIY,thereby losing access to other implementations represented by descendants of M4TRIY that are not also descendants of NEW MATRIY
§16.1 INHERITANCE AND ASSERTIONS 575 NEW_MATRIX must be able to accept and handle correctly any call that MATRIX would accept. If we made the precondition of the new invert stronger than the original (as in epsilon >= ^ (–5)), calls which are correct for MATRIX would now be incorrect; if we made the postcondition weaker, the result returned would not be as good as guaranteed by MATRIX. By using a weaker precondition and a stronger postcondition we correctly treat all calls from clients of MATRIX, while offering a better deal to our own clients. Cutting out the middleman The last comment points to an interesting consequence of the Assertion Redeclaration rule. In our general scheme the assertions of the redeclared version, γ and δ, if different from α and β, are more favorable to the clients, in the sense explained earlier (weaker precondition, stronger postcondition). But a client of A which uses A' through polymorphism and dynamic binding cannot make good use of this improved contract, since its only contract is with A. Only by becoming a direct client of A' (the shaded link with a question mark on the last figure) can you take advantage of the new contract, as in a1: A' … if a1 ● γ then a1 ● r end check a1 ● δ end -- i.e. the postcondition holds But then of course you have specialized a1 to be of type A', not the general A; you have lost the polymorphic generality of going through A. The tradeoff is clear. A client of MATRIX must satisfy the original (stronger) precondition, and may only expect the original (weaker) postcondition; even if its request gets served dynamically by NEW_MATRIX it has no way of benefiting from the broader tolerance of inputs and tighter precision of results. To get this improved specification it must declare the matrix to be of type NEW_MATRIX, thereby losing access to other implementations represented by descendants of MATRIX that are not also descendants of NEW_MATRIX. The routine, the client and the subcontractor A r is require α … ensure β end C A' r++ is require γ … ensure δ end ?
576 INHERITANCE TECHNIQUES $16.1 Subcontracting The Assertion Redeclaration rule fits nicely in the Design by Contract theory introduced in the chapter bearing that title. We saw that the assertions of a routine describe the contract associated with that routine:the client is bound by the precondition and entitled to the postcondition,and conversely for the class implementer. Inheritance,with redeclaration and dynamic binding,means subcontracting.When you have accepted a contract,you do not necessarily want to carry it out yourself. Sometimes you know of somebody else who can do it cheaper and perhaps better.This is exactly what happens when a client requests a routine from M4TR/Y but,through dynamic binding,may actually call at run time a version redefined in a proper descendant.Here "cheaper"refers to routine redefinition for more efficiency,as in the rectangle perimeter example of an earlier chapter,and "better"to improved assertions in the sense just seen. The Assertion Redeclaration rule simply states that if you are an honest subcontractor and accept a contract,you must be willing to do the job originally requested, or better than the requested job,but not less. The scheme described in the last section-declaring a/of type 4'to benefit from the improved contract-is similar to the behavior of a customer who tries to get a better deal by bypassing his contractor to work directly with the contractor's own subcontractor In the Design by Contract view,class invariants are general constraints applying to both contractors and clients.The parents'invariant rule expresses that all such constraints are transmitted to subcontractors. It is only with assertions,and with the two rules just seen,that inheritance takes on its full meaning for object-oriented design.The contracting-subcontracting metaphor is a powerful analogy to guide the development of correct object-oriented software;certainly one of the central deas. Abstract preconditions The rule on weakening preconditions may appear too restrictive in the case of an heir that restricts the abstraction provided by its parent.Fortunately,there is an easy workaround, consistent with the theory. A typical example arises if you want to make a class BOUNDED STACK inherit from a general STACK class.In BOUNDED_STACK the procedure for pushing an element onto the stack,put,has a precondition,which requires count <capacity,where count is the current number of stack elements and capacity is the physically available size. For the general notion of STACK,however,there is no notion of capacity.So it seems we need to strengthen the precondition when we move down to BOUNDED STACK.How do we build this inheritance structure without violating the Assertion Redeclaration rule? The answer is straightforward if we take a closer look at client needs.What needs to be kept or weakened is not necessarily the concrete precondition as implemented by the
576 INHERITANCE TECHNIQUES §16.1 Subcontracting The Assertion Redeclaration rule fits nicely in the Design by Contract theory introduced in the chapter bearing that title. We saw that the assertions of a routine describe the contract associated with that routine: the client is bound by the precondition and entitled to the postcondition, and conversely for the class implementer. Inheritance, with redeclaration and dynamic binding, means subcontracting. When you have accepted a contract, you do not necessarily want to carry it out yourself. Sometimes you know of somebody else who can do it cheaper and perhaps better. This is exactly what happens when a client requests a routine from MATRIX but, through dynamic binding, may actually call at run time a version redefined in a proper descendant. Here “cheaper” refers to routine redefinition for more efficiency, as in the rectangle perimeter example of an earlier chapter, and “better” to improved assertions in the sense just seen. The Assertion Redeclaration rule simply states that if you are an honest subcontractor and accept a contract, you must be willing to do the job originally requested, or better than the requested job, but not less. The scheme described in the last section — declaring a1 of type A' to benefit from the improved contract — is similar to the behavior of a customer who tries to get a better deal by bypassing his contractor to work directly with the contractor’s own subcontractor In the Design by Contract view, class invariants are general constraints applying to both contractors and clients. The parents’ invariant rule expresses that all such constraints are transmitted to subcontractors. It is only with assertions, and with the two rules just seen, that inheritance takes on its full meaning for object-oriented design. The contracting-subcontracting metaphor is a powerful analogy to guide the development of correct object-oriented software; certainly one of the central deas. Abstract preconditions The rule on weakening preconditions may appear too restrictive in the case of an heir that restricts the abstraction provided by its parent. Fortunately, there is an easy workaround, consistent with the theory. A typical example arises if you want to make a class BOUNDED_STACK inherit from a general STACK class. In BOUNDED_STACK the procedure for pushing an element onto the stack, put, has a precondition, which requires count <= capacity, where count is the current number of stack elements and capacity is the physically available size. For the general notion of STACK, however, there is no notion of capacity. So it seems we need to strengthen the precondition when we move down to BOUNDED_ STACK. How do we build this inheritance structure without violating the Assertion Redeclaration rule? The answer is straightforward if we take a closer look at client needs. What needs to be kept or weakened is not necessarily the concrete precondition as implemented by the
$16.1 INHERITANCE AND ASSERTIONS 577 supplier(which is the supplier's business),but the precondition as seen by the client. Assume that we write put in STACK as put (x:G)is --Push x on top. require not full deferred ensure 4+4 end with a function/il/defined always to return false,so that by default stacks are never full: full:BOOLEAN is --Is representation full? --(Default:no) do Result:=False end Then it suffices in BOUNDED STACK to redefine full: full:BOOLEAN is --Is representation full? --(Answer:if and only if number of items is capacity) do Result:=(count capacity)end A precondition such as not ful/,based on a property that is redefinable in descendants,is called an abstract precondition. This use of abstract preconditions to satisfy the Assertion Redeclaration rule may appear to be cheating,but it is not:although the concrete precondition is in fact being strengthened,the abstract precondition remains the same.What counts is not how the assertion is implemented,but how it is presented to the clients as part of the class interface (the short or flat-short form).A protected call of the form if not s.full then s.put (a)end will be valid regardless of the kind of STACK attached to s. There is,however,a valid criticism of this approach:it goes against the Open-Closed principle.We must foresee,at the STA4CK level,that some stacks will have a bounded capacity;if we have not exerted such foresight,we must go back to STACK and change its interface.But this is inevitable.Of the following two properties A bounded stack is a stack. It is always possible to add an element to a stack. one must go.If we want the first property,permitting BOUNDED STACK to inherit from STACK,we must accept that the general notion of stack includes the provision that a put operation is not always possible,expressed abstractly by the presence of the query fill
§16.1 INHERITANCE AND ASSERTIONS 577 supplier (which is the supplier’s business), but the precondition as seen by the client. Assume that we write put in STACK as put (x: G) is -- Push x on top. require not full deferred ensure … end with a function full defined always to return false, so that by default stacks are never full: full: BOOLEAN is -- Is representation full? -- (Default: no) do Result := False end Then it suffices in BOUNDED_STACK to redefine full: full: BOOLEAN is -- Is representation full? -- (Answer: if and only if number of items is capacity) do Result := (count = capacity) end A precondition such as not full, based on a property that is redefinable in descendants, is called an abstract precondition. This use of abstract preconditions to satisfy the Assertion Redeclaration rule may appear to be cheating, but it is not: although the concrete precondition is in fact being strengthened, the abstract precondition remains the same. What counts is not how the assertion is implemented, but how it is presented to the clients as part of the class interface (the short or flat-short form). A protected call of the form if not s ● full then s ● put (a) end will be valid regardless of the kind of STACK attached to s. There is, however, a valid criticism of this approach: it goes against the Open-Closed principle. We must foresee, at the STACK level, that some stacks will have a bounded capacity; if we have not exerted such foresight, we must go back to STACK and change its interface. But this is inevitable. Of the following two properties • A bounded stack is a stack. • It is always possible to add an element to a stack. one must go. If we want the first property, permitting BOUNDED_STACK to inherit from STACK, we must accept that the general notion of stack includes the provision that a put operation is not always possible, expressed abstractly by the presence of the query full
578 INHERITANCE TECHNIQUES $16.1 It would clearly be a mistake,in class STACK,to include Result=False as a postcondition for fil/or(equivalently but following the recommended style)an invariant clause not full.This would be a case of overspecification as mentioned earlier,hampering the descendants'freedom to adapt the feature. The language rule The Assertion Redeclaration rule as given so far is a conceptual guideline.How do we transform it into a safe,checkable language rule? We should in principle rely on a logical analysis of the old and new assertions,to verify that the old precondition logically implies the new one,and that the new postcondition implies the old one.Unfortunately,such a goal would require a sophisticated theorem prover which,if at all feasible,is still far too difficult (in spite of decades of research in artificial intelligence)to be integrated routinely among the checks performed by a compiler. Fortunately a low-tech solution is available.We can enforce the rule through a simple language convention,based on the observation that for any assertions o and B: o implies o or y,regardless of what y is. ·Bandδimpliesβ，regardless of whatδis. So to be sure that a new precondition is weaker than or equal to an original o,it suffices to accept it only if it is of the form a or y;and to be sure that a new postcondition is stronger than or equal to an original B,it suffices to accept it only if it is of the form B and 8.Hence the language rule implementing the original methodological rule: Assertion Redeclaration rule (2) In the redeclared version of a routine,it is not permitted to use a require or ensure clause.Instead you may: Use a clause introduced by require else,to be or-ed with the original precondition. Use a clause introduced by ensure then,to be and-ed with the original postcondition. In the absence of such a clause,the original assertion is retained. Note that the operators used for or-ing and for and-ing are the non-strict boolean See“Non-strict operators or else and and then rather than plain or and and,although in most cases the boolean operators". difference is irrelevant. page 454 Sometimes the resulting assertions will be more complicated than strictly necessary. For example in our matrix routine,where the original read
578 INHERITANCE TECHNIQUES §16.1 It would clearly be a mistake, in class STACK, to include Result = False as a postcondition for full or (equivalently but following the recommended style) an invariant clause not full. This would be a case of overspecification as mentioned earlier, hampering the descendants’ freedom to adapt the feature. The language rule The Assertion Redeclaration rule as given so far is a conceptual guideline. How do we transform it into a safe, checkable language rule? We should in principle rely on a logical analysis of the old and new assertions, to verify that the old precondition logically implies the new one, and that the new postcondition implies the old one. Unfortunately, such a goal would require a sophisticated theorem prover which, if at all feasible, is still far too difficult (in spite of decades of research in artificial intelligence) to be integrated routinely among the checks performed by a compiler. Fortunately a low-tech solution is available. We can enforce the rule through a simple language convention, based on the observation that for any assertions α and β: • α implies α or γ, regardless of what γ is. • β and δ implies β, regardless of what δ is. So to be sure that a new precondition is weaker than or equal to an original α, it suffices to accept it only if it is of the form α or γ; and to be sure that a new postcondition is stronger than or equal to an original β, it suffices to accept it only if it is of the form β and δ. Hence the language rule implementing the original methodological rule: Note that the operators used for or-ing and for and-ing are the non-strict boolean operators or else and and then rather than plain or and and, although in most cases the difference is irrelevant. Sometimes the resulting assertions will be more complicated than strictly necessary. For example in our matrix routine, where the original read Assertion Redeclaration rule (2) In the redeclared version of a routine, it is not permitted to use a require or ensure clause. Instead you may: • Use a clause introduced by require else, to be or-ed with the original precondition. • Use a clause introduced by ensure then, to be and-ed with the original postcondition. In the absence of such a clause, the original assertion is retained. See “Non-strict boolean operators”, page 454