Alvis
卫生宏

卫生宏

发表于更新于阅读时长 7 分钟

论文复读

0. 什么是卫生宏

作为应用最广泛的元编程手段，宏早在汇编语言刚刚诞生的五十年代就被引入了。最为程序员熟知的 C 宏是其最原始的一种形态，它只能操作 lexical token；早期 Lisp 则引入了基于语法树的宏。然而这两者都无法避免一个问题，就是它们有可能会预料之外地捕获环境，举例说来

c
#define INCI(i) do { int a=0; ++i; } while (0)
int main(void)
{
    int a = 4, b = 8;
    INCI(a);
    INCI(b);
    printf("a is now %d, b is now %d\n", a, b);
    return 0;
}

在上面的例子里，尽管 b 被正确的增加了，但是变量 a 却被宏内部产生的变量所遮蔽了，因此其值保持不变。这就对宏的编写者提出了很高的要求 —— 他们需要仔细挑选宏内部的变量名，以免一不小心和输入的变量名发生冲突。C/CPP 语言的使用者就是采取了这样的方法。对它的一个小改进是不用手动选新名字，而是通过调用编译器提供的函数以得到一个不会和其他变量冲突的名字，common lisp 中的gensym函数就提供了这种功能。

而为了正式地解决这样的问题，很多现代编程语言如 scheme 和 rust 都引入了卫生宏（hygiene macro）机制，下面介绍几篇相关的论文。

1. KFFD(1986)

Hygienic Macro Expansion 是卫生宏领域开天辟地的一篇论文，因为是由 Kohlbecker Friedman Felleisen Duba 四位作者写成，所以论文里介绍的算法被称为 KFFD 算法。其核心思路很简单，就是标记每个变量的引入时机，只要引入时机不一样，就视作不同变量。

KFFD 算法共分为四步，不妨拿如下 rust 程序举例，记录引入时机的全局变量称为 S，S 初始化为 0

rust
macro_rules! x {
    ($x: ident) => {
        let mut a = 10;
        while a >= 0 {
          $x = $x * 2;
          a -= 1;
        }
    }
}
pub fn foo() -> usize {
    let mut a = 1;
    x!(a);
    a
}
  1. 将所有的标识符（identifier）标上 S 并递增 S
rust
// S = 0
macro_rules! x0 {
    ($x0: ident) => {
        let mut a0 = 10;
        while a0 >= 0 {
          $x0 = $x0 * 2;
          a0 -= 1;
        }
    }
}
pub fn foo0() -> usize {
    let mut a0 = 1;
    x0!(a0);
    a0
}
// S = 1
  1. 展开所有宏，每次展开时，先将宏内的所有变量都标上 S，递增 S，再展开
rust
// S = 1
pub fn foo0() -> usize {
    let mut a0 = 1;
    {
        let mut a1 = 10;
        while a1 >= 0 {
          a0 = a0 * 2;
          a1 -= 1;
        }
    }
    a0
}
// S = 2
  1. 检查重名情况，如果有两个变量，其名字相同而标记不同，将其中一个重命名
rust
pub fn foo0() -> usize {
    let mut a0 = 1;
    {
        // rename a1 -> b1
        let mut b1 = 10;
        while b1 >= 0 {
          a0 = a0 * 2;
          b1 -= 1;
        }
    }
    a0
}
  1. 移除所有标记
rust
pub fn foo() -> usize {
    let mut a = 1;
    {
        let mut b = 10;
        while b >= 0 {
          a = a * 2;
          b -= 1;
        }
    }
    a
}

2. Syntactic Closures(1988)

两年后，MIT AI LAB 的 Alan Bawden 和 Jonathan Rees 提出了另一种方法：Syntactic Closures，可以译作语法闭包。正如函数闭包在运行时捕获了环境一样，语法闭包在宏展开的时候捕获了环境。函数闭包里的大部分变量都是从它定义的环境中来的，除了函数参数；语法闭包也是如此，只不过需要显式地传入环境。

