How to Implement Interfaces in C

If you’ve written a fair amount of C, chances are you’ve been struck by the desire to have some sort of polymorphism like the higher level languages do.

Maybe you want to have generic containers, like a linked list of generic elements, or maybe you want to have a function that takes in a polymorphic type, or anything in between. Chances are you’re somewhat frustrated at the lack of native polymorphism support.

Thankfully, polymorphism in C is nothing new, there are many articles, repositories and projects in general explaining, and using a virtual method table (vtable) based OOP polymorphism pattern. The code behind Linux, cpython implementation, and many other large scale C projects implement OOP through vtables — a pattern that is pretty common amongst the C community.

At the same time, if you’ve used this pattern, you may also know of its deficiencies.

• It’s not type safe, since type safety isn't a primary concern of this pattern.
• It inherently depends on unsafe casts.
• The semantics are ugly and hacky.
• It presents a fair bit of traps.
• Some implementations of this pattern break standard conformance and depend on implementation defined behavior. Usually, the rule they’re breaking is strict aliasing. Though, this issue really isn't hard to avoid. Cpython actually had this issue at one point, and fixed it later. But that’s not necessarily the only rule being broken. Many implementations will simply not use standard C, and instead, some extended implementation of C, such as gnuc.

There’s actually another drawback: What if you just don’t like OOP and prefer functional polymorphism rather than OOP inheritance? 

This article describes an extensible and practical design pattern you can use to achieve functional polymorphism in pure, standard C99 (or above). You can view an implementation and usage of this pattern in c-iterators, where I implement lazy, type safe, Rust-like iterators.

Drawing Inspiration From Type Classes to Create Interfaces in C

If you’re familiar with Haskell, you’re already familiar with type classes. A way to do ad-hoc polymorphism. Haskell is the main language that inspired me to come up with this design pattern. Although the end product really isn’t exactly like type classes, since type classes are inherently based on static dispatch, a feature impossible to implement in C in an extensible fashion, you’ll probably still find similarities along the way.

If you’re familiar with Rust, you’re also already familiar with type classes just with a different name and a bit less power: Traits. Once again, the end result of this pattern will not be exactly like traits, rather, they’d be more similar to trait objects. You know, dynamic traits, rust’s way of doing dynamic dispatch.

OOP also has a concept very similar to type classes and traits: interfaces.

Type classes, traits and interfaces are just ways of modeling polymorphism around actions, rather than objects. When I ask for a type that implements a type class (or a trait, or an interface), I’m asking for a type that can do certain things that fall under the type class. That’s all there is to it. Polymorphism based around abilities, not objects and object hierarchy.

More on Software EngineeringHow to Create a React Native Dropdown Menu

Type Class Pattern Goals in C

• Type safety through monomorphization and simple abstractions.
• Extensible by using dynamic dispatch, allowing them to be used in library APIs.
• Usable as completely normal types, allowing them to be used alongside existing container libraries such as C template library (CTL).
• Polymorphism is constrained around actions/abilities/functions, not objects.

Type Class Pattern Example

Before we go on to discussing and implementing the pattern itself, here's a tiny taste of what you can do with the pattern:

void print(Showable showable)
{
    char* s = showable.tc->show(showable.self);
    puts(s);
    free(s);
}

typedef enum
{
    holy,
    hand,
    grenade
} Antioch;

Antioch ant = holy;
Showable antsh = prep_antioch_show(&ant);

This is the Show type class. It describes the ability to turn a type into its string representation.

I’ve implemented Show for the Antioch type given above by defining prep_antioch_show. Now, any Antioch value can be turned into a Showable, which can then be used with generic functions working on Showable types.

How to Implement Type Class Patterns to Create Interfaces in C

We can finally talk about the design pattern itself. There are three core parts to this. I’ll demonstrate these three parts by implementing the Show type class mentioned above.

The typeclass Struct Definition

This is the struct containing the function pointers related to the type class. For Show, we’ll just be using the show function here, it takes in a value of the type for which Show is implemented (i.e., self) and returns a printable string.

typedef struct
{
    char* (*const show)(void* self);
} Show;

