Zig Monomorphization

Before making a click bait title for the article I decided to check the terms, because I heard about monomorphism only related to Rust, I never heard about it in C++ or D. Nevertheless, I had a picture that monomorphism is a way to make a function/type being able to work with arguments of various types rather than one. The main difference from polymorphism is generating an instance of the function/type per type of each argument. Polymorphism on the other hand solves the problem with passing a pointer to the original instance of type. Both of the ways can be used with C++, D, Rust, and even Go, which has generics and go generate.

Anyway, I decided to get clear about it and searched on the internet. Surprisingly, the term "monomorphism" is more popular in math. After specifying that I'm searching the definition in programming, I found the page from the Haskell wiki. Let me quote it

Monomorphism is the opposite of polymorphism. That is, a function is polymorphic if it works for several different types - and thus, a function is monomorphic if it works only for one type.

Sounds a bit controversial, because monomorphism helps to work with a set of types. I popped out Wikipedia about Polymorphism and found that the there 3 types of it and this:

While languages like C++ and Rust use monomorphized template…

Cool, so it's called "monomorphized" rather than monomorphism. Fair enough, let's jump to the article. In the article I see examples of Rust, C++ is not mentioned. I know that C++ uses templates to solve the problem. For the purpose of finding which category the templates of C++ belong to, I jumped back to article about Polymorphism. On that page I found the category Parametric polymorphism, and this

Parametric polymorphism is also available in several object-oriented languages. For instance, templates in C++ and D, or under the name generics in C#, Delphi, Java and Go…

Therefore, I don't see the difference between Parametric Polymorphism and Monomorphization. However, I'm sure that Rust community didn't make it up, because there are a couple of mentions in the community of Haskell and Ocaml.

For those who just want to see the way, I came up with this code to solve the problem with absence of interfaces

fn GetId(Self: type) type {
    return struct { get_id: fn (Self) u64 };
}

fn impl(Implementation: type, Interface: type) void {
    const i_inst: Interface = undefined;
    for (@typeInfo(Interface).Struct.fields) |d| {
        if (!@hasDecl(Implementation, d.name)) @compileError("the type doesn't implement the method '" ++ d.name ++ "'");
        const implementation_method = @field(Implementation, d.name);
        const interface_method = @field(i_inst, d.name);
        const ImplementationMethodType = @TypeOf(implementation_method);
        const InterfaceMethodType = @TypeOf(interface_method);
        if (ImplementationMethodType != InterfaceMethodType) @compileError("the type of the method '" ++ d.name ++ "' is '" ++ @typeName(ImplementationMethodType) ++ "', but the expected type is '" ++ @typeName(InterfaceMethodType) ++ "'");
    }
}

fn get_id(instance: anytype) u64 {
    comptime {
        const Implementation = @TypeOf(instance);
        const Interface = GetId(Implementation);
        impl(Implementation, Interface);
    }
    return instance.get_id();
}

const User = struct {
    id: u64,

    fn get_id(self: @This()) u64 {
        return self.id;
    }
};

const MockUser = struct {
    fn get_id(_: @This()) u64 {
        return 123;
    }
};

test "test interfaces" {
    const expect = std.testing.expect;
    try expect(get_id(User{ .id = 1 }) == 1);
    try expect(get_id(MockUser{}) == 123);
}

Zig reminded me about D, because of the comptime. It is really similar to the templates from D. Namely, you use the same language for meta-programming as for programming. In both languages you can use regular features like variables, looks, forks. I played with Zig a little bit and noticed straightaway that there are no interfaces. I found a couple of articles, but all of them were about polymorphism. However, I was curious about monomorphization.

Technically, Zig has already a way to use the same function against a set of types. Consider the following code:

const std = @import("std");

const User = struct {
    id: u64,

    fn get_id(self: @This()) u64 {
        return self.id;
    }
};

const MockUser = struct {
    fn get_id(_: @This()) u64 {
        return 123;
    }
};

