Functional programming in C

This post/​pro­gram (as I’m writ­ing it in lit­er­ate style) is a con­tin­u­a­tion of my pre­vi­ous posts about func­tional pro­gram­ming in C++. I promise I’m not go­ing to post about do­ing it in as­sem­bly lan­guage (I think) ….

I came to like the sim­plic­ity of C very much and got in­ter­ested in how you could write func­tional code in it.

There is one ir­ri­tat­ing thing about C as a vi­able pro­gram­ming lan­guage. Microsoft’s com­piler sup­port is not good. It just sup­ports ANSI C, not C99 or C11. So, if you want to use more mod­ern idy­oms, you got to use gcc or clang. In this post I as­sume you use gcc. I will point out the gcc spe­cific ex­ten­sions.

Also, the C stan­dard li­brary is pretty lim­ited, so I de­cided to use GLib to com­ple­ment it. I also cre­ated some macros to sim­plify the syn­tax. I never un­der­stood why peo­ple like tem­plates and think macros are evil. It takes me all of 5 min­utes to do a -E on GCC to de­bug the re­sult of a macro ex­pan­sion. With tem­plates, well, that’s dif­fer­ent.

So, in sum­mary, this post is about how you can write func­tional code in C, per­haps with some gcc ex­ten­sions and cer­tainly with some macro tricks. Let’s call it funkyC (thanks Ian ). I’m go­ing to show how to use it first. Next post I’m go­ing to show how it’s im­ple­mented.

Discriminated unions in C

With a bit of macro magic, you can get a de­cent look­ing dis­crim­i­nated union syn­tax. First we need to in­clude the cor­rect head­ers. lu­tils.h is where all the macros are de­fined.

#include <glib.h>
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
#include <signal.h>
#include <string.h>

#include "lutils.h"

Then you can de­clare a dis­crim­i­nated union with the syn­tax be­low. It suf­fers from two prob­lems: repet­ing the list of pos­si­ble types in union_decl and re­peat­ing the name of the dis­crim­i­nated union in union_end. Perhaps there is a way to avoid that, but I haven’t found it.

The syn­tax for the union_­type call is the same as you would use in­side a struct de­c­la­ra­tion. We’ll see how this works when we look at lu­tils.h.

union_decl  (Car, Volvo, Fiat, Ferrari)
union_type      (Volvo,     int x; double y;)
union_type      (Fiat,      char* brand, *model;)
union_type      (Ferrari,   char* brand, *model;)
union_end   (Car)

We can cre­ate a Car ei­ther on the stack, as be­low, or on the heap and we can set its value with union_set.

Notice the us­age of the new struct con­struc­tion syn­tax to sim­u­late op­tional named pa­ra­me­ters in C. I would pre­fer not to have a dot at the start of the name, but over­all it is beau­ti­ful (if I can say that my­self).

static void printCar(Car*);

static void testUnion() {
    Car c;

    union_set   (&c, Volvo, .x = 3, .y = 4);
    printCar    (&c);
    union_set   (&c, Ferrari, .brand = "Ferrari");
    printCar    (&c);
    union_set   (&c, Fiat, .brand = "Fiat", .model = "234");
    printCar    (&c);
}

You can then ac­cess val­ues in­side your dis­crim­i­nated union with nor­mal if state­ments.

static void testCar(Car*, char const *);

static void printCar(Car* c) {

    if(c->kind == Volvo) {
        int x = c->Volvo.x;
        g_assert_cmpint(x, ==, 3);
    }

Or per­haps you want the equiv­a­lent of a match state­ment in F# (aka an ex­pres­sion that re­turns a value based on the type of the dis­crim­i­nated union). Notice that, as log­i­cal, all the ex­pres­sions need to re­turn the same type. That’s why union_­fail takes a value of the ex­pres­sion type.

    char temp[40];

    char* value =   c->kind == Volvo    ?   itoa(c->Volvo.x, temp, 10)
                  : c->kind == Ferrari  ?   (void)c->Ferrari.model, c->Ferrari.brand
                  : c->kind == Fiat     ?   c->Fiat.model
                                        :   union_fail("Not a valid car type");

If you are will­ing to be gcc spe­cific, then your ex­pres­sion can be com­prised of mul­ti­ple state­ments, of which the last one re­turns the value of the ex­pres­sion. This al­lows a much more flex­i­ble syn­tax for your match clauses.

#ifdef __GNUC__

    value       =   c->kind == Volvo    ? ({
                                            struct Volvo* it = &c->Volvo;
                                            itoa(it->x, temp, 10);
                                          })
                  : c->kind == Ferrari  ?   (void)c->Ferrari.model, c->Ferrari.brand
                  : c->kind == Fiat     ?   c->Fiat.model
                                        :   union_fail("Not a valid car type");

    testCar(c, value);

#endif // __GNUC__
}

