使用 explicit renaming 实现卫生宏

接上篇，前面对 scheme 卫生宏的实现方式有个整体的介绍，这一次具体讲其中 explicit renaming 这种方式的实现原理。

首先讲 alpha 变换。alpha 变换这东西，说的就是函数的参数名字其实是无所谓的。

(lambda (a b) (+ a b))

跟下面这个完全是等价的。

(lambda (a1 b2) (+ a1 b2))

alpha 变换就是自由的把函数名字随便换。alpha 变换这么实现：

(define (alpha-convert exp env)
    (match
        (x (symbol? exp)) (replace-symbol x env))
        (lambda (x) body)
          (let ((new-env (cons (x . x1) env)))
            `(lambda (x)
                ,(alpha-convert body new-env))))
                

用一个环境，环境里面是 (原符号 . rename后的符号)。

为什么要讲 alpha 变换呢？ 因为 explicit renaming 其核心就是在做 alpha 变换！

考虑一个宏：

(swap! x y)
(let ((tmp x))
      (set! x y)
      (set! y tmp))

如果我们把展开宏显式的重命名一下，注意前面说过的卫生的原则 – 卫生的本质问题，还是作用域。把需要使用 宏定义时作用域 的变量用 [] 框起来：

([let] (([tmp] x))
      ([set!] x y)
      ([set!] y [tmp]))

[let] [set!] [tmp] 指代的是宏定义时的符号，而 x y 则是宏展开时期的符号。每一次宏展开生成都赋予一个唯一 id，因此我们可以把上面写成：

([let 1] (([tmp 1] x))
      ([set! 1] x y)
      ([set! 1] y [tmp 1]))
      

如果有多次的宏展开，比如 (swap! (or x 1) y) 第一次展开 swap! 时：

([let 1] (([tmp 1] (or x 1))
      ([set! 1] (or x 1) y)
      ([set! 1] y [tmp 1]))
      

第二次再展开 or 之后：

([let 1] (([tmp 1] ([if 2] x x 1))
      ([set! 1] ([if 2] x x 1) y)
      ([set! 1] y [tmp 1]))
      

注意其中的 [let 1] 跟 [if 2] 分别是对 swap! 和 or 的两次展开过程，每次展开都对应了一个唯一 id。如果我们有一个 [let 1] 和 [let 3]，它俩有可能是同一个东西，只是在不同的宏展开过程中赋予的 id 不同。

如果看 er-macro-transform 的说明，它说每次展开都是在不同的词法环境中，所以不同的宏展开后的符号不会跟其它任何地方冲突。怎么理解的呢？嗯，其实就是做了 alpha 变换。对于前面的前面的例子，如果我们再夹杂一个 alpha 变换，可以写成这样子：

([let 1] (([tmp 1] x@523423132)
      ([set! 1] x@523423132 y@44512342)
      ([set! 1] y@44512342 [tmp 1]))

alpha 变换使用的 宏展开时环境： ((x . x@523423132) (y . y@44512342))

这是最重点的地方，准确来说，遇到宏展开会做两步操作：

• 第一步是在宏展开时，把 let set! 变成 [let 1] [set! 1]
• 第二步是将展开的结果做 alpha 替换，对普通的符号，使用宏展开时环境替换；对于 [let 1] 这种，使用宏定义时环境替换

或者放点代码会更清楚一点：

(define (expand exp menv env)
  (cond
  ((symbol? exp) (alpha-convert exp env))
  ((generated? exp)
    (let ((env-of-def (assq (generated-uid exp) menv)))
      (alpha-convert (generated-sym exp) env)))
  ((pair? exp)
    (let ((den (binding (car exp) menv env)))
      (cond
      ((special? den) (expand-special-form den exp menv env))
      ((macro? den) (expand-macro den exp menv env))
      (else (expand-application exp menv env)))))
  (else exp)))  ;; for const like string, number and so on

其中的 env 是一个符号，到一个绑定。绑定内容可能是 alpha 变换后的符号，或者特殊表 if begin set! lambda，也可能是宏。

宏的表示是 转换函数，以及宏定义时环境。generated 就是 (name . uid)

menv 是 uid 到 env 的映射，因为展开 generated 需要两步，通过 generated-uid 从 menv 获取到 generated 定义时的环境，下一步在是在该环境里面对 generated-sym 做 alpha 变换。

(define (expand-macro mac exp menv env)
  (let* ((transform (macro-func mac)) ;;提取宏转换函数
        (env-of-def (macro-env mac)) ;;提取宏定义时环境
        (uid (unique-id))            ;;每次展开生成唯一 id
        (new-menv (cons (uid . env-of-def) menv)) ;;唯一 id 到 env 绑定
        (rename (lambda (x) (make-generated x uid))) ;; rename 会传递给宏用于绑定 宏定义时环境
        (new-exp (transform exp rename))) ;; 调用宏转换函数，会生成 [let uid]
    (expand new-exp new-menv env))) ;; 对宏展开的结果，递归再展开

expand-special-form 是对 if begin set! lambda 等东西做展开，其中 lambda 的展开：

(define (expand-lambda exp menv env)
  (let* ((args (cadr exp))              ;; (a b c)
        (values (map rename args))     ;; (a@5 b@6 c@7)
        (binds (map cons args values)) ;; ((a . a@5) (b . b@6) (c . c@7))
        (new-env (append binds env)))  ;; 新的 env，用于 alpha 变换
    `(lambda ,values
      ,@(expand-sequence (cddr exp) menv new-env))))

expand-special-forma 里面另个比较特殊的是 expand-defmacro，它要将 mac 加到 env 里面去。 应该解释清楚了。

最后看一个问题是，为什么 alpha 变换是卫生的，而 gensym 不是？

(let ((tmp#jsdjflsdf 32))
    (some-macro))

在 some-macro 展开用 (let ((tmp (gensym)))) 引入的 tmp，可能正好是 tmp#jsdjflsdf，就会被前面的绑定误捕获了。而在 alpha 变换中，tmp#jsdjflsdf 在环境里面是 tmp#jsdjflsdf@123，宏展开时的 id 不可能是 @123，它只能是一个不一样的 id 了。