The Implementation of Scheme Hygienic macro

July 26, 2008 – 10:43 pm

我在很早的时候曾经写过一篇叫做“Play with macro”的文章,介绍了 Common Lisp 式的 macro ,那是一个很基本但又很强大的工具,比较容易理解。相比之下,Scheme 的 macro 就不一样了,虽然我很早就知道 Scheme 的 macro 是一种叫做 Hygienic macro 的东西,但是直到最近才明白它是怎么一回事,因为我要实现这样一个系统。

Common Lisp 的 macro 其实就是一段 Common Lisp 代码——一段操控代码的代码。因为在 Lisp 里程序的结构本身就是以一种类似于语法树的形式存在的,很好处理,所以宏的存在和广泛应用也理所当然了,而在 C/C++ 甚至于 Ruby、Python 这种语法复杂的语言里做这样的事情就很麻烦。C 提供了一个基于文本替换的宏,能完成不少事情。相比之下,Scheme 的那种基于模式匹配的宏反而更像 C 语言的预处理宏一些。然而 hygienic 并不是表示模式匹配的意思,而是指“保证宏展开的时候不与现有的符号冲突”,只是碰巧 Scheme 采用了模式匹配的方式罢了。

今天我就来介绍一下 Scheme 的宏(只包括 R5RS 中要求的 syntax-rules ,而不包括 R6RS 中提到的 syntax-case 以及其他类似的东西)系统以及我是如何在 skime 中实现它的。其实写这篇文章的时候 skime 的 macro 系统还没有完全实现,只是到最后要做 hygienic 的东西的时候发现这个邪恶的东西需要和编译器结合太紧密了,而且前面的结构似乎有需要不小的改动的可能,所以我决定写一篇 blog 来理一下自己的思路。很多时候碰到困扰自己的问题,如果能详细地给别人描述一遍的话,在描述的过程中往往就能自己发现问题了。 :D

Pattern Matching Macro — Syntax Rules

先从一个例子开始吧:一个叫做 swap 的宏,用 Common Lisp 的宏来写的话,一个最简单的版本是这个样子:

(defmacro swap (a b)
  `(let ((tmp ,a))
     (setf ,a ,b)
     (setf ,b tmp)))

(其实 let 语句可以平行赋值,但是这里只是做一个演示)普通情况下工作都挺好,但是当 a 或 b 中有一个叫做 tmp 时就不行了。这就是变量冲突。为了避免这个问题,Common Lisp 里可以用 gemsym 来产生一个不会和其他任何 symbol 发生冲突的 symbol ,而不是使用 tmp 这个硬编码的 symbol :

(defmacro swap (a b)
  (let ((tmp (gensym)))
    `(let ((,tmp ,a))
       (setf ,a ,b)
       (setf ,b ,tmp))))

而 Scheme 的宏则规定必须自动处理这种有可能冲突发生的情况。在 Scheme 中,swap 宏可以这样写:

(define-syntax swap
    (syntax-rules ()
      ((swap a b)
       (let ((tmp a))
         (set! a b)
         (set! b tmp)))))

syntax-rules 是 R5RS 中规定的 Scheme 的宏,它由一个 literal 列表和一系列的 syntax rule 组成。

(syntax-rules <literals> (<syntax rule> ...))

对于上面的 swap 宏来说,literals 是一个空表 () ,而 syntax rule 也只有一个。每个 syntax rule 是一个由两项组成的列表:第一项是用于匹配的 pattern ,第二项是匹配之后进行转换的 template 。

这里表示匹配型如 (swap a b) 的表达式,并将其按照模板转换为对应的 let 的表达式,其中 ab 都是匹配用的 pattern variable,例如,当匹配到 (swap foo bar) 的时候,在对应的 template 中,ab 会被相应地替换为 foobar 而变成

(let ((tmp foo))
  (set! foo bar)
  (set! bar tmp))

这看起来和普通的 Common Lisp 来说好像是换汤不换药的,其实不是这样,在 Scheme 中上面的宏在匹配到 (swap tmp bar) 或者 (swap foo tmp) 的时候仍然能够正常工作,而不会发生冲突。不过,既然要讲宏的实现,我们不妨先把这个比较有趣的内容放到后面,从头讲起(当然,你也可以直接跳到后面的 hygienic macro 去)。

