Curried Functions in C

http://almostvalid.blogspot.kr/2013/05/curried-functions-in-c.html

Curried Functions in C

A curried function is a function which takes only one parameter and returns a function defined according to that parameter. This is a more powerful idea than is implied by that last sentence. And curried functions are everywhere.

Take Haskell, for example. In Haskell, *every* function is curried. Not just ones you specify. Everything. So, in Haskell, if you have

foo :: (Integral a) => a -> a -> a
foo a b = a + b

Writing

foo a b

Is equivalent to

(foo a) b

The reason for this is that foo isn't invoked with two parameters passed. Instead, foo is invoked with one parameter passed, which results in an expression in terms of another variable. This expression is returned as a function and then applied to the next argument.

The equivalent of a curried function in math would be something like this:

f(x) = x / y

If one were to invoke f, with x=5, the resulting expression would be

f(5) = 5 / y

Which is an expression in terms of y. (Of course, this wouldn't really happen in math, but this is just an example to attempt to make currying more clear to those unfamiliar with the idea.)

This concept of returning expressions is nice, and it can be used in a whole lot of neat ways, but how do we apply it to C? And that's the important part.

Let's examine C's concept of a function.

In C, functions are not first-class objects. In Python, you can write

def foo(a, b):
        a(b)
def bar(b):
        return b + 1
foo(bar, 5) # => 6

However, of course, in C, you can't pass functions directly. You can, however, use pointers to functions. And pointers, of course, are just variables. And, as it turns out, every function name is actually just a pointer to that function.

So, if in the statement

foo(a, b, c);

foo is just a pointer to something, why does this result in the function being called?

Simple.

The parentheses are actually C's call operator. That's right. It's an operator, just like + or * or sizeof or &.

This leads us to an interesting question. Because we know

foo(a, b, c) * 2 + 1;

Is a valid C expression, in which whatever the return value of foo is will be operated on with the rest of the expression, can we also use the call operator on expressions which evaluate to function pointers?

The answer is yes.

For example, in C, you can write:

typedef int (*fun_t)(int);

int bar(int a)
{
        return a * 5;
}

fun_t foo(void)
{
        return bar;
}

void some_fun(void)
{
        foo()(5); // => 25
}

Now, this is seriously cool, in a lot of ways. And, we can use it to write curried functions.

But, of course, typing is painful, and we don't want to do a lot of typing and thinking about what-should-return-what. So, we should write a macro.

Let's do that.

Here's the macro I came up with:

#define DECLARE_CURRIED_FUNCTION(name, type, op) \
    typedef type (*_curry_##name##_t)(type); \
    type _curried_a_##name; \
    type _curried_ret_##name(type b) { \
        type a = _curried_a_##name; \
        op;\
        return b; /* stifle warnings */ \
    } \
    _curry_##name##_t name(type a) { \
        _curried_a_##name = a; \
        return _curried_ret_##name; \
    }

This is a macro which will define a curried version of a function which takes two arguments. Those arguments are referenced in op as a and b. This macro will have to be tweaked to support functions with a different amount of arguments - multiple flavors may have to be created, though the creation of different flavors is trivial. As well, as the value of a is passed in a global variable, nasty bugs may occur if, in a multithreaded application, a is not serialized or thread-local. Also, for best results, use this macro in the global scope, and not within functions.

With those caveats out of the way, we have a neat little macro. Now, we can define curried functions neatly:

DECLARE_CURRIED_FUNCTION(add, int, return a+b);

Then, if we wish to fully evaluate add:

add(5)(3); // => 8

Which is neat. We can also use partial application to expand the power of map macros:

#define map_array(fun, array, len) \
        for (int _map = 0; _map < len; map++)
                fun(array[_map]);

DECLARE_CURRIED_FUNCTION(foo, int, printf("%d\n", a+b));

/* ... */

int array[] = { 1, 2, 3, 4, 5 };
map_array(foo(5), array, 5); //prints 6\n7\n8\n9\n10\n

This is extraordinarily useful - we may now write with a nice syntax otherwise complicated expressions.

We can also use this technique to write otherwise annoying statements in a rather nice syntax.

Consider a function which takes the dot product of 3d vectors from two sets of 3 integers.

Ordinarily, we'd write it like this:

result = dot_product(1, 2, 3, 4, 5, 6);

Using this technique, though, we can separate the two vectors, resulting in a somewhat prettier function call:

result = dot_product(1, 2, 3)(4, 5, 6);

This technique is extremely powerful. I refer to this as the "curry-by-pointer-return" technique, as we are returning pointers to functions.

Currying is an extraordinarily useful tool, and now, we have a pretty syntax to do it with.

Posted by henry at 9:20 AM