[PLT logo] Comp 311 Notes: Chapter 10

Method Invocation in Object-Oriented Languages

With the exception of sophisticated control operations like exceptions and continuation-based primitives (which we will discuss in the next lecture), we have discussed all of the fundamental language constructs in programming languages with one prominent omission: method invocation in object-oriented languages.

The technical term for object-oriented method invocation is dynamic dispatch. In the programming languages literature, the term dynamic binding is often used as a synonym for dynamic binding but this terminology is misleading and should be avoided. Dynamic binding is also used to refer to the binding mechanism using to support dynamic scope, the semantically obscene alternative to the lexical scoping rules used in programming languages like Scheme, ML, Haskell, Java, and even Algol-like languages such as Pascal to determine the meaning of free variables in procedures. There is no connection between dynamic dispatch and dynamic scope so the term dynamic binding creates confusion.

Before we dicuss the details of dynamic dispatch, let us quickly describe how object-oriented languages differ from procedural and functional languages. An object is a structure (like Scheme cons and empty,, C structs, or Pascal records) that includes code as well as data. The members of an object can include fields that hold (pointers to) executable code called methods as well as conventional data fields. Methods are procedures with one small but very important difference: a method takes the object in which it resides as a hidden argument. Within the body of the method, a special keyword such as this or self (depending on the particular object-oriented language) is used to refer to this hidden argument. The usual notation for invoking method m in object o is 

o.m(a1,...,an)
where a1,...an is the list of arguments to the method. In such an invocation, the object o is called the receiver of the invocation. The term method call is often used as a synonym for method invocation.

In most object-oriented languages, objects are defined by instantiating classes which are templates for creating objects. In such languages, a program simply consistes of a set of class definitions.

To accommodate conventional procedural computation (which is occasionally necessary), class-based object-oriented languages also support the declaration of static (sometimes called class) members. A static field f in a class C is simply a global variable with the name C.f: there is one such field in the entire program rather than one per object of class C. Similarly, a static method m in a class C is simply a procedure with the name C.m: such a method does not take a hidden argument this because it is not associated with a specific object.

Inheritance

Class-based object-oriented languages support a special form of code-factoring called inheritance which eliminates the ugly parameterization that appears in programs that are factored using lambda-abstraction. Every class C has a designated superclass S that it extends. All of the dynamic (non-static) members of S are automatically declared as members of the class C. A special built-in class (called Object in Java) is the top class in this class hierarchy; this class includes methods like equality that are defined for all objects.

A class C can redefine a method m inherited from its superclass S, replacing the inherited method definition by the definition provided in C. This process is called method overriding and has profound consequences for the behavior of method calls on an object of class C. If other (non-overridden) methods inherited by C from S invoke the overriden method m they execute the method definition for m in C rather than the definition for m in S because m is retrieved from the receiver object which is an instance of class C, not class S.

Most class-based object-oriented languages allow a class C that overrides a method m to invoke the overriden method definition using special syntax for the "receiver" such as 

super.m(...)

Implementation

In class-based object-oriented languages, method code is not actually stored in objects because all objects of the same class share exactly the same method code. It would be extremely wasteful of memory space to copy that code in every object of a class. Instead, the repeated features of all objects in a class are "factored out" and stored in a special class object associated with the entire class. Every object of class C contains a hidden pointer in the object header to the class object. The class object for a class C contains: To execute a method invocation 
o.m(a1,...,an)
where o is an object of class C and 
a1,...an
is are object values, the implementation (interpreter or compiled code) must search the method table of C to find a method that matches the signature of m. In Java, the signature of m includes the argument types of m. In untyped OO languages like Smalltalk, it only includes the name. If the a matching method definition is not found in the method table of C, the search process is recursively invoked on the superclass of C.

When the matching definition is found, the implementation passes a parameter list consisting of the object o (the hidden parameter) followed by the the proper arguments a1, ..., an according to the procedure call protocol in the machine. (In Java, the parameters are passed on the stack.)

To execute a field access 

o.f
where o is an object of class C and f is a field name, the implementation searches for the specified field of o. In class-based object-oriented language like Java, the field extraction process can be performed by simply loading the data from the appropriate offset (which is fixed by the definition of the class C). In class-based object-oriented languages, fields cannot be dynamically added to objects during program execution; the class definition completely determines the form of an object of that class.

The invocation of static methods and accessing of static fields is straightforward because static methods are procedures and static fields are globbal variables. The language implementation (interpreter or compiler) knows the addresses of all procedures and global variables. (In Java where classes are dynamically loaded, the first access to static method or field must perform a simple search of the static method table for the class containing the method or field. But the retrieved address can then be stored in a known location in a local table for the calling class since it will not change for the duration of program execution.)

Optimization

Since searching for the invoked method is slow, we would like to eliminate this overhead. In Java, the static type system provides all of the information required to find the address of the matching method by indexing into the method table. To support this optimization the method table must be expanded to include all the dynamic (non-static) methods declared in class C or its superclasses. The methods appear in the table in the order in which they appear in the class hierarchy starting from the root class (Object} in Java); within each class the methods appear in lexical order.

In such a representation, a method m that is defined for all instances of class C, must occur in a fixed position in the method table for C and all of its subclasses. Hence, the index in the method table of method m for any object of type C (an instance of C or one of its subclasses) must be the same. The language implementation (interpreter or compiler) can simply load the appropriate entry from the table containing the address of the code to be executed.

cork@cs.rice.edu