六离合释:健康宏展开的故事

Belleve Invis · 2015-03-29

本文同步发布至 知乎专栏

今受 @RednaxelaFX 的邀请,到此地方来,本打算像写书那样,写个长的系列,唤作《六离合释》,借个 Panini 文法里的词来说语言理论,不过写书我实在是坚持不下来,所以还是东一榔头西一棒子地讲一些小的细节好了。

给程序语言设计宏系统实际上是挺麻烦的事。C/C++ 的宏实际上就是 token 层面的查找替换,早期的 lisp 要更好些,是在 AST 层面的查找替换,由于 lisp 的节点可以随意组合、文法统一,所以在人们眼里 lisp 宏一直是强大的象征。

但是,最好的宏系统实际上是在 Scheme 里。无论是 C/C++,还是 Common Lisp,它的宏都是使用动态作用域的,也就是说,考虑你想实现个类似 javascript 里的 “||” 算符:

(defmarco or (x y)
    (let ((t (gensym))
        `(let ((,t ,x))
             (if (falsy ,t) ,y ,t))))

这里我们使用临时变量 t 避免 x 被重复计算,同时满足 javascript “||” 里的短路特性。falsy 是一个用来判断 x 是否为「假」值的自定义函数。这个宏看上去十分完美。

但他仍然有问题:因为用户很可能会覆写掉 falsy 的定义:

(let ((falsy (lambda (x) #t)) (or 0 1)) ;0

你应该看出来问题所在了:传统的宏展开中,被宏引入的新语法节点中的所有名称使用的是宏调用处的作用域,这往往和用户的意图不一致:他们希望使用宏定义处的作用域,就像嵌套函数里的变量名一样。这就是著名的「宏健康性」问题。

1986 年,Kohlbecker 等发明了 KFFD 算法第一次实现了健康的宏展开,基于此方法的宏系统成为了 R5RS 的标准。1988 年,Bawden 等提出的文法闭包(Syntactic closure)允许进行细粒度的作用域指派控制,借以实现一些「不健康的」特殊宏。1992 年,Dybvig(嗯,就是王某人说的那位)的 syntax-case 系统完善了 KFFD 体系,并成为了新的标准。

实现健康宏展开的思路并不算复杂:我们只需要在展开宏的步骤里同时维护每个名字的作用域绑定就可以了。假设用于宏展开的函数是 mfrakM𝔐,它的参数是语法树 cc 和作用域 ee

对于变量,我们把它绑定到 e 上。

mfrakM (Variable rm ~ c, e)=Binding rm (c, e)𝔐(Variablec,e)=Binding(c,e)

对于宏定义,我们解析宏定义得到一个宏「函数」,它是将若干个语法树变换成一个语法树的过程。所有的宏函数都会记录其定义时所在的作用域。

mfrakM (MacroDefinition rm ~ c, e)=MacroFunction rm (c, e)𝔐(MacroDefinitionc,e)=MacroFunction(c,e)

对于宏调用,有趣的地方就来了:我们事先将参数进行包装成文法闭包mfrakK(a, e)𝔎(a,e),然后直接丢给宏函数。宏函数返回的结果则在一个新创建的,宏函数定义作用域的子作用域中展开。

mfrakM (MacroCall rm(name, args), e)=𝔐(MacroCall(name,args),e)=
qquad let bf(mfn = ResolveMacro rm(name, e)).  let(mfn=ResolveMacro(name,e)).
qquad let bf(wrapped = map bf(args, lambda a. mfrakK (a, e))).  let(wrapped=map(args,λa.𝔎(a,e))).
qquad qquad mfrakM(ApplyMacro rm(mfn, wrapped), partial upvalue rm(mfn))    𝔐(ApplyMacro(mfn,wrapped),upvalue(mfn))

而对于文法闭包的处理,哼哼,我们不是记录了它的作用域 e'e{} 吗?直接展开便是:

mfrakM (mfrakK(c, e'), e) = mfrakM(c, e')𝔐(𝔎(c,e{}),e)=𝔐(c,e{})

而为什么我们可以这么做呢?因为宏函数实际上不会去「触碰」文法闭包,如上面的 orxy 都是整体进,整体出的,它们会直接无损地从宏函数里出来;而宏函数中新加入的变量——比如 t——则没有闭包加持,会落到我们布置好的「陷阱」作用域——partial upvalue rm(mfn)upvalue(mfn) 里,实现了健康的宏展开。

而且,由于宏函数的多样性,如果用户需要,他完全可以拆掉文法闭包来实现特殊的宏:如一些 DSL 需要修改宏参数所在的作用域,单纯的健康宏展开就做不到了。