fn get_id(user: anytype) u64 {
    return user.get_id();
}

pub fn main() !void {
    _ = get_id(User{ .id = 1 });
    _ = get_id(MockUser{});
}

Now let's take a look at the defined symbols in the binary

$ nm -W ./zig-out/bin/ziguser | grep main.get_id
00000000010348a0 t main.get_id__anon_2597
00000000010348b0 t main.get_id__anon_2600

We see, that the compiler creates a binary with two versions of the function get_id. However, our function is dead simple. In reality, we might meet a function of hundreds lines, which passes its arguments to other functions, and those functions accept anytype as well. In this case, it will be tricky to understand which methods the types of the arguments must have. It's better to have something like in Rust:

fn get_id(user: impl GetId) -> u64 {
    return user.get_id();
}

Given that, we can say that the input argument user must have the methods from the trait GetId implemented. Trying to adapt it to Zig, I remembered about the Concepts for D, which I used a lot for betterC mode. The language has interfaces to implement Polymorphism, but the library does the monomorphization, thanks to the compiling time features of D. Here is how we do write the client code with the library in D:

import concepts : implements;

interface GetId {
    ulong getId();
}

@implements!(User, GetId)
struct User {
    ulong id;
    ulong getId() { return this.id; }
}

Therefore, the plan is this:

• Represent an interface as structure which contains a set of fields, each one is a function.
• Get the names of the fields and compare them with the names of the fields of the type of the argument.
• Then I compare the types of the fields.

It's great, that Zig allows use structures for some metaprogramming features, not just for representing some entities. We have instruments rather than policies.

Zig has a set of functions to do a compile-time reflection:

• @hasDecl allows to check a declaration inside a type.
• @hasField allows to check a field of a type.

Given that and the structure:

const User = struct {
    id: u64,

    fn get_id(self: @This()) u64 {
        return self.id;
    }
};

We can find out whether a structure has some fields this way:

if (@hasDecl(User, "get_id")) {
    // the type has the field "get_id"
}

if (@hasField(User, "id")) {
    // the type has the field "id"
}

However, to access both of them we use only one function @field. Given that and the function @TypeOf, the type of the function is obtained this way:

const method_type = @TypeOf(@field(User, "get_id");

Happy days! Now, we've got to make a structure, and use its methods to assert the acceptable interface.

Things worked slightly different for my interface structure. I declared it as:

const GetId = struct {
    fn get_id(_: @This()) u64 {}
};

The problem of the code that we can't get the field when we call either @typeInfo(GetId).Struct.decls or @typeInfo(Interface).Struct.fields. Not sure, if it's a bug, though. Nonetheless, I declared the structure this way, making the method a field.

const GetId = struct {
    get_id: fn (@This()) u64,
};

That means that every instance must have the field declared. However, as we want to use the structure as an interface only, it's not a problem. Later I came across another issue, when I did @field(GetId, "get_id") I got the compilation error error: struct 'main.GetId' has no member named 'get_id'. It makes sense, because now get_id is a field of a structure. Therefore, we have to make an instance of the structure. Luckily, Zig allows us to declare an instance only. Namely, we can do

const instance: GetId = undefined;
const method_type = @TypeOf(@field(instance, "get_id");

Here, we have another problem the type of the function of User doesn't match the type of the function of GetId.

Look at the function @This. The function returns the innermost type. Therefore, for the structure GetId the code @TypeOf(@field(GetId, "get_id"); returns fn(GetId) u64, but I need fn(User) u64 when I compare the types of the methods. I came up with the a simple idea to make a template out of the interface structure. Therefore, the structure turned into this:

fn GetId(Self: type) type {
    return struct {
        get_id: fn (Self) u64,
    };
}

This is something to improve. When we do @TypeOf(@field(GetId, "get_id"); we can inspect the types of the parameters of the type of the function, and skip the first one when we compare them to the parameters of the type of the argument. In a real code, I would've done it for sure.