C中的函数式编程有哪些工具？

我最近一直在思考如何在C(而不是 C++)中进行函数式编程.显然,C是一种过程语言,本身并不真正支持函数式编程.

是否有任何编译器/语言扩展可以为语言添加一些函数式编程结构？GCC提供嵌套函数作为语言扩展; 嵌套函数可以从父堆栈框架访问变量,但距离成熟的闭包还有很长的路要走.

例如,我认为在C中真正有用的一件事是,在任何需要函数指针的地方,你都可以传递一个lambda表达式,创建一个衰变为函数指针的闭包.C++ 0x将包含lambda表达式(我觉得很棒); 但是,我正在寻找适用于直C的工具.

[编辑]为了澄清,我不是试图解决C中更适合函数式编程的特定问题; 如果我想这样做,我只是想知道那里有什么工具.

你可以使用GCC的嵌套函数来模拟lambda表达式,事实上,我有一个宏为我做这个:

#define lambda(return_type, function_body) \
  ({ \
    return_type anon_func_name_ function_body \
    anon_func_name_; \
  })

使用这样:

int (*max)(int, int) = lambda (int, (int x, int y) { return x > y ? x : y; });

函数式编程不是关于lambdas,而是关于纯函数.所以以下大致推广功能风格:

只使用函数参数,不要使用全局状态.

最大限度地减少副作用,即printf或任何IO.返回描述可以执行的IO的数据,而不是直接在所有函数中引起副作用.

这可以通过简单的c来实现,不需要魔法.

FFCALL允许您在C中构建闭包 - callback = alloc_callback(&function, data)返回一个callback(arg1, ...)等于调用的函数指针function(data, arg1, ...).但是,您必须手动处理垃圾收集.

相关地,已经在Apple的GCC分支中添加了块 ; 它们不是函数指针,但是它们允许你传递lambda,同时避免需要手动构建和释放捕获变量的存储空间(实际上,一些复制和引用计数发生,隐藏在一些语法糖和运行时库之后).

Hartel&Muller的书,功能C,现在可以在(2012-01-02)找到:http://eprints.eemcs.utwente.nl/1077/(有PDF版本的链接).

想到的主要事情是使用代码生成器.您是否愿意使用提供函数式编程的不同语言编程,然后从中生成C代码？

如果这不是一个有吸引力的选择,那么你可以滥用CPP来获得部分途径.宏系统应该让您模拟一些函数式编程思想.我听说过gcc是以这种方式实现的,但我从未检查过.

C当然可以使用函数指针传递函数,主要问题是缺少闭包,类型系统往往会妨碍.您可以探索比CPP更强大的宏系统,例如M4.我想最终,我建议的是,如果没有很大的努力,真正的C不能完成任务,但你可以扩展C以使其完成任务.如果您使用CPP,那么该扩展看起来最像C,或者您可以转到频谱的另一端并从其他语言生成C代码.

如果你想实现闭包,你将不得不使用汇编语言和堆栈交换/管理.不推荐反对它,只是说这是你必须做的.

不知道你将如何在C中处理匿名函数.在冯·诺依曼机器上,你可以在asm中执行匿名函数.

函数式编程风格的前提是一流的功能。如果您愿意，可以在便携式C语言中对其进行仿真：

手动管理词汇范围绑定，也称为闭包。

手动管理功能变量的生命周期。

函数应用程序/调用的替代语法。

/* 
 * with constraints desribed above we could have
 * good approximation of FP style in plain C
 */

int increment_int(int x) {
  return x + 1;
}

WRAP_PLAIN_FUNCTION_TO_FIRST_CLASS(increment, increment_int);

map(increment, list(number(0), number(1)); // --> list(1, 2)


/* composition of first class function is also possible */

function_t* computation = compose(
  increment,
  increment,
  increment
);

*(int*) call(computation, number(1)) == 4;

struct list_t {
  void* head;
  struct list_t* tail;
};

struct function_t {
   void* (*thunk)(list_t*);
   struct list_t* arguments;
}

void* apply(struct function_t* fn, struct list_t* arguments) {
  return fn->thunk(concat(fn->arguments, arguments));
}

/* expansion of WRAP_PLAIN_FUNCTION_TO_FIRST_CLASS */
void* increment_thunk(struct list_t* arguments) {
  int x_arg = *(int*) arguments->head;
  int value = increment_int(x_arg);
  int* number = malloc(sizeof *number);

  return number ? (*number = value, number) : NULL;
}

struct function_t* increment = &(struct function_t) {
  increment_thunk,
  NULL
};

/* call(increment, number(1)) expands to */
apply(increment, &(struct list_t) { number(1), NULL });