474 INTRODUCTION TO INHERITANCE $14.3 Limits to polymorphism Unrestrained polymorphism would be incompatible with a static notion of type. Inheritance governs which polymorphic attachments are permissible. The polymorphic attachments used as examples,such as p:=randp:=1,all had as source type a descendant of the target's class.We say that the source type conforms to the target class;for example SOUARE conforms to RECTANGLE and to POLYGON but not to TR/ANGLE.This notion has already been used informally but we need a precise definition: Definition:conformance A type U conforms to a type T only if the base class of U is a descendant of the base class of 7;also,for generically derived types,every actual parameter of Umust(recursively)conform to the corresponding formal parameter in T. Why is the notion of descendant not sufficient?The reason is again that since we See"Types and encountered genericity we have had to make a technical distinction between types and classes”,page325 classes.Every type has a base class,which in the absence of genericity is the type itself (for example POLYGON is its own base class),but for a generically derived type is the class from which the type is built;for example the base class of L/ST[POLYGON]is L/S7. The second part of the definition indicates that B [Y]will conform to 4 [Y]if B is a descendant of4 and Y a descendant of Y. Note that,as every class is a descendant of itself,so does every type conform to itself. With this generalization of the notion of descendant we get the second fundamental typing rule: Type Conformance rule An attachment of target x and source y(that is to say,an assignmentx:=y,or the use ofy as an actual argument to a routine call where the corresponding formal argument isx)is only valid if the type ofy conforms to the type ofx. The Type Conformance rule expresses that you can assign from the more specific to the more general,but not conversely.Sop:=r is valid butr:=p is invalid. The rule may be illustrated like this.Assume I am absent-minded enough to write just "Animal"in the order form I send to the Mail-A-Pet company.Then,whether I receive a dog,a ladybug or a killer whale,I have no right to complain.(The hypothesis is that classes DOG etc.are all descendants of AN/MAL.)If,on the other hand,I specifically request a dog,and the mailman brings me one morning a box with a label that reads ANIMAL,or perhaps MAMMAL (an intermediate ancestor),I am entitled to return it to the sender-even if from the box come unmistakable sounds of yelping and barking. Since my order was not fulfilled as specified,I shall owe nothing to Mail-A-Pet
474 INTRODUCTION TO INHERITANCE §14.3 Limits to polymorphism Unrestrained polymorphism would be incompatible with a static notion of type. Inheritance governs which polymorphic attachments are permissible. The polymorphic attachments used as examples, such as p := r and p := t, all had as source type a descendant of the target’s class. We say that the source type conforms to the target class; for example SQUARE conforms to RECTANGLE and to POLYGON but not to TRIANGLE. This notion has already been used informally but we need a precise definition: Why is the notion of descendant not sufficient? The reason is again that since we encountered genericity we have had to make a technical distinction between types and classes. Every type has a base class, which in the absence of genericity is the type itself (for example POLYGON is its own base class), but for a generically derived type is the class from which the type is built; for example the base class of LIST [POLYGON] is LIST. The second part of the definition indicates that B [Y] will conform to A [X] if B is a descendant of A and Y a descendant of X. Note that, as every class is a descendant of itself, so does every type conform to itself. With this generalization of the notion of descendant we get the second fundamental typing rule: The Type Conformance rule expresses that you can assign from the more specific to the more general, but not conversely. So p := r is valid but r := p is invalid. The rule may be illustrated like this. Assume I am absent-minded enough to write just “Animal” in the order form I send to the Mail-A-Pet company. Then, whether I receive a dog, a ladybug or a killer whale, I have no right to complain. (The hypothesis is that classes DOG etc. are all descendants of ANIMAL.) If, on the other hand, I specifically request a dog, and the mailman brings me one morning a box with a label that reads ANIMAL, or perhaps MAMMAL (an intermediate ancestor), I am entitled to return it to the sender — even if from the box come unmistakable sounds of yelping and barking. Since my order was not fulfilled as specified, I shall owe nothing to Mail-A-Pet. Definition: conformance A type U conforms to a type T only if the base class of U is a descendant of the base class of T; also, for generically derived types, every actual parameter of U must (recursively) conform to the corresponding formal parameter in T. Type Conformance rule An attachment of target x and source y (that is to say, an assignment x := y, or the use of y as an actual argument to a routine call where the corresponding formal argument is x) is only valid if the type of y conforms to the type of x. See “Types and classes”, page 325
$14.3 TYPING FOR INHERITANCE 475 Instances The original discus-With the introduction of polymorphism we need a more specific terminology to talk about sion was"The mold instances.Informally,the instances of a class are the run-time objects built according to and the instance". page 167. the definition of a class.But now we must also consider the objects built from the definition of its proper descendants.Hence the more precise definition: Definition:direct instance,instance A direct instance of a class C is an object produced according to the exact definition of C,through a creation instruction!!x..where the target x is of type C(or,recursively,by cloning a direct instance of C). An instance of C is a direct instance of a descendant of C. The last part of this definition implies,since the descendants of a class include the class itself,that a direct instance ofC is also an instance of C. So the execution of pl,p2:POLYGON:r:RECTANGLE upl...;!r...;p2:=r will create two instances of POLYGON but only one direct instance(the one attached to p/).The other object,to which the extract attaches both p2 and r,is a direct instance of RECTANGLE-and so an instance of both POLYGON and RECTANGLE. Although the notions of instance and direct instance are defined above for a class, they immediately extend to any type(with a base class and possible generic parameters). Polymorphism means that an entity of a certain type may become attached not only to direct instances of that type,but to arbitrary instances.We may indeed consider that the role of the type conformance rule is to ensure the following property: Static-dynamic type consistency An entity declared of a type T may at run time only become attached to instances of T. Static type,dynamic type The name of the last property suggests the concepts of“static type'”and“dynamic type'”., The type used to declare an entity is the static type of the corresponding reference.If,at run time,the reference gets attached to an object of a certain type,this type becomes the dynamic type of the reference. So with the declaration p:POLYGON,the static type of the reference that p denotes is POLYGON;after the execution of !p,the dynamic type of that reference is also POLYGON;after the assignment p:=r,with r of type RECTANGLE and non-void,the dynamic type is RECTANGLE
§14.3 TYPING FOR INHERITANCE 475 Instances With the introduction of polymorphism we need a more specific terminology to talk about instances. Informally, the instances of a class are the run-time objects built according to the definition of a class. But now we must also consider the objects built from the definition of its proper descendants. Hence the more precise definition: The last part of this definition implies, since the descendants of a class include the class itself, that a direct instance of C is also an instance of C. So the execution of p1, p2: POLYGON; r: RECTANGLE … !! p1 …; !! r …; p2 := r will create two instances of POLYGON but only one direct instance (the one attached to p1). The other object, to which the extract attaches both p2 and r, is a direct instance of RECTANGLE — and so an instance of both POLYGON and RECTANGLE. Although the notions of instance and direct instance are defined above for a class, they immediately extend to any type (with a base class and possible generic parameters). Polymorphism means that an entity of a certain type may become attached not only to direct instances of that type, but to arbitrary instances. We may indeed consider that the role of the type conformance rule is to ensure the following property: Static type, dynamic type The name of the last property suggests the concepts of “static type” and “dynamic type”. The type used to declare an entity is the static type of the corresponding reference. If, at run time, the reference gets attached to an object of a certain type, this type becomes the dynamic type of the reference. So with the declaration p: POLYGON, the static type of the reference that p denotes is POLYGON; after the execution of !! p, the dynamic type of that reference is also POLYGON; after the assignment p := r, with r of type RECTANGLE and non-void, the dynamic type is RECTANGLE. Definition: direct instance, instance A direct instance of a class C is an object produced according to the exact definition of C, through a creation instruction !! x… where the target x is of type C (or, recursively, by cloning a direct instance of C). An instance of C is a direct instance of a descendant of C. Static-dynamic type consistency An entity declared of a type T may at run time only become attached to instances of T. The original discussion was “The mold and the instance”, page 167
476 INTRODUCTION TO INHERITANCE $14.3 The Type Conformance rule states that the dynamic type must always conform to the static type. To avoid any confusion remember that we are dealing with three levels:an entity is See"Srates ofaref. an identifier in the class text,at run time its value is a reference (except in the expanded erence".page 246. case);the reference may get attached to an object.Then: An object only has a dynamic type,the type with which it has been created.That type will never change during the object's lifetime. At any time during execution,a reference has a dynamic type,the type of the object NONE will be seenin to which it is currently attached (or the special type NONE if the reference is void). “The bottom of the The dynamic type may change as a result of reattachment operations. pit".page 582. Only an entity has both a static type and dynamic types.Its static type is the type with which it was declared:T if the declaration was x:T.Its dynamic type at some execution-time instant is the type of its reference value,meaning the type of the attached object. In the expanded case there is no reference;the value ofx is an object of type 7,and x has T as both its static type and as its only possible dynamic type. Are the restrictions justified? The two typing rules may sometimes seem too restrictive.For example,the second instruction in both of the following sequences will be statically rejected: R1·p=r,r=P R2.p:=r;x:=p.diagonal In RI,we refuse to assign a poly gon to a rectangle entity even though that polygon happens at run time to be a rectangle (like refusing to accept a dog because it comes in a box marked"animal").In R2,we decide that diagonal is not applicable to p even though at run time it would in fact be-as it were by accident. But closer examination of these examples confirms that the rules are justified.If you attach a reference to an object,better avoid later problems by making sure that they are of compatible types.And if you want to apply a rectangle operation,why not declare the target as a rectangle? In practice,cases of the form RI and R2 are unlikely.Assignments such as p:=r will normally occur as part of some control structure that depends on run-time conditions, such as user input.A more realistic polymorphic scheme may look like this: !!r.make (...).. screen.display icons -Display icons representing various polygons screen.wait for mouse click -Wait for the user to click the mouse button x:=screen.mouse position Find out at what position -the mouse was clicked chosen icon :screen.icon where is (x)--Find out what icon appears at the --mouse's position
476 INTRODUCTION TO INHERITANCE §14.3 The Type Conformance rule states that the dynamic type must always conform to the static type. To avoid any confusion remember that we are dealing with three levels: an entity is an identifier in the class text; at run time its value is a reference (except in the expanded case); the reference may get attached to an object. Then: • An object only has a dynamic type, the type with which it has been created. That type will never change during the object’s lifetime. • At any time during execution, a reference has a dynamic type, the type of the object to which it is currently attached (or the special type NONE if the reference is void). The dynamic type may change as a result of reattachment operations. • Only an entity has both a static type and dynamic types. Its static type is the type with which it was declared: T if the declaration was x: T. Its dynamic type at some execution-time instant is the type of its reference value, meaning the type of the attached object. In the expanded case there is no reference; the value of x is an object of type T, and x has T as both its static type and as its only possible dynamic type. Are the restrictions justified? The two typing rules may sometimes seem too restrictive. For example, the second instruction in both of the following sequences will be statically rejected: R1 • p:= r; r := p R2 • p := r; x := p ● diagonal In R1, we refuse to assign a polygon to a rectangle entity even though that polygon happens at run time to be a rectangle (like refusing to accept a dog because it comes in a box marked “animal”). In R2, we decide that diagonal is not applicable to p even though at run time it would in fact be — as it were by accident. But closer examination of these examples confirms that the rules are justified. If you attach a reference to an object, better avoid later problems by making sure that they are of compatible types. And if you want to apply a rectangle operation, why not declare the target as a rectangle? In practice, cases of the form R1 and R2 are unlikely. Assignments such as p := r will normally occur as part of some control structure that depends on run-time conditions, such as user input. A more realistic polymorphic scheme may look like this: !! r ● make (…); … screen ● display_icons -- Display icons representing various polygons screen ● wait_for_mouse_click -- Wait for the user to click the mouse button x := screen ● mouse_position -- Find out at what position -- the mouse was clicked chosen_icon := screen ● icon_where_is (x) -- Find out what icon appears at the -- mouse’s position See “States of a reference”, page 240. NONE will be seen in “The bottom of the pit”, page 582
$14.3 TYPING FOR INHERITANCE 477 if chosen icon=rectangle icon then p :=r elseif.… p:=“Some other type of polygon'”.. 0 end ..Uses of p,for example p.display,p.rotate,... On the last line,p can denote arbitrary polygons,so you should only apply general POLYGON features.Clearly,operations valid for rectangles only,such as diagonal, should be applied to ronly (for example in the first clause of the if).Where p as such is going to be used,in the instructions following the if instruction,only operations defined for all variants of polygons are applicable to it. In another typical case,p could just be a formal routine argument: some routine (p:POLYGON)is... and you execute a call some routine(r),valid as per the Type Conformance rule;but when you write the routine you do not know about this call.In fact a call some routine (r)fort or type TRIANGLE,or any other descendant of POLYGON for that matter,would be equally valid,so all you can assume is that p represents some kind of polygon-any kind of polygon.It is quite appropriate,then,that you should be restricted to applying POLYGON features to p. It is in this kind of situation-where you cannot predict the exact type of the attached object-that polymorphic entities such as p are useful. Can ignorance be bliss? It is worthwhile reinforcing the last few points a bit since the concepts now being introduced will be so important in the rest of our discussion.(There will be nothing really new in this short section,but it should help you understand the basic concepts better, preparing you for the more advanced ones which follow. If you are still uneasy at the impossibility of writing p.diagonal even after a call p:=r-case R2-you are not alone;this is a shock to many people when they start grappling with these concepts.We know that p is a rectangle because of the assignment, so why may we not access its diagonal?For one thing,that would be useless.After the polymorphic assignment,as shown in the following extract from an earlier figure,the same RECTANGLE object now has two names,a polygon name p and a rectangle name r: After a 02 polymorphic attachment (RECTANGLE)
§14.3 TYPING FOR INHERITANCE 477 if chosen_icon = rectangle_icon then p := r elseif … p := “Some other type of polygon” … º end … Uses of p, for example p ● display, p ● rotate, … On the last line, p can denote arbitrary polygons, so you should only apply general POLYGON features. Clearly, operations valid for rectangles only, such as diagonal, should be applied to r only (for example in the first clause of the if). Where p as such is going to be used, in the instructions following the if instruction, only operations defined for all variants of polygons are applicable to it. In another typical case, p could just be a formal routine argument: some_routine (p: POLYGON) is… and you execute a call some_routine (r), valid as per the Type Conformance rule; but when you write the routine you do not know about this call. In fact a call some_routine (t) for t or type TRIANGLE, or any other descendant of POLYGON for that matter, would be equally valid, so all you can assume is that p represents some kind of polygon — any kind of polygon. It is quite appropriate, then, that you should be restricted to applying POLYGON features to p. It is in this kind of situation — where you cannot predict the exact type of the attached object — that polymorphic entities such as p are useful. Can ignorance be bliss? It is worthwhile reinforcing the last few points a bit since the concepts now being introduced will be so important in the rest of our discussion. (There will be nothing really new in this short section, but it should help you understand the basic concepts better, preparing you for the more advanced ones which follow.) If you are still uneasy at the impossibility of writing p ● diagonal even after a call p :=r — case R2 — you are not alone; this is a shock to many people when they start grappling with these concepts. We know that p is a rectangle because of the assignment, so why may we not access its diagonal? For one thing, that would be useless. After the polymorphic assignment, as shown in the following extract from an earlier figure, the same RECTANGLE object now has two names, a polygon name p and a rectangle name r: After a polymorphic attachment p r (RECTANGLE) O2
478 INTRODUCTION TO INHERITANCE $14.3 In such a case,since you do know that the object O2 is a rectangle and have access to it through its rectangle name r,why would you write a diagonal access operation in the form p.diagonal?This is uninteresting since you can just write it as r.diagonal;using the object's official rectangle name removes any doubt as to the validity of applying a rectangle operation.Using the polygon name p,which could just as well denote a triangle object,brings nothing and introduces uncertainty. Polymorphism,in fact,loses information:when as a result of the assignment p:=r you are able to refer to the rectangle object O2 under its polygon name p,you have lost something precious:the ability to use rectangle-specific features.What then is the purpose?In this case,there is none.The only interesting application,as noted,arises when you do not know for sure what kind of polygon p is,as a result of a conditional instruction if some condition then p:=r else p:=something else...,or because p is a formal routine argument and you do not know what the actual argument will be.But then in such cases it would be incorrect and dangerous to apply to p anything else than POLYGON features. To continue with the animal theme,imagine that someone asks"do you have a pet?" and you answer"yes,a cat!".This is similar to a polymorphic assignment,making a single object known through two names of different types:"my_pet"and "my_cat" now denote the same animal.But they do not serve the same purpose;the first has less information than the second.You can use either name if you call the post-sales division of Mail-A-Pet,Absentee Owner Department ("I am going on holiday,what's your price for keeping my_pet [or:my_cat]for to weeks"),but if you phone their Destructive Control Department to ask "Can I bring my_pet for a de-clawing Tuesday?",you probably will not get an appointment until the employee has made you confirm that you really mean my_cat. When you want to force a type In some special cases there may be a need to try an assignment going against the grain of inheritance,and accept that the result is not guaranteed to yield an object.This does not normally occur,when you are properly applying the object-oriented method,with objects that are internal to a certain software element.But you might for example receive over the network an object advertized to be of a certain type;since you have no control over the origin of the object,static type declarations will guarantee nothing,and you must test the type before accepting it. When we receive that box marked“Animal'”rather than the expected“Dog”,we might be tempted to open the "Animal"box anyway and take our chances,knowing that if its content is not the expected dog we will have forfeited our right to return the package,and depending on what comes out of it we may not even live to tell the story. Such cases require a new mechanism,assignment attempt,which will enable us to See"ASSIGNMENT write instructions of the formr=p(where?=is the symbol for assignment attempt,ATTEMPT16.5. versus:=for assignment),meaning "do the assignment if the object type is the expected page 591. one for r,otherwise make r void".But we are not equipped yet to understand how this instruction fits in the proper use of the object-oriented method,so we will have to return to it in a subsequent chapter.(Until then,you did not read about it here
478 INTRODUCTION TO INHERITANCE §14.3 In such a case, since you do know that the object O2 is a rectangle and have access to it through its rectangle name r, why would you write a diagonal access operation in the form p ● diagonal? This is uninteresting since you can just write it as r ● diagonal; using the object’s official rectangle name removes any doubt as to the validity of applying a rectangle operation. Using the polygon name p, which could just as well denote a triangle object, brings nothing and introduces uncertainty. Polymorphism, in fact, loses information: when as a result of the assignment p := r you are able to refer to the rectangle object O2 under its polygon name p, you have lost something precious: the ability to use rectangle-specific features. What then is the purpose? In this case, there is none. The only interesting application, as noted, arises when you do not know for sure what kind of polygon p is, as a result of a conditional instruction if some_condition then p:= r else p := something_else …, or because p is a formal routine argument and you do not know what the actual argument will be. But then in such cases it would be incorrect and dangerous to apply to p anything else than POLYGON features. To continue with the animal theme, imagine that someone asks “do you have a pet?” and you answer “yes, a cat!”. This is similar to a polymorphic assignment, making a single object known through two names of different types: “my_pet” and “my_cat” now denote the same animal. But they do not serve the same purpose; the first has less information than the second. You can use either name if you call the post-sales division of Mail-A-Pet, Absentee Owner Department (“I am going on holiday; what’s your price for keeping my_pet [or: my_cat] for two weeks”); but if you phone their Destructive Control Department to ask “Can I bring my_pet for a de-clawing Tuesday?”, you probably will not get an appointment until the employee has made you confirm that you really mean my_cat. When you want to force a type In some special cases there may be a need to try an assignment going against the grain of inheritance, and accept that the result is not guaranteed to yield an object. This does not normally occur, when you are properly applying the object-oriented method, with objects that are internal to a certain software element. But you might for example receive over the network an object advertized to be of a certain type; since you have no control over the origin of the object, static type declarations will guarantee nothing, and you must test the type before accepting it. When we receive that box marked “Animal” rather than the expected “Dog”, we might be tempted to open the “Animal” box anyway and take our chances, knowing that if its content is not the expected dog we will have forfeited our right to return the package, and depending on what comes out of it we may not even live to tell the story. Such cases require a new mechanism, assignment attempt, which will enable us to write instructions of the form r ?= p (where ?= is the symbol for assignment attempt, versus := for assignment), meaning “do the assignment if the object type is the expected one for r, otherwise make r void”. But we are not equipped yet to understand how this instruction fits in the proper use of the object-oriented method, so we will have to return to it in a subsequent chapter. (Until then, you did not read about it here.) See “ASSIGNMENT ATTEMPT”, 16.5, page 591