The Procedure Abstraction Part IV: Run-time Structures for OOLsWhat about Object-Oriented Languages?Object-Oriented LanguagesOOLs & the Procedure AbstractionImplementing Object-Oriented LanguagesJava Name SpaceJava Symbol TablesSlide 8Slide 9OOL Storage Layout (Java)Dealing with Single InheritanceSlide 12Slide 13Single Inheritance and Dynamic DispatchThe Inheritance HierarchySlide 16Multiple InheritanceMultiple Inheritance ExampleSlide 19Casting with Multiple InheritanceMultiple Inheritance (Example)PowerPoint PresentationMultiple Inheritance with Offsets (Example)The Procedure AbstractionPart IV: Run-time Structures for OOLsCopyright 2003, Keith D. Cooper, Ken Kennedy & Linda Torczon, all rights reserved.Students enrolled in Comp 412 at Rice University have explicit permission to make copies of these materials for their personal use.What about Object-Oriented Languages?What is an OOL?•A language that supports “object-oriented programming”How does an OOL differ from an ALL? (ALGOL-Like Language)•Data-centric name scopes for values & functions•Dynamic resolution of names to their implementationsHow do we compile OOLs ?•Need to define what we mean by an OOL•Term is almost meaningless today — Smalltalk to C++ to Java •We will focus on Java and C++Object-Oriented LanguagesAn object is an abstract data type that encapsulates data, operations and internal state behind a simple, consistent interface.Elaborating the concepts:•Each object needs local storage for its attributesAttributes are static (lifetime of object ) Access is through methods•Some methods are public, others are privateMore complex linkage convention; locating them is complex•Object’s internal state leads to complex behaviorDataCodexDataCodeyDataCodezThe Concept:OOLs & the Procedure AbstractionWhat is the shape of an OOL’s name space?•Local storage in objects (beyond attributes)•Some storage associated with methodsLocal values inside a methodStatic values with lifetimes beyond methods•Methods shared among multiple objects Classes•Objects with the same state are grouped into a classSame attributes, instance variables, & methodsClass variables are static, shared among all objects of same class•Allows programmer to write it down once•Allows code reuse at both source & implementation levelIn some OOLs, everything is an object.In others, variables co-exist with objects & inside objects.Implementing Object-Oriented LanguagesSo, what can an executing method see?•The object’s own attributes & private variablesSmalltalk terminology: instance variables•The attributes & private variables of the class that defines it Smalltalk terminology: class variables•Any object defined in the global name space (or scope)Objects may contain other objects (!?!)An executing method might reference any of theseA final twist:•Most OOLs support a hierarchical notion of inheritance•Some OOLs support multiple inheritance More than one path through the inheritance hierarchyJava Name SpaceGiven a method M for an object O in a class C, M can see:•Local variables declared within M (lexical scoping)•All instance variables and class variables of the class C•All public and protected variables of any superclass of C•Any classes defined in the same package or in a package importedpublic class variables and instance variables of imported classespackage class and instance variables in the package containing C•Class declarations can be nested!These member declarations hide outer class declarations of the same name (lexical scoping)Accessibility: public, private, protected, packageJava Symbol TablesTo compile code in method M for an object O within a class C, the compiler needs:•Lexically scoped symbol table for block and class nestingJust like ALL — inner declarations hide outer declarations•Chain of symbol tables for inheritanceNeed mechanism to find the class and instance variables of all superclasses•Symbol tables for all global classes (package scope)Entries for all members with visibilityNeed to construct symbol table for imported packagesJava Symbol TablesTo find the address associated with a variable reference in method M for an object O within a class C, the compiler must•For an unqualified use (i.e., x):Search the scoped symbol table for the current methodSearch the chain of symbol tables for the class hierarchySearch global symbol table (current package and imported)Look for class (or interface)In each case check visibility attribute of x•For a qualified use (i.e.: Q.x):Search stack-structured global symbol table for class nesting for QCheck visibility attribute of xImplementing Object-Oriented LanguagesTwo critical issues in OOL implementation:•Object representation•Mapping a method invocation name to a method implementationThese both are intimately related to the OOL’s name spaceObject Representation•Static, private storage for attributes & instance variablesHeap allocate object records or “instances”•Need consistent, fast access Known, constant offsets•Provision for initialization in NEWfee() fie() foe() countx0 4 8 12OOL Storage Layout (Java)Class variables•Static class storage accessible by global name (class C)Accessible via linkage symbol &_CNested classes are handled like blocks in ALLsMethod code put at fixed offset from start of class areaObject Representation•Object storage is heap allocatedFields at fixed offsets from start of object storage•MethodsCode for methods is stored with the classMethods accessed by offsets from code vector Allows method references inlineMethod local storage in object (no calls) or on stack“leaf” routine in an ALLfee() fie() foe() countx0 4 8 12Dealing with Single Inheritance•Use prefixing of storageClass Point {int x, y;}Class ColorPoint extends Point {Color c;}xyxycselfDoes casting work properly?selfImplementing Object-Oriented LanguagesMapping message names to methods•Static mapping, known at compile-time (Java, C++)Fixed offsets & indirect calls•Dynamic mapping, unknown until run-time (Smalltalk)Look up name in class’ table of methodsWant uniform placement of standard services (NEW, PRINT, …)This is really a data-structures problem•Build a table of function pointers•Use a standard invocation sequenceImplementing Object-Oriented