Generic* tuples in C

A day ago I was asked if it’s possible in C to make some preprocessor macro that will create a tuple object from something like tuple(a, b, c). I’m not writing in C actively anymore, since I switched to Clojure some years ago, but I still like to poke with C from time to time. I’ve thought to myself, that this should be doable via macros, and decided to try it out. However, the C preprocessor is not the best way to write macros, yet unfortunately, it’s our only option.

So what is our goal here? A tuple is usually a fixed-size data structure that (often) can be indexed, and can contain elements of various types. And because of that, it may be a bit tricky to do it in C because C doesn’t have a lot of tools for deducing type or generating code. So in theory, something like a generic fixed-size array that can store elements of an arbitrary type will work fine. And the only needed is to make a proper container for elements and write some macros to automate things.

I’ve marked “generic” in the title with an asterisk, because, well, it’s C, there is no support for generics aside from the _Generic dispatcher and, well, macro concatenation. In this post, I’ll explain two solutions I’ve come up with, but both have their own constraints. The first implementation below kinda allows for any type to be used as an element but requires adding new types every time you want something else. The second implementation is more approachable, as it requires you to pre-define the type of the resulting tuple before you could use it. So it’s not like true generics, but (I think) a close approximation.

Take 1 - Union structs

Luckily for me, I’ve already experimented with “recursive” macros in C in my previous work, so I knew what to do. In theory. My initial thought was to generate an array of union structs. Each struct would contain a union, which would hold all possible types, and a type field that would just tell us what type this particular union is.

#pragma once

enum TupleItemType {
    LONG,
    DOUBLE,
    STRING,
};

struct TupleItem {
    enum TupleItemType type;
    char               pad[4];
    union {
        long   i32;
        double f64;
        char * string;
    } value;
};

For now, I’ve decided to go with only three types, as it is easy to add more. I’ve also created a Tuple struct, that holds a pointer to an array of TupleItem and its size:

struct Tuple {
    unsigned int       size;
    char               pad[4];
    struct TupleItem * tuple;
};

With that we can try to use it:

#include <stdio.h>
#include "tuple.h"

void pprint_tuple_item(struct TupleItem * x);
void pprint_tuple_item(struct TupleItem * x) {
    switch (x->type) {
        case LONG: printf("%ld", x->value.i32); break;
        case DOUBLE: printf("%f", x->value.f64); break;
        case STRING: printf("\"%s\"", x->value.string); break;
    }
}

void pprint_tuple(struct Tuple * t);
void pprint_tuple(struct Tuple * t) {
    printf("{");
    for (unsigned int i = 0; i < t->size - 1; i++) {
        pprint_tuple_item(&(t->tuple[i]));
        printf(", ");
    }
    pprint_tuple_item(&t->tuple[t->size - 1]);
    printf("}\n");
}

int main(void) {
    struct TupleItem items[] = {
        (struct TupleItem){.type = LONG, .value.i32 = 42},
        (struct TupleItem){.type = DOUBLE, .value.f64 = 22./7},
        (struct TupleItem){.type = STRING, .value.string = "foobar"},
    };
    struct Tuple tuple = {.tuple = items, .size = 3};
    pprint_tuple(&tuple);
    return 0;
}

Now, I know, that I shouldn’t create and pass arrays like that, but for now it’ll do. With these helper functions in place, compiling and running this code yields an expected result:

clang -MM --std=c99 -Wpedantic -Wextra -Weverything -Wall  *.c > .depend
clang -o main.o -c main.c --std=c99 -Wpedantic -Wextra -Weverything -Wall
clang -o bin/tuple main.o --std=c99 -Wpedantic -Wextra -Weverything -Wall
{42, 3.142857, "foobar"}

However, the original goal was to be able to say tuple(42, 22./7, "foobar") and be done with it. So it’s the macro time!

To solve this, we need a way to generate the array from above at preprocessor expansion time. This is not an easy task, as the C preprocessor doesn’t have any way to iterate an arbitrary amount of arguments. However, it’s certainly possible to iterate a known amount of arguments. So our task boils down to pre-defining enough preprocessor stages to support a certain amount of arguments. This is still a tricky task though.

