转载

M4 说要有 lambda，就有了 lambda

前言

C 语言不具备匿名函数功能，但是 Vala 想办法模拟了一个[1]。我一直想用 C 的宏模拟一个，但是技拙，或许根本就无法实现。

GCC 提供了一个扩展，可以实现匿名函数[2]。例如：

#define lambda(return_type, function_body) /     ({ return_type fn function_body fn })

这个 lambda 宏的用法如下：

lambda (int, (int x, int y) { return x > y; })(1, 2)

结果会被展开为：

({ int fn (int x, int y) { return x > y } fn; })(1, 2)

虽然挺不错，但它不是 C 标准。

最近断断续续的看了一些 GNU M4 的文档，脑洞略微开放了一些，便尝试用 M4 来模拟匿名函数。

原理

匿名函数并非真正的匿名。任何一个函数，它都需要在内存中有一个入口，即使那些支持匿名函数的编程语言也不例外。这个入口本质上就是一个内存地址。C 语言之所以不支持匿名函数，是因为 C 编译器要求每个函数的入口地址都必须绑定到一个名字上，这个名字就是函数名。那些支持匿名函数的编程语言，它们的编译器或解释器在发现匿名函数的存在时，它们或许暗自为之生成一个名字，或许直接就跳到函数的入口地址了。

不过，我对编译原理近乎无知，上述仅仅猜测。

如果在 C 语言中要模拟匿名函数，那么就必须想个办法偷偷的生成一些有名字的函数，然后用这个函数的调用来代替匿名函数的调用。例如下面这段假想的代码：

lambda(int, (int x, int y){ return x > y; })(1, 2);

应该想个办法将它变换为：

static int lambda(int x, int y){return x > y;}  lambda(1,2);

也就是先定义一个 lambda 函数，然后再调用它。如果程序中有多个匿名函数，一个 lambda 名字显然是不够用的，这就需要给 lambda 增加后缀名。例如：

lambda(int, (int x, int y){ return x > y; })(1, 2); lambda(float, (float x, float y){ return x > y; })(1.0, 2.0);

应该变换为：

static int lambda_1(int x, int y){return x > y;} static float lambda_2(float x, float y){return x > y;}  lambda_1(1,2); lambda_2(1.0, 2.0);

就这么简单。事实上，Vala 对匿名函数的模拟也就是这么做的。

难点

这些 lambda_x 函数们的定义位置应该如何自动确定，是整个模拟过程中最难解决的问题。最佳的位置应该在 #include 之后，这样它们就对任何调用它们的函数都是可见的。

例如：

#include <stdio.h> int main(void) {         if(lambda(int, (int x, int y){return x > y;})(1, 2)) {             printf("False!/n");         } }

应该被变换为：

#include <stdio.h>  static int lambda_1(int x, int y){return x > y;}  int main(void) {         if(lambda_1(1, 2)) {             printf("True!/n");         } else {             printf("False!/n");         } }

M4 的转移大法

要克服上述难题，可以用 M4 的 divert 宏。

divert 宏可以开启临时空间（临时文件），将当前的信息写入该空间，并且该空间的信息对于 divert 开启的其他临时空间是不可见的。

遵循 POSIX 标准的 M4，divert 最多能开启 10 个临时空间，编号从 0 到 9。GNU M4 对空间数量不做限制。不过 0 号临时空间是 m4 默认的工作空间。也就是说，m4 默认总是在 0 号临时空间中对宏进行展开处理，如果想让 m4 的工作空间转移到其他空间，就需要显式的调用 divert 宏进行转移。

例如：

我在 0 号空间 divert(1)dnl 现在我在 1 号空间了 divert(0)dnl 现在，我又回到了 0 号空间。

m4 的处理结果是：

我在 0 号空间 现在，我又回到了 0 号空间。 现在我在 1 号空间了

观察这个示例，我们可以得出以下规律：

某个空间中的信息是不断累积的，上例中的 0 号空间的信息累积到了一起。
非 0 号空间中的信息最终会被被放到 0 号空间中的信息之后。

再来一个略微复杂一点的例子：

