宏定义黑魔法-从入门到奇技淫巧 (5)

发表于 | 分类于 | | 阅读次数

这里是本系列的第五篇。如果你已经耐心看到了这里，那么恭喜你这一篇是我觉得最有趣的一部分。整个系列的前四篇都可以说是在给这篇的内容做铺垫。终于要开始正片了，将宏的语言能力拓展到接近图灵完备。当然我承认这个说法有点噱头的意思，因为最终实现的方法递归栈是有限的。但是这世界上递归栈有限的语言基本上递归栈都是有限的嘛，所以说是图灵完备也没有问题（逃）。

完整的 IF 语句

在上一篇中我们学习了一个可以作为 if 语句时用的宏 IF，但是使用逗号作为 if else 的分隔符多多少少有些不优雅，这一节我们在介绍一个书写起来更加漂亮的 if-else 语句实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#define IF_ELSE(condition) CAT(_IF_,  BOOL(condition))
#define _IF_1(...) __VA_ARGS__ _IF_1_ELSE
#define _IF_0(...)             _IF_0_ELSE
#define _IF_1_ELSE(...)
#define _IF_0_ELSE(...) __VA_ARGS__
IF_ELSE (0) (      \
    True branch    \
)(                 \
    False branch   \
)
-> CAT(_IF_, 0) (True branch) (False branch)
-> _IF_0 (True branch) (False branch)
-> _IF_0_ELSE (False branch)
-> False branch
IF_ELSE (1) (      \
    True branch    \
)(                 \
    False branch   \
)
-> CAT(_IF_, 1) (True branch) (False branch)
-> _IF_1 (True branch) (False branch)
-> True branch _IF_1_ELSE_ (False branch)
-> True branch

里边用到的 CAT 和 BOOL 宏在上一篇中已经定义过了。忘记了的可以返回去查阅，这里就略去了。新的 IF_ELSE 宏可以使用括号作为两个分支的分隔符，写起来也更加接近 C 语言本身的写法。原理上来说，其实就是利用了宏会向后查找一个括号的特性。使得，不同的分支会“吞掉”另外一个分支的内容。对于「真分支」来说_IF_1_ELSE_ 会吞掉「假分支」的展开过程。对于「假分支」来说直接跳过参数处理就可以了。

循环的实现

有了分支判断的能力，我们离图灵完备之间就只差循环了。原始的宏是不能够进行循环的，因为蓝色集合的存在，所以宏无法递归的展开。但是，我们有一些猥琐的方法可以绕开蓝色集合的限制，最终达到我们的目的。这里提供两种不同的循环实现方式，各有利弊，大家酌情选择。

非递归方案

首先介绍一个比较好理解，但是写起来不是那么自然地一个方案。经过这几篇教程的例子，大家对蓝色集合都很熟悉了。但是有一个比较复杂的极端情况还是要拿出来说说。这种情况是我们方案的基础。首先复习一下前几篇的知识点。

宏展开后，会后看一个 token 看是否能够组成func-like的宏以便继续展开，例如：

1
2
3
4
5
6
#define BAR() 1
#define FOO(x) BAR
FOO(1)()
-> BAR ()
-> 1

此处的 BAR 向后搜索发现了 ()，构成了一个 func-like 的宏，所以展开了。

前几节没有明确提醒大家注意的是，最后的这一次额外的展开，与蓝色集合也是有关的。

1
2
3
4
5
6
#define BAR_I() BAR
#define BAR() 1 BAR_I()
BAR() () // 蓝色集合 {}
-> 1 BAR_I() () // 蓝色集合 {BAR}
-> 1 BAR () // 蓝色集合 {BAR BAR_I}

此时由于蓝色集合中含有 BAR 所以即使满足 func-like 展开的条件 BAR 也不会被展开。

然而，预处理器只会保持当前的「蓝色集合」。在额外的展开后蓝色集合会被更新，所以我们可以这么做：

1
2
3
4
5
6
7
#define BAR_I() BAR
#define BAR() 1 BAR_I
BAR () () () // 蓝色集合 {}
-> BAR_I () () // 蓝色集合 {BAR}
-> BAR () // 蓝色集合 {BAR_I} 注意！在执行上一步的展开时，蓝色集合更新了
-> BAR_I // 蓝色集合 {BAR} 此处也更新了蓝色集合