We then use the su­per sim­ple test frame­work in GLib to make sure that it all works as ex­pected …

static void testCar(Car* c, char const * value) {
    if(c->kind == Volvo) g_assert_cmpstr(value, ==, "3");
    else if (c->kind == Fiat) g_assert_cmpstr(value, ==, "234");
    else if (c->kind == Ferrari) g_assert_cmpstr(value, ==, "Ferrari");
    else g_assert_not_reached();

}

Nested functions and lambda variables

GCC has many other cool ex­ten­sions. A very sim­ple one is nested func­tions. It al­lows you to nest func­tions :-) Look at the de­f­i­n­i­tion of doA and f2 in the func­tion be­low. Putting to­gether nested func­tions and block state­ment ex­pres­sions al­lows you, with some macro magic, to de­fine lambda func­tions in your code (from here ).

Remember that lamb­das (aka nested func­tions) are al­lo­cated on the stack. They are very fast, but you can­not store their pointer into a gloal table (unless such table is used while the stack for this func­tion is alive).

In such cases, you have to cre­ate a proper func­tion. But for the other 90% of use cases, they work pretty well. They are lamb­das in the spirit of C: very fast, but er­ror prone …

#ifdef __GNUC__

static void testLambda() {

    typedef int (*aFunc) (int);

    aFunc doA(aFunc f){

        int k(int i) {
            return f(i) + 3;
        }
        return k;
    }

    int clos = 2;

    int f2 (int i) {return i;}
    aFunc b = doA(lambda (int, (int p) {return p + clos;}));

    g_assert_cmpint(b(3), ==, 8);
}

Automatic cleanup of local variables

This is not a func­tional topic per se, but some­thing that al­ways an­noyed me tremen­dously about C. The fact that you can­not de­fine the equiv­a­lent of the us­ing state­ment in C#, or de­struc­tors in C++. Well, now you can. Or not?

Again, if you are will­ing to be GCC spe­cific, you can use an at­tribute (more on this in the up­com­ing im­ple­men­ta­tion post) to as­so­ci­ate a cleanup func­tion that gets called when your vari­able goes out of scope. In this case, I wrapped the free case in a nice look­ing macro.

But that does­n’t re­ally work. You would cer­tainly want such func­tion to be called on any kind of exit from the en­clos­ing scope (aka via exit(), abort() or longjmp()). Alas, that does­n’t hap­pen.

This re­duces the use­ful­ness of this mech­a­nism tremen­dously. Probably too much in that it lulls you into a false sense of se­cu­rity. You still need to free your re­sources in the er­ror path of your ap­pli­ca­tion.

static void testAutomaticCleanup() {
    char* stack_alloc() {
        auto_free char* b = g_malloc(10000);
        memset(b, '#', 10000);
        return b;
    };

    char * c = stack_alloc();
    g_assert(*c != '#');
}

#endif

Data structures

GLib comes with a vast li­brary of data struc­tures to use, not too dif­fer­ent from the .NET frame­work or Java. For ex­am­ple, be­low you have a sin­gle linked list …

static void testGLib() {
     GSList* list = NULL;

     list = g_slist_append(list, "Three");
     list = g_slist_prepend(list, "first");
     g_assert_cmpint(g_slist_length(list), ==, 2);

     list = g_slist_remove(list, "first");
     g_assert_cmpint(g_slist_length(list), ==, 1);

     g_slist_free(list);
}

Wrapping up

There you go, ris­ing the level of ab­strac­tion of C, still keep­ing it very fast (if you are will­ing to be gcc bound).

There are other fea­tures in func­tional pro­gram­ming lan­guages that are not in this post. Maybe I’ll get around to macro my way into them even­tu­ally, maybe not.

In the next post we’ll talk about how all of this is im­ple­mented. Below is the code for run­ning the test­cases.

int runTests(int argc, char* argv[]) {
    g_test_init(&argc, &argv, NULL);

    if(g_test_quick()) {
        g_test_add_func("/utils/automatic_cleanup", testAutomaticCleanup);
        g_test_add_func("/utils/lambda", testLambda);
        g_test_add_func("/utils/Union", testUnion);
        g_test_add_func("/utils/SList", testGLib);
    }

    return g_test_run();
}

int main(int argc, char *argv[]) {
    return runTests(argc, argv);
}

Tags

• C
• FUNCTIONAL