divert(2)dnl 我在 2 号空间 divert(0)dnl 我在 0 号空间 divert(1)dnl 现在我在 1 号空间了 divert(0)dnl 现在，我又回到了 0 号空间。

m4 的处理结果是：

我在 0 号空间 现在，我又回到了 0 号空间。 现在我在 1 号空间了 我在 2 号空间

观察这个结果，我们又得出一个结论：非 0 号空间中的信息最终会依序被放到 0 号空间中的信息之后，先放 1 号空间的，然后放 2 号空间的，以此类推。

也就是说，一切空间，它们所包含的东西，最终都会跌落到 0 号空间，而且序号越大的空间，它向 0 号空间的跌落的优先级越低。

划分 C 代码的疆域

为了迎合 lambda 的定义与调用层面的分离，不得不对 C 代码划分疆域。最粗略的划分，可以将 C 代码划分为三个区域：

C_HEAD 区：所有的 lambda_x 函数定义之前的区域，对应 divert(0) ，可以放置 #include 之类的内容；
C_LAMBDA 区：存放 lambda_x 函数们的定义，对应 divert(1) ；
C_BODY 区：存放常规 C 函数的定义，对应 divert(2) 。

这样，无论是 lambda 函数的定义，还是普通 C 函数的定义，它们最终会正确的跌落到 0 号空间中。

故事刚刚开始

我已经做了太多的铺垫，现在言归正传。不过，下面我要动用文式编程手段了，可能你不懂何为文式编程，而且也根本没啥兴趣去了解它，也没关系，但是你至少需要阅读『noweb 的用法』一文。

首先，我们要跳到一个序号为 -1 的空间，虽然它并不是正规的 M4 空间，但是任何 M4 都会支持这个空间，而且它甚至比 0 号空间更早坠落到 0 号空间……也就是说， -1 空间中的信息坠落到 0 号空间之后，它们会出现在 0 号空间中的信息之前，而且它在 0 号空间中是没有『体积』的，或者你也可以说它存在于 0 号空间的所有信息之前的一个坍缩的空间中。

<<-1 空间>>= divert(-1) @

M4 之所以要制造 -1 空间，是因为 -1 空间中的任何内容不会被 m4 回显，这就是为什么可以将这个空间称为『坍缩』于 0 号空间的所有信息之前的空间。

其他空间的内容最终都会被 m4 回显出来。例如，即使 0 号空间的一个宏的定义：

