6

我想以最小的努力将 C 中的高阶函数 (HOF) 实现为语法糖。例如，对于以下代码

function add(int x) {
  return int(int y) {
    return x + y;
  };
}

int main() {
  function add1 = add(1);
  return add1(2);
}

它被转译成纯 C

#include <stdlib.h>

typedef struct {
  void *ctx;
  void* (*fun)(void *arg, void *ctx);
} function;

function new_function(void *ctx, void* (*fun)(void *, void *)) {
  function f = {.ctx=ctx, .fun=fun};
  return f;
}

void* apply(function f, void *arg) {
  return (*(f.fun))(arg, f.ctx);
}

typedef struct {
  int x;
} context$1;

void* new_context$1(int x) {
  context$1 *ctx = malloc(sizeof(context$1));
  ctx->x = x;
  return ctx;
}

void* function$1(void *arg, void *ctx) {
  int y = (int)arg;
  int x = ((context$1*)ctx)->x;
  return (void*)(x + y);
}

function add(int x) {
  return new_function(new_context$1(x), function$1);
}

int main() {
  function add1 = add(1);
  return (int)apply(add1, (void*)2);
}

我已经运行了这个（手动）转编译版本，它工作正常。对于实现，我相信一些 AST 操作和 lambda 提升就足够了。

我的方法有任何潜在的缺陷吗？是否有任何更简单的 HOF 方法，或者我可以改进我的方法以使其更易于实施？

4

2 回答 2

2

目前有两个明显的问题：

  • 使用 void* 表示任何类型的参数和返回值最终都会中断。考虑 ia-32 上的“long long”参数，或任何按值传递的结构。
  • 如果没有垃圾收集，很难（如果可能的话）使高阶函数有用。您可以从您自己的示例中看到它，其中 context$1 是 malloc 的，但从来没有 free 的。Boehm GC 在这里可能会有所帮助。
于 2013-01-04T16:25:18.540 回答
1

请注意，您生成的代码会调用未定义的行为。在几个地方，您通过直接转换在整数类型和指针类型之间进行转换。这在 C 中是不合法的。您无法保证指针和 anint的大小相同，或者您甚至可以在它们之间进行转换而不会更改或破坏值。该代码可能会巧合地在您的特定系统上运行，但它会在许多其他系统上中断。

您可以通用处理指针和整数类型（以及结构，就此而言）的唯一方法是使用可变长度参数列表传递参数。这样，无论底层数据类型的大小如何，您都可以提取每个参数。

另一种选择是删除通用function结构并为代码中的每个 HOF 创建自定义结构。然后，函数指针可以直接列出所有必要的参数，而不是尝试将它们抽象到通用接口后面，这将消除有问题的强制转换并允许代码按预期工作，而不管使用的数据类型如何。

就可用性而言，请考虑更改您的接口，以便在声明它的行上指定（或至少列出）HOF 的返回类型。C 对象总是在声明中列出它们的类型。在您的示例中，声明是function add1 = add(1);. 要找出此函数返回的数据类型，您必须深入研究 HOF 的定义。对于您的示例代码而言，这不是一项艰巨的任务，但对于更复杂的代码而言，这可能并非易事。如果 HOF 来自库，您可能根本没有代码。也许类似的东西function(int) add1 = add(1);可能更明确。

附带说明一下，我建议您定义自动生成的函数，static以帮助防止模块之间的名称冲突。

于 2013-01-04T19:04:27.423 回答