gcc - Functional Programming (Currying) in C / Issue with Types

Question

As a dyed-in-the-wool functional programmer I find it hard not to try to shoehorn my favourite paradigm into whatever language I'm using. While writing some C I found I'd like to curry one of my functions, and then pass around the partially applied function. After reading Is there a way to do currying in C? and heeding the warnings at http://gcc.gnu.org/onlinedocs/gcc/Nested-Functions.html#Nested-Functions I came up with:

#include <stdio.h>

typedef int (*function) (int);

function g (int a) {
    int f (int b) {
        return a+b;
    }
    return f;
}

int f1(function f){
    return f(1);}

int main () {
    printf ("(g(2))(1)=%d
",f1(g(2)));
}

Which runs as expected. However, my original program works with doubles and so I thought I'd just change the appropriate types and I'd be fine:

#include <stdio.h>

typedef double (*function) (double);

function g (double a) {
    double f (double b) {
        return a+b;
    }
    return f;
}

double f1(function f){
    return f(1);}

int main () {
    printf ("(g(2))(1)=%e
",f1(g(2)));
}

This produces things like:

bash-3.2$ ./a.out 
Segmentation fault: 11
bash-3.2$ ./a.out 
Illegal instruction: 4

with the choice of error being seemingly random. Furthermore if either example is compiled with -O3 the compiler itself throws a Segmentation fault: 11 itself. I get no warnings from gcc at any point, and I'm not able to figure out what's happening. Does anyone know why the second program fails while the first doesn't? Or better still how to fix the second one?

My gcc is i686-apple-darwin11-llvm-gcc-4.2 (GCC) 4.2.1 (Based on Apple Inc. build 5658) (LLVM build 2336.11.00) and my kernel is Darwin Kernel Version 12.1.0: Tue Aug 14 13:29:55 PDT 2012; root:xnu-2050.9.2~1/RELEASE_X86_64.

edit: To be clear, I understand that what I'm trying to do is stupid. This code isn't going to run on the Curiosity rover, or the NYSE. I'm trying to understand more about how function pointers in (GNU) C work, and explain something interesting I found. I promise never to do anything like this in the real world.

Answer 1

An interesting question and I took a look at the paper in the answer cited (More functional reusability in C/C++/Objective-C with Curried functions).

So following is a suggested path to where you might want to go. I do not think this is truly a Curried function as I do not fully understand what the paper is talking about, not being a functional programmer. However, doing a bit of work, I find an interesting application of some of this concept. I am not sure this is what you want on the other hand, it kind of blows my mind that you can do this in C.

There seemed to be two problems.

First of all was to be able to handle arbitrary function calls with arbitrary argument lists. The approach I took was to use standard C Library variable arguments functionality (va_list with the va_start(), va_arg(), and va_end() functions) and to then store the function pointer along with the provided arguments into a data area so that they could then be executed at a later time. I borrowed and modified how the printf() function uses the format line to know how many arguments and their types are provided.

The next was the storage of the function and its argument list. I just used a struct with some arbitrary size just to try out the concept. This will need a bit more thought.

This particular version uses an array that is treated like a stack. There is a function that you use to push some arbitrary function with its arguments onto the stack array and there is a function that will pop the top most function and its arguments off of the stack array and execute it.

However you could actually just have arbitrary struct objects in some kind of a collection for instance a hash map and that might be very cool.

I just borrowed the signal handler example from the paper to show that the concept would work with that kind of an application.

So here is the source code and I hope it helps you come up with a solution.

You would need to add other cases to the switch so as to be able to process other argument types. I just did a few for proof of concept.

Also this does not do the function calling a function though that would seem on the surface to be a fairly straightforward extension. Like I said, I do not totally get this Curried thing.

#include <stdarg.h>
#include <string.h>

// a struct which describes the function and its argument list.
typedef struct {
    void (*f1)(...);
    // we have to have a struct here because when we call the function,
    // we will just pass the struct so that the argument list gets pushed
    // on the stack.
    struct {
        unsigned char myArgListArray[48];   // area for the argument list.  this is just an arbitray size.
    } myArgList;
} AnArgListEntry;

// these are used for simulating a stack.  when functions are processed
// we will just push them onto the stack and later on we will pop them
// off so as to run them.
static unsigned int  myFunctionStackIndex = 0;
static AnArgListEntry myFunctionStack[1000];

// this function pushes a function and its arguments onto the stack.
void pushFunction (void (*f1)(...), char *pcDescrip, ...)
{
    char *pStart = pcDescrip;
    AnArgListEntry MyArgList;
    unsigned char *pmyArgList;
    va_list argp;
    int     i;
    char    c;
    char   *s;
    void   *p;

    va_start(argp, pcDescrip);

    pmyArgList = (unsigned char *)&MyArgList.myArgList;
    MyArgList.f1 = f1;
    for ( ; *pStart; pStart++) {
        switch (*pStart) {
            case 'i':
                // integer argument
                i = va_arg(argp, int);
                memcpy (pmyArgList, &i, sizeof(int));
                pmyArgList += sizeof(int);
                break;
            case 'c':
                // character argument
                c = va_arg(argp, char);
                memcpy (pmyArgList, &c, sizeof(char));
                pmyArgList += sizeof(char);
                break;
            case 's':
                // string argument
                s = va_arg(argp, char *);
                memcpy (pmyArgList, &s, sizeof(char *));
                pmyArgList += sizeof(char *);
                break;
            case 'p':
                // void pointer (any arbitray pointer) argument
                p = va_arg(argp, void *);
                memcpy (pmyArgList, &p, sizeof(void *));
                pmyArgList += sizeof(void *);
                break;
            default:
                break;
        }
    }
    va_end(argp);
    myFunctionStack[myFunctionStackIndex] = MyArgList;
    myFunctionStackIndex++;
}

// this function will pop the function and its argument list off the top
// of the stack and execute it.
void doFuncAndPop () {
    if (myFunctionStackIndex > 0) {
        myFunctionStackIndex--;
        myFunctionStack[myFunctionStackIndex].f1 (myFunctionStack[myFunctionStackIndex].myArgList);
    }
}

// the following are just a couple of arbitray test functions.
// these can be used to test that the functionality works.
void myFunc (int i, char * p)
{
    printf (" i = %d, char = %s
", i, p);
}

void otherFunc (int i, char * p, char *p2)
{
    printf (" i = %d, char = %s, char =%s
", i, p, p2);
}

void mySignal (int sig, void (*f)(void))
{
    f();
}

int main(int argc, char * argv[])
{
    int i = 3;
    char *p = "string";
    char *p2 = "string 2";

    // push two different functions on to our stack to save them
    // for execution later.
    pushFunction ((void (*)(...))myFunc, "is", i, p);
    pushFunction ((void (*)(...))otherFunc, "iss", i, p, p2);

    // pop the function that is on the top of the stack and execute it.
    doFuncAndPop();

    // call a function that wants a function so that it will execute
    // the current function with its argument lists that is on top of the stack.
    mySignal (1, doFuncAndPop);

    return 0;
}

An additional bit of fun you can have with this is to use the pushFunction() function within a function that is invoked by doFuncAndPop() to have another function you can put onto the stack with its arguments.

For instance if you modify the function otherFunc() in the source above to look like the following:

void otherFunc (int i, char * p, char *p2)
{
    printf (" i = %d, char = %s, char =%s
", i, p, p2);
    pushFunction ((void (*)(...))myFunc, "is", i+2, p);
}

if you then add another call to doFuncAndPop() you will see that first otherFunc() is executed then the call to myFunc() that was pused in otherFunc() is executed and then finally the myFunc() call that was pushed in the main () is called.

EDIT 2: If we add the following function this will execute all of the functions that have been put onto the stack. This will allow us to basically create a small program by pushing functions and arguments onto our stack and then executing the series of function calls. This function will also allow us to push a function without any arguments then push some arguments. When popping functions off of our stack, if an argument block does not have a valid function pointer then what we do is to put that argument list onto the argument block on the top of the stack and to then execute that. A similar change can be made to the function doFuncAndPop() above as well. And if we use the pushFunction() operation in an executed function, we can do some interesting things.

Actually this could be the basis for a Threaded Interpreter.

// execute all of the functions that have been pushed onto the stack.
void executeFuncStack () {
    if (myFunctionStackIndex > 0) {
        myFunctionStackIndex--;
        // if this item on the stack has a function pointer then execute it
        if (myFunctionStack[myFunctionStackIndex].f1) {
            myFunctionStack[myFunctionStackIndex].f1 (myFunctionStack[myFunctionStackIndex].myArgList);
        } else if (myFunctionStackIndex > 0) {
            // if there is not a function pointer then assume that this is an argument list
            // for a function that has been pushed on the stack so lets execute the previous
            // pushed function with this argument list.
            int myPrevIndex = myFunctionStackIndex - 1;
            myFunctionStack[myPrevIndex].myArgList = myFunctionStack[myFunctionStackIndex].myArgList;
        }
        executeFuncStack();
    }
}

EDIT 3: Then we make a change to pushFunc() to handle a double with the following additional switch:

case 'd':
  {
     double d;
     // double argument
     d = va_arg(argp, double);
     memcpy (pmyArgList, &d, sizeof(double));
     pmyArgList += sizeof(double);
   }
break;

So with this new function we can do something like the following. First of all create our two functions similar to the original question. We will use the pushFunction() inside one function to push arguments that are then used by the next function on the stack.

double f1 (double myDouble)
{
    printf ("f1 myDouble = %f
", myDouble);
    return 0.0;
}

double g2 (double myDouble) {
    printf ("g2 myDouble = %f
", myDouble);
    myDouble += 10.0;
    pushFunction (0, "d", myDouble);
    return myDouble;
}

New we use our new functionality with the following series of statements:

double xDouble = 4.5;
pushFunction ((void (*)(...))f1, 0);
pushFunction ((void (*)(...))g2, "d", xDouble);
executeFuncStack();

These statements will execute first the function g2() with the value of 4.5 and then the function g2() will push its return value onto our stack to be used by the function f1() which was pushed on our stack first.