Defining and calling higher-order function composition functions with function pointers in C

Question

The Wikipedia article on function types lists an interesting declaration of a "higher-order function composition function":

int (*compose(int (*f)(int), int (*g)(int)))(int);

As a learning exercise, I wanted to implement this in a test program, but failed, with the compiler throwing a number of warnings and errors. My attempt:

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

int b(int x) {
    return x * 2;
}

int (*compose(int (*f)(int y), int (*g)(int z)))(int x) {
    return (*f)(x) - (*g)(x);
}

int main(void) {
    int x = 5;
    int r = (*compose)((*a)(x), (*b)(x))(x);
    printf("Compose result for x = %d: %d\n", x, r);

    return 0;
}

I would be grateful for an explanation of how the declaration from Wikipedia differs from a simple function composition like f(g(h(x))) and how it may be implemented, preferrably with a simple program similar to mine.

Answer 1

There are a few issues to address here.

• In C, you can't dynamically compose functions at run-time; only statically, at compile-time. Thus, you cannot achieve, with the signature you've chosen for compose, the run-time composition you're after. If compose is to return a (pointer to a) function - it can only return a pre-existing function. (*)
• In C, when you use the identifier of a function (which you've already defined) - the type is actually a function pointer already, i.e. the "invocation operator" (or the "parentheses operator") always applies to function pointers.
• Your syntax is a bit off.

Try this modification to your code:

#include <stdio.h> 

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

int b(int x) {
    return x * 2;
}

int compose(int (*f)(int y), int (*g)(int z), int x) {
    return f(x) - g(x);
}

int main(void) {
    int x = 5;
    int r = compose(a, b, x);
    printf("Compose result for x = %d: %d\n", x, r);

    return 0;
}

This compiles.

_{(*) - You could theoretically perform run-time compilation and return a link to the address of the resulting machine code, but that's not a language facility. In practice that's irrelevant}

Answer 2

In C you cannot create new functions at runtime; compose can only return a predefined function. Here is a short example for such a function:

int null(int x) { return 0; }
int f1(int x) { return x*x; }
int f2(int x) { return 2*x; }

int sub_f2_f1 ( int x ) { return f2(x)-f1(x); }
int sub_f1_f2 ( int x ) { return f1(x)-f2(x); }
/*...*/

int (*compose(int (*f)(int), int (*g)(int)))(int)
{
  if (f1==f2) return null;
  if (f2==null) return f1;
  if (f==f2 && g==f1) return sub_f2_f1;
  if (f==f1 && g==f2) return sub_f1_f2;
  /*...*/
  return 0;
}

Answer 3

Your compose function is declared to return a function pointer, but calculates and returns an int value instead.

Also (*a)(x) calls the a function and you pass the int result to compose, instead of a pointer to the function a itself. Same with b.

To solve your problem you first should call compose with pointers to the functions a and b:

int r = (*compose(&a, &b))(x);

Then you need to make compose return a pointer to a function, which includes creating the function to be returned:

int (*f1)(int);
int (*f2)(int);

int compose_helper(int x)
{
    return f1(x) - f2(x);
}

int (*compose(int (*f1_)(int), int (*f2_)(int)))(int)
{
    f1 = f1_;
    f2 = f2_;
    return &compose_helper;
}

In C there's really no nice way of doing this, as function composition can't be done at run-time and there needs to be global state.

---

As a side-note I really recommend that you create type-aliases for the function-pointers to make it all easier to read and understand.

As in

typedef int (fp_type)(int);

fp_type *f1;
fp_type *f2;

fp_type *compose(fp_type *f1_, fp_type *f2_) { ... }