metastuff

Coming up with a new type system on top of C

This is something of a first for me, I’m writing a blog post about something I haven’t written any lines of code for. In this case, I mostly just wanted to get my ideas written down and maybe collect some feedback before even doing anything to get these thoughts out of my head and maybe get some perspective.

Existing practice for generics

C is rather (in)famous for not having generics in the type system. When you need a vector (or, horror of horrors, a hashmap) for some type, you just whip up an implementation from scratch. Of course, this becomes a bit tedious after a while, and it’s not uncommon for developers to carry around their personal utility libraries (I know I do). Some of these utility libraries are even kind-of-generic by using the macro system and multiple #includes to generate functions and data structures for specific types at will.

Using a vector as an example, the generic code looks something like this (abridged from here):

#include <stdlib.h>
#include <assert.h>

#ifndef VEC_TYPE
#error "Need vector type"
#endif

#ifndef VEC_NAME
#error "Need vector name"
#endif

#define VEC_JOIN2(a, b) a##b
#define VEC_JOIN(a, b) VEC_JOIN2(a, b)

#define VEC(a) VEC_JOIN(VEC_NAME, a)

#define VEC_STRUCT VEC_NAME
struct VEC_STRUCT {
	size_t n;
	size_t s;
	VEC_TYPE *buf;
};

static inline struct VEC_STRUCT VEC(create)()
{
    return (struct VEC_STRUCT){
        .n = 0,
        .s = 0,
        .buf = NULL
    };
}

static inline void VEC(append)(struct VEC_STRUCT *v, VEC_TYPE n)
{
    v->n++;
    if (v->n >= v->s) {
        v->s = v->s == 0 ? 1 : 2 * v->s;
        v->buf = realloc(v->buf, v->s * sizeof(VEC_TYPE));
    }

    v->buf[v->n - 1] = n;
}

static inline VEC_TYPE *VEC(at)(struct VEC_STRUCT *v, size_t i)
{
    assert(i < v->n && "out of vector bounds");
    return &v->buf[i];
}

static inline void VEC(destroy)(struct VEC_STRUCT *v)
{
    free(v->buf);
}

and you’d use this vector ‘class’ like the following:

#include <assert.h>

#define VEC_NAME ints
#define VEC_TYPE int
#include "vec.h"

#define VEC_NAME floats
#define VEC_TYPE float
#include "vec.h"

int main()
{
    struct ints ints = ints_create();
    ints_append(&ints, 10);
    assert(*ints_at(&ints, 0) == 10);
    ints_destroy(&ints);

    struct floats floats = floats_create();
    floats_append(&floats, 20.);
    assert(*floats_at(&floats, 0) == 20.);
    floats_destroy(&floats);
}

This of course works, but the developer experience could be better. In particular, the error messages can be rather verbose. For example, a typo like #define VEC_TYPE itn generates about 140 lines of error messages. An experienced developer can generally suss out which messages are actually relevant, but for anyone new to C it might not be as easy. My utility library is as small and simple as possible and as such doesn’t have the best developer ergonomics, and something like STC, which shares the same basic operating principle, produces only about 40. Better, but still, seems a bit much, no?

Formalizing existing practice

Let’s start by moving this concept down a level. Instead of the preprocessor generating code for us, let’s let the actual compiler do it. I’m suggesting that the vector definition should look something like this:

#ifndef NGC_VEC_H
#define NGC_VEC_H

#include <stdlib.h>
#include <assert.h>

typedef vec[type] {
    struct ^^ {
        size_t n;
        size_t s;
        type *buf;
    };

    static inline struct ^^_create()
    {
        return (struct ^^){
            .n = 0,
            .s = 0,
            .buf = NULL
        };
    }

    static inline type *^^_append(struct ^^ *v, type n)
    {
        v->n++;
        if (v->n >= v->s) {
            v->s = v->s == 0 ? 1 : 2 * v->s;
            v->buf = realloc(v->buf, v->s * sizeof(VEC_TYPE));
        }

        v->buf[v->n - 1] = n;
    }

    static inline type *^^_at(struct ^^ *v, size_t i)
    {
        assert(i < v->n && "out of vector bounds");
        return &v->buf[i];
    }

    static inline void ^^_destroy(struct ^^ *v)
    {
        free(v->buf);
    }
};

#endif /* NGC_VEC_H */

and the usage would then be something like

#include "vec.h"

typedef ints = vec[int];
typedef floats = vec[float];

int main()
{
    struct ints ints = ints_create();
    ints_append(&ints, 10);
    assert(*ints_at(&ints, 0) == 10);
    ints_destroy(&ints);

    struct floats floats = floats_create();
    floats_append(&floats, 20.);
    assert(*floats_at(&floats, 0) == 20.);
    floats_destroy(&floats);
}

I’m certainly not married to the syntax quite yet, but as a quick overview, I’m using ^^ as a placeholder for “whatever the name of this type is”, and [] instead of <> to specify type arguments (no particular reason, it just seems to be the preferred method in PL circles).

