I’ve promised to write a blog post about the DIY polymorphic classes implementation in Xanthe, the experimental game I once wrote for bare-metal X86. But first, I decided to write a precursor post that explains how polymorphism and inheritance work in the first place.

This post uses D code, but if you understand what’s in here, you’ll have an idea how inheritance and polymorphism work in most languages. In particular, C++ works in the same way, except that C++ supports multiple inheritance, which makes things a bit more complicated. Higher-level, interpreted languages like Python don’t have to worry about low-level memory layout, but the fundamental ideas still apply (e.g., Python uses hash tables to do the job of vtables).

Remind Me, What are Inheritance and Polymorphism Again?

Xanthe is an arcade-style shooting game with many entities moving around the screen at once. All entities are instances of a class called RigidBody, which has data members for X/Y coordinates, velocity, etc, and represents generic blobs that obey simple physics. But the game is full of more interesting things like enemies, obstacles and missiles. Because each specialised entity is a RigidBody, they’re implemented using subclasses that inherit all the properties of the RigidBody base class.

Most of the code doesn’t care about any of that and just handles entities as generic RigidBody instances. But missiles still behave differently from enemies because they have tweaks to certain parameters and method implementations. This design pattern is called polymorphism, and has first-class support in object-oriented programming (OOP) languages.

How does it work? A lot of the magic is in one simple trick: function pointers.

Function Pointers

Just like a regular pointer is a variable that points to another piece of data, a function pointer is a variable that points to a function. (In languages like Python where all variables are references, you can just use a normal variable to reference a function.) Both functions and data are just things in memory, so there really isn’t any difference between these kinds of pointer at the low level: they both simply contain the address of something in memory.

Here’s a silly example:

import io = std.stdio;

// "void function()" is the type of a function pointer
// that takes no arguments and returns nothing.
// We'll call that a "Greeter" purely for convenience.
alias Greeter = void function();

// Here's one way to greet someone
void sayHi()
{
    io.writeln("Hi!");
}

// Here's another
void sayYo()
{
    io.writeln("Yo!");
}

// This function chooses a Greeter implementation at random
// and returns it as a function pointer
Greeter makeGreeter()
{
    import std.random : choice;
    // The & operator takes the address of the function so
    // it can be stored in a pointer
    return choice([&sayHi, &sayYo]);
}

void main()
{
    // Who knows which greeter implementation we'll get?
    auto greeter = makeGreeter();

    // Let's find out!
    // This executes whatever function "greeter" points to.
    greeter();
}

What’s the point? (Excuse the pun.) It lets us turn logic into data, which is a really powerful idea. Imagine that instead of silly greeters, we had implementations of useful operations like “save data” and “run simulation”. We could store pointers to those implementations in a lookup table, with command names like “save” and “run” as keys. If you write a program that reads commands from a file or standard input, looks them up in the table, and runs the implementations, you have a simple interpreter for a command language. Because this is just data, you can even make a plugin system by loading new commands from shared libraries.

Getting Classier

Function pointers (by themselves) can’t hold state (unlike closures or delegates in D) or have multiple actions. This simplicity isn’t necessarily a bad thing, but for the sake of an example, let’s say we decide to use polymorphic classes instead. Since this post is about how things work inside, let’s reimplement the same polymorphic class functionality using plain old structs.

We’ll make that simple command interpreter, but with classes. To keep the code as simple as possible for demo purposes, the commands won’t take any arguments. First off, here’s the result in action:


$ ./interpreter
> run
Running simulation...
Done
> save
Saved data to save_file00.dat
> run
Running simulation...
Done
> save
Saved data to save_file01.dat
> save
Saved data to save_file02.dat
> exit
Bye!

We’ll have a base Command “class”, and implementations of various commands, like Save, that derive from it using a neat trick: Each derived “class” will contain a Command instance as its first member. If you imagine the raw member data of an instance laid out in memory, that means the start of a command like Save looks exactly like a Command. Because a pointer to a struct points to the beginning of the struct, a pointer to a (derived) Save instance is effectively a pointer to a (base) Command instance, and we can pass a pointer to a Save instance to code that expects a Command instance. This is how the “subclasses can be used anywhere the base class can” magic works in compiled OOP languages (at least for single inheritance). If we have a chain of inheritance, we simply keep nesting the memory layouts like Russian dolls.

Memory layout of singly inherited class

The Command will have a virtual function execute() that’s overridden by derived classes. Of course, this is implemented using a function pointer, which we’ll store in the Command base class. When you call a method on a class instance, it shouldn’t affect other instances of the same class that happen to exist, so somehow the function that implements the method needs to know which instance it’s being called on. The solution is to do the obvious: when we call execute(), we’ll call the function pointer, also passing it a pointer to the instance as a normal function argument. The code needs to typecast this instance pointer back and forth between the base class and subclass types, but this is purely a matter of type system bookkeeping — there’s no change to the pointer at the binary level. This pointer-to-instance is also how method calls work in normal OOP. Most languages, including D, make it hidden (but accessible using a keyword like this), but Python for example makes it explicit (idiomatically using a method argument called self).

