当前位置

网站首页> 程序设计 > 开源项目 > 程序开发 > 浏览文章

M4 说要有 lambda,就有了 lambda - # cd /

作者:小梦 来源: 网络 时间: 2024-07-29 阅读:

前言

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 内建的 pushdefpopdef 宏。

最后,我们将这些脏乱差的代码统统扔到 -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_BODYint 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 标准支持函数嵌套定义,可以利用与本文相似的思路实现闭包。

参考文档

[1] Vala 与 C 相映成趣

[2] C语言的奇技淫巧

[3] 初涉 GNU M4

[4] M4 的条件与宏

[5] Notes on the M4 Macro Language

[6] GNU M4 手册

热点阅读

网友最爱