具体实现方式则是，编译器提供一个函数make-syntactic-closure，把表达式和一个语法环境绑定起来。在宏展开之后，编译器解析变量时不会像普通的变量一样从它所处的环境中去解析，而是会从之前绑定的环境中解析。make-syntactic-closure还接受一个额外的白名单参数，在这个列表里的变量会像普通变量一样解析，这样可以来提供灵活的机制来实现一些复杂的 DSL。换言之，程序员需要手动指定宏生成的代码中的变量要从哪个环境中读取。

使用这篇论文中提供的机制来改写之前的宏

rust
macro_rules! x {
    (env, $x: ident) => {
        let b = make_syntactic_closure(env, [], x);
        make_syntactic_closure(global_env, {
            let mut a = 10;
            while a >= 0 {
              b = b * 2;
              a -= 1;
            }
        })
    }
}

MIT Scheme（也就是大名鼎鼎的 SICP 中使用的 Scheme 方言）中就提供这样的机制。

3. Syntax Case(1992)

此后在 1992 年，Chez Scheme 的作者 R. Kent Dybvig 发表了 Syntactic Abstraction in Scheme。这篇论文主要是对前述 KFFD算法的扩展，相对于 KFFD 算法要遍历四次 AST 而言，这篇论文提出的synatx-case机制只需要常数的额外时间开销。synatx-case所提供的对 AST 进行模式匹配能力也是 rust 声明宏的灵感来源之一，事实上前面两种算法中并没有这样方便的机制，而是只能把宏的参数当作普通的 list 来处理。它的具体实现方式将会在下一节中一并介绍。

在现代的主流 Scheme 实现如 Guile 和 Racket 中都使用这个机制来实现卫生宏。

4. MTWT(2011)

此后经过二十多年的发展，卫生宏已经被纳入了 scheme 的核心之中，而作为其衍生的 Racket 自然也包含了这个特性。Matthew Flatt 写的 Macros that Work Together 就是对 Racket 中卫生宏机制的总结和建模。在前文的基础上，它额外增加了一些扩展。

和 KFFD 一样，它也是通过对变量进行标记来避免标识符冲突的。在这里，一个变量所附带的标记被称为语法环境(syntax context)。相比前文中的单个数字，我们用Mark这个结构来标记语法环境，一个语法环境可以有多个Mark，我们可以把语法环境看作Mark的集合。此处引入了一个小技巧，如果同一个语法环境被同一个Mark标记了两次，那效果就会互相抵消。

如之前一样，先把所有标识符都扩展上空的语法环境，这一步可以在构建 AST 的时候完成

rust
macro_rules! (x, ∅) {
    ((x, ∅): ident) => {
        let mut (a, ∅) = 10;
        while (a, ∅) >= 0 {
          (x, ∅) = (x, ∅) * 2;
          (a, ∅) -= 1;
        }
    }
}
pub fn (foo, ∅)() -> usize {
    let mut (a, ∅) = 1;
    (x, ∅)!((a, ∅));
    (a, ∅)
}

展开宏时，先用Mark标记宏调用

rust
macro_rules! (x, ∅) {
    ((x, ∅): ident) => {
        let mut (a, ∅) = 10;
        while (a, ∅) >= 0 {
          (x, ∅) = (x, ∅) * 2;
          (a, ∅) -= 1;
        }
    }
}
pub fn (foo, ∅)() -> usize {
    let mut (a, ∅) = 1;
    (x, {mark})!((a, {mark}));
    (a, ∅)
}

解析宏并展开

rust
pub fn (foo, ∅)() -> usize {
    let mut (a, ∅) = 1;
    // macro expansion
    let mut (a, ∅) = 10;
    while (a, ∅) >= 0 {
        (a, {mark}) = (a, {mark}) * 2;
        (a, ∅) -= 1;
    }
    // macro expansion end
    (a, ∅)
}

将展开结果用同样的Mark再标记一遍

rust
pub fn (foo, ∅)() -> usize {
    let mut (a, ∅) = 1;
    let mut (a, {mark}) = 10;
    while (a, {mark}) >= 0 {
        (a, ∅) = (a, ∅) * 2;
        (a, {mark}) -= 1;
    }
    (a, ∅)
}

