Polymorphism

Tip

Despite this article being quite heavy with information, I will say that it was quite under-tested. When I was taking the class, this was only used in an assignment and was tested only theoretically. I never had to use the double indirect jump.

Polymorphism is the idea that we can treat values of different concrete types in the same way through an abstracted interface. The classic example is of animals and speaking, where you have:

Animal{
	void speak();
}
 
Cat extends Animal{
	void speak(){
		"Meow"
	}
}
 
Dog extends Animal{
	void speak(){
		"Woof"
	}
}

Both cat and dog can speak(), but they do different things. This is part of CPSC 210’s learning goals, but in CPSC 213 we learn polymorphism in relation to C, and the lower level methods of implementing it.

Polymorphic Dispatch

In 210 for example, when you had an abstract type A that had a definition for a function foo(), implemented by two sub-types B and C, how would it determine what function to call? This is effectively what polymorphic dispatch is, when the compiler cannot hardcode target address in a procedure call, since the concrete (actual) type of the object is not known at compile time. The address of the function to call is therefore retrieved from memory at runtime.

Implementation with a Class Jump Table

In C, we do not have the luxury of abstractions, so we have to implement the polymorphic dispatch ourselves.

To do so, we need to implement a few things. First, we need to describe the general shape of the class/type we want to implement. What fields and methods it has in other words. For this, we will represent the class with a static struct object that contains the data and methods of the class, much like a class in Java.

struct B {
	int x;
};

Next, we want to add the actual dynamic dispatch of the class. So, if it we wanted to call b.foo(), we call the intended function of B’s actual type. To do so, we will include the functions of B only indirectly into the struct, using a table containing the type’s methods. So in our example, the following:

struct B_class{
	void (*foo)(struct B *self); //function pointer to a function called foo
	               //that returns void and takes no args
} A_class_table = {foo}; 
// this gives the struct the type alias A_class_table
// and binds the function pointer foo to an actual implementation of foo
// (foo is a function pointer here)

Note that foo needs to take in a parameter of the object class it is intended to work on, otherwise it will not have access to B’s fields inside of its scope, and won’t work as a proper method.

We would then add that table to our original struct, using a pointer to the class table:

struct B {
	struct B_class* class;
	int x;
};

This is generally called a virtual method table, or a vtable.

We can then implement other things related to the class, like a constructor:

struct B *new_B(int i) {
	struct B *this = malloc(sizeof(*this)); //malloc an instance of B
	this->class = &B_class_table; //bind it's class to the table we defined previously
	//optionally implement a separate constructor that binds i to x, but we can also just put it here
	this->x = i;
};

We can then call b.foo() with the following:

struct B *b = new_B(1);
b->class->foo(b);

To extend the class, basically have inheritance, we would define another struct table of a jump table, like so:

struct C_class {
	void (*foo) (void*); //the void* is the this/itself argument
	void (*bar) (void*);
}

The table must be a superset of of its parent’s table, so that it fits with the OOP expectations of polymorphic dispatch, where if you call foo() for an object of apparent type B and actual type C, you would call c.foo(), and you can’t call c.bar() from an object of actual type B.

Polymorphic Dispatch in Assembly

We can already load the address of the struct with an offset to a register, using an offset load instruction, and then jump to the address of that method with a jump immediate, and that’s effectively dispatch.

However, we can now do so more efficiently with the double indirect jump.