38

假设我有一个指向函数的指针_stack_push(stack* stk, void* el)。我希望能够调用curry(_stack_push, my_stack)并取回一个只需要void* el. 我想不出办法,因为 C 不允许运行时函数定义,但我知道这里有比我聪明得多的人 :)。有任何想法吗?

4

6 回答 6

21

我发现了 Laurent Dami 的一篇论文,讨论了 C/C++/Objective-C 中的柯里化:

使用 Curried 函数在 C/C++/Objective-c 中实现更多功能可重用性

对它如何在 C 中实现感兴趣:

我们当前的实现使用现有的 C 构造来添加柯里化机制。这比修改编译器要容易得多,并且足以证明柯里化的兴趣。然而,这种方法有两个缺点。首先,柯里化函数不能进行类型检查,因此需要小心使用以避免错误。其次,curry 函数不知道它的参数的大小,并且将它们当作整数大小来计算。

本文不包含 的实现curry(),但您可以想象它是如何使用函数指针可变参数函数实现的。

于 2009-06-21T05:25:31.030 回答
8

GCC 为嵌套函数的定义提供了扩展。虽然这不是 ISO 标准 C,但这可能会引起一些兴趣,因为它可以很方便地回答这个问题。简而言之,嵌套函数可以访问父函数的局部变量,并且父函数也可以返回指向它们的指针。

这是一个简短的、不言自明的示例:

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

然而,这种结构存在局限性。如果您保留指向结果函数的指针,如

one_var_func u = partial (add_int, a);

函数调用u(0)可能会导致意外行为,因为读取的变量au终止后立即被破坏partial

请参阅GCC 文档的这一部分

于 2012-06-12T12:44:04.510 回答
4

这是我的第一个猜测(可能不是最好的解决方案)。

curry 函数可以在堆外分配一些内存,并将参数值放入堆分配的内存中。诀窍是让返回的函数知道它应该从堆分配的内存中读取它的参数。如果返回函数只有一个实例,那么指向这些参数的指针可以存储在单例/全局中。否则,如果返回函数的实例不止一个,那么我认为 curry 需要在堆分配的内存中创建返回函数的每个实例(通过将诸如“获取指向参数的指针”、“推送参数”和“调用其他函数”之类的操作码写入堆分配的内存中)。在那种情况下,您需要注意分配的内存是否可执行,并且可能(我不知道)甚至害怕防病毒程序。

于 2009-06-21T05:32:05.283 回答
3

好消息:有一种方法可以在标准 ANSI C 中编写程序,而无需使用任何编译器特定的功能。(特别是它不需要gcc的嵌套函数支持。)

坏消息:它需要创建一点点可执行代码来在运行时充当蹦床函数。这意味着实现将取决于:

  • 处理器指令集
  • ABI(特别是函数调用约定)
  • 操作系统将数据标记为可执行的能力

最好的消息: 如果您只需要在真实的生产代码中执行此操作……您应该使用libffi. 它是许可许可的,并且包含针对许多平台和 ABI的谨慎、灵活的实现。


如果您还在这里,您想了解一下如何“从头开始”实现这一点。</p>

下面的程序演示了如何在 C 中将 2 参数函数柯里化为 1 参数函数,给定...</p>

它基于 Infectious Executable Stacks中的“Trampoline Illustration” ,但蹦床结构存储在(通过malloc)而不是堆栈上。这更安全,因为这意味着我们不必禁用编译器的堆栈执行保护(否gcc -Wl,-z,execstack)。

它使用Linuxmprotect系统调用使堆对象可执行。

该程序的本质是它接受一个指向双参数函数 ( uint32_t (*fp2)(uint32_t a, uint32_t b)) 的指针并将其转换为指向单参数函数 ( uint32_t (*fp1)(uint32_t a))的指针,该函数以参数fp1的预设值调用b。它通过创建小的 3 指令蹦床函数来做到这一点:

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

