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
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.
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:
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.
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:
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
Because a pointer to a struct points to the beginning of the struct, a pointer to a (derived)
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.
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
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
Here’s the code:
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.
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.