Implementing function delegates in C with unions and function pointers

Question

I'd like to be able to generically pass a function to a function in C. I've used C for a few years, and I'm aware of the barriers to implementing proper closures and higher-order functions. It's almost insurmountable.

I scoured StackOverflow to see what other sources had to say on the matter:

• higher-order-functions-in-c
• anonymous-functions-using-gcc-statement-expressions
• is-there-a-way-to-do-currying-in-c
• functional-programming-currying-in-c-issue-with-types
• emulating-partial-function-application-in-c
• fake-anonymous-functions-in-c
• functional-programming-in-c-with-macro-higher-order-function-generators
• higher-order-functions-in-c-as-a-syntactic-sugar-with-minimal-effort

...and none had a silver-bullet generic answer, outside of either using varargs or assembly. I have no bones with assembly, but if I can efficiently implement a feature in the host language, I usually attempt to.

Since I can't have HOF easily...

I'd love higher-order functions, but I'll settle for delegates in a pinch. I suspect that with something like the code below I could get a workable delegate implementation in C.

An implementation like this comes to mind:

enum FUN_TYPES {
    GENERIC,
    VOID_FUN,
    INT_FUN,
    UINT32_FUN,
    FLOAT_FUN,
};

typedef struct delegate {
    uint32 fun_type;
    union function {
        int (*int_fun)(int);
        uint32 (*uint_fun)(uint);
        float (*float_fun)(float);
        /* ... etc. until all basic types/structs in the 
           program are accounted for. */
    } function;
} delegate;

Usage Example:

void mapint(struct fun f, int arr[20]) {
    int i = 0;
    if(f.fun_type == INT_FUN) {
        for(; i < 20; i++) {
            arr[i] = f.function.int_fun(arr[i]);
        }
    }
}

Unfortunately, there are some obvious downsides to this approach to delegates:

• No type checks, save those which you do yourself by checking the 'fun_type' field.
• Type checks introduce extra conditionals into your code, making it messier and more branchy than before.
• The number of (safe) possible permutations of the function is limited by the size of the 'fun_type' variable.
• The enum and list of function pointer definitions would have to be machine generated. Anything else would border on insanity, save for trivial cases.
• Going through ordinary C, sadly, is not as efficient as, say a mov -> call sequence, which could probably be done in assembly (with some difficulty).

Does anyone know of a better way to do something like delegates in C?

Note: The more portable and efficient, the better

Also, Note: I've heard of Don Clugston's very fast delegates for C++. However, I'm not interested in C++ solutions--just C .

Toandfro

"Type checks introduce extra conditionals into your code, making it messier and more branchy than before." That's why a union of function pointer types doesn't make much sense, since you already have the enum, you could simply pass that to a switch statement, which in turn calls the appropriate function. Also, you don't seem to have considered where the parameters and return values fit in with all of this. And finally, as an universal programming rule of thumb: generic programming always makes the code slower. – Chancroid

You're right, I don't have an easy answer for return types. As for parameters, the most likely way to generically solve that in C would be with yet another union of the possible types. Yeah, it's ugly as sin. And when I looked at the generated assembly output for the posted approach, I saw that it was far less efficient than I would have liked it to be. Thus why I asked for suggestions on better approaches. – Toandfro

@PhilipConrad: Hi, did you ever manage to create that large machine-generated list of function types? – Arbitrament

Answer 1

You could add a void* argument to all your functions to allow for bound arguments, delegation, and the like. Unfortunately, you'd need to write wrappers for anything that dealt with external functions and function pointers.

Regeneracy

This is the only answer in the past 3 months, so I'll mark it as the answer out of courtesy to the poster. – Toandfro

Answer 2

There are two questions where I have investigated techniques for something similar providing slightly different versions of the basic technique. The downside of this is that you lose compile time checks since the argument lists are built at run time.

The first is my answer to the question of Is there a way to do currying in C. This approach uses a proxy function to invoke a function pointer and the arguments for the function.

The second is my answer to the question C Pass arguments as void-pointer-list to imported function from LoadLibrary().

The basic idea is to have a memory area that is then used to build an argument list and to then push that memory area onto the stack as part of the call to the function. The result is that the called function sees the memory area as a list of parameters.

In C the key is to define a struct which contains an array which is then used as the memory area. When the called function is invoked, the entire struct is passed by value which means that the arguments set into the array are then pushed onto the stack so that the called function sees not a struct value but rather a list of arguments.

With the answer to the curry question, the memory area contains a function pointer as well as one or more arguments, a kind of closure. The memory area is then handed to a proxy function which actually invokes the function with the arguments in the closure.

This works because the standard C function call pushes arguments onto the stack, calls the function and when the function returns the caller cleans up the stack because it knows what was actually pushed onto the stack.

Acreage

This sounds like a good approach, the only thing I have reservations about is copying a large struct by-value. I know that's "safer", but there would be some serious overheads, right? – Toandfro

@PhilipConrad there is always the question of overheads and whether the cost of the overheads are covered by the utility of what the functionality provides. There is a value analysis that needs to be done as to cost of doing without the functionality versus the cost of using the functionality. And the other consideration is the environment in which the functionality is being used. If the application is spending most of its time waiting on user input, I'm not sure if a few milliseconds makes that much difference. – Acreage