Inclusion PolymorphismInclusion PolymorphismTypechecking RulesRun-time Type CheckingRun-time Type Checkingldots Run-time ChecksImlementing {f ISTYPE}Implementing {f NARROW}Run-time Checks --- ExampleRun-time Checks --- Exampleldots Run-time Checks -- An $O(1)$AlgorithmRun-time Checks -- Alg. II (b)Run-time Checks -- Alg. II (c)Run-time Checks -- Alg. II (d)Inlining MethodsInlining MethodsInlining Methodsldots Inlining Methods --- ExampleType Hierarchy AnalysisType Hierarchy Analysisldots Readings and ReferencesConfused Student Email520—Spring 2005—46CSc 520Principles of ProgrammingLanguages46: OO Languages — PolymorphismChristian [email protected] of Computer ScienceUniversity of ArizonaCopyrightc 2005 Christian Collberg[1]520—Spring 2005—46Inclusion PolymorphismConsider the last two lines of the example in the followingslide:In L1, S points to a Shape object, but it could just aswell have pointed to an object of any one ofShape’ssubtypes,Square and Circle.If, for example, S had been a Circle, the assignment C:= Swould have been perfectly OK. In L2, however, Sis a Shape and the assignment C := S is illegal (aShape isn’t a Circle).[2]520—Spring 2005—46Inclusion PolymorphismVAR S : Shape; Q : Square; C : Circle;BEGINQ := NEW (Square);C :=NEW (Circle);S := Q; (* OK *)S := C; (* OK *)Q := C; (* Compile-time Error *)L1: S := NEW (Shape);L2: C := S; (* Run-time Error *)END;[3]520—Spring 2005—46Typechecking RulesTYPE T = CLASS ··· END;U = TCLASS ··· END;S = TCLASS ··· END;VAR t,r : T; u : U; s : S;A variable of type T may refer to an object of T or one ofT’s subtypes.AssignmentCompile-time Run-Timet := r; Legal Legalt := u;Legal Legalu := t;Legal Checks := u;Illegal[4]520—Spring 2005—46Run-time Type CheckingModula-3 Type-test Primitives:ISTYPE(object, T) Is object’s type a subtype of T?NARROW(object, T) If object’s type is not a subtype ofT, then issue a run-time type error. Otherwise returnobject, typecast to T.TYPECASE Expr OF Perform different actions dependingon the runtime type ofExpr.The assignment s := t is compiled into s :=NARROW(t, TYPE(s)).[5]520—Spring 2005—46Run-time Type Checking...The Modula-3 runtime-system has three functions thatare used to implement typetests, casts, and theTYPECASE statementNARROW takes a template and an object as parameter.It checks that the type of the object is a subtype of thetype of the template. If it is not, a run-time errormessage is generated. Otherwise,NARROW returns theobject itself.1.ISTYPE(S,T : Template) : BOOLEAN;2.NARROW(Object, Template) : Object;3.TYPECODE(Object) : CARDINAL;[6]520—Spring 2005—46Run-time ChecksCasts are turned into calls to NARROW, when necessary:VAR S : Shape; VAR C : Circle;BEGINS := NEW (Shape); C := S;END;⇓VAR S : Shape; VAR C : Circle;BEGINS := malloc (SIZE(Shape));C :=NARROW(S, Circle$Template);END;[7]520—Spring 2005—46Imlementing ISTYPEWe follow the object’s template pointer, andimmediately (through the templates’ parent pointers)gain access to it’s place in the inheritance hierarchy.PROCEDURE ISTYPE (S, T : TemplatePtr) : BOOLEAN;BEGINLOOPIFS = T THEN RETURN TRUE; ENDIF;S := Sˆ.parent;IF S = ROOT THEN RETURN FALSE; ENDIF;ENDLOOPENDISTYPE;[8]520—Spring 2005—46Implementing NARROWNARROW uses ISTYPE to check if S is a subtype of T. Ofso,S is returned. If not, an exception is thrown.PROCEDURE NARROW(T:TemplatePtr; S:Object):Object;BEGINIFISTYPE(Sˆ.$template, T) THENRETURNS (* OK *)ELSE WRITE "Type error"; HALT;ENDIF;END NARROW;[9]520—Spring 2005—46Run-time Checks — ExampleTYPE T = CLASS [···];S = T CLASS [···];U = T CLASS [···];V = UCLASS [···];X = SCLASS [···];Y = UCLASS [···];Z = UCLASS [···];VAR x : X;SXZUVYT[10]520—Spring 2005—46Run-time Checks — Example...ROOTparent:.....T$TemplateISTYPE(,)templateinstancevari−ablesx:parent:.....parent:.....parent:.....parent:.....parent:.....parent:.....S$TemplateU$TemplateX$Template V$Template Y$Template Z$TemplateISTYPE(x, T)[11]520—Spring 2005—46Run-time Checks – An O(1) AlgorithmThe time for a type test is proportional to the depth ofthe inheritance hierarchy. Two algorithms do type testsin constant time:1. Norman Cohen, “Type-Extension Type Tests can bePerformed in Constant Time.”2. Paul F.Dietz, “Maintaining Order in a Linked List”.The second is more efficient, but requires the entiretype hierarchy to be known. This is a problem inseparately compiled languages.SRC Modula-3 uses Dietz’ method and builds typehierarchies of separately compiled modules at link-time.These algorithms only work for single inheritance.[12]520—Spring 2005—46Run-time Checks – Alg. II (b)In the Compiler (or Linker):1. Build the inheritance tree.2. Perform a preorder traversal and assign preordernumbers to each node.3. Similarly, assign postorder numbers to each node.4. StoreT’s pre- and postorder numbers in T’s template.In the Runtime System:PROCEDURE ISTYPE (S, T : TemplatePtr) : BOOLEAN;BEGINRETURN(T.pre ≤ S.pre) AND (T.post ≥ S.post);END ISTYPE;[13]520—Spring 2005—46Run-time Checks – Alg. II (c)TYPET = CLASS [···];S = T CLASS [···];U = T CLASS [···];V = UCLASS [···];X = SCLASS [···];Y = UCLASS [···];Z = UCLASS [···];post=7pre=1 TUpre=4post=6S post=2pre=2Xpre=3post=1Vpre=5post=3Ypre=6post=4pre=7post=5Z√ISTYPE(Y,U) U.pre≤Y.pre U.post≥Y.postISTYPE(Z,S) S.pre≤Z.pre S.post6≥Z.post√ISTYPE(Z,T) T.pre≤Z.pre T.post≥Z.post[14]520—Spring 2005—46Run-time Checks – Alg. II (d)Consider U:1. U’s pre-number is≤ all it’s children’s pre numbers.2. U’s post-number is ≥ all it’s children’s post numbers.[U.pre,U.post] “covers” (in the sense thatU.pre ≤ pre and U.post ≥ post) the [pre,post] ofall it’s children.S is not a subtype of U since [U.pre,U.post] doesnot cover[S.pre,S.post] (S.post ≤ U.post butS.pre 6≥ U.pre).post=7pre=1 TUpre=4post=6S post=2pre=2Xpre=3post=1Vpre=5post=3Ypre=6post=4pre=7post=5Z[15]520—Spring 2005—46Inlining Methods[16]520—Spring 2005—46Inlining MethodsConsider a method invocation m.P (). The actualprocedure called will depend on the run-time type of m.If more than one method can be invoked at a particularcall site, we have to inline all possible methods. Theappropriate code is selected code by branching on thetype ofm.To improve on method inlining we would like to find outwhen a callm.P() can call exactly one method.[17]520—Spring
View Full Document
Unlocking...