略去 vector 形式的不说,一个 syntax rule 的 pattern 可以有以下几种形式:

  • 诸如数字、字符串之类的 self-evaluating 的值。它们只能匹配和自己相等的值。
  • 一个 literal ,即在 literals 列表中出现过的 symbol ,如果它具有一个 lexical binding ,那么它只能匹配到和自己具有相同 lexical binding 的 symbol ,或者是两个 symbol 的 name 相同而且都没有 binding 的情况下也可以匹配。在 skime 中不同 name 的 symbol 是不可能有相同的 binding 的,所以 name 相同也就成了一个必要前提。
  • 一个普通的 symbol (出去 literal 和后面要提到的几个特殊 symbol ),可以匹配任意表达式,称作 pattern variable ,可以在 template 中通过它们引用到匹配到的表达式。出现重复的 symbol 是不允许的。
  • 特殊 symbol _ (下划线),同普通 symbol 差不多,不过它将匹配到的结果直接丢弃,不能在 template 中进行引用,也因此可以重复多次出现。
  • 特殊 symbol ... ,只能出现在列表的环境之中,表示前一个 pattern 可以重复零到任意次。以下用 表示。
  • 一个列表,可以有如下形式:
    • ( ...) ,这表示一个普通的列表形式,例如 (a b c) ,它将匹配到一个列表,并且要求列表的所有子元素都能进行匹配。
    • ( ... . ) ,这表示一个 improper list ,例如 (a . c) 这种形式,不过它除了能匹配 improper list 之外,也能匹配正常的 list ,例如匹配 (1 2 3) 的结果就是 a 匹配到 1 ,而 c 匹配到 (2 3) 。其实只要清楚 lisp 中 list 的结构是由一个个的 cons cell 串联起来的就一不难理解了。
    • ( ... ) ,这里出现的 就是前面提到的那个特殊的 symbol 了,例如:(a b ...) ,可以匹配 (1)(1 2)(1 2 3) 等等。其中 b 出现零次或多次。在 R6RS 中还允许 后面再出现 。如果两者是相同类型的 pattern 的话(例如 (a b ... c) ,都是普通的 pattern variable ),贪心匹配算法就无法做到正确地匹配,但是如果是不同类型的 pattern 的话就是很简单的了。

顺理成章地,进行 pattern matching 的方法有两种:一边解析 pattern 一边进行匹配;先对 pattern 进行解析,产生出匹配的步骤,然后再进行匹配。后者的好处是重用了解析 pattern 的过程。虽然 pattern 一般都不会太复杂,不过我还是选择了后者。

我将每一个 pattern 对应到一个 matcher ,每个 matcher 有一个 bool 的 ellipsis 属性表示是否后面紧跟了一个 。而 match 方法则是一个统一的进行匹配的接口:

class Matcher(object):
    "The base class for all matchers."
    def __init__(self, name):
        self.ellipsis = False
        self.name = name
 
    def match(self, env, expr, match_dict):
        """\
        Match against expr and return the remaining expression.
        If can not match, raise MatchError.
        """
        raise MatchError("%s: match not implemented" % self)

其中一个 SequenceMatcher 刚好对应到一个列表形式的 pattern ,我把三种列表形式统一在了一起,它们的行为完全因为子 matcher 的不同而不同。它的 match 方法主要是调用 match_sequence 来完成的,即依次调用各个子 matcher 进行 match :

def match_sequence(self, env, expr, match_dict):
    expr = expr.first
    for m in self.sequence:
        expr = m.match(env, expr, match_dict)
    if expr is not None:
        # not matched expressions
        raise MatchError("%s: ramaining expressions not matched: %s" % (self, expr))

其中包含 的时候则是将对应的子 matcher 的 ellipsis 属性设置为 True 让他自己处理重复。只是对于 improper list 的情况则比较难统一在一起:因为如果是把 list 的每个元素取出来依次和子 matcher 进行匹配的话,对于 improper list pattern 的情况是行不通的。如果输入是 improper list ,则根本不可能按照普通 list 的情况取出各个子元素;如果输入是 proper list ,末尾的那个 pattern 希望看到的是尾部的所有元素的列表。