When we want to instanciate a generic type, we must give it an actual global name with typedef name = .... That name is then used to generate the names of functions and types within the ’template’ (if you want to call it that) and check for collisions. The instantiated functions are just placed into the global namespace, so for example ^^_at(...) when paired with typdef ints = ... generates a global function named ints_at(...). Any existing symbols with identical names would cause a duplicate definition error, same as with existing approaches.

Calling functions from generic types within a generic block seems rather essential, and would be done something like the following:

typedef vec[type] {
    [...]
    /* assuming the type can be summed */
    type ^^_sum(struct ^^ *v)
    {
        type total = type<>_zero();
        for (size_t i = 0; i < v->n; ++i)
            total = type<>_add(total, v->buf[i]);

        return total;
    }
    [...]
};

Again, not married to the syntax, but here I’m using <> to effectively just paste two things together, rather like ## does in the preprocessor. So, for example,

typedef math_vector2d[type] {
    struct ^^ {
        type x, y;
    };

    [...]

    struct ^^ ^^_zero()
    {
        /* I guess technically we should use type<>zero here as well, but let's
         * just assume type is a regular int or float */
        return (struct ^^){.x = 0, .y = 0};
    }

    struct ^^ ^^_add(struct ^^ a, struct ^^ b)
    {
        /* ditto but type<>add */
        return (struct ^^){
            .x = a.x + b.x,
            .y = a.y + b.y
        };
    }

    [...]
};

typedef math_floatvec2d = math_vector2d[float];
typedef floats = vec[math_floatvec2d];

would work, because typedef math_floatvec2d = ... would generate math_floatvec2d_zero() and math_floatvec2d_add() which would be used by floats_sum(), generated by typedef floats = ....

This is the minimal extent of what I’m proposing. There’s a fairly obvious limitation here, that being types with spaces in them (const int, unsigned long, struct whatever). I’ll touch on that later.

Going further

1. Specifying constant value parameters

Maybe we would like to sort our vector. With the minimal example, we would have to do something like this:

typedef vec[type] {
    [...]
    typedef int (*^^_sort_t)(type *, type *);
    void ^^_sort(struct ^^ *v, ^^_sort_t sort)
    {
        qsort(v->buf, v->n, sizeof(type), (__compar_fn_t)sort);
    }
    [...]
};

This works, but means that we pass in the function at runtime, which might be a bit annoying. What if we instead did something like the following:

typedef vec[type](int (*^^_sort)(type *, type *)) {
    [...]
    void ^^_sort(struct ^^ *v)
    {
        qsort(v->buf, v->n, sizeof(type), (__compar_fn_t)^^_sort);
    }
    [...]
};

/* instantiation would then look like */
static int int_sort(int *a, int *b)
{
    return *a - *b;
}

typedef ints = vec[int](int_sort);

This might work particularly well with lambdas, if C ever gets those, and the instantiation would compress down to

typedef ints = vec[int]([](int *a, int *b){return *a - *b});

(or whatever the lambda syntax would end up as)

This might also work alright for things like static arrays (a bit cumbersome due to having to explicitly say typedef int_arr5 = arr[int](5) but doable), though it might be better to improve the native array ergonomics (I have a specific paper in mind but I can’t find it right now, I’ll update this post if I do find it later).

2. Specifying linkage

If we know we only need one instance of a given generic type, it’s fine to just define all functions with static. If we want to allow it to be defined in a header file that is included from multiple compilation units, mark all functions static inline. But what if we want to use the same instance in multiple units, without forcing each unit to compile the body? We could potentially add linkage keywords to the instantiation, so for example

/* some_file.h */
/* adds extern to all functions and 'hides' implementations */
typedef ints = extern vec[int];

/* some_file.c */
/* provides implementations with global linkage */
typedef ints = vec[int];

3. Private/public functions

This is a short one, we could potentially make all functions defined within a template private by default, and add [[public]] to the functions that we want to expose. Might require name mangling the private functions, but I guess that’s fine since they’re not supposed to be used from dlopen() anyway?

4. Adding traits

This is a somewhat larger idea, but still more limited than traits as you might know them from other languages.

Improving our example vector example:

/* trait definition */
typedef summable {
    /* require another trait within this trait */
    [[implements(zeroable)]] ^^;

    ^^ ^^_add(^^ a, ^^ b);
};

typedef math_vector2d[summable type] {
    [[implements(summable)]] ^^;
    struct ^^ {
        type x, y;
    };

    [...]

    struct ^^ ^^_zero()
    {
        return (struct ^^){.x = type<>_zero(), .y = type<>_zero()};
    }

    struct ^^ ^^_add(struct ^^ a, struct ^^ b)
    {
        return (struct ^^){
            .x = type<>_add(a.x, b.x),
            .y = type<>_add(a.y, b.y)
        };
    }

    [...]
};