First, we’ll need a way to automatically detect the type of argument to set it to the .type field. This can be done either with extremely tricky and clunky use of __builtin_types_compatible_p or via C11 new _Generic construct. I’ve decided to go with _Generic, because it is much less code, and compile-time if is not our best friend when generating code:

#define tuple_dispatch(x)                       \
    _Generic((x),                               \
             char*: make_string,                \
             double: make_double,               \
             int: make_long,                    \
             long: make_long)(x)

struct TupleItem make_long(long);
struct TupleItem make_double(double);
struct TupleItem make_string(char *);

struct TupleItem make_long(long x) {
    return (struct TupleItem){.value.i32 = x, .type = LONG};
}

struct TupleItem make_double(double x) {
    return (struct TupleItem){.value.f64 = x, .type = DOUBLE};
}

struct TupleItem make_string(char * x) {
    return (struct TupleItem){.value.string = x, .type = STRING};
}

This macro will expand at compile time to a correct helper function, creating our desired object. Now we need to create a loop over all arguments of a variadic macro:

#define CONCATENATE(arg1, arg2) CONCATENATE1(arg1, arg2)
#define CONCATENATE1(arg1, arg2) CONCATENATE2(arg1, arg2)
#define CONCATENATE2(arg1, arg2) arg1##arg2

#define FOR_EACH_0(what, x) what(x)
#define FOR_EACH_1(what, x, ...) what(x), FOR_EACH_0(what, __VA_ARGS__)
#define FOR_EACH_2(what, x, ...) what(x), FOR_EACH_1(what, __VA_ARGS__)
#define FOR_EACH_3(what, x, ...) what(x), FOR_EACH_2(what, __VA_ARGS__)

#define TUPLE_EACH_NARG_(...)                   \
    CHOOSER(__VA_ARGS__, 3, 2, 1, 0)
#define CHOOSER(_0, _1, _2, _3, N, ...)         \
    N

#define TUPLE_EACH_(N, what, ...) CONCATENATE(FOR_EACH_, N)(what, __VA_ARGS__)
#define TUPLE_(what, ...)                                           \
    TUPLE_EACH_(TUPLE_EACH_NARG_(__VA_ARGS__), what, __VA_ARGS__)

Here, I create an iteration over four arguments at most. It’s easy to add more, just create more #define FOR_EACH_<N>(what, x, ...) what(x), FOR_EACH_<N-1>(what, __VA_ARGS__) definitions, and add respecting numbers to TUPLE_EACH_NARG_ and CHOOSER accordingly. This will allow us to loop in a functional style, applying a what macro to each argument of a vararg macro. Here’s how we do it:

#include <malloc.h>

#define tuple(...)                                                          \
    __extension__({                                                         \
        unsigned int       size  = TUPLE_EACH_NARG_(0, __VA_ARGS__);        \
        struct TupleItem   tmp[] = {TUPLE_(tuple_dispatch, __VA_ARGS__)};   \
        struct TupleItem * arr   = malloc(sizeof(struct TupleItem) * size); \
        for (unsigned int i = 0; i < size; i++)                             \
            arr[i] = tmp[i];                                                \
        (struct Tuple){.tuple = arr, .size = size};                         \
    })

Unfortunately, this uses a statement expression extension from GCC, but luckily for me, clang supports it, and I don’t care much about MSVC. Here, we create an array tmp with the TUPLE_ macro, that calls tuple_dispatch over every argument in __VA_ARGS__. Let’s use it:

#include "tuple.h"

// ------8<-------

int main(void) {
    struct Tuple tuple = tuple(42, 22./7, "foobar");
    pprint_tuple(&tuple);
    return 0;
}

This, again gives us the same result, as before, however, reduces all boilerplate to a single tuple call. Let’s see what this expands to when we compile it with gcc -E main.c:

int main(void) {
    struct Tuple tuple = __extension__({
            unsigned int size = 3;
            struct TupleItem tmp[] = {
                _Generic((42), char*: make_string, double: make_double, int: make_long, long: make_long)(42),
                _Generic((22./7), char*: make_string, double: make_double, int: make_long, long: make_long)(22./7),
                _Generic(("foobar"), char*: make_string, double: make_double, int: make_long, long: make_long)("foobar")
            };
            struct TupleItem * arr = malloc(sizeof(struct TupleItem) * size);
            for (unsigned int i = 0; i < size; i++)
                arr[i] = tmp[i];
            (struct Tuple){.tuple = arr, .size = size};
        });
    pprint_tuple(&tuple);
    return 0;
}