画成图是这样的：

seq_expand.png

也就是说通过引入 BAR_I 使得这几次展开得以在继承关系上互相平行的蓝色集合中展开。规避了禁止递归展开的问题。聪明的读者已经发现这个过程是可以无限重复下去的。这相当于给了我们近似于循环的能力，比如我想要生成一系列的函数名

1
2
3
4
5
6
7
8
9
#define FUNCTION(name) void name();
#define FUNCTION_TABLE(seq) CAT(FUNCTION_TABLE_1 seq, _END)
#define FUNCTION_TABLE_1(x) FUNCTION(x) FUNCTION_TABLE_2
#define FUNCTION_TABLE_2(x) FUNCTION(x) FUNCTION_TABLE_1
#define FUNCTION_TABLE_1_END
#define FUNCTION_TABLE_2_END
FUNCTION_TABLE((x) (y) (z) (e))
-> void x(); void y(); void z(); void e();

但是问题在于，使用这种方法并不能给出一个通用的类似 FOR_EACH 的函数，而且对于迭代的数据要就写成括号表达式的形式。这个不符合我们平时的习惯。因此，我们给出第二种实现循环的方式。

递归方案

第二种方法是基于递归调用来实现的，这种方法书写起来更加自然，但是展开效率并没有上边的高。这次要绕开蓝色集合的限制，先让我们学习一个新的技巧——延迟展开：

1
2
3
4
5
6
7
8
9
#define EMPTY()
#define DEFER(id) id EMPTY()
#define FOO() macro
FOO()
-> macro
DEFER(FOO)()
-> FOO()

神奇的事情出现了！FOO居然没有被展开！这就是我们走向递归调用的突破口。首先我们先来看看为什么此处 FOO 没有被展开:

1
2
3
DEFER(FOO)()
-> FOO EMPTY() ()
-> FOO()

此处，EMPTY() 展开后虽然会先后看一个 token，但是由于此处展开结果为空，所以并不会触发新的展开。而前边的 FOO 由于已经处理过了，所以并不会拿来和后边的() 配对。如果要展开则需要再多一次扫描的过程，比如这样：

1
2
3
4
5
6
7
#define EXPAND(...) __VA_ARGS__
EXPAND(DEFER(FOO)())
-> EXPAND(FOO EMPTY() ())
-> EXPAND(FOO ())
-> FOO ()
-> macro

在前边的内容中我们讲过，宏展开会有两次扫描。一次是参数展开，另一次是替换完毕后的重扫描，重扫描时会重新搜索可以展开的宏名。所以此处参数完全展开后成为FOO()，在重扫描的阶段被展开了!

那么延迟展开有什么用呢？延迟展开意味着你可以构造一个能够展开的式子，但是不将他加入蓝色集合，而是选则在下一次扫描中展开。我们知道宏的展开首先会对参数进行完全展开。然而，参数的完全展开是不会对宏自身的替换列表的蓝色集合产生影响的。那么我们就可以交替的使用这两次不同展开的蓝色集合树来规避蓝色集合的限制，例如：

1
2
3
4
5
6
#define BAR_I() BAR
#define BAR()  DEFER(BAR_I)()() 1
BAR()                 -> BAR_I()() 1
EXPAND(BAR())         -> BAR_I()() 1 1
EXPAND(EXPAND(BAR())) -> BAR_I()() 1 1 1

可以看到，神奇的事情出现了，BAR_I 这个宏只要存在额外的扫描，就能够不断展开。并且每次展开后都能保持同样的结构(BAR_I()())。那么如果我们不加 DEFER 会怎么样呢？

1
2
3
4
5
6
#define BAR_I() BAR
#define BAR()  BAR_I()() 1
BAR()                 -> BAR_I() 1
EXPAND(BAR())         -> BAR_I() 1
EXPAND(EXPAND(BAR())) -> BAR_I() 1

EXPAND 并没有对 BAR_I 进行新的展开。即使多次扫描也不行，由于蓝色集合的存在，展开被阻止了。我们来看看为什么。接下来的部分比较难以理解，所以需要借助示意图来说明， 首先我们分析一下为什么没有DEFER就不能展开了：

recur_fail.png

