What tools are there for functional programming in C?

I've been thinking a lot lately about how to go about doing functional programming in C (not C++). Obviously, C is a procedural language and doesn't really support functional programming natively.

Are there any compiler/language extensions that add some functional programming constructs to the language? GCC provides http://gcc.gnu.org/onlinedocs/gcc/Nested-Functions.html">nested functions as a language extension; nested functions can access variables from the parent stack frame, but this is still a long way away from mature closures.

For example, one thing that I think could be really useful in C is that anywhere where a function pointer is expected, you could be able to pass a lambda expression, creating a closure which decays into a function pointer. C++0x is going to include lambda expressions (which I think is awesome); however, I'm looking for tools applicable to straight C.

[Edit] To clarify, I'm not trying to solve a particular problem in C that would be more suited to functional programming; I'm merely curious about what tools are out there if I wanted to do so.

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.

http://www.haible.de/bruno/packages-ffcall.html">FFCALL</a> 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, http://lists.cs.uiuc.edu/pipermail/cfe-dev/2008-August/002670.html">blocks</a> 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.

If you want to implement closures, you'll have to get groady with assembly language and stack swapping/management. Not recommending against it, just saying that's what you'll have to do.

Not sure how you'll handle anonymous functions in C. On a von Neumann machine, you could do anonymous functions in asm, though.

The way I went about doing functional programming in C was to write a functional language interpreter in C. I named it Fexl, which is short for "Function EXpression Language."

The interpreter is very small, compiling down to 68K on my system with -O3 enabled. It's not a toy either - I'm using it for all the new production code I write for my business (web-based accounting for investment partnerships.)

Now I write C code only to (1) add a built-in function that calls a system routine (e.g. fork, exec, setrlimit, etc.), or (2) optimize a function that could otherwise be written in Fexl (e.g. search for a substring).

The module mechanism is based on the concept of a "context". A context is a function (written in Fexl) which maps a symbol to its definition. When you read a Fexl file, you can resolve it with any context you like. This allows you to create custom environments, or run code in a restricted "sandbox."

http://fexl.com

Look at Hartel & Muller's book, Functional C

http://www.ub.utwente.nl/webdocs/ctit/1/00000084.pdf
http://www.cs.bris.ac.uk/~henkm/f2c/index.html

The Felix language compiles to C++. Maybe that could be a step stone, if you don't mind C++.

Well quite a few programming languages are written in C. And some of them support functions as first class citizens, languages in that area are ecl (embbedabble common lisp IIRC), Gnu Smalltalk (gst) (Smalltalk has blocks), then there are libraries for "closures" e.g in glib2 http://library.gnome.org/devel/gobject/unstable/chapter-signal.html#closure which at least got near functional programming. So maybe using some of those implementations to do functional programming may be an option.

Well or you can go learning Ocaml, Haskell, Mozart/Oz or the like ;-)

Regards

What is it about C that you want to make functional, the syntax or the semantics? The semantics of functional programming could certainly be added to the C compiler, but by the time you were done, you'd essentially have the equivalent of one of the existing functional languages, such as Scheme, Haskell, etc.

It would be a better use of time to just learn the syntax of those languages which directly support those semantics.

Dont Know about C. There are some functional features in Objective-C though, GCC on the OSX also supports some features, however I would again recommend to start using a functional language, there are plenty mentioned above. I personally started off with scheme, there are some excellent books such as The Little Schemer that can help you do so.