Functional Programming (Currying) in C / Issue wit

问题:

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\n",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\n",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.

回答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\n", i, p);
}

void otherFunc (int i, char * p, char *p2)
{
    printf (" i = %d, char = %s, char =%s\n", 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\n", 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\n", myDouble);
    return 0.0;
}

double g2 (double myDouble) {
    printf ("g2 myDouble = %f\n", 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.

回答2:

You're trying to rely on undefined behaviour: Once the inner function goes out of scope because the outer one does exit, the behaviour of calling that inner function through some pointer is undefined. Anything might happen. The fact that things accidentially worked for the integer case does not imply that you can expect the same for double, or that you can even expect the same for int over different compilers, different compiler versions, different compiler flags or different target architectures.

So don't rely on undefined behaviour. Don't claim to have “heed[ed] the warnings” when in fact you acted against those warnings. The warning clearly states:

If you try to call the nested function through its address after the containing function has exited, all hell will break loose.

There are no closures in C, so there can't be currying in this sense. You can get similar effects if you pass along some data to function invocations, but that will not look exactly like a normal function call, so it won't feel like normal currying. C++ has more flexibility there, as it allows objects to behave syntactically like functions. In the C++ world, currying is usually called “binding” of function parameters.

If you really want to know why one piece of code worked but the other failed, you can take the assembly code (generated e.g. by gcc -S -fverbose-asm) and simulate the execution in your head, to see what happens to your data and stuff. Or you may use the debugger to see where things fail, or data locations change. Might take some work, and I doubt it's worth the time.

回答3:

Excuse me for not getting it, but why don't you wrap instead of curry, since you're declaring functions at compile time anyway? The advantage of currying is - or at least, it seems to me - that you can define a partially applied function at runtime, but here you aren't doing this. Or am I missing something?

#include <stdio.h>

// Basic function summing its arguments
double g (double a, double b)
{
    return a+b;
}

double f1(double a)
{
    /* "1" can be replaced by a static initialized
       by another function, e.g.
       static double local_b = g(0, 1);
    */
    return g(a, 1);
}

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

回答4:

Fixed version of above code

#include <stdio.h>

typedef double (*function) (double,double);

// Basic function summing its arguments
double g (double a, double b)
{
        return a+b;
}

double f1(function wrapfunc,double a)
{
 /* "1" can be replaced by a static initialized
     by another function, e.g.
     static double local_b = g(0, 1);
 */
 return wrapfunc(a, 1);  
}

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

a bit more about different operation functions with sample parameter example

#include<iostream>
#include<cstdio>

using namespace std;

#define N 4

#define LOOP(i) for(i=0; i<N; i++)

#define F(i) ( (int(*)(int,int))opt[i] )
#define FI F(i)
#define FJ F(j)
#define FK F(k)


int add(int a, int b) { return a + b; }

int sub(int a, int b) { return a - b; }

u int mul(int a, int b) { return a * b; }

int div(int a, int b) {
    if (b == 0 || a % b)
        return 2401;
    return a / b;
}

char whichOpt(int index)
{
    if (index == 0) return '+';
    else if (index == 1) return '-';
    else if (index == 2) return '*';
    return '/';
}

void howObtain24(int num[], void *opt[])
{
    int i, j, k, a, b, c, d;
    int ans=0;
    LOOP(i) LOOP(j) LOOP(k)
         LOOP(a) LOOP(b) LOOP(c) LOOP(d)
    {
        if (a == b || a == c || a == d || b == c || b == d || c == d)
            continue;
        if (FI(FJ(FK(num[a], num[b]), num[c]), num[d]) == 24) {
            std::cout << "((" << num[a] << whichOpt(k) << num[b] << ')'
                 << whichOpt(j) << num[c] << ')' << whichOpt(i) << num[d] << endl;
            ans++;
            continue;
        }
        if (FI(FJ(num[a], num[b]), FK(num[c], num[d])) == 24) {
            std::cout << '(' << num[a] << whichOpt(j) << num[b] << ')'
                 << whichOpt(i) << '(' << num[c] << whichOpt(k) << num[d] << ')' << endl;
            ans++;
            continue;
        }
    }
    if(ans==0)
    std::cout << "Non-Answer" << std::endl;
    return;

}

//=======================================================================
int main() {

    int num[N];

    void *opt[N] = { (void *)add, (void *)sub, (void *)mul, (void *)div };

    std::cout << "Input 4 Numbers between 1 and 10\n"
    for (int i = 0; i < N; i++)
        cin >> num[i];

    for (int j = 0; j < N; j++)
        if (num[j] < 1 || num[j] > 10) {
            std::cout << "InCorrect Input\n"

            return 0;
        }
        howObtain24(num, opt);

        return 0;
}