322 GENERICITY $10.3 Using a generic class A client may use a generic class to declare entities of its own,such as an entity representing a stack.In such a case,the declaration must provide types,called actual generic parameters-as many as the class has formal generic parameters,here just one: sp:STACK [POINT] Providing an actual generic parameter to a generic class so as to produce a type,as here,is called a generic derivation,and the resulting type,such as STACK [POINT],is said to be generically derived. A generic derivation both produces and requires a type: The result of the derivation,STACK [POINT]in this example,is a type To produce this result,you need an existing type to serve as actual generic parameter, PO/NT in the example. The actual generic parameter is an arbitrary type.Nothing prevents us,in particular, from choosing a type that is itself generically derived;assuming another generic class LIST [G],we can define a stack of lists of points: slp:STACK [LIST [POINT]] or even,using STACK [POINT]itself as the actual generic parameter,a stack of stacks of points: ssp:STACK [STACK [POINT]] There is no limit-other than suggested by the usual guideline that software texts should remain simple-to the depth of such nesting. Terminology To discuss genericity,we need to be precise about the terms that we use: To produce a type such as STACK [POINT]by providing a type,here POINT,as actual generic parameter for a generic class,here STACK,is to perform a generic derivation.You may encounter the term"generic instantiation"for that process,but it is confusing because "instantiation"normally denotes a run-time event,the production of an object-an instance-from its mold (a class).Generic derivation is a static mechanism,affecting the text of the software,not its execution.So it is better to use completely different terms. This book uses the term "parameter"exclusively to denote the types that parameterize generic classes,never to denote the values that a routine call may pass to that routine,called arguments.In traditional software parlance "parameter"and "argument"are synonymous.Although the decision of which term to use for routines and which for generic classes is a matter of convention,it is desirable to stick to a consistent rule to avoid any confusion
322 GENERICITY §10.3 Using a generic class A client may use a generic class to declare entities of its own, such as an entity representing a stack. In such a case, the declaration must provide types, called actual generic parameters — as many as the class has formal generic parameters, here just one: sp: STACK [POINT] Providing an actual generic parameter to a generic class so as to produce a type, as here, is called a generic derivation, and the resulting type, such as STACK [POINT], is said to be generically derived. A generic derivation both produces and requires a type: • The result of the derivation, STACK [POINT] in this example, is a type. • To produce this result, you need an existing type to serve as actual generic parameter, POINT in the example. The actual generic parameter is an arbitrary type. Nothing prevents us, in particular, from choosing a type that is itself generically derived; assuming another generic class LIST [G], we can define a stack of lists of points: slp: STACK [LIST [POINT]] or even, using STACK [POINT ] itself as the actual generic parameter, a stack of stacks of points: ssp: STACK [STACK [POINT ]] There is no limit — other than suggested by the usual guideline that software texts should remain simple — to the depth of such nesting. Terminology To discuss genericity, we need to be precise about the terms that we use: • To produce a type such as STACK [POINT ] by providing a type, here POINT, as actual generic parameter for a generic class, here STACK, is to perform a generic derivation. You may encounter the term “generic instantiation” for that process, but it is confusing because “instantiation” normally denotes a run-time event, the production of an object — an instance — from its mold (a class). Generic derivation is a static mechanism, affecting the text of the software, not its execution. So it is better to use completely different terms. • This book uses the term “parameter” exclusively to denote the types that parameterize generic classes, never to denote the values that a routine call may pass to that routine, called arguments. In traditional software parlance “parameter” and “argument” are synonymous. Although the decision of which term to use for routines and which for generic classes is a matter of convention, it is desirable to stick to a consistent rule to avoid any confusion
$10.3 GENERIC CLASSES 323 Type checking Using genericity,you can guarantee that a data structure will only contain elements of a single type.Assuming a class contains the declarations sc:STACK [CIRCLE];sa:STACK [ACCOUNT];c:CIRCLE;a:ACCOUNT then the following are valid instructions in routines of that class: sc.put(c） --Push a circle onto a stack of circles sa,p(a） --Push an account onto a stack of accounts c=sc.item --Assign to a circle entity the top of a stack of circles but each of the following is invalid and will be rejected: sc.put (a), --Attempt to push an account onto a stack of circles sa.put (c); --Attempt to push a circle onto a stack of accounts c=sa.item --Attempt to access as a circle the top of a stack of accounts This will rule out erroneous operations of the kind described earlier,such as attempting to withdraw money from a circle. The type rule The type rule that makes the first set of examples valid and the second invalid is intuitively clear but let us make it precise. First the basic non-generic rule.Consider a feature declared as follows,with no use of any formal generic parameter,in a non-generic class C f(a:T):Uis... This will be the Fea- Then a call of the formxf(d),appearing in an arbitrary class B wherex is of type ture Application C,will be typewise correct if and only if:f is available to B-that is to say,generally rule,page 473. exported,or exported selectively to a set of classes including B;and d is of type T.(When we bring inheritance into the picture we will also accept d if its type is based on a descendant of T.)The result of the call-there is a result since the example assumes that is a function-is of type U. Now assume that C is generic,with G as formal generic parameter,and has a feature h (a:G):G is .. A call to h will be of the form y.h(e)for some entity y that has been declared,for some type /as :C[叮 The counterpart of the non-generic rule is that e must now be of type /(or a compatible type in the sense of inheritance),since the corresponding formal argument a is declared as being of type G,the formal generic parameter,and in the case ofy we may consider G,wherever it appears in class C,as a placeholder for I.Similarly,the result of the call will be of type V.The earlier examples all follow this model:a call of the form s.put (=requires an argument=of type POINT if s is of type STACK [POINT],INTEGER
§10.3 GENERIC CLASSES 323 Type checking Using genericity, you can guarantee that a data structure will only contain elements of a single type. Assuming a class contains the declarations sc: STACK [CIRCLE]; sa: STACK [ACCOUNT]; c: CIRCLE; a: ACCOUNT then the following are valid instructions in routines of that class: sc ● put (c) -- Push a circle onto a stack of circles sa ● put (a) -- Push an account onto a stack of accounts c := sc ● item -- Assign to a circle entity the top of a stack of circles but each of the following is invalid and will be rejected: sc ● put (a); -- Attempt to push an account onto a stack of circles sa ● put (c); -- Attempt to push a circle onto a stack of accounts c := sa ● item -- Attempt to access as a circle the top of a stack of accounts This will rule out erroneous operations of the kind described earlier, such as attempting to withdraw money from a circle. The type rule The type rule that makes the first set of examples valid and the second invalid is intuitively clear but let us make it precise. First the basic non-generic rule. Consider a feature declared as follows, with no use of any formal generic parameter, in a non-generic class C f (a: T ): U is … Then a call of the form x ● f (d ), appearing in an arbitrary class B where x is of type C, will be typewise correct if and only if: f is available to B — that is to say, generally exported, or exported selectively to a set of classes including B; and d is of type T. (When we bring inheritance into the picture we will also accept d if its type is based on a descendant of T.) The result of the call — there is a result since the example assumes that f is a function — is of type U. Now assume that C is generic, with G as formal generic parameter, and has a feature h (a: G): G is … A call to h will be of the form y ● h (e) for some entity y that has been declared, for some type V, as y: C [V] The counterpart of the non-generic rule is that e must now be of type V (or a compatible type in the sense of inheritance), since the corresponding formal argument a is declared as being of type G, the formal generic parameter, and in the case of y we may consider G, wherever it appears in class C, as a placeholder for V. Similarly, the result of the call will be of type V. The earlier examples all follow this model: a call of the form s ● put (z) requires an argument z of type POINT if s is of type STACK [POINT], INTEGER This will be the Feature Application rule, page 473