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.
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
as its first member. If you imagine the raw member data of an instance laid out in memory, that means the start of a
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.
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
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
Exit. Instead of five function pointers in the
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.