有沒有辦法在 C 中進行柯里化？ (Is there a way to do currying in C?)

問題描述

有沒有辦法在 C 中進行柯里化？ (Is there a way to do currying in C?)

假設我有一個指向函數 _stack_push(stack* stk, void* el) 的指針。我希望能夠調用 curry(_stack_push, my_stack) 並取回一個只需要 void* el 的函數。我想不出辦法，因為 C 不允許運行時函數定義，但我知道這裡有比我聰明得多的人 :)。有什麼想法嗎？

參考解法

方法 1:

I found a paper by Laurent Dami that discusses currying in C/C++/Objective‑C:

More Functional Reusability in C/C++/Objective‑c with Curried Functions

Of interest to how it is implemented in C:

Our current implementation uses existing C constructs to add the currying mechanism. This was much easier to do than modifying the compiler, and is sufficient to prove the interest of currying. This approach has two drawbacks, however. First, curried functions cannot be type‑checked, and therefore require careful use in order to avoid errors. Second, the curry function cannot know the size of its arguments, and counts them as if they were all of the size of an integer.

The paper does not contain an implementation of curry(), but you can imagine how it is implemented using function pointers and variadic functions.

方法 2:

GCC provides an extension for the definition of nested functions. Although this is not ISO standard C, this may be of some interest, since it enables to answer the question quite conveniently. In short, nested function can access the parent function local variables and pointers to them can be returned by the parent function as well.

Here is a short, self‑explanatory example:

#include <stdio.h>

typedef int (*two_var_func) (int, int);
typedef int (*one_var_func) (int);

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

one_var_func partial (two_var_func f, int a) {
    int g (int b) {
        return f (a, b);
    }
    return g;
}

int main (void) {
    int a = 1;
    int b = 2;
    printf ("%d\n", add_int (a, b));
    printf ("%d\n", partial (add_int, a) (b));
}

There is however a limitation to this construction. If you keep a pointer to the resulting function, as in

one_var_func u = partial (add_int, a);

the function call u(0) may result in an unexpected behaviour, as the variable a which u reads was destroyed just after partial terminated.

See this section of GCC's documentation.

方法 3:

Here's my first guess off the top of my head (may not be the best solution).

The curry function could allocate some memory off the heap, and put the parameter values into that heap‑allocated memory. The trick is then for the returned function to know that it's supposed to read its parameters from that heap‑allocated memory. If there's only one instance of the returned function, then a pointer to those parameters can be stored in a singleton/global. Otherwise if there's more than one instance of the returned function, then I think that curry needs to create each instance of the returned function in the heap‑allocated memory (by writing opcodes like "get that pointer to the parameters", "push the parameters", and "invoke that other function" into the heap‑allocated memory). In that case you need to beware whether allocated memory is executable, and maybe (I don't know) even be afraid of anti‑virus programs.

方法 4:

The good news: There is a way to write a program that will do this in standard ANSI C, without using any compiler‑specific features. (In particular, it does not require gcc's nested function support.)

The bad news: It requires creating little bits of executable code to serve as trampoline functions at runtime. This means that the implementation will be dependent on:

• The processor instruction set
• The ABI (in particular, the function calling convention)
• The operating system's ability to mark data as executable

The best news: If you just need to do this in real, production code… you should use the closure API of libffi. It's permissively‑licensed and contains careful, flexible implementations for many platforms and ABIs.

If you're still here, you want to nerd out and understand how to implement this “from scratch.”

The program below demonstrates how to curry a 2‑parameter function into a 1‑parameter function in C, given…

• x86‑64 processor architecture
• System V ABI
• Linux operating system

It is based on the “Trampoline Illustration” from Infectious Executable Stacks, but with the trampoline structure stored on the heap (via malloc) rather on than the stack. This is much safer because it means we don't have to disable the compiler's stack execution protection (no gcc ‑Wl,‑z,execstack).

It uses the Linux mprotect system call to make the heap object executable.

The essence of the program is that it takes a pointer to a two‑parameter function (uint32_t (*fp2)(uint32_t a, uint32_t b)) and converts it to a pointer to a one‑parameter function (uint32_t (*fp1)(uint32_t a)) which invokes fp1 with a pre‑set value for the parameter b. It does this by creating little 3‑instruction trampoline functions:

movl $imm32, %esi  /* $imm32 filled in with the value of 'b' */
movq %imm64, %rax  /* $imm64 filled in with the value of 'fp2' */
jmpq *%rax

With the values of b and fp2 stitched into it appropriately, a pointer to the block of memory containing these 3 instructions can be used as the one‑parameter function pointer fp1 precisely as described above. That's because it obeys the x86‑64 System V calling convention, in which one‑parameter functions receive their first parameter in the %edi/%rdi register, and two‑parameter functions receive the second parameter in the %esi/%rsi register. In this case, the one‑parameter trampoline function receives its uint32_t parameter in %edi, then fills in the value of the second uint32_t parameter in %esi, then jumps directly to the “real” two‑parameter function which expects its two parameter in exactly those registers.

Here's the complete working code, which I've also put up on GitHub at dlenski/c‑curry:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#include <unistd.h>
#include <sys/mman.h>
#include <stdint.h>

#define PAGE_START(P) ((uintptr_t)(P) & ~(pagesize‑1))
#define PAGE_END(P)   (((uintptr_t)(P) + pagesize ‑ 1) & ~(pagesize‑1))

/* x86‑64 ABI passes parameters in rdi, rsi, rdx, rcx, r8, r9
 * (https://wiki.osdev.org/System_V_ABI), and return value
 * goes in %rax.
 *
 * Binary format of useful opcodes:
 *
 *       0xbf, [le32] = movl $imm32, %edi (1st param)
 *       0xbe, [le32] = movl $imm32, %esi (2nd param)
 *       0xba, [le32] = movl $imm32, %edx (3rd param)
 *       0xb9, [le32] = movl $imm32, %ecx (4rd param)
 *       0xb8, [le32] = movl $imm32, %eax
 * 0x48, 0x__, [le64] = movq $imm64, %r__
 *       0xff, 0xe0   = jmpq *%rax
 */

typedef uint32_t (*one_param_func_ptr)(uint32_t);
one_param_func_ptr curry_two_param_func(
    void *two_param_func, 
    uint32_t second_param)
{
    /* This is a template for calling a "curried" version of 
     * uint32_t (*two_param_func)(uint32_t a, uint32_t b),
     * using the Linux x86‑64 ABI. The curried version can be
     * treated as uint32_t (*one_param_func)(uint32_t a).
     */
    uintptr_t fp = (uintptr_t)two_param_func;
    uint8_t template[] = {
        0xbe, 0, 0, 0, 0,                                   /* movl $imm32, %esi */
        0x48, 0xb8, fp >>  0, fp >>  8, fp >> 16, fp >> 24, /* movq fp, %rax */
                    fp >> 32, fp >> 40, fp >> 48, fp >> 56,
        0xff, 0xe0                                          /* jmpq *%rax */
    };

    /* Now we create a copy of this template on the HEAP, and
     * fill in the second param. */
    uint8_t *buf = malloc(sizeof(template));
    if (!buf)
        return NULL;

    memcpy(buf, template, sizeof(template));
    buf[1] = second_param >> 0;
    buf[2] = second_param >> 8;
    buf[3] = second_param >> 16;
    buf[4] = second_param >> 24;

    /* We do NOT want to make the stack executable,
     * but we NEED the heap‑allocated buf to be executable.
     * Compiling with 'gcc ‑Wl,‑z,execstack' would do BOTH.
     *
     * This appears to be the right way to only make a heap object executable:
     *   https://stackoverflow.com/a/23277109/20789
     */
    uintptr_t pagesize = sysconf(_SC_PAGE_SIZE);
    mprotect((void *)PAGE_START(buf),
             PAGE_END(buf + sizeof(template)) ‑ PAGE_START(buf),
             PROT_READ|PROT_WRITE|PROT_EXEC);

    return (one_param_func_ptr)buf;
}

/********************************************/

int print_both_params(int a, int b)
{
    printf("Called with a=%d, b=%d\n", a, b);
    return a+b;
}

int main(int argc, char **argv)
{
    one_param_func_ptr print_both_params_b4 =
        curry_two_param_func(print_both_params, 4);
    one_param_func_ptr print_both_params_b256 = 
        curry_two_param_func(print_both_params, 256);

    print_both_params_b4(3);    // "Called with a=3, b=4"
    print_both_params_b256(6);  // "Called with a=6, b=256"

    return 0;
}

方法 5:

Here is an approach to doing currying in C. While this sample application is using the C++ iostream output for convenience it is all C style coding.

The key to this approach is to have a struct which contains an array of unsigned char and this array is used to build up an argument list for a function. The function to be called is specified as one of the arguments that are pushed into the array. The resulting array is then given to a proxy function which actually executes the closure of function and arguments.

In this example I provide a couple of type specific helper functions to push arguments into the closure as well as a generic pushMem() function to push a struct or other memory region.

This approach does require allocation of a memory area that is then used for the closure data. It would be best to use the stack for this memory area so that memory management does not become a problem. There is also the issue as to how large to make the closure storage memory area so that there is sufficient room for the necessary arguments but not so large that excess space in memory or on the stack is taken up by unused space.

I have experimented with the use of a slightly differently defined closure struct which contains an additional field for the currently used size of the array used to store the closure data. This different closure struct is then used with a modified helper functions which removes the need for the user of the helper functions to maintain their own unsigned char * pointer when adding arguments to the closure struct.

Notes and caveats

The following example program was compiled and tested with Visual Studio 2013. The output from this sample is provided below. I am not sure about the use of GCC or CLANG with this example nor am I sure as to issues that may be seen with a 64 bit compiler as I am under the impression that my testing was with a 32 bit application. Also this would approach would only seem to work with functions that use the standard C declaration in which the calling function handles popping the arguments from the stack after the callee returns (__cdecl and not __stdcall in Windows API).

Since we are building the argument list at run time and then calling a proxy function, this approach does not allow the compiler to perform a check on arguments. This could lead to mysterious failures due to mismatched parameter types which the compiler is unable to flag.

Example application

// currytest.cpp : Defines the entry point for the console application.
//
// while this is C++ usng the standard C++ I/O it is written in
// a C style so as to demonstrate use of currying with C.
//
// this example shows implementing a closure with C function pointers
// along with arguments of various kinds. the closure is then used
// to provide a saved state which is used with other functions.

#include "stdafx.h"
#include <iostream>

// notation is used in the following defines
//   ‑ tname is used to represent type name for a type
//   ‑ cname is used to represent the closure type name that was defined
//   ‑ fname is used to represent the function name

#define CLOSURE_MEM(tname,size) \
    typedef struct { \
        union { \
            void *p; \
            unsigned char args[size + sizeof(void *)]; \
        }; \
    } tname;

#define CLOSURE_ARGS(x,cname) *(cname *)(((x).args) + sizeof(void *))
#define CLOSURE_FTYPE(tname,m) ((tname((*)(...)))(m).p)

// define a call function that calls specified function, fname,
// that returns a value of type tname using the specified closure
// type of cname.
#define CLOSURE_FUNC(fname, tname, cname) \
    tname fname (cname m) \
    { \
        return ((tname((*)(...)))m.p)(CLOSURE_ARGS(m,cname)); \
    }

// helper functions that are used to build the closure.
unsigned char * pushPtr(unsigned char *pDest, void *ptr) {
    *(void * *)pDest = ptr;
    return pDest + sizeof(void *);
}

unsigned char * pushInt(unsigned char *pDest, int i) {
    *(int *)pDest = i;
    return pDest + sizeof(int);
}

unsigned char * pushFloat(unsigned char *pDest, float f) {
    *(float *)pDest = f;
    return pDest + sizeof(float);
}

unsigned char * pushMem(unsigned char *pDest, void *p, size_t nBytes) {
    memcpy(pDest, p, nBytes);
    return pDest + nBytes;
}


// test functions that show they are called and have arguments.
int func1(int i, int j) {
    std::cout << " func1 " << i << " " << j;
    return i + 2;
}

int func2(int i) {
    std::cout << " func2 " << i;
    return i + 3;
}

float func3(float f) {
    std::cout << " func3 " << f;
    return f + 2.0;
}

float func4(float f) {
    std::cout << " func4 " << f;
    return f + 3.0;
}

typedef struct {
    int i;
    char *xc;
} XStruct;

int func21(XStruct m) {
    std::cout << " fun21 " << m.i << " " << m.xc << ";";
    return m.i + 10;
}

int func22(XStruct *m) {
    std::cout << " fun22 " << m‑>i << " " << m‑>xc << ";";
    return m‑>i + 10;
}

void func33(int i, int j) {
    std::cout << " func33 " << i << " " << j;
}

// define my closure memory type along with the function(s) using it.

CLOSURE_MEM(XClosure2, 256)           // closure memory
CLOSURE_FUNC(doit, int, XClosure2)    // closure execution for return int
CLOSURE_FUNC(doitf, float, XClosure2) // closure execution for return float
CLOSURE_FUNC(doitv, void, XClosure2)  // closure execution for void

// a function that accepts a closure, adds additional arguments and
// then calls the function that is saved as part of the closure.
int doitargs(XClosure2 *m, unsigned char *x, int a1, int a2) {
    x = pushInt(x, a1);
    x = pushInt(x, a2);
    return CLOSURE_FTYPE(int, *m)(CLOSURE_ARGS(*m, XClosure2));
}

int _tmain(int argc, _TCHAR* argv[])
{
    int k = func2(func1(3, 23));
    std::cout << " main (" << __LINE__ << ") " << k << std::endl;

    XClosure2 myClosure;
    unsigned char *x;

    x = myClosure.args;
    x = pushPtr(x, func1);
    x = pushInt(x, 4);
    x = pushInt(x, 20);
    k = func2(doit(myClosure));
    std::cout << " main (" << __LINE__ << ") " << k << std::endl;

    x = myClosure.args;
    x = pushPtr(x, func1);
    x = pushInt(x, 4);
    pushInt(x, 24);               // call with second arg 24
    k = func2(doit(myClosure));   // first call with closure
    std::cout << " main (" << __LINE__ << ") " << k << std::endl;
    pushInt(x, 14);              // call with second arg now 14 not 24
    k = func2(doit(myClosure));  // second call with closure, different value
    std::cout << " main (" << __LINE__ << ") " << k << std::endl;

    k = func2(doitargs(&myClosure, x, 16, 0));  // second call with closure, different value
    std::cout << " main (" << __LINE__ << ") " << k << std::endl;

    // further explorations of other argument types

    XStruct xs;

    xs.i = 8;
    xs.xc = "take 1";
    x = myClosure.args;
    x = pushPtr(x, func21);
    x = pushMem(x, &xs, sizeof(xs));
    k = func2(doit(myClosure));
    std::cout << " main (" << __LINE__ << ") " << k << std::endl;

    xs.i = 11;
    xs.xc = "take 2";
    x = myClosure.args;
    x = pushPtr(x, func22);
    x = pushPtr(x, &xs);
    k = func2(doit(myClosure));
    std::cout << " main (" << __LINE__ << ") " << k << std::endl;

    x = myClosure.args;
    x = pushPtr(x, func3);
    x = pushFloat(x, 4.0);

    float dof = func4(doitf(myClosure));
    std::cout << " main (" << __LINE__ << ") " << dof << std::endl;

    x = myClosure.args;
    x = pushPtr(x, func33);
    x = pushInt(x, 6);
    x = pushInt(x, 26);
    doitv(myClosure);
    std::cout << " main (" << __LINE__ << ") " << std::endl;

    return 0;
}

Test output

Output from this sample program. The number in parenthesis is the line number in the main where the function call is made.

 func1 3 23 func2 5 main (118) 8
 func1 4 20 func2 6 main (128) 9
 func1 4 24 func2 6 main (135) 9
 func1 4 14 func2 6 main (138) 9
 func1 4 16 func2 6 main (141) 9
 fun21 8 take 1; func2 18 main (153) 21
 fun22 11 take 2; func2 21 main (161) 24
 func3 4 func4 6 main (168) 9
 func33 6 26 main (175)

(by user64417、Jared Oberhaus、user43513、ChrisW、Dan Lenski、Richard Chambers)

參考文件

1. Is there a way to do currying in C? (CC BY‑SA 2.5/3.0/4.0)