Developer Diary >_

It feels like ages since I last shared a post here. But the time has come for a new quest—one that dives into the core of object-oriented programming: runtime polymorphism.

It struck me how often we rely on these powerful features without fully understanding what's happening under the hood. Sure, high-level abstractions let us build amazing things quickly. But eventually, that familiar itch of curiosity returns. The "how?" questions start bubbling up, urging us to dig deeper.

This quest? It's all about the how behind runtime polymorphism.

Previously, we implemented WinZigC, a simple imperative language with only primitive data types, no data holders or object-oriented features. In WinZigC, every function call was resolved at compile time—a model known as static dispatch.

Now, we turn to ChocoPy, an object-oriented language with classes, methods, and inheritance. In this world, a variable of a superclass type can hold instances of any subclass and call overridden methods on them. But here's the twist: in ChocoPy, method calls can't always be resolved at compile time.

In C++, you need to explicitly mark functions as virtual to inform the compiler to use dynamic dispatch (i.e., choosing the method to execute at runtime). Otherwise, even overridden methods would default to the superclass implementation. In contrast, Python makes all methods virtual by default, so dynamic dispatch is the norm.

TL;DR ChocoPy

ChocoPy is a statically typed (using Python-style type annotations) subset of the Python language. Most importantly, it's an object-oriented language with support for classes, attributes, and methods.

To start, I focused on implementing class support with methods and attributes. You can check out the ChocoPy code repo.

As soon as I got dynamic dispatch working, I knew I had to write a short post about it, it plays a crucial role in enabling true object-oriented behavior.

Let's consider an example ChocoPy program

Here, I've used a simple example with a root-level class called animal. The classes dinosaur and human inherit from animal, making them child classes. This means all the attributes defined in the parent class are also available to the child classes.

class animal(object):
    encephalization_level: int = 0

    def make_noise(self: "animal"):
        print(self.sound())

    def sound(self: "animal") -> str:
        return "???"

class dinosaur(animal):
    can_fly: bool = False
    
    def breathe(self: "dinosaur"):
        pass
    
    def sound(self: "dinosaur") -> str:
        return "RAWR! [Translation: 'I miss the good old days.']"
    
class human(animal):
    greet_text: str = "Hello, world!"
    
    def sound(self: "human") -> str:
        return self.greet_text
    
h:animal = None
d:animal = None

h = human()
d = dinosaur()

print("===================== Human =======================")
h.make_noise()
print("===================================================\n")
print("=================== Dinosaur ======================")
d.make_noise()
print("===================================================\n")

Where is Dynamic Dispatch?

See how we have overriden the sound method in each individual class, as each is supposed to have its own flavour of the sound method. We invoke the self.sound method from the base class method called make_noise. self is a pointer to the actual instance.

Since we've created human and dinosaur instances, when calling h.make_noise() or d.make_noise(), the first argument to make_noise is the actual instance. But how does it know which function to invoke using that self pointer? Is it the sound() method defined in the base class, or the potentially different sound() method defined specifically within the human or dinosaur class?"

What do you think the output of the above example will be?

Yes, as you guessed, it is:

===================== Human =======================
Hello, world!
===================================================

=================== Dinosaur ======================
RAWR! [Translation: 'I miss the good old days.']
===================================================

In any object-oriented language, a call to an instance method includes the actual instance as the first argument. In Python, this is explicit. But in some other languages, it's hidden or treated as something obvious or redundant. In those languages, like C++ or Java, you can access the instance using the special keyword this. In ChocoPy and Python, the corresponding keyword is self.

Even Python makes it implicit that you're passing the instance as the first argument to the method by using syntax like h.make_noise(). In reality, this is just syntactic sugar for make_noise(h). This concept is the same in any object-oriented language—method calls are essentially function calls with the instance passed as the first argument behind the scenes.

So, there's no other way, at runtime, make_noise must pick the right method based on the instance pointer it receives. It looks up the method using that self pointer. The mechanism that makes this possible is called a virtual method table.

A code pointer to each inherited or overridden method is placed at the same offset in the virtual method table across all derived types. This means we can calculate the offset to a particular method at compile time, while still performing the actual lookup at runtime. This simple approach is incredibly powerful.

There is only one virtual method table per class, and it is generated at compile time. Each instance includes a hidden pointer to its class's virtual method table (vtable), typically placed at the very beginning.

Memory layout of 'Animal', 'Dinosaur' & 'Human' classes

On the left-hand side, there are three instances of the three class types we have defined. On the right-hand side, you can see the virtual tables for each class.