因此我并不是将 list 的每个元素取出来再交给子 matcher ,而是直接将整个 list 作为参数传递过去,如下图所示:

matcher_flatten.png

普通的 matcher 只需要将列表的第一个元素取出来进行匹配即可,例如 UnderscopeMatcher 只是简单地将其丢弃,并返回剩下的表达式:

class UnderscopeMatcher(Matcher):
    """\
    An underscope match any single expression and discard the matched result.
    """
    def __init__(self):
        Matcher.__init__(self, '_')
    def match(self, env, expr, match_dict):
        if self.ellipsis:
            while isinstance(expr, pair):
                expr = expr.rest
        else:
            if not isinstance(expr, pair):
                raise MatchError("%s: unable to match %s" % (self, expr))
            expr = expr.rest
 
        return expr

而用于处理 improper list 的 RestMatcher 将对一个 matcher 进行包装,不过它并不是原封不动地将参数转发给包装的 matcher ,而是将其放在一个 proper list 中,这样被包装的 matcher 通过 expr.first 拿到的表达式正好就是末尾的整个列表:

class RestMatcher(Matcher):
    """\
    RestMatcher match against the rest of a list like (a b . c), where c will
    be a RestMatcher. The matcher is implemented by wrapping another matcher.
    """
    def __init__(self, matcher):
        self.matcher = matcher
    def match(self, env, expr, match_dict):
        return self.matcher.match(env, pair(expr, None), match_dict)

ConstantMatcher 或者 UnderscopeMatcher 不同的是,VariableMatcher 要将匹配到的表达式保存起来,以供在 template 展开的时候引用。这个结果是保存在传递进来参数 match_dict 中的:

class VariableMatcher(Matcher):
    """\
    A variable match any single expression.
    """
    def match(self, env, expr, match_dict):
        if self.ellipsis:
            result = Ellipsis()
            while isinstance(expr, pair):
                result.append(expr.first)
                expr = expr.rest
        else:
            if not isinstance(expr, pair):
                raise MatchError("%s: unable to match %s" % (self, expr))
            result = expr.first
            expr = expr.rest
 
        match_dict[self.name] = result
        return expr

可以看到如果当前 matcher 的 ellipsis 属性为 True 的话,将会进行重复匹配,并且匹配到的结果是保存在一个 Ellipsis 对象中,其实就是一个 Python 内置的 list 简单子类,主要是用于和普通的 list 对象进行区分:

class Ellipsis(list):
    """\
    Ellipsis holds the zero or more value of an ellipsis pattern.
    """
    def __init__(self, *value):
        list.__init__(self, value)
    def __repr__(self):
        return "<ellipsis %s>" % list.__repr__(self)

使用 pattern (a b ...)(1 2 3 4) 进行匹配的结果是得到这样一个 match_dict

{
    'a': 1,
    'b': 
}

不过 ellipsis 的处理其实并不是这么简单,因为可以重复的不止是简单的 VariableMatcherSequenceMatcher 也可以重复。例如这样一个 pattern :(a (b c ...) ...) ,可以匹配到如下的表达式:

  • (1) :后面的子 SequenceMatcher 重复零次。
  • (1 (2) (3)): 子 SequenceMatcher 重复两次,而第二层的 VariableMatcher 重复零次。
  • (1 (2 3) (4 5 6)) :两次重复的次数可以不一样。

对于最后一个表达式,match 的结果应该是这样:

{
    a: 1,
    b: ,
    c: , ]>
}

然而那个子 SequenceMatcher 应该依次匹配 (2 3)(4 5 6) ,它的子 matcher 并不知道那个 sequence 是要被重复的。为了避免改动接口以及耦合太高,我采用了对子 matcher 进行欺骗的方法,传递一个“伪装的” match_dict 进去:

    def match(self, env, expr, match_dict):
        if self.ellipsis:
            md = EllipsisMatchDict()
            try:
                while isinstance(expr, pair):
                    self.match_sequence(env, expr, md)
                    expr = expr.rest
            except MatchError:
                pass
            # merge data in EllipsisMatchDict into match_dict
            match_dict.update(md)
            return expr
        else:
            if not isinstance(expr, pair):
                raise MatchError("%s: unable to match %s" % (self, expr))
            self.match_sequence(env, expr, match_dict)
            return expr.rest