将 和 的值适当bfp2缝合到其中后,指向包含这 3 条指令的内存块的指针可以fp1准确地用作单参数函数指针,如上所述。这是因为它遵循x86-64 System V 调用约定,其中单参数函数在 / 寄存器中接收它们的第一个参数%edi%rdi而双参数函数在%esi/%rsi寄存器中接收第二个参数。在这种情况下,单参数 trampoline 函数接收其uint32_t参数 in ,然后将第二个参数%edi的值填入,然后直接跳转到“真正的”双参数函数,该函数期望其两个参数恰好在那些寄存器中。uint32_t%esi

这是完整的工作代码,我也将其放在 GitHub 上的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;
}
于 2021-03-30T06:47:30.347 回答
0

这是在 C 中进行柯里化的一种方法。虽然此示例应用程序使用 C++ iostream 输出为方便起见,但它都是 C 风格的编码。

这种方法的关键是要有一个struct包含一个数组的数组,unsigned char这个数组用于为函数建立一个参数列表。要调用的函数被指定为推入数组的参数之一。然后将结果数组提供给代理函数,该函数实际执行函数和参数的闭包。

在这个例子中,我提供了几个类型特定的帮助函数来将参数推送到闭包中,以及一个通用pushMem()函数来推送一个struct或其他内存区域。

这种方法确实需要分配一个内存区域,然后用于闭包数据。最好将堆栈用于该内存区域,这样内存管理就不会成为问题。还有一个问题是要使闭包存储内存区域有多大,以便有足够的空间容纳必要的参数,但又不会太大,以至于内存或堆栈中的多余空间被未使用的空间占用。

我已经尝试过使用定义略有不同的闭包结构,它包含一个附加字段,用于存储用于存储闭包数据的数组的当前使用大小。然后,这种不同的闭包结构与修改后的辅助函数一起使用,这消除了辅助函数的用户在unsigned char *向闭包结构添加参数时维护自己的指针的需要。

注意事项和注意事项

以下示例程序是使用 Visual Studio 2013 编译和测试的。下面提供了此示例的输出。我不确定在此示例中是否使用 GCC 或 CLANG,也不确定 64 位编译器可能会出现的问题,因为我的印象是我的测试是使用 32 位应用程序进行的。此外,这种方法似乎只适用于使用标准 C 声明的函数,其中调用函数在被调用者返回后处理从堆栈中弹出参数(__cdecl而不是__stdcall在 Windows API 中)。

由于我们在运行时构建参数列表,然后调用代理函数,因此这种方法不允许编译器对参数执行检查。由于编译器无法标记的参数类型不匹配,这可能会导致神秘的失败。

示例应用程序

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

测试输出

此示例程序的输出。括号中的数字是进行函数调用的 main 中的行号。

 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)
于 2017-07-22T15:16:55.693 回答
0

因为 C 不允许运行时函数定义

这在标准 C中原则上是正确的。阅读n1570了解详情。

然而,在实践中它可能是错误的。考虑

  • 在 POSIX 系统(例如 Linux)上,在运行时在一些/tmp/generated1234.c定义某些函数的临时文件文件中生成一些 C 代码void genfoo1234(void),编译该文件(例如,使用最近的GCC编译器 as gcc -O -fPIC -Wall -shared /tmp/generated1234.c -o /tmp/generated1234.so)然后使用dlopen(3)/tmp/generated1234.so然后dlsym(3 )在genfoo1234句柄返回dlopen以获取函数指针)。根据个人经验,这种方法在今天(2021 年,在 Linux 笔记本电脑上)已经足够快,即使是交互式使用(如果每个临时生成的 C 文件都有几百行 C 代码)。

  • 在 x86、x86-64、ARM 处理器上使用一些机器代码生成库,如GNU Lightninglibgccjit(或 C++ 中的asmjit

在实践中,您将为闭包生成代码(将函数指针与封闭值分组)并将其用作回调

相关的一点是垃圾收集,所以请阅读垃圾收集手册

还可以考虑在您的应用程序中嵌入一些现有的解释器,例如LuaGNU guilePython等......

研究一下这些解释器的源代码,至少是为了获得灵感。

Quenniec 的Lisp in small piecesDragon 的书值得一​​读。两者都解释了实际问题和实施细节

另见__builtin_call_with_static_chain最近的 GCC 编译器(2021 年)。

于 2021-03-31T05:22:29.683 回答