Object-oriented programming: inheritance, dynamic binding and vtables

Object-oriented programming (OOP) is a combination of three ideas: the abstract data type (last week), inheritance and dynamic binding. The exam counterpart of this page is two kinds of questions: “Which method runs, what is printed?” (override, overload, hiding, constructor order) and “How is dynamic binding implemented?” (vtable). For the first kind, knowing the rule set is enough.

Golden rules:

1. An overridden instance method is chosen according to the object’s actual class.
2. Overload selection is done at compile time, according to the declared type of the argument.
3. Fields and static methods are not dynamically bound; the type of the variable is used.
4. The superclass’s constructor runs first.
5. vtable: copy the superclass’s, change the overridden one, add the new one at the end.

Why inheritance?

ADTs can be reused but almost always a small change is needed; copying and modifying the code is a maintenance nightmare. Inheritance derives a new class from an existing class (the superclass, parent): the subclass (derived) takes the fields and methods of the superclass, adds new ones, and overrides some.

Terms:

• Class: an ADT. Object: an instance of the class.
• Method: a subprogram defined in a class. Message: sending a method call to an object.
• Instance variable: each object’s own copy. Class variable (Java static): one per class.
• If an object of the subclass can be used wherever the superclass is expected, the subclass is a subtype. In Java public inheritance provides this.

The disadvantage of inheritance: it creates dependency between classes. A change in the superclass can affect all subclasses.

Dynamic binding

A reference of the superclass type can point to an object of one of the subclasses. If the called method is overridden, which version runs? The one of the object’s actual class. This decision is made at run time: dynamic binding (polymorphism).

Animal a = new Dog();
System.out.println(a.speak() + " " + a.name + " " + a.kind() + " " + a.intro());

Woof animal Animal I say Woof

The benefit: the code for (Animal an : zoo) an.speak(); works unchanged even with a Cat class added in the future.

When override and overload mix

class P { void m(Object o) {...P.Object} void m(String s) {...P.String} }
class Q extends P { @Override void m(Object o) {...Q.Object} }
P p = new Q(); Object o = "text";
p.m(o); p.m("text");

Q.Object P.String

Recipe: (1) compile time: the type of p is P, and one of the signatures in P is chosen according to the declared type of the argument. o is of type Object, so m(Object) is chosen even if there is a String inside. (2) run time: the version of the chosen signature in the object’s class (Q) runs.

Constructor order

class A { A() { System.out.print("A "); show(); } void show() { ... "A.show" } }
class B extends A { int v = 7; B() { super(); System.out.print("B "); }
                    @Override void show() { ... "B.show v=" + v } }
new B();

A B.show v=0 B

The superclass constructor runs first, the subclass’s field initializers after it. The show() in A’s constructor is dynamically bound and sees the not-yet-initialized v (0).

super and private

X z = new Z();      // Z.hi → "Z+" + super.hi() → Y.hi → "Y+" + super.hi() → X.hi
System.out.println(z.hi());
System.out.println(new Derived().call());   // private who() is not overridden

Z+Y+X
Base

super.m() always goes to the version of the direct superclass. private methods are not inherited; a method with the same name in the subclass is a separate method.

Language design questions

In C++, if an object on the stack is assigned by value to a variable of the superclass type, the subclass’s fields are cut off (object slicing). In Java, since all objects are on the heap and accessed by reference, this problem doesn’t exist.

Abstract classes and multiple inheritance

abstract class Shape { abstract double area(); }
Shape s = new Shape();     // error: Shape is abstract; cannot be instantiated

In multiple inheritance, if two superclasses bring two methods with the same signature (the diamond problem), which is chosen? C++ requires the programmer to qualify with Walker::move. Java does not allow multiple inheritance for classes; if default methods in interfaces clash, the compiler requires an override:

interface Walker { default String move() { return "walk"; } }
interface Swimmer { default String move() { return "swim"; } }
class Duck implements Walker, Swimmer {
    public String move() { return Walker.super.move() + "&" + Swimmer.super.move(); }
}

walk&swim

Implementation: CIR and vtable

The class instance record (CIR) is the structure of an object in memory; it is determined at compile time like a record. A subclass’s CIR copies the superclass’s CIR and adds its own fields at the end. This way the superclass’s fields are at the same offset in every subclass object.

For dynamically bound methods, every class has a virtual method table (vtable): the address of the code for each dynamically bound method in the class. Each CIR carries a pointer to its class’s vtable.

class Shape  { area(); draw(); name(); }
class Circle extends Shape  { override area(); new radius(); }
class Ring   extends Circle { override draw(); override area(); }

slot    Shape vtable    Circle vtable    Ring vtable
0       Shape.area      Circle.area      Ring.area
1       Shape.draw      Shape.draw       Ring.draw
2       Shape.name      Shape.name       Shape.name
3       -               Circle.radius    Circle.radius

for (Shape s : new Shape[]{ new Shape(), new Circle(), new Ring() })
    System.out.println(s.area() + " " + s.draw() + " " + s.name());

Shape.area Shape.draw Shape.name
Circle.area Shape.draw Shape.name
Ring.area Ring.draw Shape.name

The compiler translates the call s.area() into code that says “go to the address in slot 0 of the object’s vtable”. Whatever the class, slot 0 is always area; at run time only which table is read changes. The cost: one indirection on every call. Statically bound methods (C++ non-virtual, Java private/final) don’t pay this cost and are not in the vtable.

In multiple inheritance things get complicated: the object has a separate vtable pointer and part for each superclass.

Common mistakes

class Animal {
    String name = "animal";
    String speak() { return "..."; }
    static String kind() { return "Animal"; }
    String intro() { return "I say " + speak(); }
}
class Dog extends Animal {
    String name = "dog";
    @Override String speak() { return "Woof"; }
    static String kind() { return "Dog"; }
}
// in main:
Animal a = new Dog();
System.out.println(a.speak() + " " + a.name + " " + a.kind() + " " + a.intro());

class A { A() { System.out.print("A "); show(); }
          void show() { System.out.print("A.show "); } }
class B extends A { int v = 7;
          B() { super(); System.out.print("B "); }
          @Override void show() { System.out.print("B.show v=" + v + " "); } }
// in main:
new B();

class P { void m(Object o) { System.out.print("P.Object "); }
          void m(String s) { System.out.print("P.String "); } }
class Q extends P { @Override void m(Object o) { System.out.print("Q.Object "); } }
// in main:
P p = new Q();
Object o = "text";
p.m(o);
p.m("text");

class Shape  { area(); draw(); name(); }
class Circle extends Shape  { override area(); new radius(); }
class Ring   extends Circle { override draw(); override area(); }

class Base { private String who() { return "Base"; }
             String call() { return who(); } }
class Derived extends Base { private String who() { return "Derived"; } }
// in main:
System.out.println(new Derived().call());

class X { String hi() { return "X"; } }
class Y extends X { @Override String hi() { return "Y+" + super.hi(); } }
class Z extends Y { @Override String hi() { return "Z+" + super.hi(); } }
// in main:
X z = new Z();
System.out.println(z.hi());

abstract class Shape { abstract double area(); }
// in main:
Shape s = new Shape();

Animal[] zoo = { new Animal(), new Dog(), new Dog() };
int woofs = 0;
for (Animal an : zoo) if (an.speak().equals("Woof")) woofs++;
System.out.println(woofs + " " + (zoo[1] instanceof Animal) + " " + (zoo[0] instanceof Dog));