A simple struct containing the virtual functions. When the wrapper function is first called to convert a certain type to its type class instance, a type class struct of static storage duration is created with the function pointers for that specific type, a vtable of sorts. The pointer to this struct is then used in all type class instances. More on this will be discussed in the impl_ macro part.

The typeclass_instance struct definition

This is the concrete instance to be used as a type constraint. It should contain a pointer to the type class, and the self member containing the value to pass to the functions in the type class struct.

typedef struct
{
    void* self;
    Show const* tc;
} Showable;

The impl_ macro Used to Implement the Type Class

This macro is the real heavy lifter when it comes to type safety.

It takes in some information about the type you’re implementing a type class for, and the exact function implementations that will be used for that type and defines a function, which does the following:

• Takes in an argument of the type the implementation is for.
• Type checks the function implementations given. This is done by storing the given function implementations into function pointers of an exact and expected type.
• Initializes the type class struct to store these function pointers, with static storage duration.
• Creates and returns the type class instance, which stores a pointer to the aforementioned type class struct, and the function argument into the self member.

Following these rules, this is what impl_show would look like:

#define impl_show(T, Name, show_f)                                                                                     
    Showable Name(T x)                                                                                              
    {                                                                                                                  
        char* (*const show_)(T e) = (show_f);                                                                          
        (void)show_;                                                                                                   
        static Show const tc = {.show = (char* (*const)(void*))(show_f) };                                             
        return (Showable){.tc = &tc, .self = x};                                                                       
    }

It takes the show implementation as its third argument. In the function definition, it stores that impl in a variable of type char* (*const show_)(T e), which is the exact type it should be — T is the specific type the implementation is for. It must be a pointer type. Since it’s stored into void* self.

The (void)show_; line is to suppress the unused variable warning emitted by compilers, since show_ isn’t actually used. It’s only there for type checking purposes. These two type checking lines will be completely eliminated by any decent compiler.

Then, it simply defines a static type class and stores the function pointer inside. Then, it creates and returns the Showable struct, containing the x argument and a pointer to the type class struct.

Implementing Type Classes for Your Own Types

Once the type class and type class instance structs have been defined, all the user has to do is call the impl_ macro with their own type and the function implementations required for the type class. The declaration of the function defined by said macro can then be included in a header.

Here’s an example of implementing the previously defined Show type class for a very holy enum:

typedef enum
{
    holy,
    hand,
    grenade
} Antioch;

static inline char* strdup_(char const* x)
{
    char* s = malloc((strlen(x) + 1) * sizeof(*s));
    strcpy(s, x);
    return s;
}

/* The `show` function implementation for `Antioch*` */
static char* antioch_show(Antioch* x)
{
    /*
    Note: The `show` function of a `Showable` is expected to return a malloc'ed value
    The users of a generic `Showable` are expected to `free` the returned pointer from the function `show`.
    */
    switch (*x)
    {
        case holy:
            return strdup_("holy");
        case hand:
            return strdup_("hand");
        case grenade:
            return strdup_("grenade");
        default:
            return strdup_("breakfast cereal");
    }
}

/*
Implement the `Show` typeclass for the type `Antioch*`

This will define a function to convert a value of type `Antioch*` into a `Showable`, the function will be named `prep_antioch_show`

The `show` implementation used will be the `antioch_show` function
*/
impl_show(Antioch*, prep_antioch_show, antioch_show)

The impl_show macro here, simply translates to:

