Is there a way to do currying in C?

Say I have a pointer to a function _stack_push(stack* stk, void* el). I want to be able to call curry(_stack_push, my_stack) and get back a function that just takes void* el. I couldn't think of a way to do it, since C doesn't allow runtime function definition, but I know there are far cleverer people than me here :). Any ideas?

Solution 1:

I found a paper by Laurent Dami that discusses currying in C/C++/Objective-C:

More Functional Reusability in C/C++/Objective-c with Curried Functions

Of interest to how it is implemented in C:

Our current implementation uses existing C constructs to add the currying mechanism. This was much easier to do than modifying the compiler, and is sufficient to prove the interest of currying. This approach has two drawbacks, however. First, curried functions cannot be type-checked, and therefore require careful use in order to avoid errors. Second, the curry function cannot know the size of its arguments, and counts them as if they were all of the size of an integer.

The paper does not contain an implementation of curry(), but you can imagine how it is implemented using function pointers and variadic functions.

Solution 2:

GCC provides an extension for the definition of nested functions. Although this is not ISO standard C, this may be of some interest, since it enables to answer the question quite conveniently. In short, nested function can access the parent function local variables and pointers to them can be returned by the parent function as well.

Here is a short, self-explanatory example:

#include <stdio.h>

typedef int (*two_var_func) (int, int);
typedef int (*one_var_func) (int);

int add_int (int a, int b) {
    return a+b;
}

one_var_func partial (two_var_func f, int a) {
    int g (int b) {
        return f (a, b);
    }
    return g;
}

int main (void) {
    int a = 1;
    int b = 2;
    printf ("%d\n", add_int (a, b));
    printf ("%d\n", partial (add_int, a) (b));
}

There is however a limitation to this construction. If you keep a pointer to the resulting function, as in

one_var_func u = partial (add_int, a);

the function call u(0) may result in an unexpected behaviour, as the variable a which u reads was destroyed just after partial terminated.

See this section of GCC's documentation.

Solution 3:

Here's my first guess off the top of my head (may not be the best solution).

The curry function could allocate some memory off the heap, and put the parameter values into that heap-allocated memory. The trick is then for the returned function to know that it's supposed to read its parameters from that heap-allocated memory. If there's only one instance of the returned function, then a pointer to those parameters can be stored in a singleton/global. Otherwise if there's more than one instance of the returned function, then I think that curry needs to create each instance of the returned function in the heap-allocated memory (by writing opcodes like "get that pointer to the parameters", "push the parameters", and "invoke that other function" into the heap-allocated memory). In that case you need to beware whether allocated memory is executable, and maybe (I don't know) even be afraid of anti-virus programs.