You can see the vtable pointer placed as the first element in each instance. After that, all the other inherited and own attributes are laid out. Notice that each virtual table has placed the make_noise method first, and then the sound method second. Also, in my code, I added a new method only to the dinosaur class called breathe. Even though I declared it as the second defined method in that class, the compiler kept it after the sound method in the vtable. This ensures that every inherited or overridden method pointer is placed at the same offset within the vtable.

Implementing ChocoPy classes and methods

In LLVM bitcode, class attributes can be represented using Structure Type to define the collection of data members with their types. Methods become Functions, each taking a Pointer Type as the first argument to represent the instance.

Generated LLVM Bitcode for the example

You can just skim through it and come back after you read the sections below this.

; ModuleID = 'choco.py'
source_filename = "choco.py"
target triple = "x86_64-pc-linux-gnu"

%animal-vtbl = type { ptr, ptr }
%dinosaur-vtbl = type { ptr, ptr, ptr }
%human-vtbl = type { ptr, ptr }
%animal = type { %object, i32 }
%object = type { ptr }
%human = type { %animal, ptr }
%dinosaur = type { %animal, i1 }

@h = global ptr null
@d = global ptr null
@animal-vtbl.chocopy = constant %animal-vtbl { ptr @animal-make_noise, ptr @animal-sound }
@dinosaur-vtbl.chocopy = constant %dinosaur-vtbl { ptr @animal-make_noise, ptr @dinosaur-sound, ptr @dinosaur-breathe }
@.str = private constant [14 x i8] c"Hello, world!\00"
@human-vtbl.chocopy = constant %human-vtbl { ptr @animal-make_noise, ptr @human-sound }
@.str.1 = private constant [4 x i8] c"???\00"
@.str.2 = private constant [49 x i8] c"RAWR! [Translation: 'I miss the good old days.']\00"
@.str.3 = private constant [52 x i8] c"===================== Human =======================\00"
@.str.4 = private constant [53 x i8] c"===================================================\0A\00"
@.str.5 = private constant [52 x i8] c"=================== Dinosaur ======================\00"

declare i32 @puts(ptr)

declare ptr @malloc(i32)

define void @animal-make_noise(ptr %0) {
entrypoint:
  %self = alloca ptr, align 8
  store ptr %0, ptr %self, align 8
  %current_instance_ptr = load ptr, ptr %self, align 8
  %vtable_ptr = getelementptr inbounds %animal, ptr %current_instance_ptr, i32 0, i32 0
  %vtable = load ptr, ptr %vtable_ptr, align 8
  %func_ptr_addr = getelementptr inbounds %animal-vtbl, ptr %vtable, i32 0, i32 1
  %func_ptr = load ptr, ptr %func_ptr_addr, align 8
  %1 = call ptr %func_ptr(ptr %current_instance_ptr)
  %2 = call i32 @puts(ptr %1)
  ret void
}

define ptr @animal-sound(ptr %0) {
entrypoint:
  %self = alloca ptr, align 8
  store ptr %0, ptr %self, align 8
  ret ptr @.str.1
}

define void @dinosaur-breathe(ptr %0) {
entrypoint:
  %self = alloca ptr, align 8
  store ptr %0, ptr %self, align 8
  ret void
}

define ptr @dinosaur-sound(ptr %0) {
entrypoint:
  %self = alloca ptr, align 8
  store ptr %0, ptr %self, align 8
  ret ptr @.str.2
}

define ptr @human-sound(ptr %0) {
entrypoint:
  %self = alloca ptr, align 8
  store ptr %0, ptr %self, align 8
  %current_instance_ptr = load ptr, ptr %self, align 8
  %field_ptr = getelementptr %human, ptr %current_instance_ptr, i32 0, i32 1
  %field_val = load ptr, ptr %field_ptr, align 8
  ret ptr %field_val
}