As I’ve mentioned, _Generic will go away at compilation time and will leave invocations of respecting functions. We’ve achieved our goal, but this solution has some problems.

First, obviously _Generic and ({}) may not be available in a certain compiler, or when using an older C standard. So the portability of this code is not very good. Another problem is that the definitions inside the ({}) block may shadow outer definitions. This may not be a problem in this example, but a thing to remember. A compiler actually will warn you about it.

Take 2 - struct generation

But then it hit me. Why do we even need an array here? All we really needed was this:

#include <stdio.h>

struct Tuple {
    int _0;
    double _1;
    char* _2;
};

#define tuple(...) (struct Tuple){__VA_ARGS__}

int main() {
    struct Tuple vaiv = tuple(42, 22./7, "foo bar");
    printf("{%d, %f, %s}\n", vaiv._0, vaiv._1, vaiv._2);
    return 0;
}

This is still a tuple, right? Well, some languages have this kind of tuple access, so I think it’s OK. Examples would be Rust and Zig. Rust has this kind of field access, and Zig just uses anonymous structs with integer fields. So the only challenge here is to generate such a struct. Fortunately, the process is extremely similar:

#pragma once

#define TYPE_DISPATCH(X, N) X _##N;
#define VALUE_DISPATCH(X, N) ._##N = (X),

#define EXPAND(X) X

#define CONCATENATE(A, B) CONCATENATE1(A, B)
#define CONCATENATE1(A, B) CONCATENATE2(A, B)
#define CONCATENATE2(A, B) A##B

#define FOR_EACH_0(WHAT, X) WHAT(X, 0)
#define FOR_EACH_1(WHAT, X, ...) WHAT(X, 1) FOR_EACH_0(WHAT, __VA_ARGS__)
#define FOR_EACH_2(WHAT, X, ...) WHAT(X, 2) FOR_EACH_1(WHAT, __VA_ARGS__)
#define FOR_EACH_3(WHAT, X, ...) WHAT(X, 3) FOR_EACH_2(WHAT, __VA_ARGS__)
// define more if you need more elements in the tuple

#define TUPLE_EACH_NARG_(...) CHOOSER(__VA_ARGS__, 3, 2, 1, 0)
#define CHOOSER(_0, _1, _2, _3, N, ...) N

#define REVERSE_1(X) X
#define REVERSE_2(X, Y) Y, X
#define REVERSE_3(X, ...) EXPAND(REVERSE_2(__VA_ARGS__)), X
#define REVERSE_4(X, ...) EXPAND(REVERSE_3(__VA_ARGS__)), X
#define REVERSE_(N, ...) EXPAND(REVERSE_##N(__VA_ARGS__))
#define REVERSE(N, ...) REVERSE_(N, __VA_ARGS__)
// also define more if you need more elements

#define TUPLE_EACH_(N, WHAT, ...) CONCATENATE(FOR_EACH_, N)(WHAT, __VA_ARGS__)
#define TUPLE_(WHAT, ...) \
    TUPLE_EACH_(TUPLE_EACH_NARG_(__VA_ARGS__), WHAT, __VA_ARGS__)

#define tuple(...)                                                     \
    {                                                                  \
        .len = TUPLE_EACH_NARG_(_, __VA_ARGS__),                       \
        TUPLE_(VALUE_DISPATCH,                                         \
               REVERSE(TUPLE_EACH_NARG_(_, __VA_ARGS__), __VA_ARGS__)) \
    }

#define deftuple(...)                                                  \
    struct {                                                           \
        int len;                                                       \
        TUPLE_(TYPE_DISPATCH,                                          \
               REVERSE(TUPLE_EACH_NARG_(_, __VA_ARGS__), __VA_ARGS__)) \
    }

I’ve limited the macro to support only four-element tuples, as it can be quite ridiculous with more elements than that.

#include <stdio.h>
#include "tuple.h"

int main() {
    deftuple(int, double, char*) vaiv = tuple(42, 22./7, "foo bar");
    printf("{%d, %f, %s}\n", vaiv._0, vaiv._1, vaiv._2);
    return 0;
}

