The core principles behind object-oriented programming are encapsulation, data-hiding, polymorphism (dynamic-binding), and inheritance. Polymorphism is the most important in my opinion and is often not truly understood by students. This lab is designed to solidify your understanding by showing you how polymorphism may be implemented using C, a non-objected language. We will mimic the behavior of cfront, the original C++ to C translator (simplifying by ignoring multiple inheritance).

Problem definition

First, recall the desired behavior: polymorphism is like a message-send and the TARGET decides how to answer the message. The type of the object reference you have is totally irrelevant! In fact, there are languages like SmallTalk that are not even statically typed.

We must agree on the behavior of the following "trick" question. It always traps students because, with r.method() , they get caught up thinking about the type of r not the actual type of the object pointed at by r . Here are two simple classes and two calls to the same message:

class Human {
  String name;
  ...
  public String getName() {
    return name;
  }
  public String getInfo() {
    return getName();
  }
}

class Student extends Human {
  String ID;
  ...
  public String getName() {
    return name+":"+ID;
  }
}
...
Student s = new Student("Madonna","111-22-3333");
Human h = s;

1. What does s.getName() return? "Madonna:111-22-3333"
2. What does h.getName() return? "Madonna:111-22-3333"
3. What does h.getInfo() return? "Madonna:111-22-3333"

Why do they return the same thing? Because the same message is sent to the same object, in this case Student . The types of the object pointers of s and h are irrelevant. Those types only narrow the range of possible types--they don't identify the types.

The message send works like this for h.getInfo() :

1. h points at an object of type Student . Ask student to look up method getInfo() . It finds an inherited method from Human , which it executes. Note: you are executing code from Human . You are not somehow now in Human 's scope nor did you become a Human . You are merely executing code inherited from Human as if the code was written in Student .
2. Method getInfo() sends the message getName() to itself. It's type is Student not Human so it must execute Student 's getName() method. This is the crucial step. The method call is just a function call if it works in any other way.

The whole point of polymorphism: code can work on more than one type:

class Vehicle {...}
class Truck extends Vehicle {...}
class Car extends Vehicle {...}
...
static void foo(Vehicle v) {
    v.start(); // works for any kind of Vehicle
}

Important: v.start() will continue to work in the future when we add more kinds-of Vehicle s because it is not the call site, but the target (which we might add later) that decides how to answer.

Programming style without polymorphism

In a language like C with only function calls, you know precisely what function you are calling just by the name whereas it's ambiguous at compile-time in an object-oriented language. How do you write code to handle multiple types in C? Well, the hallmark of non-OO code is a bunch of switch es at call sites to handle multiple types (which of course break the instant you add a new type--you have to go change every switch ).

Examine the following struct definitions:

struct Object {
  int type;
};

struct Vehicle {
  int type; /* "inherits" from object */
  int color;
};

struct Car {
  int type;
  int color; /* "inherits" from Vehicle */
  int doors;
};

struct Truck {
  int type;
  int color;
  int payload;
};

To create a Car instance, you need to allocate the space and then manually invoke the "constructor" (a method I have implemented):

struct Car *car = (struct Car *)calloc(1, sizeof(struct Car));
Car_ctor(car);  /* init */

All methods that operate on objects, instance methods, take a this parameter that indicates what object to operate on. Of course in an OO language this is done behind the scenes automatically. In C, though, the passing of the instance pointer must be explicit:

int Vehicle_getColor(struct Vehicle *this) {
  printf("Vehicle_getColor\n");
  return this->color;
}

When I want to invoke method start on either a car or a truck, I need something like this that switches on the type of the incoming object:

int invoke_start(struct Vehicle *vehicle) {
  /* invoke method start(); need a switch since two implementations */
  switch (vehicle->type) {
  case CAR : Car_start((struct Car *)vehicle); break;
  case TRUCK : Truck_start((struct Truck *)vehicle); break;
  }
}

Please take a look at the C-with-switches version the Java code in our goal below. This code is easy to understand, but extremely inflexible.

Implementing polymorphism

To gain polymorphism's flexibility, we're going to have to do some atypical C programming. We're going to have to do by hand what a C++ to C translator would normally do for you.