define i32 @main() {
entry:
  %0 = call ptr @malloc(i32 24)
  store ptr @human-vtbl.chocopy, ptr %0, align 8
  %field_ptr = getelementptr %human, ptr %0, i32 0, i32 1
  store ptr @.str, ptr %field_ptr, align 8
  %field_ptr1 = getelementptr %human, ptr %0, i32 0, i32 0, i32 1
  store ptr %0, ptr @h, align 8
  %1 = call ptr @malloc(i32 24)
  store ptr @dinosaur-vtbl.chocopy, ptr %1, align 8
  %field_ptr2 = getelementptr %dinosaur, ptr %1, i32 0, i32 1
  store i1 false, ptr %field_ptr2, align 1
  %field_ptr3 = getelementptr %dinosaur, ptr %1, i32 0, i32 0, i32 1
  store ptr %1, ptr @d, align 8
  %2 = call i32 @puts(ptr @.str.3)
  %current_instance_ptr = load ptr, ptr @h, align 8
  %vtable_ptr = getelementptr inbounds %animal, ptr %current_instance_ptr, i32 0, i32 0
  %vtable = load ptr, ptr %vtable_ptr, align 8
  %func_ptr_addr = getelementptr inbounds %animal-vtbl, ptr %vtable, i32 0, i32 0
  %func_ptr = load ptr, ptr %func_ptr_addr, align 8
  call void %func_ptr(ptr %current_instance_ptr)
  %3 = call i32 @puts(ptr @.str.4)
  %4 = call i32 @puts(ptr @.str.5)
  %current_instance_ptr4 = load ptr, ptr @d, align 8
  %vtable_ptr5 = getelementptr inbounds %animal, ptr %current_instance_ptr4, i32 0, i32 0
  %vtable6 = load ptr, ptr %vtable_ptr5, align 8
  %func_ptr_addr7 = getelementptr inbounds %animal-vtbl, ptr %vtable6, i32 0, i32 0
  %func_ptr8 = load ptr, ptr %func_ptr_addr7, align 8
  call void %func_ptr8(ptr %current_instance_ptr4)
  %5 = call i32 @puts(ptr @.str.4)
  ret i32 0
}

Dynamic Dispatch implementation

Up at the very top, we're getting a blueprint of the virtual tables themselves. Notice how each class - animal, dinosaur, and human - gets its own vtable type (%animal-vtbl, %dinosaur-vtbl, %human-vtbl).

Then, we see the structures for the classes themselves. They all start with this mysterious %object which is the type that holds the space for virtual table pointer, and then tack on their own unique bits. Notice that I have embedded types to represent the nice single inheritance hierarchy.

Look closely. @animal-vtbl.chocopy neatly lists function pointers to @animal-make_noise and @animal-sound. Simple, right?

Now, check out @dinosaur-vtbl.chocopy. It's got @animal-make_noise (sharing some common ground!), but then it branches off with its own @dinosaur-sound and a unique @dinosaur-breathe! See how it's got that extra entry? That's where its special breathe ability lives.

And our @human-vtbl.chocopy? It reuses @animal-make_noise but has its own take on @human-sound.

Isn't it fascinating how LLVM lets us lay out these tables, essentially creating a roadmap for how each object will behave at runtime? It's like the compiler is pre-arranging who knows how to do what!

See how these tally with the memory layouts depicted in the diagram above.

%animal-vtbl = type { ptr, ptr }
%dinosaur-vtbl = type { ptr, ptr, ptr }
%human-vtbl = type { ptr, ptr }

%animal = type { %object, i32 }
%object = type { ptr }
%human = type { %animal, ptr }
%dinosaur = type { %animal, i1 }

@animal-vtbl.chocopy = constant %animal-vtbl { ptr @animal-make_noise, ptr @animal-sound }
@dinosaur-vtbl.chocopy = constant %dinosaur-vtbl { ptr @animal-make_noise, ptr @dinosaur-sound, ptr @dinosaur-breathe }
@human-vtbl.chocopy = constant %human-vtbl { ptr @animal-make_noise, ptr @human-sound }

According to the LLVM bitcode generated below, you can see how 24 bytes of heap memory are allocated for a human instance using malloc. The first eight bytes of this allocated memory then store the virtual table pointer:

h = human()

%0 = call ptr @malloc(i32 24)
store ptr @human-vtbl.chocopy.3, ptr %0, align 8

From the bitcode below, you can see that the make_noise function is called using dynamic dispatch. This level of indirection could be avoided by identifying the actual type of h or d at compile time, an optimization I haven't implemented yet. For now, every method invocation uses dynamic dispatch.

%current_instance_ptr = load ptr, ptr @h, align 8
...
...
call void %func_ptr(ptr %current_instance_ptr)

If static dispatch were used, the call would be directly to @animal-make_noise, which is the direct pointer to the make_noise function.

Now, lets look at the @animal-make_noise function itself:

def make_noise(self: "animal"):
    print(self.sound())

define void @animal-make_noise(ptr %0) {
entrypoint:
  %self = alloca ptr, align 8
  store ptr %0, ptr %self, align 8
  %current_instance_ptr = load ptr, ptr %self, align 8
  %vtable_ptr = getelementptr inbounds %animal, ptr %current_instance_ptr, i32 0, i32 0
  %vtable = load ptr, ptr %vtable_ptr, align 8
  %func_ptr_addr = getelementptr inbounds %animal-vtbl, ptr %vtable, i32 0, i32 1
  %func_ptr = load ptr, ptr %func_ptr_addr, align 8
  %1 = call ptr %func_ptr(ptr %current_instance_ptr)
  %2 = call i32 @puts(ptr %1)
  ret void
}

