Implementing Interfaces in C
Tags: c, tutorial, functional, polymorphism
Published: 2021-05-16 13:33:31

*Note: An extended and updated version of this demonstration can be found at [typeclass-interface-pattern](https://github.com/TotallyNotChase/typeclass-interface-pattern).*

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](https://github.com/TotallyNotChase/c-iterators), where I implement [lazy](https://en.wikipedia.org/wiki/Lazy_evaluation), type safe, rust-like iterators.

# Brief
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** (i.e 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 (aka 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, arguably, very 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](https://stackoverflow.com/questions/98650/what-is-the-strict-aliasing-rule). Though, this issue really isn't hard to avoid. CPython actually had this issue at one point, [and fixed later](https://www.python.org/dev/peps/pep-3123/). 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.

Oh, there's actually another drawback - but this one's totally subjective and doesn't contribute anything to the actual conversation- what if you just don't like OOP and prefer functional polymorphism rather than OOP inheritance? Well, I'd fall under that category :)

# Enter Type Classes
If you're familiar with [Haskell](https://www.haskell.org/), you're already familiar with [Type Classes](https://en.wikipedia.org/wiki/Type_class). 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 the similarities along the way.

If you're familiar with [Rust](https://www.rust-lang.org/), you're also already familiar with type classes! Just with a different name and a bit less power- [Traits](https://doc.rust-lang.org/rust-by-example/trait.html). 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](https://doc.rust-lang.org/rust-by-example/trait/dyn.html), rust's way of doing dynamic dispatch.

If you're not familiar with a functional language, but rather OOP languages- no worries! OOP also has a concept very similar to typeclasses and traits- [Interfaces](https://docs.oracle.com/javase/tutorial/java/concepts/interface.html).

If you aren't familiar with any of the concepts mentioned above, that's totally fine! The concepts aren't actually that complicated from a base level view. Typeclasses, Traits, Interfaces are just ways of modeling polymorphism around *actions*, rather than *objects*. When I ask for a type that implements a typeclass (or a trait, or an interface) - I'm asking for a type that *can do certain things that fall under the typeclass*. That's all there is to it. Polymorphism based around abilities, not objects and object hierarchy.

# Goals of the Typeclass Pattern
* Type safety through monomorphization and simple abstractions
* Extensible by using [dynamic dispatch](https://en.wikipedia.org/wiki/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 [CTL](https://github.com/glouw/ctl) (C template Library).
* Polymorphism constrained around actions/abilities/functions, not objects

# A Small Taste
Before we go on to discussing and implementing the pattern itself, here's a tiny taste of what you can do with the pattern-
```c
void print(Showable showable)
{
    char* s = showable.tc->show(showable.self);
    puts(s);
    free(s);
}

typedef enum
{
    holy,
    hand,
    grenade
} Antioch;
```
```c
Antioch ant = holy;
Showable antsh = prep_antioch_show(&ant);
```
This is the [`Show`](https://hackage.haskell.org/package/base-4.15.0.0/docs/Text-Show.html#t:Show) typeclass. 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.

# The Typeclass Pattern
We can finally talk about the design pattern itself. There's 3 core parts to this. I'll demonstrate these 3 parts by implementing the [`Show`](https://hackage.haskell.org/package/base-4.15.0.0/docs/Text-Show.html#t:Show) typeclass mentioned above.

## The `typeclass` struct definition
This is the struct containing the function pointers related to the typeclass. 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.
```c
typedef struct
{
    char* (*const show)(void* self);
} Show;
```
A simple struct containing the virtual function(s). When the wrapper function is first called (to convert a certain type to its typeclass instance), a typeclass 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 typeclass 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 typeclass, and the `self` member containing the value to pass to the functions in the typeclass struct.
```c
typedef struct
{
    void* self;
    Show const* tc;
} Showable;
```
## The `impl_` macro used to implement the typeclass
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 typeclass 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 typeclass struct to store these function pointers, with static storage duration
  * Creates and returns the typeclass instance, which stores a pointer to the aforementioned typeclass struct, and the function argument into the `self` member.

Following these rules, this is what `impl_show` would look like-
```c
#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 typechecking purposes. These 2 typechecking lines will be completely eliminated by any decent compiler.

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

# Implementing Typeclasses for your own types!
Once the typeclass and typeclass instance structs have been defined, all the user has to do is call the `impl_` macro with their own type and the function implementation(s) required for the typeclass. 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` typeclass for a very holy enum-
```c
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-
```c
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-
```c
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.

Great! Let's make a polymorphic function that works on `Showable`s-
```c
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-
```c
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 Typeclasses
One of the core design goals of a typeclass is to be modular. A `Show` typeclass should only have actions directly related to "showing", a `Num` typeclass 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 typeclasses.

You can model that pretty easily with this pattern-
```c
/* 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`](https://hackage.haskell.org/package/base-4.15.0.0/docs/Prelude.html#t:Enum) is also a typeclass defined like-
```c
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 typeclass 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 typeclass 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-
```c
impl_enum(Antioch*, prep_antioch_show_enum, prep_antioch_show, prep_antioch_enum)
```
The defined function would have the signature-
```c
ShowableEnumerable prep_antioch_show_enum(Antioch* x);
```

That's it!

You can now have functions that require their argument to implement multiple typeclasses-
```c
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);
}
```

# Real World Usage
With this pattern, I've implemented the lazy functional `Iterator`s in pure C. It's essentially modeled after Rust's [`Iterator`](https://doc.rust-lang.org/core/iter/trait.Iterator.html) typeclass.

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 Typeclass pattern**.

It's very similar to how rust does it, the `take` method, for example, simply returns a [`Take`](https://doc.rust-lang.org/core/iter/struct.Take.html) 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`-
```c
/* Map an increment function over the iterable */
Iterable(int) mappedit = map_over(it, incr, int, int);
```
Where `incr` is-
```c
/* 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!
```c
/* 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](https://github.com/TotallyNotChase/c-iterators) repo.