假设我有一个指向函数的指针_stack_push(stack* stk, void* el)
。我希望能够调用curry(_stack_push, my_stack)
并取回一个只需要void* el
. 我想不出办法,因为 C 不允许运行时函数定义,但我知道这里有比我聪明得多的人 :)。有任何想法吗?
6 回答
我发现了 Laurent Dami 的一篇论文,讨论了 C/C++/Objective-C 中的柯里化:
使用 Curried 函数在 C/C++/Objective-c 中实现更多功能可重用性
对它如何在 C 中实现感兴趣:
我们当前的实现使用现有的 C 构造来添加柯里化机制。这比修改编译器要容易得多,并且足以证明柯里化的兴趣。然而,这种方法有两个缺点。首先,柯里化函数不能进行类型检查,因此需要小心使用以避免错误。其次,curry 函数不知道它的参数的大小,并且将它们当作整数大小来计算。
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)
可能会导致意外行为,因为读取的变量a
在u
终止后立即被破坏partial
。
请参阅GCC 文档的这一部分。
这是我的第一个猜测(可能不是最好的解决方案)。
curry 函数可以在堆外分配一些内存,并将参数值放入堆分配的内存中。诀窍是让返回的函数知道它应该从堆分配的内存中读取它的参数。如果返回函数只有一个实例,那么指向这些参数的指针可以存储在单例/全局中。否则,如果返回函数的实例不止一个,那么我认为 curry 需要在堆分配的内存中创建返回函数的每个实例(通过将诸如“获取指向参数的指针”、“推送参数”和“调用其他函数”之类的操作码写入堆分配的内存中)。在那种情况下,您需要注意分配的内存是否可执行,并且可能(我不知道)甚至害怕防病毒程序。
好消息:有一种方法可以在标准 ANSI C 中编写程序,而无需使用任何编译器特定的功能。(特别是它不需要gcc
的嵌套函数支持。)
坏消息:它需要创建一点点可执行代码来在运行时充当蹦床函数。这意味着实现将取决于:
- 处理器指令集
- ABI(特别是函数调用约定)
- 操作系统将数据标记为可执行的能力
最好的消息:
如果您只需要在真实的生产代码中执行此操作……您应该使用libffi
. 它是许可许可的,并且包含针对许多平台和 ABI的谨慎、灵活的实现。
如果您还在这里,您想了解一下如何“从头开始”实现这一点。</p>
下面的程序演示了如何在 C 中将 2 参数函数柯里化为 1 参数函数,给定...</p>
- x86-64 处理器架构
- 系统 V ABI
- Linux操作系统
它基于
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
将 和 的值适当b
地fp2
缝合到其中后,指向包含这 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;
}
这是在 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)
因为 C 不允许运行时函数定义
然而,在实践中它可能是错误的。考虑
在 POSIX 系统(例如 Linux)上,在运行时在一些
/tmp/generated1234.c
定义某些函数的临时文件文件中生成一些 C 代码void genfoo1234(void)
,编译该文件(例如,使用最近的GCC编译器 asgcc -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 Lightning、libgccjit(或 C++ 中的asmjit)
在实践中,您将为闭包生成代码(将函数指针与封闭值分组)并将其用作回调。
相关的一点是垃圾收集,所以请阅读垃圾收集手册。
还可以考虑在您的应用程序中嵌入一些现有的解释器,例如Lua、GNU guile、Python等......
研究一下这些解释器的源代码,至少是为了获得灵感。
Quenniec 的Lisp in small pieces 和Dragon 的书值得一读。两者都解释了实际问题和实施细节
另见__builtin_call_with_static_chain
最近的 GCC 编译器(2021 年)。