CSc 453Compilers and Systems Software23 : OO LanguagesDepartment of Computer ScienceUniversity of [email protected]° 2009 Christian CollbergObject-Oriented LanguagesObject-oriented languages extend imperative languages with:1A classification scheme that allows us to specify is-a as well ashas-a relationships. Has-a is supported by Pascal, where wecan declare that one data item has another item (a recordvariable has-a record field). Object-Pascal, Oberon, etc,extends this capability with inheritance which allows us tostate that one data item is (an extension of) another item.2Late binding, which allows us to select between differentimplementations of the same abstract data type at run-time.Object-Oriented Languages. . .3Polymorphism, which is the ability of a variable to store valuesof different types. OO languages support a special kind ofpolymorphism, called inclusion polymorphism, that restrictsthe values that can be stored in a variable of type T to valuesof type T or subtypes of T .4Data encapsulation. Data (instance variables) and operations(methods) are defined together.5Templates and objects. A template (class or prototype)describes how to create new objects (instances of abstractdata types).Compiling OO LanguagesRuntime type checking (a variable of type ref T may onlyreference objects of type T or T ’s subtypes).Because of the polymorphic nature of OO languages, we can’talways know (at compile-time) the type of the object that agiven variable will refer to at run-time. When we invoke amethod we can’t actually know which piece of code we shouldexecute. Finding the right piece of code is called methodlookup. It can be done by name (Objective-C) or number(C++).Most OO languages rely on dynamic allocation. Garbagecollection is a necessary part of the runtime system of acompiler for an OO language (C++ non-withstanding). Thisrequires runtime type description.ExampleTYPE Shape = CLASSx, y : REAL;METHOD draw(); BEGIN · · · ; END;METHOD move(X,Y:REAL); BEGIN x := x+X; END;END;TYPE Square = Shape CLASSside : REAL;METHOD draw(); BEGIN · · · ; END;END;TYPE Circle = Shape CLASSradius : REAL;METHOD draw(); BEGIN · · · ; END;METHOD area():REAL; BEGIN · · · END;END;// Example in Javaclass Shape {double x, y;void draw(); { · · · }void move(double X, double Y); {x = x+X; }}class Square extends Shape {double side;void draw(); { · · · }}class Circle extends Shape {double radius;void draw(); { · · · }double area(); { · · · }}(* Example in Modula-3 *)TYPE Shape = OBJECTx, y : REALMETHODSdraw() := DefaultDraw; move(X, Y : REAL):=Move;END;Square = Shape OBJECTside : REALMETHODSdraw() := SquareDrawEND;Circle = Shape OBJECTradius : REALMETHODSdraw() := CirlceDraw; area() := ComputeAreaEND;(* Example in Modula-3 (continued) *)PROCEDURE Move (Self : Shape; X, Y : REAL) =BEGIN · · · END Move;PROCEDURE DefaultDraw (Self : Shape) =BEGIN · · · END DefaultDraw;PROCEDURE SquareDraw (Self : Square) =BEGIN · · · END SquareDraw;PROCEDURE CircleDraw (Self : Circle) =BEGIN · · · END CircleDraw;PROCEDURE ComputeArea (Self : Circle) : REAL =BEGIN · · · END ComputeArea;Example in Oberon-2TYPE Shape = RECORD x, y : REAL END;Square = RECORD (Shape) side : REAL END;Circle = RECORD (Shape) radius : REAL END;PROCEDURE (Self : Shape) Move (X, Y : REAL) =BEGIN · · · END Move;PROCEDURE (Self : Shape) DefaultDraw () =BEGIN · · · END DefaultDraw;PROCEDURE (Self : Square) SquareDraw () =BEGIN · · · END SquareDraw;PROCEDURE (Self : Circle) CircleDraw () =BEGIN · · · END CircleDraw;PROCEDURE (Self : Circle) ComputeArea () : REAL =BEGIN · · · END ComputeArea;Record LayoutRecord LayoutSingle inheritance is implemented by concatenation, i.e. theinstance variables of class C are1the variables of C ’s supertype, followed by2the variables that C declares itself.RecordLayoutInheritanceHierarchyC1’s instance varsC1’s instance varsC2’s instance varsC1’s instance varsC2’s instance varsC3’s instance varsC1C2C3The offsets of the variables that C inherits from its supertypewill be the same as in the supertype itself.In this example, C3inherits from C2which inherits from C1.C3will have the fields from C1followed by the fields from C2followed by C3’s own fields. The order is significant.RecordLayoutInheritanceHierarchyC1’s instance varsC1’s instance varsC2’s instance varsC1’s instance varsC2’s instance varsC3’s instance varsC1C2C3TYPE Shape =CLASS x,y: REAL; END;TYPE Square = ShapeCLASS side:REAL; END;TYPE Circle = ShapeCLASS radius:REAL; END;VAR S:Shape;VAR Q:Square;VAR C:Circle;radius:REALShapeSquareCircleInheritanceHierarchySQCx:REALy:REALx:REALy:REALside:REALx:REALy:REALAn OO language compiler would translate the declarations inthe previous slide into something similar to this:TYPE Shape=POINTER TO RECORDx, y: REAL;END;TYPE Square=POINTER TO RECORDx, y: REAL;side:REAL;END;TYPE Circle=POINTER TO RECORDx, y: REAL;radius:REAL;END;VAR S:Shape; Q:Square; C:Circle;TemplatesClass TemplatesTo support late binding, runtime typechecking, etc, each class isrepresented by a template at runtime. Each template has pointersto the class’s methods and supertype.methodsCodefordraw:move:area:parent:Circle$TemplateShape$Templatedraw:move:parent:ROOTSquare$drawCircle$drawShape$drawCircle$areaShape$movedraw:move:parent:Square$TemplateSquare’s x,y fields are inherited from Shape. Their offsetsare the same as in Shape.TYPE $TemplateT=POINTER TO RECORDparent : $TemplateT;move : ADDRESS;draw : ADDRESS;END;TYPE Square=POINTER TO RECORD$template : $TemplateT;x, y : REAL;side : REAL;END;CONST Square$Template:$TemplateT =[ parent= ADDR(Shape$Template);move = ADDR(Shape$move);draw = ADDR(Square$draw); ];Each method is a procedures with an extra argument (SELF), apointer to the object through which the method was invoked.TYPE Shape = CLASSx, y : REAL;METHOD draw (); BEGIN · · · ;METHOD move (X, Y : REAL);BEGIN x := x+X; · · · END;END;⇓PROCEDURE Shape$move (SELF : Shape; X,Y:REAL);BEGINSELF^.x := SELF^.x + X;SELF^.y := SELF^.y + X;END;Method LookupMethod InvocationSending the message draw to Q:1Get Q’s template, T .2Get draw’s address at offset 4in T .3Jump to draw’s address, withQ as the first argument.draw:move:parent:Square$TemplateShape$Templatedraw:move:parent: NILx = 1y = 3side = 15$templateQSquare$drawShape$moveVAR Q : Square;BEGINQ := NEW (Square);Q.x := 1; Q.y := 3; Q.side := 15;Q.draw(); Q.move(20, 30);END;⇓BEGINQ :=