这样，在重命名时，如果遇到两个标识符一样但语法环境不一样的变量，将其中之一重命名，就能完成卫生宏展开。以上这几步包括重命名都可以在宏展开时一并完成，因此只有 O(1) 的额外开销。这个算法的另一个好处是如果给每个宏都分配一个独特的Mark，那么就可以轻易知道一段代码是由哪个宏生成的，有助于程序员 debug。

rustc 的宏展开算法就是基于这篇论文里提到的算法进行了一些修改之后完成的。

原论文还在此基础上实现了定义上下文（definition context），也就是说，在外界传入一个变量的时候，我们可以合成出和这个变量定义在同一个环境中的新变量。实现并不复杂，只要把传入的变量的语法环境赋给新生成的变量就行了。

5. Scope Set(2016)

还是 racket 话事人 Matthew Flatt 写的 Binding as Sets of Scopes。他指出，尽管上一节中提及的机制已经足够好用，但是和程序员的直觉相差甚远。我们可以给每次宏展开产生一个独特的作用域，和源程序中的词法作用域一样处理。每个变量都有自己的作用域集合(scope set)。也就是说，对于上文中的代码，我们有

rust
macro_rules! (x, {macro}) {
    ((x, {macro, pat}): ident) => {
        let mut (a, {macro, let1}) = 10;
        while (a, {macro, let1}) >= 0 {
          (x, {macro, pat}) = (x, {macro, pat}) * 2;
          (a, {macro, let1}) -= 1;
        }
    }
}
pub fn (foo, {fn})() -> usize {
    let mut (a, {fn, let2}) = 1;
    (x, {fn, let2, macro})!((a, {fn, let2, use}));
    (a, {fn, let2})
}

此外，对于传入宏的所有变量，也要额外加上一个 scope，否则会在创建新变量时产生歧义。

每次展开宏时，都创建一个新的 scope，并且为展开时创建的所有标识符都加上这个 scope。

rust
pub fn (foo, {fn})() -> usize {
    let mut (a, {fn, let2}) = 1;
    let mut (a, {macro, let1, expand}) = 10;
    while (a, {macro, let1, expand}) >= 0 {
        (a, {fn, let2, use, expand}) = (a, {fn, let2, use, expand}) * 2;
        (a, {macro, let1, expand}) -= 1;
    }
    (a, {fn, let})
}

寻找标识符的定义时，只需要寻找当前可用的定义中，哪个定义的 scope 是当前标识符的 scope 的子集。如果存在多个同名的定义且 scope 都是子集，那就找最大的子集。对于第 5 行的 a，它由第 2 行的 a 定义，因为{fn, let2}是{fn, let2, expand}的最大子集；第 4 行的 a 则由第 3 行的 a 定义，因为{macro, let1, expand}是它自己的子集。进一步地，我们可以维护一张全局的由名字和 scope 指向绑定的表来完成重写，也就是说

rust
macro_rules! x1 { // x, {macro} -> x1
    (x2: ident) => { // x, {macro, pat} -> x2
        let mut a1 = 10; // a, {macro, let1} -> a1
        while a1 >= 0 {
          x2 = x2 * 2;
          a1 -= 1;
        }
    }
}
pub fn foo1() -> usize { // foo, {fn} -> foo1
    let mut a2 = 1; // a, {fn, let2} -> a2
    x1!(a2);
    a2
}

展开时

rust
pub fn foo1() -> usize {
    let mut a2 = 1;
    let mut a3 = 10; // a, {macro, let1, use, expand} -> a3
    while a3 >= 0 {
        a2 = a2 * 2;
        a3 -= 1;
    }
    a2
}

在展开时如果传入的标识符产生在定义位，那需要去掉那个因为使用宏而额外引入的 scope

rust
macro_rules! (foo, {macro}) {
    ((x, {macro, pat}): ident) => {
        let (x, {macro, pat, let}) = 10;
    }
}
pub fn (foo, {fn})() -> usize {
    (x, {fn, macro})!((a, {fn, use}));
    (a, {fn})
}

展开成

rust
pub fn (foo, {fn})() -> usize {
    let (a, {fn}) = 10;
    (a, {fn})
}
© 2016 - 2024Austaras Devas