其中的 EllipsisMatchDict 是一个特殊的 dict ,对其进行赋值实际上是 append 到一个 Ellipsis 上:

class EllipsisMatchDict(dict):
    """\
    Like MatchDict, excpet that all values are Ellipsis.
    """
    def __setitem__(self, key, value):
        el = self.get(key)
        if el is None:
            # no such key yet
            dict.__setitem__(self, key, Ellipsis(value))
        else:
            # already has the key
            el.append(value)

这样移花接木一下就自然地把整个匹配过程连接起来了。 :D 接下来是要对 template 进行展开,我使用了和匹配相似的方法:先对 template 表达式进行解析,生成一个 Template 对象,在展开的时候直接调用 Template 对象的 expand 方法,并传递先前匹配的结果 match_dict 就可以了:

class Template(object):
    "The base class for all template."
    def __init__(self):
        self.nflatten = 0
 
    def expand(self, md, nflatten=0):
        "Expand the template under match dict md."
        raise SyntaxError("Attempt to expand an abstract template.")

template 和 pattern 一样需要处理 ellipsis ,而且情况还要复杂一些,一个表达式后面可以跟不止一个 ellipsis ,所以这里不再用 bool 的 ellipsis 来表示,而是使用了数值 nflatten 。举个例子,pattern (a (b c ...) ...) 中变量 c 后面一共有两个 ellipsis ,对应的 template 中如果用到 c 了,其后面也必须要有两个 ellipsis ,例如:((b (c ...)) ...) ,不过在 template 中两个 ellipsis 可以直接连接在一起,例如:(c ... ...) ,这表示两级展开,例如,当匹配到 (1 (2 3) (4 5 6)) 的时候将展开为 (3 5 6)

同 matcher 差不多,简单 variable 的 flatten 处理很简单:

while nflatten > 0:
    val = self.flatten(val)
    nflatten -= 1
return val

因为子 template 在跟着 ellipsis 的时候会展开为一个列表,为了统一处理,让所有的操作都返回列表,在不需要展开的时候只需要返回一个单元数的列表就可以了,这样 SequenceTemplate 只需要将子 template 返回的结果连接起来就可以了:

def expand_0(self, md, idx):
    elems = []
    for tmpl in self.sequence:
        elems.extend(tmpl.expand(md, idx))
    rest = self.tail.expand(md, idx)[0]
    for elem in reversed(elems):
        rest = pair(elem, rest)
    return [rest]

然而 SequenceTemplate 本身的 ellipsis 处理就要更麻烦一些了。例如这样一个 template :((1 c) ... ...) ,其中变量 c 已经 match 到的结果是 , ]> 。对于子 template (1 c) 来说,它要将自己重复 3 次,这三次中要保证变量 c 分别引用到 match_dict['c'][0][0]match_dict['c'][1][0]match_dict['c'][1][1] ,即 2 、4 和 5 。然而变量 c 并不知道自己处在什么样的环境中,因此 SequenceTemplate 将合适的下标计算出来,通过 idx 参数传递给自己的子 template 们。

这里还有一个问题,就是 flatten 的时候 flatten 为几项,是需要根据子 template 中的变量匹配的结果来决定的。比如 (c) ...c 匹配的结果为 的时候就要 flatten 为三项。这个数值在进行 flatten 之前进行计算:

def expand_flatten(self, md, idx, flatten):
    if flatten == 0:
        return self.expand_0(md, idx)
    length = 0
    for name in self.ellipsis_names:
        var = md.get(name, Ellipsis())
        for i in idx:
            var = var[i]
        if not isinstance(var, Ellipsis):
            raise SyntaxError("Too many ellipsis after variable %s" % name)
        if length == 0 or length == len(var):
            length = len(var)
        else:
            raise SyntaxError("Incompatible ellipsis match counts for variable %s" % name)
    if length > 0:
        idx.append(0)
        res = []
        for i in range(length):
            idx[-1] = i
            res.extend(self.expand_flatten(md, idx, flatten-1))
        idx.pop()
        return res
    else:
        return ()

