编程语言宏之卫生实现

前两篇博文引入和讲解了各种宏的用法，本文进一步讲解宏的各种分类及实现。

宏的分类

scheme 宏的概念之所以不易于理解，就在于各种概念混杂在一起了，如果我们从各种角度分开看，应该会更于理解。

如果我们从宏是否是卫生或者不卫生角度看，宏可以被分为两类：卫生宏，不卫生宏。

如果我们从宏是否是高级或者低级的角度看，宏可以被分为两类：高级宏，低级宏。

如果我们从宏是否是声明式或者过程式的角度看，宏可以被分为两类：声明宏，过程宏。这种分类与高级/低级分类雷同，不过用不同的名称更能说明含义。

如果我们从宏是否是词法标记(token)替换或者语法树替换的角度看，宏可以被分为两类：词法宏，语法宏。

下面是一些宏系统实现的分类：

宏实现	卫生/不卫生	高级/低级	声明/过程	词法/语法
c macro	不卫生宏	低级宏	过程宏	词法宏
defmacro	不卫生宏	低级宏	过程宏	语法宏
syntax-rules	卫生宏	高级宏	声明宏	语法宏
syntatic-closure	卫生宏	低级宏	过程宏	语法宏
explicit-renaming	卫生宏	低级宏	过程宏	语法宏
syntax-case	卫生宏	低级&高级宏	声明&过程宏	语法宏

其中 syntatic-closure、explicit-renaming 和 syntax-case 前面并未涉及，这几个宏系统是 scheme 为了引入卫生宏而发明的各种算法底层实现，下文将有进一步讲解。

宏系统的各种实现

自 scheme 引入卫生宏的概念后，历史上出现了各种实现方式，下面是一个简单的时间线：

1986: Kohlbecker - introduced the idea of hygiene, low-level, used an O(n2) coloring algorithm
1987: Kohlbecker - introduced declare-syntax, high-level, the precursor to syntax-rules
1988: Bawden & Rees - "Syntactic closures," low-level, faster than Kohlbecker's algorithm
1991: Clinger & Rees - Explicit renaming, low-level, based on syntactic-closures but also supports syntax-rules
1992: Dybvig - Syntax-case, primary motivation to remove the distinction between low-level and high-level

第一个，Kohlbecker 首次提出了宏的卫生的概念。因为这个算法低效，现今已经没有人用了。

第二个，作者还是 Kohlbecker，用模式匹配的方式来声明宏，这就是 syntax-rules 的前身。

第三个，syntax closure，引入语法闭包概念，下文重点介绍此概念。

第四个，explicit renaming，显式重命名，本质与 syntax closure 类似。

第五个，syntax-case，即支持低级/过程宏，也支持高级/声明宏，在 r6rs 中定义，但是由于其实现非常复杂，引起了很大争议，最终在 r7rs 中被去除，r7rs 只保留了 systax-rules 的声明宏定义，因低级宏的实现各方都未能达成一致，很难标准化，所以在最新的 r7rs 标准定义中只定义了 syntax-rules 声明宏。

syntax closure，语法闭包

卫生宏的本质问题是：符号到底对应宏定义时期的环境，还是宏展开时期的环境。

由此 syntax closure 算法引入了两个环境变量，usage-environment 和 macro-environment，分别对应宏展开时的环境和宏定义时的环境，为了获取某个环境中某个符号所绑定的对象，又引入了 make-syntactic-closure 过程。

这样我们可以用 syntax closure 宏系统来实现卫生的 swap 宏：

