10 Genericity omthe merging of module and types concepts,we have been able to develop a powerful notion of class,which serves as the basis of the object-oriented method and can already,as it stands,enable us to do much.But to achieve our goals of extendibility, reusability and reliability we must make the class construct more flexible,an effort that will proceed in two directions.One,vertical in the figure below,represents abstraction and specialization;it will give rise to the study of inheritance in subsequent chapters.The present chapter studies the other dimension,horizontal in the figure:type parameterization, also known as genericity. Dimensions of Abstraction generalization SET OF BOOKS Type parameterization Type parameterization LIST OF LIST OF LIST OF PEOPLE BOOKS JOURNALS LINKED LIST OF BOOKS Specialization 10.1 HORIZONTAL AND VERTICAL TYPE GENERALIZATION With the mechanisms studied so far we have all that we need to write the class at the center of the figure,LIST_OF_BOOKS,of which an instance represents a list of book objects. We know what kinds of feature it would have:put to add an element,remove to delete an
10 Genericity From the merging of module and types concepts, we have been able to develop a powerful notion of class, which serves as the basis of the object-oriented method and can already, as it stands, enable us to do much. But to achieve our goals of extendibility, reusability and reliability we must make the class construct more flexible, an effort that will proceed in two directions. One, vertical in the figure below, represents abstraction and specialization; it will give rise to the study of inheritance in subsequent chapters. The present chapter studies the other dimension, horizontal in the figure: type parameterization, also known as genericity. 10.1 HORIZONTAL AND VERTICAL TYPE GENERALIZATION With the mechanisms studied so far we have all that we need to write the class at the center of the figure, LIST_OF_BOOKS, of which an instance represents a list of book objects. We know what kinds of feature it would have: put to add an element, remove to delete an Dimensions of generalization LIST_OF_ PEOPLE LIST_OF_ BOOKS LIST_OF_ JOURNALS SET_OF_ BOOKS LINKED_LIST_ OF_BOOKS Abstraction Specialization Type parameterization Type parameterization
318 GENERICITY $10.2 element,count to find out how many elements are present and so on.But it is easy to see two ways of generalizing the notion of LIST OF BOOKS: Lists are a special case of"container"structure,of which other examples (among many)include trees,stacks and arrays.A more abstract variant might be described by a class SET OF BOOKS.A more specialized variant,covering a particular choice of list representation,might be described by a class LINKED LIST OF BOOK.S.This is the vertical dimension of our figure-the dimension of inheritance. Lists of books are a special case of lists of objects of any particular kind,of which other examples (among many)include lists of journals,lists of people,lists of integers.This is the horizontal dimension of our figure -the dimension of genericity,our topic for the rest of this chapter.By giving classes parameters representing arbitrary types,we will avoid the need to write many quasi-identical classes-such as LIST OF BOOKS and LIST OF PEOPLE-without sacrificing the safety afforded by static typing. The relation between these two mechanisms is an elusive question for students of Appendix B. object-oriented concepts.Should inheritance and genericity be viewed as comrades or competitors in the rush towards more flexible software?That question is the subject of an appendix.In the present chapter we concentrate on genericity;this will also enable us to take a closer look at one of the most common examples of generic structure:arrays. 10.2 THE NEED FOR TYPE PARAMETERIZATION Genericity is not really a new concept in this discussion,although we have not yet seen it See"Genericin". applied to classes.We encountered the idea a first time when reviewing traditional page 96,and again approaches to reusability;and when we studied the mathematical model-abstract data "Genericity'”,page 131. types-we saw the need to define an ADT as parameterized by types. Generic abstract data types Our working ADT example,STACK,was declared as STACK [G],meaning that any actual use requires you to specify an"actual generic parameter"representing the type of the objects stored in a particular stack.The name G as used in the ADT's specification stands for any possible type that these stack elements may have;it is called the formal generic parameter of the class.With this approach you can use a single specification for all possible stacks;the alternative,hard to accept,would be to have a class INTEGER STACK,a class REAL STACK and so on. Any ADT describing "container"structures-data structures such as sets,lists, trees,matrices,arrays and many others that serve to keep objects of various possible types -will be similarly generic. The same concerns,applied to the container classes of our software systems rather than to the container ADTs of our mathematical models,will yield a similar solution
318 GENERICITY §10.2 element, count to find out how many elements are present and so on. But it is easy to see two ways of generalizing the notion of LIST_OF_BOOKS: • Lists are a special case of “container” structure, of which other examples (among many) include trees, stacks and arrays. A more abstract variant might be described by a class SET_OF_BOOKS. A more specialized variant, covering a particular choice of list representation, might be described by a class LINKED_LIST_OF_ BOOKS. This is the vertical dimension of our figure — the dimension of inheritance. • Lists of books are a special case of lists of objects of any particular kind, of which other examples (among many) include lists of journals, lists of people, lists of integers. This is the horizontal dimension of our figure — the dimension of genericity, our topic for the rest of this chapter. By giving classes parameters representing arbitrary types, we will avoid the need to write many quasi-identical classes — such as LIST_OF_BOOKS and LIST_OF_PEOPLE — without sacrificing the safety afforded by static typing. The relation between these two mechanisms is an elusive question for students of object-oriented concepts. Should inheritance and genericity be viewed as comrades or competitors in the rush towards more flexible software? That question is the subject of an appendix. In the present chapter we concentrate on genericity; this will also enable us to take a closer look at one of the most common examples of generic structure: arrays. 10.2 THE NEED FOR TYPE PARAMETERIZATION Genericity is not really a new concept in this discussion, although we have not yet seen it applied to classes. We encountered the idea a first time when reviewing traditional approaches to reusability; and when we studied the mathematical model — abstract data types — we saw the need to define an ADT as parameterized by types. Generic abstract data types Our working ADT example, STACK, was declared as STACK [G], meaning that any actual use requires you to specify an “actual generic parameter” representing the type of the objects stored in a particular stack. The name G as used in the ADT’s specification stands for any possible type that these stack elements may have; it is called the formal generic parameter of the class. With this approach you can use a single specification for all possible stacks; the alternative, hard to accept, would be to have a class INTEGER_ STACK, a class REAL_STACK and so on. Any ADT describing “container” structures — data structures such as sets, lists, trees, matrices, arrays and many others that serve to keep objects of various possible types — will be similarly generic. The same concerns, applied to the container classes of our software systems rather than to the container ADTs of our mathematical models, will yield a similar solution. Appendix B. See “Genericity”, page 96, and again “Genericity”, page 131
$10.2 THE NEED FOR TYPE PARAMETERIZATION 319 The issue Let us keep the stack example,no longer as a mathematical ADT but as a software class. We know how to write a class INTEGER STACK describing the notion of stack of integers.Features will include cout(number ofelements),put(push a new element),item (top element),remove (pop the top element),empry (is this stack empty?). Type /NTEGER will be used frequently in this class.For example it is the type of the argument of put and of the result of item: put (element:INTEGER)is --Push element on top. do...end item:INTEGER is --Item at top do...end These appearances of type INTEGER follow from the rule of explicit declaration that we have used in developing the notation:any time you introduce an entity,denoting possible run-time objects,you must write an explicit type declaration for it,such as element: INTEGER.Here this means that you must specify a type for the query item,for the argument element of procedure put,and for other entities denoting possible stack elements. But as a consequence you must write a different class for every sort of stack: INTEGER STACK,REAL STACK,POINT STACK,BOOK STACK...All such stack classes will be identical except for the type declarations of item,element and a few other entities:since the basic operations on a stack are the same regardless of the type of stack elements,nothing in the bodies of the various routines depends on the choice of INTEGER,REAL,POINT or BOOK as the type of stack element.For anyone concerned with reusability,this is not attractive. The issue,then,is the contradiction that container classes seem to cause between two of the fundamental quality goals introduced at the beginning of this book: Reliability:retaining the benefits of type safety through explicit type declarations. Reusability:being able to write a single software element covering variants of a given notion. The role of typing Chapter 17. Why insist on explicit type declarations(the first of the two requirements)?This is part of the general question of typing,to which an entire chapter is devoted later in this book.It is not too early to note the two basic reasons why an O-O notation should be statically typed: The readability reason:explicit declarations tell the reader,loud and clear,about the intended use of every element.This is precious to whoever-the original author,or someone else-needs to understand the element,for example to debug or extend it
§10.2 THE NEED FOR TYPE PARAMETERIZATION 319 The issue Let us keep the stack example, no longer as a mathematical ADT but as a software class. We know how to write a class INTEGER_STACK describing the notion of stack of integers. Features will include count (number of elements), put (push a new element), item (top element), remove (pop the top element), empty (is this stack empty?). Type INTEGER will be used frequently in this class. For example it is the type of the argument of put and of the result of item: put (element: INTEGER) is -- Push element on top. do … end item: INTEGER is -- Item at top do … end These appearances of type INTEGER follow from the rule of explicit declaration that we have used in developing the notation: any time you introduce an entity, denoting possible run-time objects, you must write an explicit type declaration for it, such as element: INTEGER. Here this means that you must specify a type for the query item, for the argument element of procedure put, and for other entities denoting possible stack elements. But as a consequence you must write a different class for every sort of stack: INTEGER_STACK, REAL_STACK, POINT_STACK, BOOK_STACK… All such stack classes will be identical except for the type declarations of item, element and a few other entities: since the basic operations on a stack are the same regardless of the type of stack elements, nothing in the bodies of the various routines depends on the choice of INTEGER, REAL, POINT or BOOK as the type of stack element. For anyone concerned with reusability, this is not attractive. The issue, then, is the contradiction that container classes seem to cause between two of the fundamental quality goals introduced at the beginning of this book: • Reliability: retaining the benefits of type safety through explicit type declarations. • Reusability: being able to write a single software element covering variants of a given notion. The role of typing Why insist on explicit type declarations (the first of the two requirements)? This is part of the general question of typing, to which an entire chapter is devoted later in this book. It is not too early to note the two basic reasons why an O-O notation should be statically typed: • The readability reason: explicit declarations tell the reader, loud and clear, about the intended use of every element. This is precious to whoever — the original author, or someone else — needs to understand the element, for example to debug or extend it. Chapter 17
320 GENERICITY $10.3 The reliability reason:thanks to explicit type declarations,a compiler will be able to detect erroneous operations before they have had a chance to strike.In the fundamental operations of object-oriented computation,feature calls of the general formx.(a....),wherex is of some type TX,the potential for mischief is manyfold: the class corresponding to TX might not have a feature called /the feature might exist but be secret;the number of arguments might not coincide with what has been declared for fin the class;the type for a or another argument might not be compatible with what /expects.In all such cases,letting the software text go through unopposed -as in a language without static typechecking-would usually mean nasty consequences at run time,such as the program crashing with a diagnostic of the form "Message not understood"(the typical outcome in Smalltalk,a non-statically-typed O-O language).With explicit typing,the compiler will not let the erroneous construct through. The key to software reliability,as was pointed out in the discussion of that notion,is prevention more than cure.Many studies have found that the cost of correcting an error grows astronomically when the time of detection is delayed.Static typing,which enables the early detection of type errors,is a fundamental tool in the quest for reliability Without these considerations we would not need explicit declarations,and so we would not need genericity.As a consequence the rest of this chapter only applies to statically typed languages,that is to say languages which require all entities to be declared and enforce rules enabling compilers to detect type inconsistencies prior to execution.In a non-statically-typed language such as Smalltalk,there is no role for genericity;this removes a language construct,but also removes any protection against schemes such as my_stack.put (my circle) my account:=my stack.item my_account.withdraw (5000) where an element is retrieved from the top of the stack and treated as if it were a bank account even though it is in reality (because of the first instruction)a circle,so that the software ends up trying to withdraw five thousand dollars from a circle on the screen. Static typing protects us against such mishaps;combining it with the reusability requirement implies that we develop a mechanism for genericity. 10.3 GENERIC CLASSES Reconciling static typing with the requirement of reusability for classes describing container structures means,as illustrated by the stack example,that we want both to: Declare a type for every entity appearing in the text of a stack class,including entities representing stack elements. Write the class so that it does not give out any clue about the elements'type,and hence that it can be used to build stacks of arbitrary elements
320 GENERICITY §10.3 • The reliability reason: thanks to explicit type declarations, a compiler will be able to detect erroneous operations before they have had a chance to strike. In the fundamental operations of object-oriented computation, feature calls of the general form x ● f (a, …), where x is of some type TX, the potential for mischief is manyfold: the class corresponding to TX might not have a feature called f; the feature might exist but be secret; the number of arguments might not coincide with what has been declared for f in the class; the type for a or another argument might not be compatible with what f expects. In all such cases, letting the software text go through unopposed — as in a language without static typechecking — would usually mean nasty consequences at run time, such as the program crashing with a diagnostic of the form “Message not understood” (the typical outcome in Smalltalk, a non-statically-typed O-O language). With explicit typing, the compiler will not let the erroneous construct through. The key to software reliability, as was pointed out in the discussion of that notion, is prevention more than cure. Many studies have found that the cost of correcting an error grows astronomically when the time of detection is delayed. Static typing, which enables the early detection of type errors, is a fundamental tool in the quest for reliability. Without these considerations we would not need explicit declarations, and so we would not need genericity. As a consequence the rest of this chapter only applies to statically typed languages, that is to say languages which require all entities to be declared and enforce rules enabling compilers to detect type inconsistencies prior to execution. In a non-statically-typed language such as Smalltalk, there is no role for genericity; this removes a language construct, but also removes any protection against schemes such as my_stack ● put (my_circle) my_account := my_stack ● item my_account ● withdraw (5000) where an element is retrieved from the top of the stack and treated as if it were a bank account even though it is in reality (because of the first instruction) a circle, so that the software ends up trying to withdraw five thousand dollars from a circle on the screen. Static typing protects us against such mishaps; combining it with the reusability requirement implies that we develop a mechanism for genericity. 10.3 GENERIC CLASSES Reconciling static typing with the requirement of reusability for classes describing container structures means, as illustrated by the stack example, that we want both to: • Declare a type for every entity appearing in the text of a stack class, including entities representing stack elements. • Write the class so that it does not give out any clue about the elements’ type, and hence that it can be used to build stacks of arbitrary elements
$10.3 GENERIC CLASSES 321 At first sight these requirements seem irreconcilable but they are not.The first one commands us to declare a type;it does not assume that the declaration is exact!As soon as we have provided a type name,we will have pacified the type checking mechanism. ("Name your fear,and it will go away".)Hence the idea of genericity:to obtain a type- parameterized class,equip it with the name of a fictitious type,called the formal generic parameter. Declaring a generic class By convention the generic parameter will use the name G for Generic;this is a style recommendation,not a formal rule.If we need more generic parameters they will be called H.and so on. The syntax will include the formal generic parameters in square brackets after the class name,as with generic ADTs in a previous chapter.Here is an example: indexing description:"Stacks of elements of an arbitrary type G" class STACK [G]feature count:INTEGER --Number of elements in stack empty:BOOLEAN is --Are there no items? do...end full:BOOLEAN is --Is representation full? do...end item:G is --Top element do...end put (x:G)is --Add x on top. do...end remove is --Remove top element. do...end end--class STACK In the class,you may use a formal generic parameter such as G in declarations:not only for function results (as in item)and formal arguments ofroutines (as in put),but also for attributes and local entities
§10.3 GENERIC CLASSES 321 At first sight these requirements seem irreconcilable but they are not. The first one commands us to declare a type; it does not assume that the declaration is exact! As soon as we have provided a type name, we will have pacified the type checking mechanism. (“Name your fear, and it will go away”.) Hence the idea of genericity: to obtain a typeparameterized class, equip it with the name of a fictitious type, called the formal generic parameter. Declaring a generic class By convention the generic parameter will use the name G for Generic; this is a style recommendation, not a formal rule. If we need more generic parameters they will be called H, I and so on. The syntax will include the formal generic parameters in square brackets after the class name, as with generic ADTs in a previous chapter. Here is an example: indexing description: "Stacks of elements of an arbitrary type G" class STACK [G] feature count: INTEGER -- Number of elements in stack empty: BOOLEAN is --Are there no items? do … end full: BOOLEAN is -- Is representation full? do … end item: G is -- Top element do … end put (x: G) is -- Add x on top. do … end remove is -- Remove top element. do … end end -- class STACK In the class, you may use a formal generic parameter such as G in declarations: not only for function results (as in item) and formal arguments of routines (as in put), but also for attributes and local entities