Kapok 的设计与实现: Macro
Kapok是我设计与实现的一个基于Erlang VM的现代Lisp编程语言。《念念不忘，亦有回响》这篇文章叙述了这门编程语言的概况。下面我们来聊一聊其中Macro的具体设计和实现。
Lisp是一系列采用括号包围中缀表达式的列表形式来编写代码的编程语言的统称，借用一位朋友的说法，Lisp就是“裸写AST”。由于这种特别的写法，在Lisp里面将代码作为数据来操作相当容易，而实现这种操作的就是Macro。有很多的书籍和资料都有描述Lisp Macro，这里就不展开了，简单的来说，Lisp Macro是一种在编译时执行的，接受列表输入，输出列表的特殊函数。如果我们构思一下如何在Erlang VM上为一门Lisp语言实现Macro，可以得到这几个要点：
- Macro实现为函数，而Erlang和Erlang VM支持函数
- Macro对应的实现函数，其输入是代码AST，输出也是AST
- Macro在编译时执行，Macro本身的代码需要在被调用前的代码编译前编译完成
下面我们进一步看看Kapok Macro的具体实现。
函数的实现 #
将Lisp Macro实现为函数，首先我们要在Erlang VM上实现Lisp函数。Erlang是一门函数式编程语言，在它的代码编译过程中，生成的Abstract Form(或称为Syntax Tree)和Core Erlang这两种中间代码都直接支持函数。Erlang函数比较特别，参数个数(Arity)也是函数签名的一部分，它支持多个子句但是每个子句只能有固定个数的参数，举例erlang:spawn/1和erlang:spawn/3是一个同名函数的两个子句。目前已经存在的几个Erlang VM上的语言实现，如LFE等，大都沿用了Erlang函数的这个设计，除了Elixir在函数参数的最后面引入Keyword List。如果将Kapok的函数直接编译成Erlang函数，函数参数定义和签名可以照抄过来，是容易做到的。但传统的Lisp，比如Common Lisp, 在函数参数定义这块支持&optional, &rest, &key这几个关键字，其中&optional表示这个关键字后面的参数是可选的，&rest表示将后面的参数构造成一个list，&key表示可以用key value匹配的形式来调用函数。能不能在Erlang VM上实现对这几个关键字的支持呢？不妨尝试一下。
首先思考一下如何实现&optional，我们知道&optional后面的参数在调用时可以不传入而采用默认值。举例来说，如果在Common Lisp里面有这个函数定义
(defun f (a &optional b c)
;; 具体实现
...
)
以下面几种方式来调用都是合法的
(f 1 2 3)
(f 1 2)
(f 1)
这种调用的形式可以适配到Erlang的子句上面来。比如上面的函数定义f可以实现成Erlang函数：
f(A) ->
f(A, nil, nil).
f(A, B) ->
f(A, B, nil).
f(A, B, C) ->
%% 具体实现
...;
如果参数B, C被省略了，那么就用一个默认值来调用参数多一个的子句，这里假定默认参数统一为Atom nil(Lisp里面optional参数的默认值为symbol nil)。
然后再考虑如何实现&rest, &key。我们看看一个常用的函数参数实现技巧。假设现在需要定义一个函数，这个函数只允许有一个参数(不考虑这个限制是否合理)，然而你需要传入两个参数，你会怎么定义这个函数？
%% An Erlang function which calculates the area of a rectangle
%% with specified length and width.
calc_area({length, width}) ->
length * width.
你会将这个函数的唯一参数定义成一个能存放两个参数的结构，然后在调用时用实际参数构造一个这样的结构传入。上面是一个以Erlang编写的例子，事实上用其它语言比如Python, C来实现，思路也是一样。
类似地，对于&rest参数，可以将&rest后面的参数构造成一个列表传入。举例说明，若有Lisp的函数定义
(defun f (a &rest b)
;; 具体实现
...
)
可以翻译成对应的Erlang函数如下：
f(A) ->
f(A, []).
f(A, B) ->
;; 具体实现，此处B是一个列表
...
如果调用Lisp函数f的实际参数超过一个，那么从第二个参数开始及之后的实际参数都会被放入一个List中，赋值给B变量。比如对于调用
(f 1 2 3 4)
那么实际调用的对应代码就变成
f(A = 1, B = [2 3 4])
对于关键字&key，也可以采取类似的思路。比如对于函数定义
(defun f (a &key b c)
;; 具体实现
...
)
会翻译成对应的Erlang函数定义
f(A) ->
f(A, maps:new()).
f(A, Map) ->
%% 具体实现
...
调用时会变换实际参数为第二个形参构造一个Map。比如这样的调用
(f 1 :c 3)
会翻译成
f(A = 1, Map = #{c => 3})
所描述的都是Lisp函数定义里，固定参数后出现&optional, &rest, &key三个关键字其中之一的简单情况。如果两个关键字都用上，还是否能够工作呢？我们知道&rest, &key都在最后一个参数上做文章，如果&rest, &key同时出现，那最后一个参数是构造成List还是Map？幸好这种情况不会发生，在Common Lisp的编程规范中限制了函数定义中&optional, &rest, &key这几个关键字的用法如下：
- 固定参数 +
&optional/&rest/&key其中之一的简单情况，上面我们已经过了一遍 &key与&optional,&rest混用会产生奇怪行为，所以&key不能与它们混用&optional可与&rest混用，但是约定&optional在前，&rest在后
只有第3点是混用的情况，根据的实现方式可知&optional和&rest没有冲突，第3点是可以实现的。
上面花了很长的篇幅来详细描述如何在Erlang VM实现Lisp函数，由开头的讨论可知Macro也是函数，有了函数的实现作为基础，下面我们进一步讨论Macro函数的输入输出。
AST的处理 #
从代码的书写形式来看，在Lisp里面代码是列表，因此Lisp Macro的输入和输出都是列表。在实现层面，Lisp列表形式的代码会经过词法分析语法分析，最后变成编译器内部表示AST。AST主要保存这几类信息：类别，数值，元数据。例如，在Lisp代码里面的100字面量，就需要一个AST数据结构记录下它是一个常量，值为整数100，它在代码文件里面的行号是多少等。Kapok内部将AST定义为Erlang Tuple
{Category, Meta, Value}
其中Category表示这个结点的类别，比如integer常量，list, map等。Meta是一个保存元数据的Property List。Value则是记录了实际的取值，比如对于integer常量，就记录了常量的值是100，对于List类型，就记录了这个List包含的所有元素的子结点AST。
熟悉Elixir元编程的人看到这个定义会觉得很熟悉，因为AST在Elixir中的定义也是如此。
Macro的输入和输出都是AST，在编译过程中，每一个对Macro的调用，都是使用参数的对应的AST来调用Macro的实现函数。举例说明，比如对于Macro定义
(defmacro unless [test &rest body]
"""Evaluates test. If logical false, evaluates body in an implicit do."""
`(case (core.true? ~test)
(^true ^ok)
(^false ~@body)))
有调用代码如下
(unless (f 1)
(g 2)
(h 3))
那么在Macro展开的时候会得到调用如下，以对应Erlang代码来描述：
unless(AST{(f 1)}, [AST{(g 2)}, AST{(h 3)}])
其中AST{X}表示Lisp表达式X(也就是在Lisp代码里面看到的形式)对应的AST，每个AST展开都是上面所述的Tuple结构，为方便描述这里使用了简单表示。Macro展开的过程，即是输入的AST流经过unless函数，对应的参数经过变换之后得到输出如下:
AST{(case (core.true? (f 1))
(^true ^ok)
(^false (g 2) (h 3)))}
整个输出是一个完整的case表达式的AST，检查case表达式和unless Macro的定义，我们可知AST{(f 1)}插入到了指定的条件判断参数处，而[AST{(g 2)}, AST{(h 3)}]中的元素被取出放入了false分支。
在Kapok编译的最后阶段，这种内部AST会转换成Erlang Abstract Form，最后把它用Erlang Compiler编译并加载到Erlang VM。这部分的转换的逻辑相当于繁琐，篇幅所限就不再一一展开。
Macro编译，展开 #
普通函数一般是在运行时执行的，Macro与之不同，它在编译时执行。要在编译时调用一个Macro，这个Macro的定义必须已知，并且经过编译，才可能被调用。在Erlang里面，模块(Module)即是代码的基本组织单元，也是编译的基本单元，虽然也可以对单个表达式进行编译。已有的几种基于Erlang VM的语言，如Elixir, LFE，都采用了将他们的代码模块翻译到Erlang模块然后按模块编译的方式。按模块编译对于Macro的编译和展开会产生一个编译顺序的问题，举例来说在Elixir里面，你需要先声明一个模块m1，在里面编写宏mac的定义，然后声明另外一个模块m2，在m2里面的代码，假设是函数f，调用mac，编译的时候会先编译m1，使得mac的定义被编译过，然后编译m2，编译m2时在mac被调用的地方执行它。你不能把f和mac都写在同一个模块，否则在这个模块被编译的时候，mac就不能被执行。在Kapok中，我沿用了Joxa的一个技巧，f和mac可以写到同一个模块，但是mac必须放在f之前，在编译时，如果发现f中的代码调用了一个当前模块的Macro，那么就将f之前的代码当成一个完整的模块，以一个随机生成的模块名，送到Erlang Compiler编译，编译后就可以调用其中的mac。
每次调用一个Macro，都会将调用时的参数AST传入，得到结果AST，再插入到原来调用处，这样称之为一次展开。在Lisp中，Macro的展开是递归的，即是说如果展开mac之后，得到的代码若还有其它的Macro，比如unless，还会进一步展开，直至所有Macro都全部展开为止。
一个完整的例子 #
最后，以一个完整的例子来说明整个Kapok编译过程，包括上面提到的函数翻译，Macro的编译和展开等，以帮助理解。用一个简单的Kapok函数定义为例
(defn g [n]
(io.format "call g(n = ~p)~n", [n]))
这段代码经过词法分析，语法分析阶段后，会生成AST如下：
{list,[{line,4},{column,1}],
[{identifier,[{line,4},{column,2}],defn},
{identifier,[{line,4},{column,7}],g},
{literal_list,[{line,4},{column,9}],
[{identifier,[{line,4},{column,10}],n}]},
{list,[{line,5},{column,3}],
[{dot,[{line,5},{column,6}],{io,format}},
{binary_string,[{line,5},{column,14}],<<"call g(n = ~p)~n">>},
{literal_list,[{line,5},{column,34}],
[{identifier,[{line,5},{column,35}],n}]}]}]}
其结构比较简明，从中可以识别出标识符defn, g, n及list等结构。这个AST由于没有任何Macro调用，经过Macro Expand阶段没有任何变化，然后会转换成Erlang Abstract Form如下：
{function,0,g,1,
[{clause,4,
[{var,4,n}],
[],
[{call,5,
{remote,5,{atom,0,io},{atom,0,format}},
[{bin,0,[{bin_element,0,{string,0,"call g(n = ~p)~n"},default,default}]},
{cons,0,{var,5,n},{nil,0}}]}]}]}
这段中间代码同样比较简单，容易看到函数g只带一个参数n，在它唯一的一个子句里面调用了一个io.format函数。
我们可以加上前面提到的Macro，并且添加一个调用Macro的代码，如下：
(defmacro unless [test &rest body]
"""Evaluates test. If logical false, evaluates body in an implicit do."""
(io.format "call unless macro~n")
`(case (core.true? ~test)
(^true ^ok)
(^false
(io.format "before exprs in body!~n")
~@body)))
(defn f [n]
(g n)
(unless (== n 0)
(io.format "1. n: ~p~n" [n])
(io.format "2. hello macro~n")))
f的定义在经过词法与语法分析阶段后得到AST
{list,[{line,16},{column,1}],
[{identifier,[{line,16},{column,2}],defn},
{identifier,[{line,16},{column,7}],f},
{literal_list,[{line,16},{column,9}],
[{identifier,[{line,16},{column,10}],n}]},
{list,[{line,17},{column,3}],
[{identifier,[{line,17},{column,4}],g},
{identifier,[{line,17},{column,6}],n}]},
{list,[{line,18},{column,3}],
[{identifier,[{line,18},{column,4}],unless},
{list,[{line,18},{column,11}],
[{identifier,[{line,18},{column,12}],'=='},
{identifier,[{line,18},{column,15}],n},
{number,[{line,18},{column,17}],0}]},
{list,[{line,19},{column,5}],
[{dot,[{line,19},{column,8}],{io,format}},
{binary_string,[{line,19},{column,16}],<<"1. n: ~p~n">>},
{literal_list,[{line,19},{column,29}],
[{identifier,[{line,19},{column,30}],n}]}]},
{list,[{line,20},{column,5}],
[{dot,[{line,20},{column,8}],{io,format}},
{binary_string,[{line,20},{column,16}],
<<"2. hello macro~n">>}]}]}]}
其中可以看到有{list, _, [{identifier, _, unless}, ...]}这样一个宏调用。因为这个宏是在同一个模块的前面定义的，Kapok编译器就将f之前的代码，包括g, unless的定义作为另一个模块编译完后，用f中调用unless的实际参数AST作为参数来调用unless。即unless被调用时得到的参数如下：
{list,[{line,18},{column,11}],
[{identifier,[{line,18},{column,12}],'=='},
{identifier,[{line,18},{column,15}],n},
{number,[{line,18},{column,17}],0}]},
[{list,[{line,19},{column,5}],
[{dot,[{line,19},{column,8}],{io,format}},
{binary_string,[{line,19},{column,16}],<<"1. n: ~p~n">>},
{literal_list,[{line,19},{column,29}],
[{identifier,[{line,19},{column,30}],n}]}]},
{list,[{line,20},{column,5}],
[{dot,[{line,20},{column,8}],{io,format}},
{binary_string,[{line,20},{column,16}],<<"2. hello macro~n">>}]}]
其中第一个参数是一个list AST，第二个参数是一个List，它的元素也是两个AST。这一串AST流经unless函数之后，经过转换返回的结果是
{list,
[{line,10},{column,4}],
[{identifier,[{line,10},{column,5}],'case'},
{list,
[{line,10},{column,10}],
[{dot,[{line,10},{column,15}],{core,'true?'}},
{list,
[{line,18},{column,11}],
[{identifier,[{line,18},{column,12}],'=='},
{identifier,[{line,18},{column,15}],n},
{number,[{line,18},{column,17}],0}]}]},
{list,
[{line,11},{column,6}],
[{atom,[{line,11},{column,7}],true},
{atom,[{line,11},{column,12}],ok}]},
{list,
[{line,12},{column,6}],
[{atom,[{line,12},{column,7}],false},
{list,
[{line,13},{column,7}],
[{dot,[{line,13},{column,10}],{io,format}},
{binary_string,
[{line,13},{column,18}],
<<"before exprs in body!~n">>}]},
{list,
[{line,19},{column,5}],
[{dot,[{line,19},{column,8}],{io,format}},
{binary_string,[{line,19},{column,16}],<<"1. n: ~p~n">>},
{literal_list,
[{line,19},{column,29}],
[{identifier,[{line,19},{column,30}],n}]}]},
{list,
[{line,20},{column,5}],
[{dot,[{line,20},{column,8}],{io,format}},
{binary_string,
[{line,20},{column,16}],
<<"2. hello macro~n">>}]}]}]}
从中可以看到输入的AST参数已经被转换插入到指定的地方，这个unless返回的AST也将被插入到f中unless被调用的地方，从而达到修改/变换代码的效果。由于篇幅所限，f以及整个模块最后生成的Erlang Abstract code就不一一展示了。最后贴出整个示例的完整模块Kapok代码如下：
(ns x
(require io))
(defn g [n]
(io.format "call g(n = ~p)~n", [n]))
(defmacro unless [test &rest body]
"""Evaluates test. If logical false, evaluates body in an implicit do."""
(io.format "call unless macro~n")
`(case (core.true? ~test)
(^true ^ok)
(^false
(io.format "before exprs in body!~n")
~@body)))
(defn f [n]
(g n)
(unless (== n 0)
(io.format "1. n: ~p~n" [n])
(io.format "2. hello macro~n")))
(defn main []
(f 0)
(f 1))
假定这份代码在文件x.kpk中，编译安装kapok之后(具体的编译安装过程可以参考Kapok文档，不再详述)使用命令
$ kapok x.kpk
即完成编译x模块，并运行其中的main函数。可得到结果输出
call unless macro
call g(n = 0)
call g(n = 1)
before exprs in body!
1. n: 1
2. hello macro
在代码里，main函数调用了2次f，f又调用了g，于是有2行call g(...的输出。然而由于unless是在编译时被调用的，只在f的定义里被调用了一次，所以只能看到1行"call unless macro"的输出，而且unless展开时输出的这一行在最前面，因为它是在编译阶段执行的，而所有其它io.format都是在运行阶段执行的。最后我们来看一下最后三行输出，“before exprs …“一行是在Macro里面定义的，“1. …”, “2. …“这两行则是在调用unless时的输入参数，它们按指定的顺序被组合到同一个case分支中。