Here’s the code:

import io = std.stdio;
import std.string;

// This is the base "class"
struct Command
{
    // Normal method call
    // getName() actually has a "this" argument that's used
    // to find _name, but the language hides it from us
    string getName()
    {
        // Could write this as this._name to show how it 
        // really works
        return _name;
    }

    // Here's the virtual method
    void execute()
    {
        // We get the this argument implicitly, but because
        // we're reimplementing things from scratch, we have
        // to pass it on explicitly
        _execute_impl(&this);
    }

    private:
    string _name;

    // Here's the function pointer that points to the
    // implementation of execute()
    // Calling execute() will do different things depending
    // on how this is overridden.
    void function(Command*) _execute_impl;
}

// Here's one command implementation
struct Run
{
    private:
    // Run inherits all the functionality of Command simply
    // by containing a Command instance as a member.
    // If we used the normal inheritance provided by the
    // language, this would be hidden from us.
    // Run specialises Command by setting _name and the
    // implementation of execute().
    Command _base = Command("run", &ExecuteRun);
}
// Here's Run's implementation of the execute() virtual
// function.  The "instance" argument is like "this" in a
// normal method (but that name's already taken by D).
// This function could be a static member of Run, but I'm
// putting it here just to emphasise that it's a 100% normal
// function.
void ExecuteRun(Command* instance)
{
    // Pretend to do something useful
    import core.thread : Thread, dur;
    io.writeln("Running simulation...");
    Thread.sleep(dur!"seconds"(1));
    io.writeln("Done");
}

// This command is slightly more complex because it extends
// Command with its own member
struct Save
{
    private:
    // The base is the first member so that a pointer to the
    // start of a Save instance also points to the start of
    // a Command instance, making it easy to pass Save
    // instances to code that's written for generic Command
    // instances.
    Command _base = Command("save", &ExecuteSave);
    // Here's a member that's a special extension for Save
    int _save_cnt = 0;
}
void ExecuteSave(Command* instance)
{
    // Again, instance is like "this".  Because we're doing
    // everything ourselves, here, we have to typecast it to
    // a Save pointer before using it, but that's just to
    // make the type system happy.  The pointer still points
    // to the same place in memory.
    auto save = cast(Save*)instance;

    // We use the _save_cnt member to "save" to a different
    // filename each time.
    io.writef("Saved data to save_file%02d.dat\n", save._save_cnt);
    save._save_cnt++;
}

// Need a way out
// There's a lot of DRYing out that could be done in this
// code, but I'm spelling everything in detail to show how
// it all works.
struct Exit
{
    private:
    Command _base = Command("exit", &ExecuteExit);
}
void ExecuteExit(Command* instance)
{
    import std.c.stdlib : exit;
    io.writeln("Bye!");
    exit(0);
}

// Okay, here's the interpreter

void main()
{
    // Here's the list of commands
    auto commands = [
        cast(Command*) new Run(),
        cast(Command*) new Save(),
        cast(Command*) new Exit(),
    ];

    // We build up a command lookup table
    Command*[string] command_table;
    foreach (command; commands)
    {
        command_table[command.getName()] = command;
    }

    // TODO: add help command and instructions

    // Here's the loop that reads in commands and runs them
    while (true)
    {
        // Prompt
        io.write("> ");
        string line = io.readln();
        if (line is null) break;
        line = line.strip;

        // Look up command and execute it if it exists
        Command* command = command_table.get(line, null);
        if (command)
        {
            command.execute();
        }
        else
        {
            io.writeln("Sorry, unknown command");
        }
    }
}

VTables

If this stuff is completely new to you, you might need to study and/or play with the above source code a bit to understand what’s going on. But it shows pretty much how inheritance and polymorphism work in most real languages — with just one important difference: vtables.

The Command class is simple enough, but imagine if it actually had five virtual functions, and we had ten instances of the Save class. As implemented above, that would mean five function pointers in every instance. Each Save instance would have the same list of virtual function implementations, so we’d have ten copies of these five function pointers.

D and other languages don’t implement virtual functions in such a simplistic way, though. Instead of copying the same list of virtual function implementations into each instance of Save, we have one copy of the list that’s shared by all instances. This list is called the vtable. There’s another vtable for Run and another for Exit. Instead of five function pointers in the base class Command, there’s just one pointer to the appropriate vtable. This vtable pointer effectively defines the behaviour of the class instance.

VTables add an extra level of indirection to looking up the right implementation of a virtual method, which gives virtual methods a reputation for being slow. You can use function pointers directly instead if benchmarking says it makes things better.

Back to Xanthe

Xanthe used its own implementation of classes because standard D classes use code from the runtime library. (The PowerNex kernel uses the simpler alternative of selectively including the standard class implementation.)

Xanthe’s implementation of classes works in the same kind of way as described above, but use a few features of D to make things more ergonomic. I’ll go into detail about that in another post.