We receive an instance pointer in virtual register %0. If you look at the memory layouts of the animal and human, their first 16 bytes share a common data layout and fields. This means it's safe to access the initial parts of the instance by treating it as an animal.

It first stores the ptr argument to stack memory represented by %self for convenience:

%self = alloca ptr, align 8
store ptr %0, ptr %self, align 8

Then it dereferences the pointer saved in %self to get the actual object pointer in heap memory, which is saved to the virtual register %currentinstanceptr:

%current_instance_ptr = load ptr, ptr %self, align 8

Then we want to go to the location of the vtable. Since the vtable pointer is always the first element in our object layouts, we load the first element of %currentinstanceptr by looking at it as an %animal struct type.

Here it calculates the location to the vtable pointer in %currentinstanceptr. The i32 0, i32 0 instructs to get the first element (index 0) of the %animal structure, which is the vtable pointer. Then we load the actual pointer to the vtable. So, %vtable is a virtual register that points to the virtual method table of the object:

%vtable_ptr = getelementptr inbounds %animal, ptr %current_instance_ptr, i32 0, i32 0
%vtable = load ptr, ptr %vtable_ptr, align 8

So far so good. Now we want to look up the address of the sound method (aka function pointer) using %vtable. We know that the vtable pointer itself is at index 0, so the sound method pointer is at index 1:

%func_ptr_addr = getelementptr inbounds %animal-vtbl, ptr %vtable, i32 0, i32 1
%func_ptr = load ptr, ptr %func_ptr_addr, align 8

At runtime, %func_ptr will be dynamic because different instances (from human or dinosaur) have their own implementations for the sound method, and their corresponding function pointers are placed at the second position of their respective virtual method tables.

Then we call the function using its address like below, passing the %currentinstanceptr (self) to the sound method and printing the output:

%1 = call ptr %func_ptr(ptr %current_instance_ptr)
%2 = call i32 @puts(ptr %1)

So, the moment of truth! When we actually run our code and those make_noise() calls happen, what does our trusty %func_ptr end up pointing to? Buckle up, because this is where the dynamic magic truly shines:

See that? Even though the make_noise logic is the same, the actual sound function that gets called is different depending on whether we're talking to a human or a dinosaur! That's the power of dynamic dispatch in action, the program figures out the right method to call while it's running.

Pretty neat, huh? This isn't just a ChocoPy quirk, either. This fundamental idea of virtual tables and runtime resolution is a cornerstone of how many object-oriented languages bring polymorphism to life.

A cool fact about ChocoPy

Any valid ChocoPy program also happens to be valid Python! This opens the door for a straightforward performance showdown. Let's see how our compiled ChocoPy code stacks up against its interpreted Python.

First, I compiled our animal sounds program using our chocopyc compiler and then created an executable with clang:

./build/chocopyc tests/choco.py
clang-17 -x ir ./tests/choco.py.ll -o animalsounds -g

And here's the result when we ran the compiled binary:

$ time animalsounds 

===================== Human =======================
Hello, world!
===================================================

=================== Dinosaur ======================
RAWR! [Translation: 'I miss the good old days.']
===================================================


real    0m0.002s
user    0m0.000s
sys     0m0.002s

Now, let's see how Python fares interpreting the same ChocoPy code:

time python3 ./tests/choco.py

===================== Human =======================
Hello, world!
===================================================

=================== Dinosaur ======================
RAWR! [Translation: 'I miss the good old days.']
===================================================


real    0m0.021s
user    0m0.015s
sys     0m0.005s

Unsurprisingly, the compiled ChocoPy binary blazes past the interpreted Python version!

Behind the post

My journey into understanding object-oriented implementation was heavily influenced by Chapter 10 of "Programming Language Pragmatics," fourth edition (the fifth edition is also out now!). If you found this post interesting, I highly recommend checking it out. Their discussion on implementing interfaces is particularly thought-provoking.

To truly grok the intricacies of object-orientation with LLVM, I also experimented by writing a similar example in C++ and examining the emitted LLVM bitcode.

Of course, the ultimate step was building the ChocoPy compiler itself. Feel free to explore the code here: https://github.com/Amila-Rukshan/chocopy.

That wraps up this post! Catch you in the next one.

Until then, take care!