展开过程如上图所示。首先先完全展开参数部分BAR()。参数完全展开后，我们得到BAR() 1，注意此处参数的蓝色集合（图中用红色表示）为 {BAR BAR_I}。之后执行替换和重扫描，由于BAR在参数的蓝色集合中，所以重扫描并不会再次展开 BAR，整个展开到此结束。因为后续对于BAR()的展开都属于参数 BAR()的嵌套展开。

如果是有 DEFER 的情况，则展开过程如下图所示：

recur_success.png

参数完全展开后得到 BAR_I ()() 1，此时蓝色集合中并没有BAR_I因此可以继续展开得到BAR()1。此时，我们构造了一个和第一种方案类似的情况，也是两个宏交替展开，区别在于，上一个方案每次回消耗掉一个()，由于 DEFER 的存在每次都能够早出一个新的不被消耗的()，所以并不需要括号表达式来辅助。此时我们可以用同样的结构构造一个通用的FOR_EACH宏：

1
2
3
4
5
6
7
8
#define FOR_EACH(macro, x, ...) macro(x) DEFER(FOR_EACH_I)() (macro, __VA_ARGS__)
#define FOR_EACH_I() FOR_EACH
#define FOO(x) void x();
FOR_EACH(FOO, x, y, z)                  -> void x(); FOR_EACH_I () (FOO, y, z)
EXPAND(FOR_EACH(FOO, x, y, z))          -> void x(); void y(); FOR_EACH_I () (FOO, z)
EXPAND(EXPAND(FOR_EACH(FOO, x, y, z)))  -> void x(); void y(); void z(); FOR_EACH_I () (FOO, )

基本的雏形已经出现，但是当参数列表为空时，展开结果会有一个丑陋的小尾巴。还记不记的上一节提到过的模式匹配和检测？此处就派上了用场。

1
2
3
4
5
6
7
8
#define FOR_EACH(macro, x, ...) CAT(FOR_EACH_, IS_EMPTY(__VA_ARGS__)) (macro, x, __VA_ARGS__)
#define FOR_EACH_0(macro, x, ...) macro(x) DEFER(FOR_EACH_I)() (macro, __VA_ARGS__)
#define FOR_EACH_1(...) macro(x)
#define FOR_EACH_I() FOR_EACH
#define FOO(x) void x();
EXPAND(EXPAND(EXPAND(FOR_EACH(FOO, x, y, z))))  -> void x(); void y(); void z();

大致思路就是通过判断参数是否为空决定是否继续展开。注意这里不能使用我们上一节的 IF_ELSE 宏，因为其中有多次展开（多次扫面），所以 DEFER 宏会失效。如果想要使用的话，应该嵌套多层 DEFER 有兴趣的读者可以尝试一下。

现在还有最后一个问题，就是每多扫描一次，我们就需要多写一个 EXPAND 宏，这显然是不实用的。怎么解决呢？嘛，答案是真的没办法解决这个问题，因为扫描数是有限的，这也保证了无论如何宏展开一定会终止。但是我们可以使用一个折中的方案，用 n^3 的增长速率来定义多个扫描，例如：

1
2
3
4
5
6
7
8
#define EVAL(...)  EVAL1(EVAL1(EVAL1(__VA_ARGS__)))
#define EVAL1(...) EVAL2(EVAL2(EVAL2(__VA_ARGS__)))
#define EVAL2(...) EVAL3(EVAL3(EVAL3(__VA_ARGS__)))
#define EVAL3(...) EVAL4(EVAL4(EVAL4(__VA_ARGS__)))
#define EVAL4(...) EVAL5(EVAL5(EVAL5(__VA_ARGS__)))
#define EVAL5(...) __VA_ARGS__
EVAL(FOR_EACH(FOO, x, y, z)) -> void x(); void y(); void z();

我们定义了 5 个宏，大概能有 243 次扫描。有人说这也太丑了吧，说好的图灵完备呢？嘛，其实这里相当于我们的「宏程序」拥有一个深度为 243 的递归栈。要知道默认情况下 Python 也就 900 多的递归栈，写十个EVAL也够用了。而且像 Boost 这种经典库的预处理实现也是一模一样的原理。现实生活中并不存在内存无限大的机器，所以笔者认为，这里把他叫做图灵完备，至少是弱图灵完备，是没有问题的。搭配上一节的内容，你就可以像写普通程序一样写宏了。不过限于篇幅就不在这里赘述了。

本节到此结束，下节预告，宏的那些坑。