The tricky part here was to realize how to reverse the argument list. The problem here was that our FOR_EACH_ macro goes forward the argument list, but backward in the sense that it starts at some arbitrary FOR_EACH_<N> and continues until it reaches FOR_EACH_0. So when generating for the struct fields, I had to reverse the arguments before the generation, so the _<N> fields matched. For a better understanding, here’s the result of running only the preprocessor with gcc -E main.c:

int main() {
    struct { int len; char* _2; double _1; int _0; } vaiv = { .len = 3, ._2 = ("foo bar"), ._1 = (22./7), ._0 = (42), };
    printf("{%d, %f, %s}\n", vaiv._0, vaiv._1, vaiv._2);
    return 0;
}

Note that while we’ve defined our tuple as (int, double, char*), the order in the struct is in reverse: {int len; char* _2; double _1; int _0;}. And because of that we now can use the initializer-list, and still access args in the correct order. The same happens when we create the tuple itself: tuple(42, 22./7, "foo bar") becomes {.len=3, ._2 = ("foo bar"), ._1 = (22./7), ._0 = (42),}.

Conclusion

So here are two ways of creating generic tuples in C. I understand that this may be not the most practical or even optimal way of creating tuples in C, but the last one is appealing to me because it’s a fully compile-time thing. And it was a nice puzzle, especially after two years of not using C almost at all.

I like the second solution more because it’s just an tuple.h file, without tuple.c counterpart as with the first solution. And unlike the first solution, you don’t need to modify any code to use it, only if you need a tuple with more arguments than supported by macros, but it’s a common thing in both solutions. There’s probably a nicer way to generate such iterations, but I’m not familiar with this one.

Though, unlike the first implementation, the second one doesn’t allow iteration over the tuple in any form, as it’s not really a sequence anymore, so the len field may be a bit pointless. In statically typed languages iteration over a tuple can be hard, because each element can have a different type. It was possible with the first implementation because we’ve explicitly stored tuple item type in the tuple item itself, so we had to implement “generic” functions that would know how to work with a given element, but the dispatch happened at runtime. Rust, for example, doesn’t allow iteration over tuples, as it doesn’t even guarantee the order of elements in the tuple. Zig allows iteration, but only at compile-time, as far as I understand it.

Speaking of Zig, right now I’m learning it, and it actually brings me a lot of memories about learning C, and overall feels great. In this blog, I’ve already ranted about C mostly its macros and syntax, and I still think most things I’ve said are valid. E.g. the tuple macro above suffers from the requirement to typedef compound types, like structs or long type things.

And learning Zig now feels like learning a better C. A lot of patterns are probably doable in both languages, given how minimalist both of those are, but Zig almost always feels much clearer.

Consider an amateur attempt at creating Cons cells in Zig, and then doing mostly the same thing in C via macros:

(Posted it as an image, because this post already has way too much code. I’ve described how this kind of generics works in Macros section of the already mentioned C rant.)

Well, this is another approach to generic functions in C, and it’s not that hard to write such macros - just write it as an ordinary code, then select a type you need to be generic and make a few text substitutions with your editor of choice. But while this is doable, and works, my main point is that Zig feels a lot more clear, and achieves the same thing, I believe via mostly the same ways. Being more clear is an obvious benefit, and C code here has a nasty bug, kudos if you’ll manage to spot it in this macro mess.

I’m bringing Zig here, not because it has support for tuples or a more clear syntax but because even though C gets new standards, it still feels like it’s standing in place, and nothing really changes over the years. And Zig, while young, has quite ambitious goals of both supporting C ABI and competing with C without depending on it. If you write in C, I encourage you to go and try Zig for a bit - it has a clear vision of a small system language. Another interesting thing on the horizon is Drew DeVault’s secret system language. I have not yet looked at it, but from what I’ve read in the blog posts, it seems quite interesting. We’ll see how it compares to Zig when it’ll becomes available.

Going back to the main topic of this post, I think there are more robust ways of doing this. Probably a lot of dynamically typed languages that are implemented in C are doing something like that, mainly for implementing a generic type to pass around. I’m yet to try my solution in practice, and as I’ve mentioned, this probably won’t work in its current state. But I hope it was at least an example of interesting use of C macros. And now, in case I’ll forget how to do this macro iteration, I’ll have a place to look :)