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 <is defined.In a language that enhances security through static typing,we want to enforce this requirement at compile time,not wait until run time.We need a way to specify that type G must be equipped with the right operation In Ada this will be written by treating the operator<=as a generic parameter of its own.Syntactically it is a function;as a syntactic facility,it is possible to invoke such a function using the usual infix form if it is declared with a name in double quotes,here "<="Again the following declaration becomes legal Ada if the interface and implementation are taken apart. generic type G is private; with function "<="(a,b:G)return BOOLEAN is <> function 0(x,y:G)return G is begin ifx <=y then return x;else return y end if; end minimum; The keyword with introduces generic parameters representing routines,such as"<=" You may perform a generic derivation minimum for any type,say Tl,such that there exists a function,say TI le,of signature function (a,b:T1)return BOOLEAN: function TI minimum is new minimum(TI,TI le). If function T/le is in fact called "<="more precisely if its name and type signature match those of the corresponding formal routine,then you do not need to include it in the list of actual parameters to the generic derivation.So because type /NTEGER has a predefined"<="function with the right signature,you can simply declare function int minimum is new minimum(INTEGER) This use of default routines with matching names and types is made possible by the clause is <in the declaration of the formal routine,here "<="Operator overloading,as permitted (and in fact encouraged)by Ada,plays an essential role:many different types will have a "<="function. This discussion of constrained genericity for routines readily transposes to packages. Assume you need a generic package for handling matrices of objects of any type G,with matrix sum and product as basic operations.Such a definition only makes sense if type G has a sum and a product of its own,and each of these operations has a zero element;these features of G will be needed in the implementation of matrix sum and product.The public part of the package may be written as follows: generic type G is private; zero:G: uniry:G. with function"+"(a,b:G)return G is <> 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 <= is defined. In a language that enhances security through static typing, we want to enforce this requirement at compile time, not wait until run time. We need a way to specify that type G must be equipped with the right operation. In Ada this will be written by treating the operator <= as a generic parameter of its own. Syntactically it is a function; as a syntactic facility, it is possible to invoke such a function using the usual infix form if it is declared with a name in double quotes, here "<=". Again the following declaration becomes legal Ada if the interface and implementation are taken apart. generic type G is private; with function "<=" (a, b: G) return BOOLEAN is <>; function 0(x, y: G) return G is begin if x <= y then return x; else return y end if; end minimum; The keyword with introduces generic parameters representing routines, such as "<=". You may perform a generic derivation minimum for any type, say T1, such that there exists a function, say T1_le, of signature function (a, b: T1) return BOOLEAN: function T1_minimum is new minimum (T1, T1_le); If function T1_le is in fact called "<=", more precisely if its name and type signature match those of the corresponding formal routine, then you do not need to include it in the list of actual parameters to the generic derivation. So because type INTEGER has a predefined "<=" function with the right signature, you can simply declare function int_minimum is new minimum (INTEGER); This use of default routines with matching names and types is made possible by the clause is <> in the declaration of the formal routine, here "<=". Operator overloading, as permitted (and in fact encouraged) by Ada, plays an essential role: many different types will have a "<=" function. This discussion of constrained genericity for routines readily transposes to packages. Assume you need a generic package for handling matrices of objects of any type G, with matrix sum and product as basic operations. Such a definition only makes sense if type G has a sum and a product of its own, and each of these operations has a zero element; these features of G will be needed in the implementation of matrix sum and product. The public part of the package may be written as follows: 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 <>;