代码中 ellipsis_names 是一个所有子孙 template 中的 pattern variable 的名字的列表,这是在解析 template 表达式构建 Template 对象的时候自动收集的信息。

另外,当子 template 中各个变量匹配的数目不一样的时候进行展开会触发一个 SyntaxError 的异常,例如 pattern ((a ...) (b ...)) 的 template 可以是 ((a b) ...) ,当匹配表达式 ((1 2) (3 4)) 的时候会展开为 ((1 3) (2 4)) ,然而却无法正确展开匹配 ((1 2 3) (4 5)) 的结果。

上面的 expand_flatten 其实是一个递归过程,每次处理可以将 nflatten 减一。SequenceTemplateexpand 方法只是简单地调用了 expand_flatten :

def expand(self, md, idx=[]):
    return self.expand_flatten(md, idx, self.nflatten)

到此为止,pattern matching 和 template expanding 的过程大致就描述出来了,主要麻烦的地方还是在 sequence 的 ellipsis 的处理上。而且,这样得到的结果还并不能称作 hygienic

Hygienic Macro — more than textual replacing

回到最初的那个 swap 的例子吧。当使用 (swap foo tmp) 的时候展开的结果应该是:

(let ((tmp foo))
  (set! foo tmp)
  (set! tmp tmp))

R5RS 上说:

If a literal identifer is inserted as a free identifer then it refers to the binding of that identifer within whose scope the instance of syntax-rules appears. If a literal identifer is inserted as a bound identifer then it is in effect renamed to prevent inadvertent captures of free identifers.

也就是说,上面的 tmp 会被“重命名”以避免冲突。我觉得这句话的关键是要“避免冲突”,而实际如何避免却不一定局限于“重命名”的方式。如果采用“重命名”的话,则还是局限在 textual replacing 上,而且这样 macro 需要理解哪些是 free identifier 哪些是 bound identifier 似乎有难度,检测 letdefine 之类的是不行的,有了宏之后用户可以随时定义自己的 letdefine

跳出 symbol 字面上的意思,并不是简单地把 symbol 填到 template 相应的位置上去,而是带上更多的信息。考虑刚才那个 swap 宏展开的结果:

swap-macro.png

其中的 symbol 分为三种颜色:

  • 红色表示 dynamic scope 中,即在 macro 被使用之时说出的环境中的 symbol 。
  • 绿色表示在 lexical scope 中,即在 macro 本身被定义之时说出的环境中的 symbol 。
  • 蓝色表示则表示其他 symbol 。

一开始我被搞得很晕,直到我写到这里才突然明白过来。说 Scheme 的宏是 lexical scoping 的,原来是这个意思:在 Common Lisp 中宏被展开之后将在宏展开的地方(环境中)进行求值,而 Scheme 中宏展开之后的求值的环境是宏定义的时候的环境,就像一个 lambda closure 那样。

再仔细一看确实和函数十分神似,pattern variable 就对应到函数的参数,它们(红色的部分)是在宏被展开的环境中求值的,而其他的(包括蓝色和绿色的部分)全部都是在宏被定义的环境中进行求值的。下面这个例子:

(define foo 100)
(define-syntax stx
  (syntax-rules ()
    ((stx a) (list foo a))))
 
(let ((foo 10))
  (stx foo))

得到的结果是 (100 10) ,正好说明了这一点。只是对于函数来说,所有的参数将在函数调用之前在调用的环境中求值,然后直接把值传递过去,剩下的部分全部都会在函数本身的 lexical scoping 中求值,界限是十分清楚的。而对于 macro 来说,“参数”(即 pattern variable)是否被求值,以及何时被求值都是可以由用户控制的,所以会出现上面那样一个表达式( (set! tmp tmp) )中两个相同的 symbol 应该在不同的环境中计算的情况。为此,有些情况下 symbol 必须携带它自己的环境信息。

于是定义一个 DynamicClosure 类:

class DynamicClosure(object):
    """\
    The transform result of a macro will be evaluated in the lexical scope
    where the macro is defined. However, all the expressions captured by
    the pattern variable should still be evaluated in the dynamic scope
    where the macro is used. So they'll carry their env with them.
    """
 
    __slots__ = ('closure', 'expr')
 
    def __init__(self, env, expr):
        self.closure = env
        self.expr = expr

