Menu

The Missing Zig Polymorphism / Runtime Dispatch Reference

Feb 13, 2022

Polymorphism in Zig is not well explained, and there are no good references for it. It’s never explained why it’s like that. I decided to experiment my way there, and write about what I found.

Zig does not have a convenient polymorphism language feature (like interface in C# or virtual methods in C++ classes), and it’s not going to get one (you can dig into the references to that issue to try to understand the discussion).

So if you need it, you have to build your own Polymorphism out of existing language features. That may either make you feel excited or scared. I was apathetic and really not interested. But I really like Zig, and I had a strong need for it, so I bit the bullet.

(BTW, there’s also interface.zig, but I haven’t tried it, so I can’t vouch for it)

In Runtime Polymorphism, why, how? Alex Naskos explains different paradigms for dynamic dispatch in Zig.

It seems the Zig community converged on a fat pointer solution, where an object that supports dynamic dispatch contains two pointers: a vtable pointer and an object pointer. This is what is used in the standard library, e.g. in Allocator. Along the way here we’ll get into some details that I hope will illuminate why that decision makes sense (I end up in pretty much the same place).

Where I end is going to be very close to the 3rd option in Alex Naskos' talk (12:49). But his presentation is very condensed. It didn’t quite leave me in a place where I understood the details of what is going on. Perhaps it’s enough for you?

Goal

I want to write a simple expression calculator that represents the expression as a graph.

The expression might be (2+3)*(4*5). Here’s a visualization of the graph:

Graph representing the expression (2+3)(45)

The result of the computation should be 100.

I suggest that in order to do this, we need a polymorphic node type. node can have an arbitrary number of inputs, and it needs to have a Compute function which must be runtime dispatched so we can ask any type of node to compute its result. You can see that we need 3 implementations of node, with different Compute implementations for integer literal, operator plus and operator multiply.

Prerequisitess

In C++ it’s easy to extend a base class with additional fields and methods, just use : to inherit from a base class in your derived class. Zig offers no mechanism to inherit from a type, so the idea of extending a class or overriding it’s virtual methods is not going to work. (There is an method for doing polymorphism by composition using @fieldParentPtr, but it is no longer the prefered method)

The fact that we can’t extend a struct by adding or overriding members means that we can’t just have a polymorphic implementation in one object. As far as I can tell, it is necessary to use a polymorphic “wrapper” object that references your implementation object.

One other thing before we start.

Below, you will see me use a pattern like this:

1
2
3
4
5

    const SomeVar = struct {
        fn SomeFunction(SomeArgs) void {
            DoSomething().
        }
    }.SomeFunction

This is a workaround for Zigs lack of inline function declarations. You should think of the above as

1
2
3

    const SomeVar = fn(SomeArgs) void {
        DoSomething();
    };

Proposal #1717 will address this eventually, but in the meantime this is required.

Function pointers

Starting from scratch - we know that dynamic dispatch is built using function pointers. So let’s try that for our wrapper polymorphic object. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

const node = struct {
    Compute: fn(self: *node) i32,

    pub fn make(Object: *literal_value) node {
        return node {
            .Compute = ???,
        };
    }
};

const literal_value = struct {
    Value: i32 = undefined,

    pub fn Compute(self: *literal_value) i32 {
        return self.Value;
    }
};

test "literal computes expected value" {
    var LiteralThree = literal_value { .Value = 3 };
    var Node = node.make(&LiteralThree);

    try std.testing.expectEqual(@as(i32, 3), Node.Compute(&Node));
}

Here node is our polymorphic wrapper and literal_value the node implementation that represents a literal integer.

But how do we construct Compute on line 6?

We can’t.

node has no storage for the reference to the implementation object, so there is no way to connect Node to LiteralThree.

Detour: Closures

You might ask, couldn’t we just do something like this?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

const node = struct {
    Compute: fn(self: *node) i32,

    pub fn make(Object: *literal_value) node {
        return node {
            .Compute = struct {
                fn Compute(self: *node) i32 {
                    _ = self;
                    return Object.Compute();
                }
            }.Compute,
        };
    }
};

The idea here is to capture Object on line 4 in a closure, and call it directly on line 9. If you try this you will get

error: 'Object' not accessible from inner function

refering to line 9.

That is because Zig does not support closures.

Add Object Reference

Let’s add a reference to the object we’re making polymorphic.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

const node = struct {
    Object: *literal_value = undefined,
    Compute: fn(self: *node) i32,

    pub fn make(Object: *literal_value) node {
        return node {
            .Object = Object,
            .Compute = struct {
                fn Compute(self: *node) i32 {
                    return self.Object.Compute();
                }
            }.Compute,
        };
    }
};

const literal_value = struct {
    Value: i32 = undefined,

    pub fn Compute(self: *literal_value) i32 {
        return self.Value;
    }
};

test "literal computes expected value" {
    var LiteralThree = literal_value { .Value = 3 };
    var Node = node.make(&LiteralThree);

    try std.testing.expectEqual(@as(i32, 3), Node.Compute(&Node));
}

Here I’ve added an object pointer on line 2, and update make so the node Compute method invokes Compute on the referenced Object.

This works! But one problem here is that we use the specialized literal_value directly as the type of the wrapped object. Let’s try to make node support more types.

Polymorphism

Instead of declaring Object as *literal_node, I’ll use an int pointer with no type information. I define the type int_ptr to make this a little clearer. (You could also use anyopaque but it introduces alignment problems that only complicates the solution.)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

const int_ptr = usize;

const node = struct {
    Object: int_ptr = undefined,
    Compute: fn(self: *node) i32,

    pub fn make(Object: anytype) node {
        const ObjectPtrType = @TypeOf(Object);
        return node {
            .Object = @ptrToInt(Object),
            .Compute = struct {
                fn Compute(self: *node) i32 {
                    const TypedObject = @intToPtr(ObjectPtrType, self.Object);
                    return TypedObject.Compute();
                }
            }.Compute,
        };
    }
};

const literal_value = struct {
    Value: i32 = undefined,

    pub fn Compute(self: *literal_value) i32 {
        return self.Value;
    }
};

const square = struct {
    Input: *node = undefined,

    pub fn Compute(self: *square) i32 {
        const Val = self.Input.Compute(self.Input);
        return Val*Val;
    }
};

test "square computes expected value" {
    var LiteralThree = literal_value { .Value = 3 };
    var Node1 = node.make(&LiteralThree);

    var Square = square { .Input = &Node1 };
    var Node2 = node.make(&Square);

    try std.testing.expectEqual(@as(i32, 9), Node2.Compute(&Node2));
}

This is essentially just the changes needed to change *literal_value to int_ptr in node. Our solution is now polymorphic!

I also introduced the square operator to make sure we had at least one node type that had an input, so we can demonstrate calling Compute on its input, making the computation recursive.

Dot syntax

You may have noticed that when we invoke node.Compute we have to supply the self argument manually, which is surprising. You can see this on lines 33 and 45 in the example above.

This is because there is apparently a difference in Zig between

1
2
3
4
5

var SomeStruct = struct {
    pub fn SomeFunction() void {
        DoSomething();
    }
};

and

1
2
3

var SomeStruct = struct {
    SomeFunction: fn() void;
};

It seems the dot syntax which automatically applies self as the first argument to the struct method only works in the first case! I spent some time researching this, but I could not figure out if this was expected.

Fortunately it is fixable with some additional typing:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

const int_ptr = usize;

const node = struct {
    Object: int_ptr = undefined,
    VirtualTable: virtual_table = undefined,

    const virtual_table = struct {
        Compute: fn(self: *node) i32,
    };

    pub fn Compute(self: *node) i32 {
        return self.VirtualTable.Compute(self);
    }

    pub fn make(Object: anytype) node {
        const ObjectPtrType = @TypeOf(Object);
        return node {
            .Object = @ptrToInt(Object),
            .VirtualTable = . {
                .Compute = struct {
                    fn Compute(self: *node) i32 {
                        const TypedObject = @intToPtr(ObjectPtrType, self.Object);
                        return TypedObject.Compute();
                    }
                }.Compute,
            }
        };
    }
};

const literal_value = struct {
    Value: i32 = undefined,

    pub fn Compute(self: *literal_value) i32 {
        return self.Value;
    }
};

const square = struct {
    Input: *node = undefined,

    pub fn Compute(self: *square) i32 {
        const Val = self.Input.Compute();
        return Val*Val;
    }
};

test "literal computes expected value" {
    var LiteralThree = literal_value { .Value = 3 };
    var Node = node.make(&LiteralThree);

    try std.testing.expectEqual(@as(i32, 3), Node.Compute());
}

test "square computes expected value" {
    var LiteralThree = literal_value { .Value = 3 };
    var Node1 = node.make(&LiteralThree);

    var Square = square { .Input = &Node1 };
    var Node2 = node.make(&Square);

    try std.testing.expectEqual(@as(i32, 9), Node2.Compute());
}

This is a little bit verbose, but fixes the problem.

I also wrapped the the Compute function pointer in node inside virtual_table. This avoids the naming conflict between the Compute function pointer and the pass-through function we introduced to make sure dot notation worked as expected on node.Compute. It also prepares us a little for the next step.

Fat pointer, but not too fat

Now, the problem with the above solution - what if the interface grows much larger? What if we have 10 or 20 function pointers? The object we’re passing around grows with every method we add to the virtual table. That is not great for performance, because it will consume cache and memory bandwidth. We can quickly verify the object size growth:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

const node = struct {
    Object: int_ptr = undefined,
    VirtualTable: virtual_table = undefined,

    const virtual_table = struct {
        Compute: fn(self: *node) i32,
        AnotherFunction: fn(self: *node, i32) void,
        OneMoreFunction: fn(self: *node) void,
    };

    pub fn Compute(self: *node) i32 { return self.VirtualTable.Compute(self); }
    pub fn AnotherFunction(self: *node, Argument: i32) void { self.VirtualTable.AnotherFunction(self, Argument); }
    pub fn OneMoreFunction(self: *node) void { self.VirtualTable.OneMoreFunction(self); }

    pub fn make(Object: anytype) node {
        ...
    }
};

test "node is size of four pointers - the object pointer and three function pointers" {
    var LiteralThree = literal_value { .Value = 3 };
    var Node = node.make(&LiteralThree);

    try std.testing.expectEqual(@as(usize, 4*@sizeOf(int_ptr)), @sizeOf(@TypeOf(Node)));
}

We see that the size of node is indeed 4 pointers, or 32 bytes. So the size of the wrapper can become large, and we would prefer this to be just two pointers.

This is straightforward to fix:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

const int_ptr = usize;

const node = struct {
    Object: int_ptr = undefined,
    VirtualTable: *const virtual_table = undefined,

    const virtual_table = struct {
        Compute: fn(self: *node) i32,
    };

    pub fn Compute(self: *node) i32 {
        return self.VirtualTable.Compute(self);
    }

    pub fn make(Object: anytype) node {
        const ObjectPtrType = @TypeOf(Object);
        return node {
            .Object = @ptrToInt(Object),
            .VirtualTable = &.{
                .Compute = struct {
                    fn Compute(self: *node) i32 {
                        const TypedObject = @intToPtr(ObjectPtrType, self.Object);
                        return TypedObject.Compute();
                    }
                }.Compute,
            }
        };
    }
};

You can run the same test as before to verify the size of this object will remain 16 bytes if you add additional functions.

This solution is now very close to the 3rd option presented in Alex Naskos' talk.

One difference I would like to point out here is that Alex uses the comptime keyword when creating the pointer to the virtual table. As far as I could tell in my tests, omitting it did not make any difference, but I could not tell you why.

Now we can build our acceptance test:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

const operator_plus = struct {
    Input1: *node = undefined,
    Input2: *node = undefined,

    pub fn Compute(self: *operator_plus) i32 {
        return self.Input1.Compute() + self.Input2.Compute();
    }
};

const operator_multiply = struct {
    Input1: *node = undefined,
    Input2: *node = undefined,

    pub fn Compute(self: *operator_multiply) i32 {
        return self.Input1.Compute() * self.Input2.Compute();
    }
};

test "(2+3)*(4*5) == 100" {
    var LiteralTwo = literal_value { .Value = 2 };
    var LiteralThree = literal_value { .Value = 3 };
    var LiteralFour = literal_value { .Value = 4 };
    var LiteralFive = literal_value { .Value = 5 };

    var NodeLiteralTwo = node.make(&LiteralTwo);
    var NodeLiteralThree = node.make(&LiteralThree);
    var NodeLiteralFour = node.make(&LiteralFour);
    var NodeLiteralFive = node.make(&LiteralFive);

    var Plus = operator_plus { .Input1 = &NodeLiteralTwo, .Input2 = &NodeLiteralThree };
    var NodePlus = node.make(&Plus);

    var Multiply = operator_multiply { .Input1 = &NodeLiteralFour, .Input2 = &NodeLiteralFive };
    var NodeMultiply = node.make(&Multiply);

    var Result = operator_multiply { .Input1 = &NodePlus, .Input2 = &NodeMultiply };
    var NodeResult = node.make(&Result);


    try std.testing.expectEqual(@as(i32, 100), NodeResult.Compute());
}

Thanks for reading

That’s it folks. I hope you have better starting point for writing polymorphic code in Zig than you did before.

Site menu

Back to top