What tools are there for functional programming in C?

Question

You can use GCC's nested functions to simulate lambda expressions, in fact, I have a macro to do it for me:

#define lambda(return_type, function_body) \
  ({ \
    return_type anon_func_name_ function_body \
    anon_func_name_; \
  })

Use like this:

int (*max)(int, int) = lambda (int, (int x, int y) { return x > y ? x : y; });

Functional programming is not about lambdas, it is all about pure functions. So the following broadly promote functional style:

1. Only use function arguments, do not use global state.

2. Minimise side effects i.e. printf, or any IO. Return data describing IO which can be executed instead of causing the side effects directly in all functions.

This can be achieved in plain c, no need for magic.

FFCALL lets you build closures in C -- callback = alloc_callback(&function, data) returns a function pointer such that callback(arg1, ...) is equivalent to calling function(data, arg1, ...). You will have to handle garbage collection manually, though.

Relatedly, blocks have been added to Apple's fork of GCC; they're not function pointers, but they let you pass around lambdas while avoiding the need to build and free storage for captured variables by hand (effectively, some copying and reference counting happens, hidden behind some syntactic sugar and runtime libraries).

Hartel & Muller's book, Functional C, can nowadays (2012-01-02) be found at: http://eprints.eemcs.utwente.nl/1077/ (there is a link to PDF version).

Prerequisite for functional programming style is a first class function. It could be simulated in portable C if you tolerate next:

• manual management of lexical scope bindings, aka closures.
• manual management of function variables lifetime.
• alternative syntax of function application/call.

/* 
 * with constraints desribed above we could have
 * good approximation of FP style in plain C
 */

int increment_int(int x) {
  return x + 1;
}

WRAP_PLAIN_FUNCTION_TO_FIRST_CLASS(increment, increment_int);

map(increment, list(number(0), number(1)); // --> list(1, 2)


/* composition of first class function is also possible */

function_t* computation = compose(
  increment,
  increment,
  increment
);

*(int*) call(computation, number(1)) == 4;

runtime for such code could be as small as one below

struct list_t {
  void* head;
  struct list_t* tail;
};

struct function_t {
   void* (*thunk)(list_t*);
   struct list_t* arguments;
}

void* apply(struct function_t* fn, struct list_t* arguments) {
  return fn->thunk(concat(fn->arguments, arguments));
}

/* expansion of WRAP_PLAIN_FUNCTION_TO_FIRST_CLASS */
void* increment_thunk(struct list_t* arguments) {
  int x_arg = *(int*) arguments->head;
  int value = increment_int(x_arg);
  int* number = malloc(sizeof *number);

  return number ? (*number = value, number) : NULL;
}

struct function_t* increment = &(struct function_t) {
  increment_thunk,
  NULL
};

/* call(increment, number(1)) expands to */
apply(increment, &(struct list_t) { number(1), NULL });

In essence we imitate first class function with closures represented as pair of function/arguments plus bunch of macroses. Complete code could be found here.

The main thing that comes to mind is the use of code generators. Would you be willing to program in a different language that provided the functional programming and then generate the C code from that?

If that's not an attractive option, then you could abuse CPP to get part of the way there. The macro system should let you emulate some functional programming ideas. I've heard tell that gcc is implemented this way but I've never checked.

C can of course pass functions around using function pointers, the main problems are lack of closures and the type system tends to get in the way. You could explore more powerful macro systems than CPP such as M4. I guess ultimately, what I'm suggesting is that true C isn't up to the task without great effort but you could extend C to make it be up to the task. That extension would look the most like C if you use CPP or you could go to the other end of the spectrum and generate C code from some other language.