The goal

Our goal is to essentially implement the following simple Java code in C (you will find solution poly.c, poly.inc.c and 2 include files as attachments):

class Vehicle {
    int color = 0;
    public void start() { /* ... */ }
    public int getColor() { return this.color; }
}

class Car extends Vehicle {
    int doors = 0;
    public void start() { /* ... */ }
    public void setDoors(int doors) { this.doors = doors; }
}

class Truck extends Vehicle {
    int payload = 0;
    public void start() { /* ... */ }
    public void setPayload(int payload) { this.payload = payload; }
}

public class OO {
    public static void main(String[] args) {
	Car car = new Car();
	Truck truck = new Truck();

	int color = car.getColor();
	car.getColor();

	Vehicle vehicle = null;
	vehicle = car;   // note: no cast!
	vehicle.start(); // calls Car.start()
	car.start();     // calls Car.start()
	vehicle = truck;
	vehicle.start(); // calls Truck.start()
    }
}

We need a struct for each object and, instead of having the type value in each struct, an array of function pointers will be used. For every virtual method there will be an entry in the function pointer table. This table is called the vtable. The entire structure is organized as follows:

You will notice that there is no relationship or pointers between the struct instances. Unless an application needs run time type information there is no point in wasting memory for each object to have an associated class definition object.

Some unusual, but necessary C constructs

Before you try to solve this problem, I need to either refresh your memory or introduce you to the idea of a function pointer in C; see How to read C declarations.

Implementing vtables

The solution vtable.c is a translation of the Java objects from above into C struct declarations, appropriate virtual tables ( vtables), and invocations of a few methods using the vtables rather than via a switch statement.

The output we get is the following:

BUILD
Object_ctor
Vehicle_ctor
Car_ctor
Object_ctor
Vehicle_ctor
Truck_ctor

MESSAGE SENDS
Vehicle_getColor
Car_start
Car_start
Truck_start

Define objects

We need to define Object , Vehicle , Car , and Truck . Each object must have the appropriate data fields as defined in both the Java and switch-version of the C code. You do not need nor want the type field anymore. Instead, you replace it (at struct offset 0--the first field) with a vtable "pointer to an array of pointers to functions returning int."

Define vtables

Ok, so you have the "objects" defined. Now you need to do the actual polymorphism implementation: the vtable.

1. Define tables Object_vtable , Vehicle_vtable , Car_vtable , and Truck_vtable . Note that since there are no defined methods on our Object , that vtable will be empty. You can just put a null pointer in the table.
2. Modify the various xxx_ctor() methods so that they set the vtable pointer of the appropriate object.
3. Set up #define constants to identify offsets within your vtables. For example, the start() method will always be first in Car_vtable and Truck_vtable since it is the first (and only) method in Vehicle :

   #define METHOD_START		0

The size of a class' vtable is the maximum number of methods in its interface.

Invoke methods

You now have some C structures set up to properly simulate polymorphism. You now need to fill in the blanks remaining in the vtable.c main() function:

struct Vehicle *vehicle;
  vehicle = (struct Vehicle *)car;

  // simulate: int color = vehicle.getColor()
  int color = ...;

  ...; // vehicle.start()
  ...; // car.start()
  ...; // truck.start()

Note that vehicle points at a car so vehicle.getColor() but it doesn't matter, it should still pick up the inherited method and execute Vehicle_getColor() . The next method calls invoke Car_start() , Car_start() , and Truck_start() as a result of the polymorphism. You will not call these methods directly.

The pattern for invoking a method is:

(*(*obj->vtable)[method-index])(obj);

which says, get me the appropriate function pointer and dereference it to actually invoke the method; pass the object in as the this pointer.

This pattern starts by asking for the vtable pointer field of your object obj : obj->vtable . Since it is a pointer to array of stuff,you need to dereference it before you can treat it like an array: (*obj->vtable) . Now, get the method pointer at the right index: ((*obj->vtable)[method-index] . Now you have a pointer to a function; to call it, just dereference the whole mess, hence, the last pointer dereference.