The Mechanics of OO Code

It is brash of me to describe the rationale of OO rules for polymorphism and inheritance. I had nothing to do with their development and indeed I am not an expert there.

I find the various language rules, enforced mainly by compilers, somewhat arbitrary and capricious and therefore hard to remember and without a grasp of such rules one cannot use OO languages well, nor can one even reliably reason about their security properties.

Some say that OO is supposed to insulate the programmer from mechanism and thus ease the conceptual load. Being a reductionist I find mechanisms easier to understand than the consequent rules however and the rules stem rather directly from the mechanisms. Learning the mechanism has helped me and may help others learn and perhaps even appreciate the rules. I will talk exclusively about Java but C++ is very similar.

A little History

You can easily skip this section. I like to reminisce.

With the introduction of the IBM/360 in the early 60’s IBM described the File Control Block (FCB). Each time a program opened a file an FCB was created in the user’s address space. FCBs had a common layout and code that needed to use a file could consult its FCB and thus be largely insulated from the amazing variety of forms that 360 files took. At a fixed well known offset within the FCB (the offsets haven’t changed in 35 years) you could find the address of the code to read the next record for a given file. The construction of the FCB was dynamic and might require many overlays (blocks of code) from the disk and take many(!) seconds. Access methods would be contingently loaded too at this time. This process would depend on intended use and the format of the file as provided by:

These three sources of information would be merged and reconciled according to obscure published rules.

A little class theory

When the Java programmer says class X extends Y then class X has thereby been defined to be a new direct subclass of class Y. The subclasses of class X are the direct subclasses of X together with the their subclasses. (Note the recursion.) If class X is a direct subclass of class Y then Y is the direct superclass of X. Except for Object every class has just one direct superclass. The superclasses of X are those classes with X as a subclass.

The compiler builds the tree of classes with class Object at the root and other classes are immediately inferior to their direct superclass.

A call site is the machine code that the compiler emits when it encounters a method invocation in the source. The compiler is able to assign a compile time class to each variable, parameter or subexpression that designates an object reference. The compiler is thus able to determine a compile time class for the object to be invoked at the call site knowing that the class of the real object will be a subclass of the compile time class. The mechanisms I refer to are used by the compiled code for a call site that invokes a method.

For each non-abstract class the compiler emits a “v-table” with a code address for each method declared for that class. During compilation the compiler maintains a mapping between method spellings for a class and offsets in the table for that class. The v-table is processed normally by the loader, and read by the call site code. For each class there is also a data layout which each instance of the class will use to keep its instance variable values.

If X is an direct subclass of Y then Y’s v-table will be formatted as an initial portion of X’s v-table. (The v-table for the subclass is bigger!) All of the code addresses in X’s table will be the same as Y’s table except for those methods where X overrides Y’s methods. In fact Y can use X’s table if there is no overriding.

Object Representation

Each class uses a consistent data layout for each of its instances. Within this layout is the address of the v-table for the class. Each code fragment located by the v-table knows (was compiled in light of) the data layout of this class. The code fragment also knows the layout of the v-table.

Some of these code fragments serve both for a class and its superclass etc. This is possible because superclass data layout is a proper subset of the class data layout.

Abstract classes have no instances and that is why no v-table is needed. Abstract classes have one or more methods for which there is no code and thus no code address for a v-table. The mapping from method signature to v-table offset is, however fixed even for abstract classes. The programmer causes this by declaring an abstract method with no implementation.

Invoking an Object

With the above background we can imagine the construction of the call site. That code acquires or produces an object reference, OR, in the form of the address of an instance of the object’s data layout. The called code that implements the method (within the object) will need to access values that are local to its instance. The call site code will: It is significant that the call site needs no conditionality on the real class of the invoked object. It does appear to have four sequentially dependent memory references counting both fetching OR and fetching the first instruction of the method. Compilers may be able to overlap these fetches with other useful work. Some of the fetches may also be done at compile time when the compiler knows that there are no overridden classes and can thus embed the method code address in the call site code. This may be facilitated for final methods. There are other possible optimizations as well.

Why the Rules

Many of the rules immediately follow from the implementation plan. Here are some examples:
A variable (or parameter) object reference can take a reference to an object which is a subclass of the declared variable but not a super class. This is a limitation imposed at compile time on both assignment statements and arguments passed to parameters.
This is to insure that code that invokes the referenced object will always branch to a valid method. i.e. that the referenced v-table will have a valid code address entry. Indeed the code there will expect the shape of the arguments. i.e. that the code branched to will be of the correct signature.
The language provides the final for methods.
This is so that the compiler can sometimes know at compile time the address of the method and thus produce faster code. The same assurance is available to the programmer of the method who knows that an extender of his class can not subvert the meaning of the final method.

Disadvantages

Personally I find it disturbing that methods are not final by default. I think that this is prone to security blunders. The implementor of a non final class with non final methods has granted any programmer with access to his class the ability to change the meaning of any of the “subroutines”. The overridable method is a powerful tool that will be reliable only when the programmer of the original class has given careful thought to the consequences. I do not recall seeing documentation for a Java class that provides complete information on the internal consequences of overriding a method. The internal consequences are those resulting when the super class code calls an overridden class.

I have talked with an experienced user of SmallTalk, C++ and Java. He likes the default and looks at the programming process as the process of collecting code for reuse. Overriding can be used to form new unanticipated function but typically only by reading the code of the class being extended. The KeyKos paradigm is that programming produces services, not code. Code is shared almost exclusively by writing code to define generally useful objects. Indeed one never asks or typically knows what language a useful object is written in.

Alternative Plans

The compilation technique above determines much of the flavor of languages such as Java and C++. That v-tables are shared among instances of a class means that they cannot change at run-time. I gather that the Self language provides a v-table for each instance.