VariableTemplate 的结果包装起来:

def expand(self, env, md, idx=[]):
    val = md.get(self.name, Ellipsis())
    for i in idx:
        val = val[i]
    nflatten = self.nflatten
    val = [val]
    while nflatten > 0:
        val = self.flatten(val)
        nflatten -= 1
    if len(val) > 0 and isinstance(val[0], Ellipsis):
        raise SyntaxError("Ellipsis after variable %s is less than expected." % s\
name)
    return [DynamicClosure(env, v) for v in val]

如果对比前面的代码,你会发现这里的 expand 方法已经多了一个叫做 env 的参数,用于构造 DynamicClosure 。这是因为我也是一边写本文理清思路一般完成代码的。

事实上,这里可以做一些优化,许多东西,比如数字之类的,就是和所处的环境无关的,不需要创建一个 DynamicClosure 。而且,仅有这个模型还需要做很多工作,因为 skime 是先将 Scheme 代码编译为字节码再解释执行的,宏的展开是在编译的时候做的(准确地说应该是在编译之前),像这种环境交错的表达式并不好直接编译。而且环境通常不能直接引用,因为编译期的环境和运行期的环境不一定是同一个值,例如每个 lambda 表达式在每次执行的时候都会产生新的环境,然而编译的时候只会有一个环境存在。

通过 disasm 方法可以看到可读形式的字节码:

from skime.compiler.parser import parse
from skime.compiler.compiler import Compiler
from skime.vm import VM
 
compiler = Compiler()
vm = VM()
 
proc = compiler.compile(parse("""
        (begin
          (define (fact n)
            (define (iter res i)
              (if (= i 0)
                res
                (iter (* res i)
                      (- i 1))))
            (iter 1 n))
 
            (fact 5))"""), vm.env)
 
print proc.disasm()
print proc.literals[0].disasm()
print proc.literals[0].literals[0].disasm()

运行的结果如下,分别是最顶层的 form ,fact 函数和 iter 函数的字节码:

============================================================
Diasassemble of form at B7B77F2C
literals:
   0: 
   1: 5

instructions:
--------------------------------------------------
0000         push_literal literal=0
0002          fix_lexical
0003            set_local name: fact
0005         push_literal literal=1
0007           push_local name: fact
0009                 call argc=1

============================================================
Diasassemble of proc at B7B77F6C
arguments: n
literals:
   0: 

instructions:
--------------------------------------------------
0000         push_literal literal=0
0002          fix_lexical
0003            set_local name: iter
0005               push_1
0006           push_local name: n
0008           push_local name: iter
000A            tail_call argc=2

============================================================
Diasassemble of proc at B7B77FCC
arguments: res, i
literals:

instructions:
--------------------------------------------------
0000           push_local name: i
0002               push_0
0003     push_local_depth depth=2, idx=4 (name: =)
0006                 call argc=2
0008    goto_if_not_false ip=0x0020
000A           push_local name: res
000C           push_local name: i
000E     push_local_depth depth=2, idx=2 (name: *)
0011                 call argc=2
0013           push_local name: i
0015               push_1
0016     push_local_depth depth=2, idx=1 (name: -)
0019                 call argc=2
001B     push_local_depth depth=1, idx=1 (name: iter)
001E            tail_call argc=2
0020           push_local name: res
0022                  ret

虽然 push_local 那里打印的是变量的名字,这其实是为了调试方便而特意转换的,实际上是通过在编译器确定的整数偏移值来定位的,而不是运行期再通过变量名查表。看 push_local_depth 指令应该更清楚一些,这是用于引用外层(lexical scope)变量的指令,在字节码中直接指出了层数(depth)和偏移(idx),运行的时候直接通过 lexical scope 的父环境取得外层的局部变量。

但是正如前面提到的那样,lexical parent 在编译期是无法确定的,为此有一个 fix_lexical 指令专门用来做这个事情。通常情况下 fix 过的 lambda 才是可以正确执行的,不过这也是编译器自动完成的。原来这条指令只是给 lambda 用的,叫做 make_lambda ,现在 macro 牵涉到的环境处理更加复杂了,于是就改成了一条通用一些的指令。

