C 中的函数式编程(柯里化)/类型问题

问题描述

作为一名彻头彻尾的函数式程序员，我发现很难不尝试将我最喜欢的范式硬塞进我使用的任何语言中.在编写一些 C 时，我发现我想咖喱我的一个函数，然后传递部分应用的函数.阅读有没有办法在C中进行currying? 并注意 http://gcc.gnu 上的警告.org/onlinedocs/gcc/Nested-Functions.html#Nested-Functions 我想出了:

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)));
}

按预期运行.但是，我的原始程序使用 double s，所以我想我只需要更改适当的类型就可以了:

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)));
}

这会产生如下结果:

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

错误的选择似乎是随机的.此外，如果任一示例使用 -O3 编译，则编译器本身会抛出 Segmentation fault: 11 本身.我在任何时候都没有收到来自 gcc 的警告，而且我无法弄清楚发生了什么.有谁知道为什么第二个程序失败而第一个没有?或者更好的是如何修复第二个?

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?

我的 gcc 是 i686-apple-darwin11-llvm-gcc-4.2 (GCC) 4.2.1(基于 Apple Inc. build 5658)(LLVM build 2336.11.00) 而我的内核是Darwin 内核版本 12.1.0:2012 年 8 月 14 日星期二 13:29:55 PDT；根:xnu-2050.9.2~1/RELEASE_X86_64.

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.

明确地说，我明白我正在尝试做的事情很愚蠢.这段代码不会在好奇号火星车或纽约证券交易所上运行.我试图更多地了解 (GNU) C 中的函数指针如何工作，并解释我发现的一些有趣的事情.我保证永远不会在现实世界中做这样的事情.

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.

推荐答案

一个有趣的问题，我看了看答案中引用的论文 (在 C/C++/Objective-C 中使用 Curried 函数的更多功能可重用性).

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).

以下是您可能想去的地方的建议路径.我不认为这真的是一个柯里化函数，因为我不完全理解这篇论文在说什么，我不是一个函数式程序员.然而，做了一些工作，我发现了一些这个概念的有趣应用.另一方面，我不确定这是否是您想要的，您可以在 C 中执行此操作让我大吃一惊.

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.

似乎有两个问题.

首先是能够使用任意参数列表处理任意函数调用.我采用的方法是使用标准 C 库变量参数功能(带有 va_start()、va_arg() 和 va_end() 函数的 va_list)，然后将函数指针与提供的参数一起存储到数据区域中，以便它们然后可以在以后执行.我借用并修改了 printf() 函数如何使用格式行来了解提供了多少个参数及其类型.

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;
}

另外一个有趣的地方是在由 doFuncAndPop() 调用的函数中使用 pushFunction() 函数来获得另一个函数可以将其参数放入堆栈.

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.

例如，如果您将上面源代码中的函数 otherFunc() 修改为如下所示:

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);
}

如果你添加另一个对 doFuncAndPop() 的调用，你会看到第一个 otherFunc() 被执行，然后调用 myFunc()> 在 otherFunc() 中推送的内容被执行，然后最后在 main () 中推送的 myFunc() 调用被调用.

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.

编辑 2:如果我们添加以下函数，这将执行已放入堆栈的所有函数.这将允许我们通过将函数和参数压入堆栈然后执行一系列函数调用来基本上创建一个小程序.这个函数还允许我们推送一个没有任何参数的函数，然后推送一些参数.当从堆栈中弹出函数时，如果参数块没有有效的函数指针，那么我们要做的是将该参数列表放入堆栈顶部的参数块中，然后执行它.也可以对上面的函数 doFuncAndPop() 进行类似的更改.如果我们在执行的函数中使用 pushFunction() 操作，我们可以做一些有趣的事情.

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.

实际上这可能是的基础线程解释器.

// 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();
    }
}

编辑 3:然后我们对 pushFunc() 进行更改以使用以下附加开关处理双精度:

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;

因此，使用这个新函数，我们可以执行以下操作.首先创建我们的两个类似于原始问题的函数.我们将在一个函数中使用 pushFunction() 将参数压入堆栈，然后下一个函数将使用这些参数.

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 我们通过以下一系列语句使用我们的新功能:

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();

这些语句将首先执行值为 4.5 的函数 g2() 然后函数 g2() 将其返回值压入我们的堆栈中以供使用由函数 f1() 首先压入我们的堆栈.

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.

这篇关于C 中的函数式编程(柯里化)/类型问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！