Showable prep_antioch_show(Antioch* x)
{
    char* (*const show_)(Antioch* e) = (show_f);
    (void)show_;
    static Show const tc = {.show = (char* (*const)(void*)(show_f) };
    return (Showable){.tc = &tc, .self = x};
}

Now, you can convert an Antioch into a Showable like so:

Antioch ant = holy;
Showable antsh = prep_antioch_show(&ant);

And this Showable will automatically dispatch to the antioch_show function whenever someone calls the show function inside it.

Let’s make a polymorphic function that works on Showables:

void print(Showable showable)
{
    char* s = showable.tc->show(showable.self);
    puts(s);
    free(s);
}

You can now easily print an Antioch with these abstractions:

Antioch ant = holy;
print(prep_antioch_show(&ant));

Where this really shines though, is when you have multiple types that implement Show — all of them can be used with print or any other function that works on a generic Showable.

Combining Multiple Type Classes in C

One of the core design goals of a type class is to be modular. A Show type class should only have actions directly related to showing, a Num type class should only have actions directly related to numerical operations. Unlike objects, that may contain many different methods of arbitrary relevance to each other.

This means that, more often than not, you’ll want a type that can do multiple different classes of actions. A type that implements multiple type classes.

You can model that pretty easily with this pattern:

/* Type constraint that requires both `Show` and `Enum` to be implemented */
typedef struct
{
    void* self;
    Show const* showtc;
    Enum const* enumtc;
} ShowableEnumerable;

#define impl_show_enum(T, Name, showimpl, enumimpl)                                                                    \
    ShowableEnumerable Name(T x)                                                                                       \
    {                                                                                                                  \
        Showable showable = showimpl(x);                                                                               \
        Enumerable enumerable = enumimpl(x);                                                                           \
        return (ShowableEnumerable){.showtc = showable.tc, .enumtc = enumerable.tc, .self = x};                        \
    }

Where Enum is also a type class defined like:

typedef struct
{
    size_t (*const from_enum)(void* self);
    void* (*const to_enum)(size_t x);
} Enum;

typedef struct
{
   void* self;
   Enum const* tc;
} Enumerable;

#define impl_enum(T, Name, from_enum_f, to_enum_f)                                                                     \
    Enumerable Name(T x)                                                                                               \
    {                                                                                                                  \
        size_t (*const from_enum_)(T e) = (from_enum_f);                                                               \
        T (*const to_enum_)(size_t x)   = (to_enum_f);                                                                 \
        (void)from_enum_;                                                                                              \
        (void)to_enum_;                                                                                                \
        static Enum const tc = {                                                                                       \
            .from_enum = (size_t (*const)(void*))(from_enum_f), .to_enum = (void* (*const)(size_t x))(to_enum_f)       \
        };                                                                                                             \
        return (Enumerable){.tc = &tc, .self = x};                                                                     \
    }

Essentially, you can have a struct that stores each of the type class pointers you want to combine, and the self member. The impl macro would also be very simple. It should simply define a function that puts the given value into ShowableEnumerable’s self, as well as use the impl functions to get the type class instances of that type.

With this, if you implemented Show for Antioch* and defined the function as prep_antioch_show, and also implemented Enum with the function name prep_antioch_enum, you could call impl_show_enum using:

impl_enum(Antioch*, prep_antioch_show_enum, prep_antioch_show, prep_antioch_enum)

The defined function would have the signature:

ShowableEnumerable prep_antioch_show_enum(Antioch* x);

You can now have functions that require their argument to implement multiple typeclasses:

void foo(ShowableEnumerable se)
{
    /* Use the enumerable abilities */
    size_t x = se.enumtc->from_enum(se.self);
    /* Use the showable abilities */
    char* s = se.showtc->show(se.self);
}

More on Software EngineeringPython: How to List Files in Directory

Implementing an Interface in C Example

With this pattern, I’ve implemented the lazy functional Iterators in pure C. It’s essentially modeled after Rust’s Iterator type class.

But that’s not all. A lazy Iterator isn’t complete without cool abstractions like take, drop, map, filter, etc. You can implement all of these abstractions using the same type class pattern.

It’s very similar to how rust does it. The take method, for example, simply returns a Take struct in Rust. This struct has its own Iterator implementation, which is what allows this whole abstraction to be completely lazy.

map is even cooler. Here’s an example of mapping a function over an Iterable, it:

/* Map an increment function over the iterable */
Iterable(int) mappedit = map_over(it, incr, int, int);

Where incr is:

/* A function that increments and returns the given integer */
static int incr(int x) { return x + 1; }

Once again, fully type safe and completely lazy. This map operation isn't performed until you explicitly iterate over the iterable. Which means, you can chain take_from and map_over and there won’t be multiple iterations, just one:

/* Map an increment function over the iterable */
Iterable(int) mappedit = map_over(it, incr, int, int);
/* Take, at most, the first 10 elements */
Iterable(int) mappedit10 = take_from(mappedit, 10, int);

The exact code to implement these, as well as thorough explanations of the semantics can be found in the c-iterators repository.

Frequently Asked Questions