我一直想在编译期的时候通过计算 depth 的值来实现 macro 中交错的环境引用,比如那个 swap 的例子,只要让两个 tmp 变量引用到合适的位置就可以了。可是写了一部分代码之后发现越来越混乱了。最后我发现了问题所在:宏是在它自己的 lexical scope 中计算的,这在 lexical scope 的继承链中应该是宏展开的时候说处的环境的祖先,如果说这个时候从祖先向下引用变量还不算麻烦的话,再考虑在宏展开的代码中又引入了新的 lexical scope 的情况,这时候两个环境实际上是同一祖先的两个“远亲”,要互相引用的话就不可能是一个 depth 值那么简单了。

所以我最后还是放弃了那种做法,而是把宏展开得到的表达式作为一个新生成的 lambda (更确切地说是一个 form ,直接在所属的环境中求值,而不是像 lambda 那样在一个新的 scope 中求值)在宏定义的那个 lexical scope 中编译,并对 DynamicClosure 进行特殊处理。这里我也放弃了通过 depth 进行相对引用的想法,而是直接让 closure 携带自己的环境信息,不过正如前面说的那样,这里的环境是编译期的环境,所以在 macro 展开的代码可以执行之前,所有的 DynamicClosure 需要在运行期进行 fix 一遍,还是用前面的 fix_lexical 指令。

DynamicClosure 的求值增加了一个新的指令:dynamic_eval ,在运行时暂时切换到对应的环境中进行求值,还有就是对诸如 set!define 的支持。前者需要对正确的地址进行设置,后者的语义实际上需要将其当作普通的 symbol 进行处理。

对于上面的 swap 的例子:

(begin
  (define-syntax swap
                 (syntax-rules ()
                   ((swap a b)
                    ((lambda (tmp)
                       (set! a b)
                       (set! b tmp))
                     a))))
  (define foo 4)
  (define tmp 5)
  (swap foo tmp)
  (cons foo tmp))

编译出来的字节码大致是这个样子:

============================================================
Diasassemble of proc at 9D9742C
arguments: tmp
literals:
   0: >
   1: >

instructions:
--------------------------------------------------
0000         push_literal literal=0
0002         dynamic_eval
0003         push_literal literal=1
0005    dynamic_set_local idx: 32, name: foo
0007           push_local idx: 0, name: tmp
0009                  dup
000A         push_literal literal=0
000C    dynamic_set_local idx: 33, name: tmp
000E                  ret

可以看到其中两个 tmp 是不一样的,一个是当前的局部变量,idx = 0,另一个是通过 DynamicClosure 引用到的,idx = 33 。我这里的 Scheme 代码没有用 let ,而是手工创建了一个 lambda 来引进一个 lexical scope ,主要是因为 skime 还没有实现 let 表达式的语义。

一开始我还在犹豫是否要实现宏,但是想到如果有了宏,let 就可以用一个宏来表示,就立马决定一定要实现这个东西,虽然有点复杂。不过在实现了之后我才明白 Scheme 的 hygienic macro 是不能拿来实现 let 。下面这段代码:

(define-syntax let
  (syntax-rules ()
    ((let ((var val) ...)
       expr ...)
     ((lambda (var ...)
        expr ...)
      val ...))))

是不对的。因为 expr 是 pattern variable 匹配到的表达式,它们会是以 DynamicClosure 的形式存在,并且会在展开的环境中求值,而不是在由 lambda 新创建的环境中,因此无法实现应有的效果。

不过,虽然最初的企图失败了,然而我还是得到了一个可用的 macro system ,而且真正明白了 Scheme 的 hygienic macro (至少是 syntax-rules 形式的)以及一种可行的实现方式。也算歪打正着吧。 :D

  1. 2 Responses to “The Implementation of Scheme Hygienic macro”

  2. 发现你的博客上有很多漂亮的图片,都是你自己做的吗?用什么?photoshop?

    By zhuli on Jul 27, 2008

  3. @有些是自己做的了。工具不定,能找到什么就用什么吧,Photoshop、GIMP、Fireworks、Inkscape 之类的都用过,主要是因为每个都只会用那么一点,所以感觉用哪个都差不多的样子。

    By pluskid on Jul 27, 2008

Post a Comment