Functional C Programming: Higher order functions, closures, lifted types…

TL;DR

tl;dr You can implement many functional programming techniques in C.  Map, filter, closures, and lifted types are all very possible.  Function pointers are worth understanding. Code.

template

Functional C

I was having a conversation with a lover of Haskell who lamented C’s lack of functional constructs.  Eager to show him that C does in fact support functional programming, i decided to write a small, functional C library.  I posted the code here and hacker news seems to have enjoyed it.  

The following is a brief explanation about how to go about building a functional C library.  It walks through the basics and leaves the implementation details to the code itself.  Here is a more technical README.

Function Pointers

The basis of writing functional C is an understanding of the function pointer.  A good rule of thumb in C is that everything is and/or has a memory location (think & operator).  Functions are no different; they are locations of sequences of instructions that reside in memory.  Since this is the case, they can passed into another function just like any other memory location.   Anyone who has used qsort or signals in C has used a function pointer before, to specify a comparison or a handler function, respectively.

e.g. the standard libraries’ qsort function takes a function pointer names compar:

void qsort ( void * base, 
             size_t num, 
             size_t size, 
             int ( * compar ) ( const void *, const void * ) );

Lists, Lists, Lists…

Once you can pass functions as values, the next step is picking a data structures to store sequences of things.  Lists are perfectly suited to this task. Haskell, ML, & Lisp all use lists.

Our list structure is pretty simple:

struct list {
  void *val;
  list *next;
};

Map, Filter & Other High Order Functions

With function pointers and lists, its time to define some simple higher order functions.

Map applies a function to a list of items, one by one, and returns the resulting list.

//yeah, it's map; args is an extra pointer that is passed as the val to each 
//invocation of fn.
list *
map(list *l, void *(*fn)(void *, void *), void *args)

Filter takes a list and returns a list of only those items that return true when passed into the function.

//yup, and filter too
list *
filter(list *l, bool (*fn)(void *, void *), void *args)

Closures

To close a function, one binds a function to environment that it is to be executed in.  E.g. if i have a function that takes in two integers, a and b, and returns their sum, i can bind 2 to the value b to get a new function, called addtwo, that adds two to any number i put into it.

To implement closures, we need a few things:

  1. A way to store environments and their variables
  2. A way to bind environments to functions to create closures
  3. A way to call a closure and execute its function within its environment

To store our closures, we use lists of environment variables that store each value along with its size in memory.  To store a closure, we’ll store a function pointer and an environment.

struct closure {
  void *(*fn)(list *);
  list *env;
};

struct envobj {
  void *val;
  ssize_t size;
};

Environments store variables with their size metadata in order to permit polymorphic C functions.  I’ll write more about this later.  To simplifying lifting a standard variable into an environment for binding to a function, i’ve written some helper functions:

//returns a lifted integer
envobj *
liftint(int a);

//this transforms a list into an environment
list *
liftlist(list *l, ssize_t s)

These lifted types can be bound a function that takes a list of arguments as its input via the bind function:

closure *
bind(closure *c, void *(*fn)(list *), envobj *env);

Finally, with a closure obtained, we can call the closure in its environment with the call function:

void *
call(closure *c, envobj *env);

Conclusion

Putting everything all together now:

int
main(int argc, char **argv) {
  //LET THE MEMORY LEAKING BEGIN!!!
  //range returns a list of integers from start to finish
  iter(map(range(0, 10), dbl,NULL), printint, NULL);
  iter(filter(range(0, 10), odd, NULL), printint, NULL); 

  //Darker magic?  Not really...
  closure *addtwo = bind(NULL, add, liftint(2));
  closure *addten = bind(NULL, add, liftint(10));

  printf("%d\n", *(int *)call(addtwo, liftint(3)));
  printf("%d\n", *(int *)call(addten, liftint(3)));

  //all together now, with pseudo types everywhere woopie!!!
  list *vars = liftlist(range(0, 10), sizeof(int));
  list *res = lmap(vars, addtwo);
  iter(res, printint, NULL);

  exit(0);
}

Lambda functions and memory management are two things that i am working on.

As a disclaimer, i don’t feel that you should program this way.  This is the wrong way to do C programming.  However, it’s good to make sure that you understand function pointers.  They are useful.

 

11 thoughts on “Functional C Programming: Higher order functions, closures, lifted types…

  1. Lisp Hacker

    congratulations, you’ve written a minimal runtime for lisp. Now all you need to do is write a lisp parser and interpreter and you’ll be saving yourself lots of keystrokes and cognitive load in the future!

    Reply
  2. Pekka

    You know, you can omit the difficult function pointer syntax when declaring or defining functions that take function pointer parameters. If you declare them to take functions with the usual C function syntax, these params decay naturally to function pointers and your code will look a little less cluttered.

    Here is an example that compiles with GCC -Wall without warnings: http://pastebin.com/MsJLY22j

    Reply
  3. Caruccio

    Can’t you people see? Every single computer program ends as a set of assembly instructions. If language “X” is capaple of doing “Y”, thus C (the language) surely can do it too. Maybe not as easy, but it can.

    Reply
  4. guest

    I think the most idiomatic way of doing “functional programming in C” is just to lambda lift non-toplevel functions and create structs to represent the closure bindings. Parametric polymorphism can be implemented either through the opaque (void *) trick you use here, or by specializing data-types and functions to the types which are concretely instantiated in the program.

    The advantage being that it’s more flexible than using a pre-built library, and you retain the option of doing memory management for the heap-allocated stuff, instead of just letting memory leak.

    You can also refrain from using function pointers entirely (since these are slow in modern computer architectures), but in this case you will generally need to do defunctionalization as well: a call to a first-class function turns into a call to an apply() procedure which takes in a type-tagged union/variant record containing a tag for the function and fields for the function arguments, and dispatches the function call appropriately. In principle, you’d use a single apply() subroutine and type-tagged union for the entire program, but obviously you can do a lot better than that since each call to a first-class function can refer to only a subset of all functions in the program.

    This is actually just replicating some of the compilation steps which happen when compiling a functional program into native code. But doing it manually gives you a better understanding of both procedural and functional programming, and it’s more efficient as well.

    Reply
  5. dmitry_vk

    Your example lacks deallocation of created closures and environments. And this is the critical and hard part in implementing closures. In most languages with closures, storage for closures, environments and binding is managed automatically (either by garbage collector or reference counters). In bare C you would have to know exactly when to deallocate closures – and this is tricky.

    Reply
  6. Odd Sort

    In “Map, Filter & Other High Order Functions,” it’s a bit disappointing to see mention of functions which consume functions but not of functions which produce them. I feel like showing map, fold, filter, etc. but not showing something like compose or curry/uncurry is only doing half the job.

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>