Higher order functions in C

Question

Is there a "proper" way to implement higher order functions in C.

I'm mostly curious about things like portability and syntax correctness here and if there are more than one ways what the merits and flaws are.

Edit: The reason I want to know how to create higher order functions are that I have written a system to convert PyObject lists (which you get when calling python scripts) into a list of C structures containing the same data but organized in a way not dependant on the python.h libraries. So my plan is to have a function which iterates through a pythonic list and calls a function on each item in the list and places the result in a list which it then returns.

So this is basically my plan:

typedef gpointer (converter_func_type)(PyObject *)

gpointer converter_function(PyObject *obj)
{
    // do som stuff and return a struct cast into a gpointer (which is a void *)
}

GList *pylist_to_clist(PyObject *obj, converter_func_type f)
{
   GList *some_glist;
   for each item in obj
   {
       some_glist = g_list_append(some_glist, f(item));
   }
   return some_glist;
}

void some_function_that_executes_a_python_script(void)
{
   PyObject *result = python stuff that returns a list;
   GList *clist = pylist_to_clist(result, converter_function);
}

And to clearify the question: I want to know how to do this in safer and more correct C. I would really like to keep the higher order function style but if that is frowned upon I greatly appreciate ways to do this some other way.

Sphenogram

Good question, but vague. It seems like you've done some research into this. Consider updating your question to indicate what you have already found? The answers given are great, but can only be as specific as the question. – Ameliaamelie

Answer 1

If you're keen on doing this in plain C, you need to remember to include the option to pass in a context pointer from the caller of the functor (the higher-order function) to the function passed in. This lets you simulate enough of a closure that you can make things work easily enough. What that pointer points to... well, that's up to you, but it should be a void* in the functor's API (or one of the many aliases for it, such as gpointer in the GLib world or ClientData in the Tcl C API).

[EDIT]: To use/adapt your example:

typedef gpointer (converter_func_type)(gpointer,PyObject *)

gpointer converter_function(gpointer context_ptr,PyObject *obj)
{
    int *number_of_calls_ptr = context_ptr;
    *number_of_calls_ptr++;
    // do som stuff and return a struct cast into a gpointer (which is a void *)
}

GList *pylist_to_clist(PyObject *obj, converter_func_type f, gpointer context_ptr)
{
   GList *some_glist;
   for each item in obj
   {
       some_glist = g_list_append(some_glist, f(context_ptr,item));
   }
   return some_glist;
}

void some_function_that_executes_a_python_script(void)
{
   int number_of_calls = 0;
   PyObject *result = python stuff that returns a list;
   GList *clist = pylist_to_clist(result, converter_function, &number_of_calls);
   // Now number_of_calls has how often converter_function was called...
}

This is a trivial example of how to do it, but it should show you the way.

Harvell

Answer 2

Technically, higher-order functions are just functions that take or return functions. So things like qsort are already higher-order.

If you mean something more like the lambda functions found in functional languages (which is where higher order functions really become useful), those are quite a bit harder and can't be done naturally in current standard C. They're just not part of the language. Apple's blocks extension is the best candidate. It only works in GCC (and LLVM's C compiler), but they are really useful. Hopefully something like that will catch on. Here's a few relevant resources:

• Apple's documentation on the feature (references some Apple-specific technologies and also addresses Objective-C, but the core block stuff is part of their extensionto C)
• Here's a good intro on blocks
• Cocoa for Scientists' overview of C blocks

Nebulize

Answer 3

The big problem with implementing higher-order functions in C is that to do anything non-trivial you need closures, which are function pointers augmented with data structures containing local variables they have access to. Since the whole idea behind closures is to capture local variables and pass those along with the function pointer, it's hard to do without compiler support. And even with compiler support it's hard to do without garbage collection because variables can exist outside of their scope, making it hard to figure out when to free them.

Gerick

Answer 4

This is an answer to the question: how to compose functions in C, which is redirected here.

You can create a data structure to implement a list data type. that structure can contain function pointers.

#include<stdlib.h>
#include<malloc.h>

typedef (*fun)();

typedef struct funList { fun car; struct funList *cdr;} *funList;

const funList nil = NULL;

int null(funList fs){ return nil==fs; }

fun car(funList fs)
{
   if(!null(fs)) return fs->car; 
   else 
   {
     fprintf(stderr,"error:can't car(nil) line:%d\n",__LINE__);
     exit(1);
   }
}

funList cdr(funList ls)
{ if(!null(ls)) return ls->cdr; 
  else 
  {
    fprintf(stderr,"error:can't cdr(nil) line:%d\n",__LINE__);
    exit(1);
  }
}