define(`foo', `bar')

它也会被回显为一个空的字符，而它之后如果有换行符，那么换行符也会被 m4 回显出来。因为在 m4 眼里，宏也是文本，文本也是宏。只有 -1 空间能够逃脱 m4 的集权统治， -1 空间，M4 的锡安！

脏乱差的锡安

矩阵里的城市，干净又简洁。锡安城里的一切都是脏乱差。M4 的 -1 空间也永远是这个样子。但是，没有脏乱差的锡安，矩阵也就无法再进化。

我们在 -1 空间中做的第一件事，就是为上一节所划分的三个 C 代码区域命名，也就是定义三个名称较为友好的 M4 宏：

<<-1 空间>>= define(`C_HEAD',   `divert(0)') define(`C_LAMBDA', `divert(1)') define(`C_BODY',   `divert(2)') @

然后，考虑如何为每个匿名函数取一个『独一无二』的名字。当然，这理论上是不可能的，因为 C 语言的命名空间是全局的。所以我们只能假定在一个 .c 文件内，除了匿名函数可以使用 lambda_x 这样的名字之外，其他函数不会用这样的名字。所以，现在我们要解决的问题就是如何为 lambda 增加后缀 _x ，并使得 x 的取值范围为整数集。

M4 不支持变量，但是可以利用宏定义模拟变量及其赋值操作：

<<定义全局变量 N>>= define(`_set', `undefine(`$1')define(`$1', `$2')') _set(`N', 0) @

在此，我定义了一个可以对变量进行赋值的宏 _set ，然后用它将一个（全局）变量 N 『赋值』为 0 。实际上就是在 _set 宏中取消 N 的定义，然后重新定义一个 N 。这里， _set 是『返回』一个宏的宏，可以称之为『高阶宏』。

接下来，就是定义一个可以定义匿名函数的宏 lambda_define ：

<<C 的匿名函数模拟>>= define(`lambda_define', `static $2 lambda_`'N`('$1`)'{$3;}') @

这个 lambda_define 宏的用法如下：

lambda_define(`int x, int y',               `int',               `return x > y')

这个宏的第一个参数，是匿名函数所接受的形参，第二个参数是匿名函数的返回值类型，第三个参数是匿名函数体。 m4 会将这个宏展开为：

static int lambda_0(int x, int y){return x > y;}

之所以是 lambda_0 ，是因为前面已经将 N 的初值设为 0 了。

接下来，就是定义 lambda 宏，它可以帮助我们产生匿名函数的定义，并在相应的位置调用这个匿名函数：

<<C 的匿名函数模拟>>= define(`lambda',        `_set(`N', incr(N))`'dnl `'`'`'`'pushdef(`X', `divnum')dnl        `'`'`'`'C_LAMBDA`'lambda_define(`$1',`$2',`$3') `'`'`'`'C_BODY`'lambda_`'N`'divert(X)popdef(`X')') @

lambda 宏的定义，看似复杂，实则简单。复杂之处是一堆 空的成对引号 —— `' 。只需将这些空的成对的引号理解为没有宽度的『空格』即可。本来是没必要用这些么多成对的空引号的，但是用它们，一是为了安全，防止某个宏的展开结果污染了别的宏，二是为了第三、四行代码的『缩进』。如果直接用空格或 Tab 键，m4 会将它们如实的回显出来，这显然不是我想要的。 dnl 宏的作用也是为了代码的美观——让宏定义代码换行但是又可以避免 m4 的输出结果中引入多余的换行符。

如果克服了空的成对引号与换行恐惧症，那么 lambda 的定义就相当简单了，它首先让 N 的值增 1，这是利用 M4 提内建的宏 incr 实现的。然后，从当前空间——其编号已经被我保存在 X 宏的定义中——转移到 C_LAMBDA 空间，然后调用 lambda_define 宏，产生 C 匿名函数的定义代码。然后从 C_LAMBDA 空间转移到 C_BODY 空间，产生 C 匿名函数的调用代码，最后再回到 X 空间。注意， X 已经被我模拟为一个局部变量了，用的是 M4 内建的 pushdef 与 popdef 宏。

最后，我们将这些脏乱差的代码统统扔到 -1 空间：

<<-1 空间>>= <<定义全局变量 N>> <<C 的匿名函数模拟>> @

回到 Matrix

想必你已经受够了 -1 空间中的那些诡异的 M4 代码。现在，在后脑勺上插上线，回到矩阵的世界吧。再见，锡安！ C_HEAD 就是矩阵的入口，也就是 0 号空间的入口。

<<c-lambda.m4>>= <<-1 空间>> C_HEAD`'dnl @

现在，我要严肃，不再使用黑客帝国的比喻。从文式编程的角度来看，上文中所有的 M4 代码现在都被扔到了一个名为 c-lambda.m4 的文件中了。

如果你将本文所有内容复制到一份文本文件中，假设这份文本文件叫作 c-lambda.nw，然后使用 noweb 产生 c-lambda.m4 文件。所用的命令如下：

$ notangle -Rc-lambda.m4 c-lambda.nw > c-lambda.m4

试试看

现在尝试在 C 代码中调用 c-lambda.m4 中定义的 lambda 宏是否可用。这需要新建一份 M4 文件，然后由这份 M4 文件产生一份 .c 文件。也就是说，这时你应该将 M4 视为 C 代码的生成器，也可以视为在用 M4 进行 元编程 。

假设新建的这份 M4 文件为 test-lambda.m4，它与 c-lambda.m4 文件在同一目录。用文式编程的手法可将 test-lambda.m4 文件抽象的表示为：

<<test-lambda.m4>>= <<C_HEAD 区域>> <<C_BODY 区域>> @

为什么没有 C_LAMBDA 区域？因为这个区域是我们要悄悄生成的……否则，上文中的工作就白做了。

在 C_HEAD 区域，首先应该加载 c-lambda.m4 文件，因为我们所需要的 lambda 宏实在这份文件中定义的。

<<C_HEAD 区域>>= include(`c-lambda.m4')dnl @

之所以用 dnl ，是因为不希望这行语句在 m4 的回显结果中引入多余的空格。在 M4 中， dnl 的主要任务就是这个。注意，由于 c-lambda.m4 文件的末尾已经调用了 C_HEAD 宏，将 M4 的空间切换到了 0 号空间，所以这里就不需要再调用 C_HEAD 了。

C_BODY 区域需要调用 `C_BODY' 宏进行空间切换：

<<C_BODY 区域>>= C_BODY @

然后在 main 函数中寻找一个机会『定义』并『应用』一个匿名函数：

<<C_BODY 区域>>= int main(void) {         if(lambda(`int x, int y', `int', `return x > y')(1, 2)) {                 printf("False!/n");         } else {                 printf("True!/n");         } } @

既然 C_BODY 区域 调用了 printf 函数，那么 C_HEAD 区域 必须要 #include <stdio.h> ：

<<C_HEAD 区域>>= #include <stdio.h>  @

现在，将本文的全部内容复制到一份文本文件 test-lambda.nw 中，然后执行以下命令即可生成 test-lambda.m4 文件，进而生成 test-lambda.c 文件：

$ notangle -Rtest-lambda.m4 test-lambda.nw > test-lambda.m4 $ m4 test-lambda.m4 > test-lambda.c

得益于管道，上述的两行命令与

$ notangle -Rtest-lambda.m4 test-lambda.nw | m4 > test-lambda.c

所得 test-lambda.c 的内容如下：

#include <stdio.h>  static int lambda_1(int x, int y){return x > y;}  int main(void) {         if(lambda_1(1, 2)) {                 printf("False!/n");         } else {                 printf("True!/n");         } }

结语

这篇文档并非炫耀如何把手捆住，以示我用脚也可以写字。它仅仅是我学习 GNU M4 的一个很小的练习，顺便以文式编程的方式将思路与实现详细的记录了下来。

另外，C 语言也不需要匿名函数。因为 C 语言的表现力太差，像下面这样的代码：

include(`c-lambda.m4') #include <stdio.h> #include <stdlib.h> #include <string.h> C_BODY int main (void) {  char *str_array[5] = {"a", "abcd", "abc", "ab", "abcde"};  qsort (&str_array, 5, sizeof (char *), lambda(`const void *s1, const void *s2',             `int',             `char *str1 = *(char **)s1;              char *str2 = *(char **)s2;                 size_t l1 = strlen (str1);              size_t l2 = strlen (str2);              if (l1 > l2)               return 1;              else if (l1 == l2)               return 0;              else               return -1'));  for (int i = 0; i< 5; i++)   printf ("%s ", str_array[i]);  printf ("/n");  return 0; }

不知道是不是真的有人愿意看……

本文中所用的 M4 知识，大部分出自[3, 4]。每当我觉得 M4 知识匮乏的时候，就去翻翻[5, 6]。其实，M4 非常简单，而且我用 M4 所实现的这点东西，用其他脚本也很容易实现，但是我觉得 M4 的实现非常简洁——简而不洁。以下代码是 c-lambda.m4 的全部内容：

divert(-1) define(`C_HEAD',   `divert(0)') define(`C_LAMBDA', `divert(1)') define(`C_BODY',   `divert(2)') define(`_set', `undefine(`$1')define(`$1', `$2')') _set(`N', 0) define(`lambda_define', `static $2 lambda_`'N`('$1`)'{$3;}') define(`lambda',        `_set(`N', incr(N))`'dnl `'`'`'`'pushdef(`X', `divnum')dnl        `'`'`'`'C_LAMBDA`'lambda_define(`$1',`$2',`$3') `'`'`'`'C_BODY`'lambda_`'N`'divert(X)popdef(`X')') C_HEAD`'dnl

一共 13 行代码。如果牺牲一点可读性，可以简化到 10 行以内。

最后需要强调一点， 这个 lambda 并非闭包 。不过，C99 标准支持函数嵌套定义，可以利用与本文相似的思路实现闭包。