Essentially, we create a trait summable, which says that for a type to be summable, let’s say int, there must exists two functions, int int_zero() and int int_add(int a, int b). When using <>, we can check if the right-hand side exists in the given trait, so for example type<>_add can check if summable has something of the form type type_add(type a, type b), so we can check that library implementers don’t accidentally use more features than they’ve claimed to require, as can be the case in C++.

On the other side, when a user instantiates a template, we can check if the types given as parameters implement the required traits, and give out a single early error if they don’t. Unsure if checking a trait implementation should be done implicitly (i.e. look through the current scope for all required functions) or explicitly (i.e. the type needs to say [[implements(summable)]]), but in the above example I’ve used the explicit method. The explicit method is presumably a bit more useful since that way we can check if the template actually implements all functions it claims to implement and report an error if it doesn’t.

Note that there’s something of an edge case here with how C uses type tags. In the above example I’ve explicitly used struct ^^ a, but I left struct out in the trait definition. I’m still a bit unsure if the best approach here would be to always use something like typedef struct {...} ^^, or if it’s possible to automatically deduce the tag during lookup.

4.1 Extending existing traits

It might be useful to allow users to give an existing type more functions and implement extra traits that way. There are at least two approaches, not necessarily mutually exclusive, that I can think of:

  1. Allow extending existing instantiated types, something like
/* implements summable */
typedef math_floatvec2d = math_vector2d[float];

/* all type parameters/constant values etc. are set */
continue math_floatvec2d {
    [[implements(negatable)]] ^^;

    struct ^^ ^^_neg(struct ^^ a) {
        /* we know that floats are negatable so this is fine */
        return (struct ^^){
            .x = -a.x,
            .y = -a.y
        };
    }
};
  1. Allow supertemplates, something like
typedef our_supertrait {
    [[implements(summable)]] ^^;
    [[implements(negatable)]] ^^;
};

/* type must implement summable so math_floatvec2d is happy */
typedef more_generic_floatvec2d[our_supertrait type]: math_floatvec2d[type] {
    [[implements(negatable)]] ^^;

    struct ^^ ^^_neg(struct ^^ a) {
        return (struct ^^){
            .x = type<>_neg(a.x),
            .y = type<>_neg(a.x)
        };
    }
};

4.2 Implementing traits for existing types

With the stuff above, we could potentially do something like this for primitive types:

/* primitive being a built-in allowing us to use +/-* etc */
typedef arithmetic[primitive type] {
    [[implements(addable)]] ^^;
    [[implements(negatable)]] ^^;
    /* etc, subable, mulable, other dumb names */

    /* implementations */
    ^^ ^^_add(^^ a, ^^ b)
    {
        return a + b;
    }

    /* etc, but importantly, no typedef for alias! */
};

typedef ull = arithmetic[unsigned long long];

/* create alias ull that matches instance, now if people want to use unsigned
 * long long in vec or somewhere, they would need to use
 *
 *   typedef ulls = vec[ull];
 *
 */
typedef unsigned long long ull;

typedef ul = arithmetic[unsigned long];
typedef unsigned long ul;

/* etc. */
typedef int = arithmetic[int];
/* no typedef! */

But admittedly it’d be pretty nice to not have to use ull when we meant unsigned long long, and the above doesn’t handle type modifiers too well. It might be nice to provide some kind of aliasing feature, like typedef ull(unsigned long long) = arithmetic[unsigned long long] for primitive types, but I would imagine that this would also be useful for existing libraries that we might want to wrap. Something like

/* in some library */
mylib_t mylib_add(mylib_t a, mylib_t b);

/* we want to tell the compiler the library implements some of our traits */
typedef mylib_wrapper {
    [[implements(addable)]] ^^;

    typedef mylib_t ^^;

    ^^ ^^_add(^^ a, ^^b) {
        return mylib_add(a, b);
    }
};

/* we can explicitly pass mylib_wrapper as a type argument to templates, as it
 * is an alias to mylib_t, but with the alias the compiler would also be smart
 * enough to look for mylib_wrapper when encountering mylib_t */
typedef mylib_wrapper(mylib_t) = mylib_wrapper;

Implementation

As mentioned at the start, currently nada. I’m a bit unsure what the best approach to take here would be, on one extreme I could just start integrating this into an existing compiler (probably not gcc or clang, but something smaller like chibicc or kefir or something) and that would probably give the best results (from an end-user perspective), but that would probably be a fairly major undertaking for a concept I’m not sure there’s really any interest in. I think it would be cool, which might be enough of a motivator, but there are only so many hours in a lifetime :)

The other extreme might be to ‘quickly’ hack together something that goes between the preprocessor and the main compiler, that just outputs the function instantiations wherever required. This might allow most ideas I’ve outlined in this post to be implemented (not sure about private/public) but it seems like a somewhat fragile approach and I’m a bit worried about the quality of error messages.

For now, I’ll just post this and maybe have a look at it every now and then and see if I can’t clear my head a bit.

#C