Genericity versus inheritance The material that follows,and its appearance in an appendix,deserve some background explanation.Part of the original impetus for the work that eventually led to this book was a study that I performed in 1984;in preparation for a graduate course that I was to teach on"advanced concepts in programming languages",I compared the"horizontal"module extension mechanism of genericity,illustrated by Ada,Z,LPG and other generic languages,with the"vertical"mechanism of inheritance introduced by Simula:how these techniques differ,to what extent they compete,and to what extent they complement each other.This led to an article on"Genericity versus Inheritance"[M 1986],presented at the first OOPSLA conference,and to a chapter in the first edition of the present book. When preparing this new edition I felt that both genericity and inheritance were now understood well enough,and their treatment detailed enough in the rest of the book,to make the chapter appear too specialized:useful mostly to readers interested in issues of language design or O-O theory.So I removed it.But then I found out that a regular flow of articles in the software press still showed must puzzlement over the issue,especially in the context of C++for which many people seem to be searching for general guidelines on when to use "templates"and when to use inheritance.This means the discussion still has its place in a general presentation of object technology,although it is perhaps best severed from the main part of the text.Hence this appendix. The topics reviewed are,in order:genericity;inheritance;how to emulate each of these mechanisms through the other;and,as a conclusion,how best to reconcile them. If you have read carefully the remainder of this book,you will find the beginning of this discussion familiar since we must restart with the basics to get a full picture of each mechanism,of its contribution,and of its limitations.As we probe deeper and deeper, perhaps stepping briefly into a few dead ends along the way,the ideal combination of genericity and inheritance will progressively unfold before our eyes,imposing itself in the end as almost inevitable and letting us understand,in full detail,the fascinating relationship between the two principal methods for making software modules open to variation and adaptation
B Genericity versus inheritance The material that follows, and its appearance in an appendix, deserve some background explanation. Part of the original impetus for the work that eventually led to this book was a study that I performed in 1984; in preparation for a graduate course that I was to teach on “advanced concepts in programming languages”, I compared the “horizontal” module extension mechanism of genericity, illustrated by Ada, Z, LPG and other generic languages, with the “vertical” mechanism of inheritance introduced by Simula: how these techniques differ, to what extent they compete, and to what extent they complement each other. This led to an article on “Genericity versus Inheritance” [M 1986], presented at the first OOPSLA conference, and to a chapter in the first edition of the present book. When preparing this new edition I felt that both genericity and inheritance were now understood well enough, and their treatment detailed enough in the rest of the book, to make the chapter appear too specialized: useful mostly to readers interested in issues of language design or O-O theory. So I removed it. But then I found out that a regular flow of articles in the software press still showed must puzzlement over the issue, especially in the context of C++ for which many people seem to be searching for general guidelines on when to use “templates” and when to use inheritance. This means the discussion still has its place in a general presentation of object technology, although it is perhaps best severed from the main part of the text. Hence this appendix. The topics reviewed are, in order: genericity; inheritance; how to emulate each of these mechanisms through the other; and, as a conclusion, how best to reconcile them. If you have read carefully the remainder of this book, you will find the beginning of this discussion familiar since we must restart with the basics to get a full picture of each mechanism, of its contribution, and of its limitations. As we probe deeper and deeper, perhaps stepping briefly into a few dead ends along the way, the ideal combination of genericity and inheritance will progressively unfold before our eyes, imposing itself in the end as almost inevitable and letting us understand, in full detail, the fascinating relationship between the two principal methods for making software modules open to variation and adaptation
1168 GENERICITY VERSUS INHERITANCE $B.I B.1 GENERICITY We begin our review by appraising the merits of genericity as it exists in a number of languages,object-oriented or not.Let us rely for convenience on the notations- semicolons and all-of the best known non-O-O generic language,Ada(meaning by default,as elsewhere in this book,Ada 83).So for the rest of this section we forget about O-O languages and techniques. Only the most important form of Ada genericity will be considered:type parameterization,that is to say the ability to parameterize a software element(in Ada,a package or routine)by one or more types.Generic parameters have other,less momentous uses in Ada,such as parameterized dimensions for arrays.We may distinguish between unconstrained genericity,imposing no specific requirement on generic parameters,and constrained genericity,whereby a certain structure is required. Unconstrained genericity Unconstrained genericity removes some of the rigidity of static typing.A trivial example is a routine (in a language with Ada-like syntax but without explicit type declarations)to swap the values of two variables: procedure swap (x,y)is This extract and the local next few are in Ada or Ada-like syntax. begin t:=x;x:=yy:=t end swap; This form does not specify the types of the elements to be swapped and of the local variable 1.This is too much freedom,since a call swap (a,b),where a is an integer and b a character string,will not be prohibited even though it is probably an error. To address this issue,statically typed languages such as Pascal and Ada require developers to declare explicitly the types of all variables and formal arguments,and enforce a statically checkable type compatibility constraint between actual and formal arguments in calls and between source and target in assignments.The procedure to exchange the values of two variables of type G becomes: procedure G_swap (x,y:in out G)is t:G; begin t:=x;x:=yy:=t; end swap, Demanding that G be specified as a single type averts type incompatibility errors,but in the constant haggling between safety and flexibility we have now erred too far away from flexibility:to correct the lack of safety of the first solution,we have made the solution inflexible.We will need a new procedure for every type of elements to be exchanged,for example INTEGER swap,STRING swap and so on.Such multiple declarations lengthen and obscure programs.The example chosen is particularly bad since all the declarations will be identical except for the two occurrences of G
1168 GENERICITY VERSUS INHERITANCE §B.1 B.1 GENERICITY We begin our review by appraising the merits of genericity as it exists in a number of languages, object-oriented or not. Let us rely for convenience on the notations — semicolons and all — of the best known non-O-O generic language, Ada (meaning by default, as elsewhere in this book, Ada 83). So for the rest of this section we forget about O-O languages and techniques. Only the most important form of Ada genericity will be considered: type parameterization, that is to say the ability to parameterize a software element (in Ada, a package or routine) by one or more types. Generic parameters have other, less momentous uses in Ada, such as parameterized dimensions for arrays. We may distinguish between unconstrained genericity, imposing no specific requirement on generic parameters, and constrained genericity, whereby a certain structure is required. Unconstrained genericity Unconstrained genericity removes some of the rigidity of static typing. A trivial example is a routine (in a language with Ada-like syntax but without explicit type declarations) to swap the values of two variables: procedure swap (x, y) is local t; begin t := x; x := y; y := t; end swap; This form does not specify the types of the elements to be swapped and of the local variable t. This is too much freedom, since a call swap (a, b), where a is an integer and b a character string, will not be prohibited even though it is probably an error. To address this issue, statically typed languages such as Pascal and Ada require developers to declare explicitly the types of all variables and formal arguments, and enforce a statically checkable type compatibility constraint between actual and formal arguments in calls and between source and target in assignments.The procedure to exchange the values of two variables of type G becomes: procedure G_swap (x, y: in out G) is t: G; begin t := x; x := y; y := t; end swap; Demanding that G be specified as a single type averts type incompatibility errors, but in the constant haggling between safety and flexibility we have now erred too far away from flexibility: to correct the lack of safety of the first solution, we have made the solution inflexible. We will need a new procedure for every type of elements to be exchanged, for example INTEGER_swap, STRING_swap and so on. Such multiple declarations lengthen and obscure programs. The example chosen is particularly bad since all the declarations will be identical except for the two occurrences of G. This extract and the next few are in Ada or Ada-like syntax
$B.1 GENERICITY 1169 Static typing may be considered too restrictive here:the only real requirement is that the two actual arguments passed to any call of swap should be of the same type,and that their type should also be applied to the declaration of the local variable t.It does not matter what this type actually is as long as it satisfies these properties. In addition the arguments must be passed in in out mode,so that the procedure can change their values.This is permitted in Ada. Genericity provides a tradeoff between too much freedom,as with untyped languages,and too much restraint,as with Pascal.In a generic language you may declare G as a generic parameter of swap or an enclosing unit.Ada indeed offers generic routines, along with the generic packages described in chapter 33.In quasi-Ada you can write: generic type G is private, procedure swap (x,y:in out G)is :G, begin t:=x.x:=yy:=t; end swap; The only difference with real Ada is that you would have to separate interface from implementation,as explained in the chapter on Ada.Since information hiding is irrelevant for the discussion in this chapter,interfaces and implementations will be merged for ease of presentation. The generic...clause introduces type parameters.By specifying G as "private",the writer of this procedure allows himself to apply to entities oftype G(x,y and 1)operations available on all types,such as assignment or comparison,and these only. The above declaration does not quite introduce a routine but rather a routine pattern; to get a directly usable routine you will provide actual type parameters,as in procedure int swap is new swap (INTEGER). procedure str_swap is new swap (STRING); etc.Now assuming that i and j are variables of type INTEGER,s and t of type STRING, then of the following calls int swap (i,j),str swap (s,t);int swap (i,s),str swap (s,j),str swap (i,j), all but the first two are invalid,and will be rejected by the compiler. More interesting than parameterized routines are parameterized packages.As a minor variation of our usual stack example,consider a queue package,where the operations on a queue (first-in,first out)are:add an element;remove the oldest element added and not yet removed;get its value;test for empty queue.The interface is:
§B.1 GENERICITY 1169 Static typing may be considered too restrictive here: the only real requirement is that the two actual arguments passed to any call of swap should be of the same type, and that their type should also be applied to the declaration of the local variable t. It does not matter what this type actually is as long as it satisfies these properties. In addition the arguments must be passed in in out mode, so that the procedure can change their values. This is permitted in Ada. Genericity provides a tradeoff between too much freedom, as with untyped languages, and too much restraint, as with Pascal. In a generic language you may declare G as a generic parameter of swap or an enclosing unit. Ada indeed offers generic routines, along with the generic packages described in chapter 33. In quasi-Ada you can write: generic type G is private; procedure swap (x, y: in out G) is t: G; begin t := x; x := y; y := t; end swap; The only difference with real Ada is that you would have to separate interface from implementation, as explained in the chapter on Ada. Since information hiding is irrelevant for the discussion in this chapter, interfaces and implementations will be merged for ease of presentation. The generic… clause introduces type parameters. By specifying G as “private”, the writer of this procedure allows himself to apply to entities of type G (x, y and t) operations available on all types, such as assignment or comparison, and these only. The above declaration does not quite introduce a routine but rather a routine pattern; to get a directly usable routine you will provide actual type parameters, as in procedure int_swap is new swap (INTEGER); procedure str_swap is new swap (STRING); etc. Now assuming that i and j are variables of type INTEGER, s and t of type STRING, then of the following calls int_swap (i, j); str_swap (s, t); int_swap (i, s); str_swap (s, j); str_swap (i, j); all but the first two are invalid, and will be rejected by the compiler. More interesting than parameterized routines are parameterized packages. As a minor variation of our usual stack example, consider a queue package, where the operations on a queue (first-in, first out) are: add an element; remove the oldest element added and not yet removed; get its value; test for empty queue. The interface is:
1170 GENERICITY VERSUS INHERITANCE SB.I generic type G is private; package OUEUES is type QUEUE(capacity:POSITIVE)is private; function empty (s:in OUEUE)return BOOLEAN: procedure add (t:in G;s:in out OUEUE): procedure remove (s:in out OUEUE) function oldest (s:in QUEUE)return G; private type OUEUE (capacity:POSITIVE)is --The package uses an array representation for queues record implementation:array (0..capacity)of G; count:NATURAL; end record; end OUEUES: Again this does not define a package but a package pattern;to get a directly usable package you will use generic derivation,as in package INT_QUEUES is new QUEUES (INTEGER); package STR_QUEUES is new QUEUES(STRING). Note again the tradeoff that generic declarations achieve between typed and untyped approaches.OUEUES is a pattern for modules implementing queues of elements of all possible types G,while retaining the possibility to enforce type checks for a specific G,so as to rule out such unholy combinations as the insertion of an integer into a queue of strings. The form of genericity illustrated by both of the examples seen so far,swapping and queues,may be called unconstrained since there is no specific requirement on the types that may be used as actual generic parameters:you may swap the values of variables of any type and create queues of values of any type,as long as all the values in a given queue are of the same type. Other generic definitions,however,only make sense ifthe actual generic parameters satisfy some conditions.This form may be called constrained genericity. Constrained genericity As in the unconstrained case,the examples of constrained genericity will include both a routine and a package. Assume first you need a generic function to compute the minimum of two values. You can try the pattern of swap: generic From here on most routine declarations type G is private; omit the in mode function minimum (x,y:G)return G is begin specification for ifx <=y then return x;else return y;end if; arguments,ph加chis end21171u71, optional
1170 GENERICITY VERSUS INHERITANCE §B.1 generic type G is private; package QUEUES is type QUEUE (capacity: POSITIVE) is private; function empty (s: in QUEUE) return BOOLEAN; procedure add (t: in G; s: in out QUEUE); procedure remove (s: in out QUEUE); function oldest (s: in QUEUE) return G; private type QUEUE (capacity: POSITIVE) is -- The package uses an array representation for queues record implementation: array (0 .. capacity) of G; count: NATURAL; end record; end QUEUES; Again this does not define a package but a package pattern; to get a directly usable package you will use generic derivation, as in package INT_QUEUES is new QUEUES (INTEGER); package STR_QUEUES is new QUEUES (STRING); Note again the tradeoff that generic declarations achieve between typed and untyped approaches. QUEUES is a pattern for modules implementing queues of elements of all possible types G, while retaining the possibility to enforce type checks for a specific G, so as to rule out such unholy combinations as the insertion of an integer into a queue of strings. The form of genericity illustrated by both of the examples seen so far, swapping and queues, may be called unconstrained since there is no specific requirement on the types that may be used as actual generic parameters: you may swap the values of variables of any type and create queues of values of any type, as long as all the values in a given queue are of the same type. Other generic definitions, however, only make sense if the actual generic parameters satisfy some conditions. This form may be called constrained genericity. Constrained genericity As in the unconstrained case, the examples of constrained genericity will include both a routine and a package. Assume first you need a generic function to compute the minimum of two values. You can try the pattern of swap: generic type G is private; function minimum (x, y: G) return G is begin if x <= y then return x; else return y; end if; end minimum; From here on most routine declarations omit the in mode specification for arguments, which is optional
$B.1 GENERICITY 1171 Such a function declaration,however,does not always make sense;only for types G on which a comparison operator function 0(x,y:G)return G is begin ifx with function "*"(a.b:G)return G is <>
§B.1 GENERICITY 1171 Such a function declaration, however, does not always make sense; only for types G on which a comparison operator ; function 0(x, y: G) return G is begin if x in the declaration of the formal routine, here "; with function "✳" (a, b: G) return G is <>;
1172 GENERICITY VERSUS INHERITANCE SB.I package MATRICES is type MATRIX (lines,columns:POSITIVE)is private; function "+(ml,m2:MATRIX)return MATRIX: function "*(ml,m2:MATRIX)return MATRIX: private type MATRIX (lines,columns:POSITIVE)is array (I..lines,1..columns)of G; end MATRICES; Typical generic derivations are: package INTEGER MATRICES is new MATRICES(INTEGER,0,1); package BOOLEAN MATRICES is new MATR/CES (BOOLEAN,false,true,"or","and"); Again,you may omit actual parameters corresponding to formal generic routines (here "+"and"")for type INTEGER,which has matching operations;but you will need them for BOOLEAN.(It is convenient to declare such parameters last in the formal list; otherwise key word notation is required in derivations that omit the corresponding actuals. It is interesting here to take a look at the body (implementation)of such a package: package body MATR/CES is ..Other declarations .. function ""(ml,m2:G)is result:MATRIX (ml'lines,m2'columns); begin if ml'columns /m2'lines then raise incompatible sizes, end if; for i in ml'RANGE(1)loop for j in m2'RANGE(2)loop result (i,j):=zero; for k in mI'RANGE(2)loop result(i,j)=result(i,)+ml(i,k)米m2(k,) end loop; end loop; end loop; return result end"米": end MATRICES. This extract relies on some specific features of Ada: For a parameterized type such as MATRIX (lines,columns:POSITIVE),a variable declaration must provide actual parameters,e.g.mm:MATRIX(100.75);you may then retrieve their values using apostrophe notation,as in mim'lines which in this case has value 100
1172 GENERICITY VERSUS INHERITANCE §B.1 package MATRICES is type MATRIX (lines, columns: POSITIVE) is private; function "+" (m1, m2: MATRIX) return MATRIX; function "✳" (m1, m2: MATRIX) return MATRIX; private type MATRIX (lines, columns: POSITIVE) is array (1 .. lines, 1 .. columns) of G; end MATRICES; Typical generic derivations are: package INTEGER_MATRICES is new MATRICES (INTEGER, 0, 1); package BOOLEAN_MATRICES is new MATRICES (BOOLEAN, false, true, "or", "and"); Again, you may omit actual parameters corresponding to formal generic routines (here "+" and "✳") for type INTEGER, which has matching operations; but you will need them for BOOLEAN. (It is convenient to declare such parameters last in the formal list; otherwise keyword notation is required in derivations that omit the corresponding actuals.) It is interesting here to take a look at the body (implementation) of such a package: package body MATRICES is … Other declarations … function "✳" (m1, m2: G) is result: MATRIX (m1'lines, m2'columns); begin if m1' columns /= m2'lines then raise incompatible_sizes; end if; for i in m1'RANGE(1) loop for j in m2'RANGE(2) loop result (i, j) := zero; for k in m1'RANGE(2) loop result (i, j) := result (i, j) + m1 (i, k) ✳ m2 (k, j) end loop; end loop; end loop; return result end "✳"; end MATRICES; This extract relies on some specific features of Ada: • For a parameterized type such as MATRIX (lines, columns: POSITIVE), a variable declaration must provide actual parameters, e.g. mm: MATRIX (100, 75); you may then retrieve their values using apostrophe notation, as in mm'lines which in this case has value 100
$B.2 INHERITANCE 1173 If a is an array,a'RANGE(i)denotes the range of values in its i-th dimension;for example mI'RANGE(1)above is the same as 1..ml'lines. If requested to multiply two dimension-wise incompatible matrices,the extract raises an exception,corresponding to the violation of an implicit precondition. The minimum and matrix examples are representative of Ada techniques for constrained genericity.They also show a serious limitation of these techniques:only syntactic constraints can be expressed.All that a programmer may require is the presence of certain routines("<=","+",""in the examples)with given types;but the declarations are meaningless unless the routines also satisfy some semantic constraints.Function minimn only makes sense if"<="is a total order relation on G;and to produce a generic derivation of MATR/CES for a type G,you should make sure that operations"+"and""have not just the right signature,GxG-G,but also the appropriate properties:associativity, distributivity,zero a zero element for "+and unity for "etc.We may use the mathematical term ring for a structure equipped with operations enjoying these properties. B.2 INHERITANCE So much for pure genericity.The other term ofthe comparison is inheritance.To contrast it with genericity,consider the example of a general-purpose module library for files.First here is the outline of an implementation of"special files"in the Unix sense,that is to say, files associated with devices: This extract and the class DEVICE feature next few are in the 0-0 notation of the open (file descriptor:INTEGER)is do...end rest of this book. close is do ..end opened:BOOLEAN end--class DEVICE An example use of this class is: dl:DEVICE;fl:INTEGER;... !dl.make;dl.open (f1). if dl.opened then... Consider next the notion of a tape device.For the purposes of this discussion,a tape unit has all the properties of devices,as represented by the three features of class DEVICE, plus the ability to rewind its tape.Rather than building a class from scratch,we may use inheritance to declare class TAPE as an extension-cum-modification of DEV/CE.The new class extends DEVICE by adding a new procedure rewind,describing a mechanism applicable to tapes but not necessarily to other devices;and it modifies some of DEVICE's properties by providing a new version of open,describing the specifics of opening a device that happens to be a tape drive. Objects of type TAPE automatically possess all the features of DEVICE objects,plus their own (here rewind).Class DEVICE could have more heirs,for example D/SK with its own specific features such as direct access read
§B.2 INHERITANCE 1173 • If a is an array, a' RANGE(i) denotes the range of values in its i-th dimension; for example m1'RANGE(1) above is the same as 1 .. m1'lines. • If requested to multiply two dimension-wise incompatible matrices, the extract raises an exception, corresponding to the violation of an implicit precondition. The minimum and matrix examples are representative of Ada techniques for constrained genericity. They also show a serious limitation of these techniques: only syntactic constraints can be expressed. All that a programmer may require is the presence of certain routines ("<=", "+", "✳" in the examples) with given types; but the declarations are meaningless unless the routines also satisfy some semantic constraints. Function minimum only makes sense if "<=" is a total order relation on G; and to produce a generic derivation of MATRICES for a type G, you should make sure that operations "+" and "✳" have not just the right signature, G × G → G, but also the appropriate properties: associativity, distributivity, zero a zero element for "+" and unity for "✳" etc. We may use the mathematical term ring for a structure equipped with operations enjoying these properties. B.2 INHERITANCE So much for pure genericity. The other term of the comparison is inheritance. To contrast it with genericity, consider the example of a general-purpose module library for files. First here is the outline of an implementation of “special files” in the Unix sense, that is to say, files associated with devices: class DEVICE feature open (file_descriptor: INTEGER) is do … end close is do … end opened: BOOLEAN end -- class DEVICE An example use of this class is: d1: DEVICE; f1: INTEGER; … !! d1 ● make; d1 ● open (f1); if d1 ● opened then … Consider next the notion of a tape device. For the purposes of this discussion, a tape unit has all the properties of devices, as represented by the three features of class DEVICE, plus the ability to rewind its tape. Rather than building a class from scratch, we may use inheritance to declare class TAPE as an extension-cum-modification of DEVICE. The new class extends DEVICE by adding a new procedure rewind, describing a mechanism applicable to tapes but not necessarily to other devices; and it modifies some of DEVICE’s properties by providing a new version of open, describing the specifics of opening a device that happens to be a tape drive. Objects of type TAPE automatically possess all the features of DEVICE objects, plus their own (here rewind). Class DEVICE could have more heirs, for example DISK with its own specific features such as direct access read. This extract and the next few are in the O-O notation of the rest of this book
1174 GENERICITY VERSUS INHERITANCE $B.2 Objects of type TAPE will possess all the features of type DEVICE,possibly adapted (in the case of open),and complemented by the new feature rewind. With inheritance comes polymorphism,permitting assignments of the formx=y,This is approximate but only if the type ofx is an ancestor of the type ofy.The next associated property is terminology:“isan dynamic binding:if x is a device,the call x.open (f7)will be executed differently ancestor of"stands for“conforms to” depending on the assignments performed onx before the call:afterx=y,wherey is a tape, Precise rules appear the call will execute the tape version. in earlier chapters. We have seen the remarkable benefits of these inheritance techniques for reusability and extendibility.A key aspect was the Open-Closed principle:a software element such as DEIICE is both usable as it stands (it may be compiled as part of an executable system) and still amenable to extensions (if used as an ancestor of new classes). Next come deferred features and classes.Here we note that Unix devices are a special kind of file;so you may make DEVICE an heir to class FILE,whose other heirs might include TEXT FILE (itself with heirs NORMAL and DIRECTORY)and BINARY FILE. The figure shows the inheritance graph,a tree in this case. open A simple FILE close inheritance hierarchy,with deferred and effective classes DEVICE TEXT FILE BINARY FILE Inherits from DEVICE BINARY FILE *Deferred Although it is possible to open or close any file,how these operations are performed depends on whether the file is a device,a directory etc.So FILE is a deferred class with deferred routines open or close,making descendants responsible for implementing them: deferred class FILE feature open (file_descriptor:INTEGER)is deferred end close is deferred end. end--class FILE Effective descendants of F/LE will provide effective implementations of open and close
1174 GENERICITY VERSUS INHERITANCE §B.2 Objects of type TAPE will possess all the features of type DEVICE, possibly adapted (in the case of open), and complemented by the new feature rewind. With inheritance comes polymorphism, permitting assignments of the form x := y, but only if the type of x is an ancestor of the type of y. The next associated property is dynamic binding: if x is a device, the call x ● open (f1) will be executed differently depending on the assignments performed on x before the call: after x := y, where y is a tape, the call will execute the tape version. We have seen the remarkable benefits of these inheritance techniques for reusability and extendibility. A key aspect was the Open-Closed principle: a software element such as DEVICE is both usable as it stands (it may be compiled as part of an executable system) and still amenable to extensions (if used as an ancestor of new classes). Next come deferred features and classes. Here we note that Unix devices are a special kind of file; so you may make DEVICE an heir to class FILE, whose other heirs might include TEXT_FILE (itself with heirs NORMAL and DIRECTORY) and BINARY_FILE. The figure shows the inheritance graph, a tree in this case. Although it is possible to open or close any file, how these operations are performed depends on whether the file is a device, a directory etc. So FILE is a deferred class with deferred routines open or close, making descendants responsible for implementing them: deferred class FILE feature open (file_descriptor: INTEGER) is deferred end close is deferred end; end -- class FILE Effective descendants of FILE will provide effective implementations of open and close. This is approximate terminology; “is an ancestor of ” stands for “conforms to”. Precise rules appear in earlier chapters. A simple inheritance hierarchy, with deferred and effective classes ∗ FILE DEVICE Inherits from TEXT_FILE BINARY_ FILE ∗ Deferred DEVICE BINARY_ FILE open* close*
SB.3 EMULATING INHERITANCE WITH GENERICITY 1175 B.3 EMULATING INHERITANCE WITH GENERICITY To compare genericity with inheritance,we will study how,if in any way,the effect of each feature may be emulated in a language offering the other. First consider a language such as Ada(again meaning Ada 83),offering genericity but not inheritance.Can it be made to achieve the effects of inheritance? The easy part is name overloading.Ada,as we know,allows reusing the same routine name as many times as needed for operands of different types;so you can define types such as TAPE,DISK and others,each with its own version of the routines: This extract and the procedure open (p:in out TAPE;descriptor:in INTEGER); next few are in Ada procedure close (p:in out D/SK); syntax. No ambiguity will arise if the routines are distinguished by the type of at least one operand.But this solution does not provide polymorphism and dynamic binding,whereby d.close,for example,would have a different effect after assignments d:=di and d:=ta, where di is a DISK and ta a TAPE. To obtain the same effect,you have to use records with variant fields:define type DEVICE(unit:DEVICE TYPE)is record ..Fields common to all device types... case unit is when tape =>..fields for tape devices ... when disk =>..fields for disk devices.... ..Other cases...; end case end record where DEVICE TYPE is an enumerated type with elements tape,disk etc.Then there would be a single version of each the procedures on devices (open,close etc.),each containing a case discrimination of the form case d'uit is when tape =>..action for tape devices...; when disk=>...action for disk devices...; ..other cases.... end case See"Single Choice” This uses explicit discrimination in each case,and closes off the list of choices, page 61. forcing every routine to know of all the possible variants;addition of new cases will cause changes to all such routines.The Single Choice principle expressly warned against such software architectures. So the answer to the question of this section is essentially no: Emulating inheritance It appears impossible to emulate inheritance through genericity
§B.3 EMULATING INHERITANCE WITH GENERICITY 1175 B.3 EMULATING INHERITANCE WITH GENERICITY To compare genericity with inheritance, we will study how, if in any way, the effect of each feature may be emulated in a language offering the other. First consider a language such as Ada (again meaning Ada 83), offering genericity but not inheritance. Can it be made to achieve the effects of inheritance? The easy part is name overloading. Ada, as we know, allows reusing the same routine name as many times as needed for operands of different types; so you can define types such as TAPE, DISK and others, each with its own version of the routines: procedure open (p: in out TAPE; descriptor: in INTEGER); procedure close (p: in out DISK); No ambiguity will arise if the routines are distinguished by the type of at least one operand. But this solution does not provide polymorphism and dynamic binding, whereby d ● close, for example, would have a different effect after assignments d := di and d := ta, where di is a DISK and ta a TAPE. To obtain the same effect, you have to use records with variant fields: define type DEVICE (unit: DEVICE_TYPE) is record … Fields common to all device types … case unit is when tape => … fields for tape devices …; when disk => … fields for disk devices …; … Other cases …; end case end record where DEVICE_TYPE is an enumerated type with elements tape, disk etc. Then there would be a single version of each the procedures on devices (open, close etc.), each containing a case discrimination of the form case d'unit is when tape => … action for tape devices …; when disk => … action for disk devices …; … other cases …; end case This uses explicit discrimination in each case, and closes off the list of choices, forcing every routine to know of all the possible variants; addition of new cases will cause changes to all such routines. The Single Choice principle expressly warned against such software architectures. So the answer to the question of this section is essentially no: Emulating inheritance It appears impossible to emulate inheritance through genericity. This extract and the next few are in Ada syntax. See “Single Choice”, page 61
1176 GENERICITY VERSUS INHERITANCE SB.4 B.4 EMULATING GENERICITY WITH INHERITANCE Let us see if we will have more luck with the reverse problem:can we achieve the effect of Ada-style genericity in an object-oriented language with inheritance? The O-O notation introduced in earlier chapters does provide a generic parameter mechanism.But since we are comparing pure genericity versus pure inheritance,the rule of the game for some time,frustrating as it may be,is to pretend we have all but forgotten about that genericity mechanism.As a result the solutions presented in this section will be substantially more complex than those obtainable with the full notation,described in the rest of this book and in later sections.As you read this section,remember that the software extracts are not final forms,but for purposes of discussion only. Surprisingly perhaps,the simulation turns out to be easier,or at least less artificial, for the more sophisticated form of genericity:constrained.So we begin with this case. Emulating constrained genericity:overview The idea is to associate a class with a constrained formal generic type parameter.This is a natural thing to do since a constrained generic type may be viewed,together with its constraining operations,as an abstract data type.Consider for example the Ada generic clauses in our two constrained examples,minimum and matrices: generic This extract is in Ada type G is private, syntax. with function" with function ""(a,b:G)return G is <> We may view these clauses as the definitions of two abstract data types, COMPARABLE and RING ELEMENT;the first is characterized by a comparison operation"<=",and the second by features zero,unity,"+"and "*" In an object-oriented language,such types may be directly represented as classes. We cannot define these classes entirely,for there is no universal implementation of"<=", "+"etc.;rather,they are to be used as ancestors of other classes,corresponding to actual generic parameters.Deferred classes provide exactly what we need: deferred class COMPARABLE feature This extract and all infix "<="(other:COMPARABLE):BOOLEAN is deferred end remaining ones are in the 0-0 notation end -class COMPARABLE of this book
1176 GENERICITY VERSUS INHERITANCE §B.4 B.4 EMULATING GENERICITY WITH INHERITANCE Let us see if we will have more luck with the reverse problem: can we achieve the effect of Ada-style genericity in an object-oriented language with inheritance? The O-O notation introduced in earlier chapters does provide a generic parameter mechanism. But since we are comparing pure genericity versus pure inheritance, the rule of the game for some time, frustrating as it may be, is to pretend we have all but forgotten about that genericity mechanism. As a result the solutions presented in this section will be substantially more complex than those obtainable with the full notation, described in the rest of this book and in later sections. As you read this section, remember that the software extracts are not final forms, but for purposes of discussion only. Surprisingly perhaps, the simulation turns out to be easier, or at least less artificial, for the more sophisticated form of genericity: constrained. So we begin with this case. Emulating constrained genericity: overview The idea is to associate a class with a constrained formal generic type parameter. This is a natural thing to do since a constrained generic type may be viewed, together with its constraining operations, as an abstract data type. Consider for example the Ada generic clauses in our two constrained examples, minimum and matrices: generic type G is private; with function " generic type G is private; zero: G; unity: G; with function "+" (a, b: G) return G is <>; with function "✳" (a, b: G) return G is ; We may view these clauses as the definitions of two abstract data types, COMPARABLE and RING_ELEMENT; the first is characterized by a comparison operation "<=", and the second by features zero, unity, "+" and "✳". In an object-oriented language, such types may be directly represented as classes. We cannot define these classes entirely, for there is no universal implementation of "<=", "+" etc.; rather, they are to be used as ancestors of other classes, corresponding to actual generic parameters. Deferred classes provide exactly what we need: deferred class COMPARABLE feature infix “<=” (other: COMPARABLE): BOOLEAN is deferred end end -- class COMPARABLE This extract is in Ada syntax. This extract and all remaining ones are in the O-O notation of this book