funList cons(fun f, funList fs)
{  funList ls;

   ls=(funList) malloc(sizeof(struct funList));
   if(NULL==ls)
   {
     fprintf(stderr,"error:can't alloc mem for cons(...) line:%d\n",__LINE__);
     exit(1);
   }

   ls->car=f;
   ls->cdr=fs;

   return ls;
}

we can write a function comp which applies a list of functions:

type_2 comp(funList fs, type_1 x)
{  
   return (null(fs)) ? x : car(fs)(comp(cdr(fs),x)); 
}

An example of how it works. We use (f g h) as a short notation for cons(f,cons(g,cons(h,nil))), which is applied to a given argument x:

comp((f g h),x)

=

f(comp((g h),x))

=

f(g(comp((h),x)))

=

f(g(h(comp(nil,x))))

=

f(g(h(x)))

if you had used the polymorphic list type in a typed language like SML or Haskell the type of comp should be:

comp :: ([a -> a],a) -> a

because in that context all the members in a list have the same type. C can be more flexible in this sense. Maybe something like

typedef void (*fun)();

or

typedef (*fun)();

you should see what the C manual say about this. And be sure that all contiguous functions have compatible types.

The functions to compose should be pure, i.e. without side effects nor free variables.

Shawn

Cheers for the simple solution. Very well written and nicely explained. – Skinned

Answer 5

In straight c, this is really only done through function pointers, which are both a pain and not meant for this type of thing (which is partially why they are a pain). Blocks (or closures, according to non-apple) are fantastic for this, though. They compile in gcc-4.x or something, and icc something, but regardless thats what you're looking for. Unfortunately, I can't seem to find any good tutorials online, but suffice to say it works something like this:

void iterate(char *str, int count, (^block)(str *)){
  for(int i = 0; i < count; i++){
    block(list[i]);
  }
}

main() {
  char str[20];
  iterate(str, 20, ^(char c){
    printf("%c ", c);
  });

  int accum = 0;
  iterate(someList, 20, ^(char c){
    accum += c;
    iterate(str, 20, ^(char c){
      printf("%c ", c);
    });
  });
}

obviously this code is pointless, but it it prints each character of a string (str) with a space in between it, then adds all of the characters together into accum, and every time it does it prints out the list of characters again.

Hope this helps. By the way, blocks are very visible in Mac OS X Snow Leopard api-s, and I believe are in the forthcoming C++0x standard, so they're not really that unusual.

Ivanaivanah

The lambdas in the C++1x standard are very different from Apple's blocks extension to C. The C++ feature wouldn't really be meaningful in a C context anyway. – Nebulize

Oh, that one i've never seen... what is the ^ unary? – Sphenogram

The ^ is block definition syntax. Think of it as equivalent to the star in a function pointer, only for blocks. – Nebulize

Answer 6

Practically any interesting higher order function application requires closures, which in C entails the laborous and error-prone routine of manually defining and filling struct function arguments.

Jacoby

Answer 7

It's very difficult to do in straight C. It's more possible in C++ (see functors tutorial or Boost's bind and function libraries). Finally, C++0x adds native support for lambda functions, which takes care for you of capturing in closure all of the variables that your funcion depends on.

Bonneau

Answer 8

If you want to create higher order functions, don't use C. There are C solutions to your problem. They may not be elegant, or they may be more elegant that you realize.

[Edit] I suggested that the only way to achieve this was to use a scripting language. Others have called me out on it. So, I'm replacing that suggestion with this: [/Edit]

What are you trying to achieve? If you want to mimic closures, use a language that supports them (you can tie into Ruby, lua, javascript, etc through libraries). If you want to use callbacks, function pointers are ok. Function pointers combine the most dangerous areas of C (pointers and the weak type system), so be careful. Function pointer declarations are not fun to read, either.

You find some C libraries using function pointers because they have to. If you're writing a library, maybe you need to use them, too. If you're just using them within your own code, you're probably not thinking in C. You're thinking in lisp or scheme or ruby or ... and trying to write it in C. Learn the C way.

Bladder

Higher order functions are "merely" functions which either take one or several functions as arguments or return a function. All this can be done in C, using pointers to function. The "merely" is quoted because while the mechanics of this can be relatively simply (albeit more or less naturally and extensively supported by different languages) the usage of higher order functions can lead to very powerful and mind bending programming. – Borehole

Higher order != dynamic code. A higher order function is merely a function that operates on functions, which is perfectly doable in C. A sort algorithm with a pluggable comparison function is a higher order function. A numeric integrator is. A timer callback registration is. The main challenge is that you have to learn the syntax, which is rather different than anything else in the language. – Inhibitory

They don't rely on them as much as fairly often require them. You will find that very often using function pointers requires you to case your nicely typed pointer to a void *. sort() is a good example. If you're not trying to do anything too generic, you'll be able to avoid this problem. – Bladder