(define-syntax swap
  (lambda (form usage-environment macro-environment)
    (let ((a (make-syntactic-closure usage-environment '() (cadr form)))
          (b (make-syntactic-closure usage-environment '() (caddr form)))
          (let (make-syntactic-closure macro-environment '() 'let))
          (tmp (make-syntactic-closure macro-environment '() 'tmp))
          (set! (make-syntactic-closure macro-environment '() 'set!)))
      `(,let ((,tmp ,a))
        (,set! ,a ,b)
        (,set! ,b ,tmp)))))

其中的 form 就是我们使用 swap 宏的形式，比如 (swap x y) 宏调用形式，这样，展开时上面的 (car form) 返回的是 swap 符号， (cadr form) 返回的是 x 符号， （caddr form) 返回的是 y 符号。

make-syntactic-closure 的调用方法是：

(make-syntactic-closure env free-variables form)

返回的对象与 form 等同，只是转换 form 使用 env 环境内的符号绑定，而 free-variables 列表是 form 内被排除不被解释的符号列表，这为了在宏的使用中，可以使用一些特殊的符号作为某些标记，比如 loop 循环中的 break、continue 标记。

上面定义 swap 的方法显式的定义了 a, b 符号引用的是 usage-environment 环境的绑定，宏展开时的环境，而 let、tmp、set! 符号引用的是 macro-environment 环境的绑定，宏定义时的环境。

为了简化上面的写法，在定义宏时可以让符号默认使用宏定义时的环境或者默认使用宏展开时的环境，由此出现了两种 syntax 的变种：

sc-macro-transformer，默认使用宏定义时的环境
rsc-macro-transformer，默认使用宏展开时的环境

(define sc-macro-transformer
  (lambda (f)
    (lambda (form usage-environment macro-environment)
      (make-syntactic-closure macro-environment '() (f form usage-environment)))))

(define rsc-macro-transformer
  (lambda (f)
    (lambda (form usage-environment macro-environment)
      (f form macro-environment))))

sc-macro-transformer

其中 sc 是 syntax closure 的缩写， sc-macro-transformer 定义宏的符号默认使用宏定义时环境的绑定，所以只需要接受宏展开时的环境变量 usage-environment 参数了，

下面是用 sc-macro-transformer 定义 swap 宏的方法：

(define-syntax swap
  (sc-macro-transformer
    (lambda (form usage-environment)
      (let ((a (make-syntactic-closure usage-environment '() (cadr form)))
            (b (make-syntactic-closure usage-environment '() (caddr form))))
        `(let ((tmp ,a))
          (set! ,a ,b)
          (set! ,b tmp))))))

rsc-macro-transformer

其中 rsc 是 reverse syntax closure 的缩写， rsc-macro-transformer 定义宏的符号默认使用宏展开时环境的绑定，所以只需要接受宏定义时的环境变量 macro-environment 参数了，

下面是用 rsc-macro-transformer 定义 swap 宏的方法：

(define-syntax swap
  (rsc-macro-transformer
    (lambda (form macro-environment)
      (let ((a (cadr form))
            (b (caddr form))
            (let (make-syntactic-closure macro-environment '() 'let))
            (tmp (make-syntactic-closure macro-environment '() 'tmp))
            (set! (make-syntactic-closure macro-environment '() 'set!)))
        `(,let ((,tmp ,a))
          (,set! ,a ,b)
          (,set! ,b ,tmp))))))

rsc-macro-transformer 可以用类似于 lisp 中的 defmacro 的方法定义 swap 宏：

  (define-syntax swap!
    (rsc-macro-transformer
     (lambda (form env)
       (let ((a (cadr form))
             (b (caddr form))
             (tmp (gensym)))
         `(let ((,tmp ,a))
            (set! ,a ,b)
            (set! ,b ,value))))))

上面的宏与 lisp 中的用 defmacro 定义 swap 宏的方法等效。

er-macro-transformer

er-macro-transformer 是后来又发明的另外一种宏系统，不再显式传递 usage-environment 和 macro-environment 参数，而是传递 rename 参数用来重命名符号，和一个 compare 参数用来比较两个符号是否相同。

其中 er 是 explicit renaming 的缩写，显示重命名。

下面是用 syntax closure 实现 er-macro-transformer 的方法：

(define er-macro-transformer
  (lambda (f)
    (lambda (form usage-environment macro-environment)
      (let ((rename
              (let ((renames '()))
                (lambda (identifier)
                  (let ((cell (assq identifier renames)))
                    (if cell
                        (cdr cell)
                        (let ((name (make-syntactic-closure macro-environment '() identifier)))
                          (set! renames (cons (cons identifier name) renames))
                          name))))))
            (compare
              (lambda (x y) (identifier=? usage-environment x usage-environment y))))
        (f form rename compare))))))

下面是用 er-macro-transformer 定义 swap 的方法：

  (define-syntax swap!
    (er-macro-transformer
      (lambda (form rename compare)
        (let ((a (cadr form))
              (b (caddr form)))
          `(,(rename 'let) ((,(rename 'tmp) ,a))
             (,(rename 'set!) ,a ,b)
             (,(rename 'set!) ,b ,(rename 'tmp)))))))

syntax-case

syntax-case 是一种兼有低级/高级特性的宏系统，被 r6rs 引入，后因其复杂的实现又被 r7rs 去除了。

下面我们分别用低级特性和高级特性来分别写 swap 宏对应的实现方式。

syntax-case 高级方式

(define-syntax swap!
  (lambda (stx)
    (syntax-case stx ()
      ((swap! a b)
       (syntax
         (let ((tmp a))
           (set! a b)
           (set! b tmp)))))))

这种高级方式已经非常类似于 syntax-rules 了，这里的 stx 是一个 syntax 语法对象， syntax-case 首先通过 (swap! a b) 解析匹配它，这里有点声明式的含义，而后面的 syntax 语句与 syntax-rules 并不同，不是模板，而是一个正常执行的语句，这里有点过程式的含义。

如果匹配到，将相关的语法对象绑定到 a 和 b 符号，然后返回后面的 syntax 对象，否则报错，这里的 syntax 语句就是把各种语法对象重新再进行组装起来。

syntax-case 低级方式

syntax-case 可以对 sexp 的执行各种计算，只要保证最后再转换成 syntax 对象就可以了。

  (define-syntax swap
    (lambda (stx)
      (syntax-case stx ()
        ((swap! a b)
         (let ((a (syntax-object->datum (syntax a)))
               (b (syntax-object->datum (syntax b))))
           (datum->syntax-object
             (syntax swap!)
             `(let ((tmp ,a))
                (set! ,a ,b)
                (set! ,b tmp))))))))

总结

从使用角度看，syntax-rules 无疑是最简单的，基本没有心智负担，但是 syntax-rules 并不是太自由，不能像 defmacro 那样自由的对 sexp 进行计算。

从实现角度看，syntax closure 语法闭包是最易实现的，但是使用上没有 syntax-rules 简单。

syntax-rules是一种高级宏系统，大多 scheme 都是通过低级宏来实现它的。