Kapok的设计与实现: Macro

木棉花

Kapok是我设计与实现的一个基于Erlang VM的现代Lisp编程语言。《念念不忘,亦有回响》这篇文章叙述了这门编程语言的概况。下面我们来聊一聊其中Macro的具体设计和实现。

Lisp是一系列采用括号包围中缀表达式的列表形式来编写代码的编程语言的统称,借用一位朋友的说法,Lisp就是“裸写AST”。由于这种特别的写法,在Lisp里面将代码作为数据来操作相当容易,而实现这种操作的就是Macro。有很多的书籍和资料都有描述Lisp Macro,这里就不展开了,简单的来说,Lisp Macro是一种在编译时执行的,接受列表输入,输出列表的特殊函数。如果我们构思一下如何在Erlang VM上为一门Lisp语言实现Macro,可以得到这几个要点:

  1. Macro实现为函数,而Erlang和Erlang VM支持函数
  2. Macro对应的实现函数,其输入是代码AST,输出也是AST
  3. Macro在编译时执行,Macro本身的代码需要在被调用前的代码编译前编译完成

下面我们进一步看看Kapok Macro的具体实现。

函数的实现

将Lisp Macro实现为函数,首先我们要在Erlang VM上实现Lisp函数。Erlang是一门函数式编程语言,在它的代码编译过程中,生成的Abstract Form(或称为Syntax Tree)和Core Erlang这两种中间代码都直接支持函数。Erlang函数比较特别,参数个数(Arity)也是函数签名的一部分,它支持多个子句但是每个子句只能有固定个数的参数,举例erlang:spawn/1erlang:spawn/3是一个同名函数的两个子句。目前已经存在的几个Erlang VM上的语言实现,如LFE等,大都沿用了Erlang函数的这个设计,除了Elixir在函数参数的最后面引入Map。如果将Kapok的函数直接编译成Erlang函数,函数参数定义和签名可以照抄过来,是容易做到的。但传统的Lisp,比如Common Lisp, 在函数参数定义这块支持&optional, &rest, &key这几个关键字,其中&optional表示这个关键字后面的参数是可选的,&rest表示将后面的参数构造成一个list,&key表示可以用key value匹配的形式来调用函数。能不能在Erlang VM上实现对这几个关键字的支持呢?不妨尝试一下。

首先思考一下如何实现&optional,我们知道&optional后面的参数在调用时可以不传入而采用默认值。举例来说,如果在Common Lisp里面有这个函数定义

1
2
3
4
(defun f (a &optional b c)
  ;; 具体实现
  ...
  )

以下面几种方式来调用都是合法的

1
2
3
(f 1 2 3)
(f 1 2)
(f 1)

这种调用的形式可以适配到Erlang的子句上面来。比如上面的函数定义f可以实现成Erlang函数:

1
2
3
4
5
6
7
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。我们看看一个常用的函数参数实现技巧。假设现在需要定义一个函数,这个函数只允许有一个参数(不考虑这个限制是否合理),然而你需要传入两个参数,你会怎么定义这个函数?

1
2
3
4
%% 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的函数定义

1
2
3
4
(defun f (a &rest b)
  ;; 具体实现
  ...
  )

可以翻译成对应的Erlang函数如下:

1
2
3
4
5
f(A) ->
  f(A, []).
f(A, B) ->
  ;; 具体实现,此处B是一个列表
  ...

如果调用Lisp函数f的实际参数超过一个,那么从第二个参数开始及之后的实际参数都会被放入一个List中,赋值给B变量。比如对于调用

1
(f 1 2 3 4)

那么实际调用的对应代码就变成

1
f(A = 1, B = [2 3 4])

对于关键字&key,也可以采取类似的思路。比如对于函数定义

1
2
3
4
(defun f (a &key b c)
  ;; 具体实现 
  ...
  )

会翻译成对应的Erlang函数定义

1
2
3
4
5
f(A) ->
  f(A, maps:new()).
f(A, Map) ->
  %% 具体实现
  ...

调用时会变换实际参数为第二个形参构造一个Map。比如这样的调用

1
(f 1 :c 3)

会翻译成

1
f(A = 1, Map = #{c => 3})

所描述的都是Lisp函数定义里,固定参数后出现&optional, &rest, &key三个关键字其中之一的简单情况。如果两个关键字都用上,还是否能够工作呢?我们知道&rest, &key都在最后一个参数上做文章,如果&rest, &key同时出现,那最后一个参数是构造成List还是Map?幸好这种情况不会发生,在Common Lisp的编程规范中限制了函数定义中&optional, &rest, &key这几个关键字的用法如下:

  1. 固定参数 + &optional/&rest/&key 其中之一的简单情况,上面我们已经过了一遍
  2. &key&optional, &rest混用会产生奇怪行为,所以&key不能与它们混用
  3. &optional可与&rest混用,但是约定&optional在前,&rest在后

只有第3点是混用的情况,根据的实现方式可知&optional&rest没有冲突,第3点是可以实现的。

上面花了很长的篇幅来详细描述如何在Erlang VM实现Lisp函数,由开头的讨论可知Macro也是函数,实现了函数就实现了Macro。下面我们进一步讨论Macro函数的输入输出。

AST的处理

从代码的书写形式来看,在Lisp里面代码是列表,因此Lisp Macro的输入和输出都是列表。在实现层面,Lisp列表形式的代码会经过词法分析语法分析,最后变成编译器内部表示AST。AST主要保存这几类信息:类别,数值,元数据。例如,在Lisp代码里面的100字面量,就需要一个AST数据结构记录下它是一个常量,值为整数100,它在代码文件里面的行号是多少等。Kapok内部将AST定义为Erlang Tuple

1
{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定义

1
2
3
4
5
(defmacro unless [test &rest body]
  """Evaluates test. If logical false, evaluates body in an implicit do."""
  `(case (core.true? ~test)
     (^true ^ok)
     (^false ~@body)))

有调用代码如下

1
2
3
(unless (f 1)
  (g 2)
  (h 3))

那么在Macro展开的时候会得到调用如下,以对应Erlang代码来描述:

1
unless(AST{(f 1)}, [AST{(g 2)}, AST{(h 3)}])

其中AST{X}表示Lisp表达式X(也就是在Lisp代码里面看到的形式)对应的AST,每个AST展开都是上面所述的Tuple结构,为方便描述这里使用了简单表示。Macro展开的过程,即是输入的AST流经过unless函数,对应的参数经过变换之后得到输出如下:

1
2
3
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被调用的地方执行它。你不能把fmac都写在同一个模块,否则在这个模块被编译的时候,mac就不能被执行。在Kapok中,我沿用了Joxa的一个技巧,fmac可以写到同一个模块,但是mac必须放在f之前,在编译时,如果发现f中的代码调用了一个当前模块的Macro,那么就将f之前的代码当成一个完整的模块,以一个随机生成的模块名,送到Erlang Compiler编译,编译后就可以调用其中的mac

每次调用一个Macro,都会将调用时的参数AST传入,得到结果AST,再插入到原来调用处,这样称之为一次展开。在Lisp中,Macro的展开是递归的,即是说如果展开mac之后,得到的代码若还有其它的Macro,比如unless,还会进一步展开,直至所有Macro都全部展开为止。

一个完整的例子

最后,以一个完整的例子来说明整个Kapok编译过程,包括上面提到的函数翻译,Macro的编译和展开等,以帮助理解。用一个简单的Kapok函数定义为例

1
2
(defn g [n]
  (io.format "call g(n = ~p)~n", [n]))

这段代码经过词法分析,语法分析阶段后,会生成AST如下:

1
2
3
4
5
6
7
8
9
10
{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, nlist等结构。这个AST由于没有任何Macro调用,经过Macro Expand阶段没有任何变化,然后会转换成Erlang Abstract Form如下:

1
2
3
4
5
6
7
8
{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的代码,如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
{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被调用时得到的参数如下:

1
2
3
4
5
6
7
8
9
10
11
12
{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函数之后,经过转换返回的结果是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
{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也将被插入到funless被调用的地方,从而达到修改/变换代码的效果。由于篇幅所限,f以及整个模块最后生成的Erlang Abstract code就不一一展示了。最后贴出整个示例的完整模块Kapok代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
(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文档,不再详述)使用命令

1
$ kapok x.kpk

即完成编译x模块,并运行其中的main函数。可得到结果输出

1
2
3
4
5
6
call unless macro
call g(n = 0)
call g(n = 1)
before exprs in body!
1. n: 1
2. hello macro

在代码里,main函数调用了2次ff又调用了g,于是有2行call g(...的输出。然而由于unless是在编译时被调用的,只在f的定义里被调用了一次,所以只能看到1行”call unless macro”的输出,而且unless展开时输出的这一行在最前面,因为它是在编译阶段执行的,而所有其它io.format都是在运行阶段执行的。最后我们来看一下最后三行输出,”before exprs …“一行是在Macro里面定义的,”1. …”, “2. …“这两行则是在调用unless时的输入参数,它们按指定的顺序被组合到同一个case分支中。

念念不忘,亦有回响

电影《一代宗师》佛前灯

多年以前,当我在Linux下选择Emacs做为编辑器的时候,似乎只是一个比较随机的选择。当时我已经接触并使用VI有一段日子,然而我使用它的体验并不算愉快,也许是我被VI命令模式和编辑模式搞乱了太多次,于是想找个其它编辑器试试,而当时我所知道的Linux终端字符界面编辑器并不多,Emacs是其中一个,然后我就开始使用Emacs,从此一发不可收拾,走上了一条不断修炼的漫漫长路。这段经历后来浓缩成了《Emacs修炼之道》这篇文章。Emacs不仅给我提供了一个舒适高效的编辑器工具与环境,也引领我走入了Lisp语言的世界。

Lisp语言诞生自几十年前,这几十年间世事沧桑,一个又一个浪潮在计算机行业冒升又落下,一门又一门新的编程语言流行而又衰落,Lisp语言早已退出流行的行列,然而却始终吸引着一小群程序员前仆后继地不断进入它的世界。除了传统的几种Lisp方言,2007年出现的Clojure将Lisp在JVM平台重新做了一个现代的实现,也掀起了一波新的潮流,吸引了很多人的关注和使用。几十年前诞生的编程语言,大多早已消失在历史的长河中了,为什么Lisp能够保持长期的生命力呢?正如看待黑客文化时有人主要关注它的政治正确,有人则将它看成是嗡嗡作响的经济引擎,不同的人对Lisp优点的看法也大不相同。有人喜欢Lisp以List作为唯一代码组织方式的简单明了,有人欣赏Lisp由核心几个特殊Form支撑起来的体系,对应着数学领域里面的公理上搭建大厦的体系结构,有人则更实利化只关注可以帮助提高开发效率的那些方面。在我看来,Lisp最吸引我的一点就是强大的元编程能力,非常便于编写DSL。当然这并不是说其它方面不重要,如交互式编程,强调函数式风格但又不强制函数式为唯一风格等特点也是可圈可点。

Lisp的思想和设计是如此优秀,然而传统的几种方言的实现Scheme,Common Lisp还有另外几个方言都没能紧跟这个时代的步伐,Clojure的作者Rich Hickey必定是深知这点,才会创造了Clojure。感谢Rich,我们得以知道在某个语言的成熟VM上实现一个现代Lisp的可行性,也欣赏到了Clojure设计与哲学的种种优雅美丽之处。Clojure设计于运行在JVM之上,固然是它的成功关键,因为如此一来就可以重用成熟的JVM环境以及丰富的代码库,同时Java程序员这个群体也非常庞大,能吸引到的Clojure使用者也多。另一方面也产生了一些缺点,因为底层的JVM原本是为Java设计实现的,而Java的并发模型还停留在操作系统进程/线程和锁这一种方式,因此Clojure除了保留Java的并发原语之外,还在并发上做了多种尝试,像软事务内存,几种不同的原语delay, future, promise,还有几种不同的引用类型。如此多的新概念和原语不可谓不丰富,同时也是繁多复杂。每当我的脑细胞因为折腾可变与不变或者write skew而被烧死一部分的时候,我总是怀念Erlang Actor并发模型的简单。

既然要顺适多核化的趋势,就需要语言本身的并发机制支持用户态进程/协程。那么为什么不直接使用Erlang呢?虽然Erlang并不是Lisp,但Erlang的设计也受到Lisp的影响,很多地方都有Lisp的影子,比如交互shell,热更新等。然而我对Erlang也有觉得不满意的地方,除了经常被, ; .几个符号搞晕之外,最大的不满是来自于在Erlang里做元编程的不便,但是Erlang代码又有很强烈的元编程需求,比如OTP里面的大片模板代码。因此在编写Erlang代码的时候,我又相当怀念Lisp的Macro。

那么,能否把Erlang和Lisp两者的优点结合起来呢,就像在JVM上实现Clojure一样,也许可以在Erlang VM上实现一门Lisp语言?到我的脑海中冒出这个想法的时候,距离我最早接触Erlang已经有三年多时间,距离学习Clojure已经有两年,另外当时在工作上我也写了大半年的Golang,是的,近几年中我学习/使用过的编程语言也不少,基本上每年都会学一到两门新语言,虽然不是每个新学语言都有机会用来写大量的代码,但也算是见识了不少编程语言,也许是对很多好的语言有着更高的期望吧,没有哪种已知的编程语言令我觉得非常满意。带着把Erlang和Lisp结合的想法,我发现原来Erlang VM就像Java VM,VM之上也有中间语言层,可以基于这中间层来实现一门Lisp,而且,早在几年前,就已经有人这样做了。我发现了Robert Virding写的LFE,和Eric Merritt写的Joxa。

作为参与设计Erlang的元老,Robert一直以来也是探索Erlang应用方面的先行者,早在2007年就写了LFE,并且影响了一众后来基于Erlang VM的新语言,如Elixir。LFE是Lisp Flavored Erlang的缩写,顾名思义,LFE就是把Erlang写成Lisp,除了多了一些括号之外(去掉了Erlang原来的分隔符如, ; .等)跟Erlang十分相似,LFE的设计目标在于提供一个可扩展语法的Erlang,它的实现也达到这个目标。然后跟我理想中的Lisp语言相去有一定距离,我并不喜欢它的Lisp-2风格,跟Erlang相似的模块设计如显式的export,只在编译时可用的Macro等方面。

另外一个实现Joxa则是由Eric在2011年开始写的,Eric也是Erlang界的老前辈了,他先是试用过LFE,然后觉得并不如意才重新设计和实现了Joxa,之前我写过的文章《Joxa: 一种基于Erlang VM的现代Lisp编程语言》详细描述了两者的渊源和差别,这里就不再展开了。总的来说,Joxa的Lisp味相对更浓一些,更符合我的个人口味。在过去的一年多时间里,我仔细阅读了Joxa的实现并添加了Erlang R17后引入的Map的语法。Joxa虽好,但有两个主要原因让我不得不考虑重新做一个实现:

  1. Joxa目前的实现是用自举的方式将Lisp代码经过编译转换成Core Erlang,自举是很cool的一种实现编译器的方式,然而用在语法不够稳定的场景下,会提高后续语言开发的复杂度和难度。Core Erlang也是一个规模小巧设计良好的中间层,然而文档方面相当缺乏,很多时候必需花大量时间人手去获取从上层到它的翻译细节。相对来说更上层的Abstract Format虽然规模更大,然而文档较多,一些工具也只工作在这一层,所以更适合用于做为编译器的目标语言。在这一点上我和Eric讨论得出的一致结论是,要将Joxa用Erlang重写并将目标输出定位到Abstract Format,却因为彼此都忙暂时未有足够精力将其重写。

  2. Joxa的设计目标强调它要小而简,希望成为一个小的核心语言,如果其他人有需要就在其上定制扩展。这种设计也是Lisp语言的一种传统特色,由于扩展性强,可以做到核心小扩展大,类似的思想也被人在不同的语言和项目上实现,比如PyPy和Python 3。然而我更希望有一套功能较多较全的编程语言,因此需要在语法和代码规模上都需要添加(或者改动,但主要是添加)很多内容,这就与Joxa的目标有冲突。据我所知Eric对Joxa有明确的定位,应该不会乐意在Joxa里面接受这些添加或改变,因此最好我还是用一个新项目名字来重写一个基于Erlang VM的Lisp实现。

一直以来我有个朦胧的想法,希望在下一个我能够自己决定命名的项目,能够用上一个带有我居住所在地中国华南地区的风物,或者带有东南亚色彩的名字,在给这个新项目取名时,老家旧居楼房前面的两棵高大的木棉树出现在我的脑海,那是一种在南方非常常见非常普通的树,平时不会特别觉察到它们的存在,然而有时觉察到它们的存在却又不禁觉得特别,像鲁迅笔下所说:“在我的后园,可以看见墙外有两株树,一株是枣树,还有一株也是枣树”。于是就将这个新项目的名字取为木棉,英文是Kapok。

我想,Kapok这个新的基于Erlang VM上的Lisp实现会包含如下这些内容:

  1. 一套类似Clojure风格的现代Lisp语法(Lisp-1),当然在语法上并不能无脑照抄Clojure,比如方括号[]在Clojure中表示Vector,在Erlang却是List,那么Kapok里如何选择?若语义跟随前者,是用Erlang的tuple来实现Vector语义还是另外再做一套实现?若语义跟随后者,和普通圆括号()又如何区分,各自的使用场景如何确定?每处细节都需要仔细考量,这些细节也会影响其它方面,如下面将提到的兼容性。另外Clojure语法糖较多,而我不喜欢太甜。

  2. 与Erlang VM保持最大的兼容,在Erlang VM上实现的多种语言,都选择了将语法及语义尽量向Erlang靠拢,比如新语言的函数直接编译成Erlang的函数,如此得以保持良好的兼容性,新语言的代码可以直接与Erlang VM基础设施与已有库代码进行相互调用,不像Clojure那样需要通过中间包装。Erlang是一门函数式语言,这意味着新语言最好也保持这种函数式的语义,当然也可以通过上层逻辑修改这种限制,比如另一门基于Erlang VM的语言Elixir通过在编译器做变量名映射的技巧使得在Elixir里同一个变量可以做多次绑定,如此一来Elixir在变量使用上更像命令式语言。基于两个原因我个人更偏向于在Kapok里面完全保留Erlang的函数式语义,一是它利于并发,二是它语义更清晰。

  3. 新的语言机制,目前已经在考虑中的有:支持Clojure的Protocol(运行时类型分派,让语言更动态),探索一套带类型标注的DSL来做强类型编程(强制编译时类型检查,让语言更静态),Lazy API。其中第Protocal和Lazy API源自Clojure(当然Clojure也借鉴了其它语言),并且已经在Elixir中得到实现。同时我对其它新想法持开放的态度。

  4. 功能丰富接口现代的标准库,包括常用宏,文件,网络等方面,特别一提的是Erlang原生用字符列表来表示字符串并不理想,因此需要有一整套高效易用的unicode字符串标准库,在LFE和Elixir中都重新定义了binary string,这是一个比较好的方案,可以借鉴。

  5. 强大且现代的开发工具集,包括:文档及Apropos接口/工具,编辑器集成(如Emacs mode), 项目管理工具(参考Mix),交互性开发环境(集成Slime和Swank)等

上面的几点综合了Clojure, Erlang, Joxa, LFE, Elixir, Emacs等多种语言或机制,希望可以取多家之长,提供一套强大完整的开发环境。当然也可以说是一个大杂烩,然而不是无脑照搬,库和工具集可以丰富多样,然而基础语法需要保持简约节制,避免出现C++或Scala那样过于烧脑的设计。同时也要了解到上面几点内容只是一个初步的想法,后面可能会根据实际情况有所添加或改变。我一直有个用一门新编程语言编写一个开源数据库的朦胧想法,Kapok完善到一定程度之后,也许可以用Kapok来完成我这个想法。

有了简要设计,就可以开工编写代码了,首先要实现的是1, 2两点,亦即核心编译器部分。要写Kapok的想法早在去年就已经产生,然而一直拖拖拉拉未能动手。去年年中祖母去世,让我明白到时间匆匆人生太短,有些事情想做就抓紧时间去做,迟早人生的终点只是青山上的一把黄土。于是开始动手,由于平时上下班剩余时间不多,生活琐事缠身,进展较为缓慢,拖拉了几个月逐渐完成了编译器前端,大概到今年初开始写后端,也算是慢慢重温了一遍大学时开的编译课程。最近有了一些时间,终于折腾到可以跑起来的程度。我想Kapok这个项目不可谓不大,终究不能短期内完成,要做到非常完善的程度,更是有待时日。就像长跑,并非重在一时之快慢,积跬步恒坚持,方能走得更久更远。我所需要做的,就是调整呼吸,跨开步子。

于是就把Kapok开源了,github地址在这里,虽然暂时还有很多问题和缺点,也有很多想法未能实现,但我想这也算是一个不错的长跑起步。

十年之前,当我第一次安装并启动Emacs的时候,决没有料到会十年之后它带领我在Lisp的世界走了这么远。几年之前在接触Erlang,Clojure的时候,没有想到有一天会用Erlang重写一门Clojure风格的Lisp语言。一年之前开始着手Kapok的时候,我也不知道这个项目要做到何时,做到什么程度。然后事情冥冥中就这样发生了,而我将沿着这条路继续向前走。王家卫电影《一代宗师》里面,宫先生说“念念不忘,必有回响”,行知做人跟练武一样,秉着意念坚持下去,终究能有一点回响。

Joxa: 一种基于Erlang VM的现代Lisp编程语言

Joxa是一种基于Erlang VM的现代Lisp编程语言,创始人是美国的Eric Merritt[1]。通过在Erlang VM上引入一个精心设计的Lisp语法,它保留了Lisp和Erlang两者的众多优点:简洁而且语义清晰的Lisp语法,强大的Macro,鼓励交互式开发,支持高并发,函数式风格等,并且与现有的Erlang平台保持良好兼容。它是一门功能全面的通用编程语言。

Joxa的官方网站是joxa.org,在这个官方网站上,有它的源代码github地址,以及在线文档。为什么这门编程语言取名为Joxa呢?关于Joxa这个名字的由来,Eric Merritt曾经对我在邮件组的提问做过如下解释:

其实这个名字并无特别的意义。很多年前我想开始一个“基于Java的某个项目”,于是有了它的缩写Joxa这个名字。这个项目从来没有开始做过,但我把域名买下来了并一直持有着。到今天,4个字母的域名已经很少能注册到了,所以我决定用它来做为这门语言的名字。[2]

除了名字开头有个字母”J”,Joxa与Java并没有太大的关系了,Joxa主要受到了Erlang及基于JVM的编程语言Clojure的影响。下面我们先介绍一下Erlang和Clojure,再讨论Joxa受到了它们的哪些影响。

1. Erlang, Clojure以及Joxa

1.1 Erlang,高并发的函数式容错编程语言

Erlang是一门通用的并发程序设计语言,它由瑞典爱立信的Joe Armstrong在上世纪80年代开发,并于1998年对外开源,Erlang这个名字来源自丹麦数学家及统计学家Agner Krarup Erlang。经过近30年的发展,Erlang目前是支持高并发的编程语言翘楚之一,它在语言层面封装了Actor模型,实现了用户空间的轻量级进程,将消息传递作为Actor间通信的唯一方式,避免了由传统的线程和锁在并发方面的限制与缺点。Erlang被设计为电信级系统的编程语言,强调分布式,容错,软实时和公平调度,在语法上它主要受到Prolog及Lisp的影响,保留了函数式,动态,交互式开发等特点。具体来讲,Erlang这个名字可以分成3个方面的要素:

  1. 编程语言Erlang本身
  2. 总称为OTP的一系列程序设计原则及代码库
  3. 称为Erlang VM或BEAM的Erlang虚拟机

Erlang设计于近30年前,因此从现在的角度来看,它在语法,编程环境(包括文档等)及工具链等方面有很多地方都有改进空间。由于Erlang VM是目前工业界支持高并发的最成熟的VM之一,大量技术专家及工程师们在上面投入了无数的工作,通过在Erlang VM上设计一门新语言来重用Erlang VM的优良特性,既能发挥Erlang VM的长处,又能改善Erlang语言本身在语法、工具链等方面的缺点,扬长而避短,是比较完美的方案。业界近几年涌现了众多基于Erlang VM的编程语言,下面介绍其中几种:

  1. LFE
    LFE是Lisp Flavored Erlang的缩写,它是由Robert Virding[3]于2007年开始开发的一门函数式的并发的通用编程语言,LFE采用了Lisp-2[4]风格的语法,通过将LFE代码编译为Core Erlang代码运行在BEAM上,保留了Erlang VM分布式,容错,软实时等优点,同时支持Lisp Macro,使得LFE兼有强大的元编程能力,并实现了一个功能丰富的REPL[5]
  2. Reia
    Reia是一门基于Erlang VM上的类似Ruby的脚本编程语言,它由Tony Arcieri[6]于2010年中开始开发,它在Erlang VM的分布式,并发,容错,热更新的基础之上,引入了Ruby的友好语法,灵活的代码块,反射及元编程功能力。遗憾的是,Reia在2011年宣布不再更新。
  3. Elixir
    Elixir是一门动态的函数式编程语言,它由José Valim[7]于2012年开发。Elixir同样采用了类Ruby的语法,通过支持强大的Macro功能,它在简洁的语言核心上,建立了一系列的标准库,包括Unicode字符串及相关操作,重写了单元测试框架,丰富的数据类型等,它吸收了Clojure的Protocol,严格和惰性API,还提供了现代的交互命令行,脚本相关的库函数及项目管理工具。通过将Elixir代码编译为Erlang AST,Elixir得以重用Erlang VM的高并发及高效率,克服了Ruby在并发方面的缺陷。由于得到Jose及其它Ruby界牛人的喜爱及宣传[8],Elixir在近两年开始流行起来。

由于本文主要是讲Joxa,上述这几种编程语言只是简单带过,就不详细展开了。

上面几种编程语言的设计方案虽然有很多不同之处,但从整体思路上几乎是相同的,那就是:通过将代码编译成为Erlang VM上的代码,良好兼容Erlang VM,于是保留了上述3要素中的后两点,同时从头设计语言的语法,并在标准库,工具链等一些方面做补充完善。Joxa的设计也是类似,它选择了Lisp做为Erlang VM上的新语言,不过它走了一条和LFE不同的道路。Eric Merritt后来专门写了一个博客文章《Differences Between Joxa and LFE》来谈Joxa和LFE的不同之处,他说:

最主要和重要的区别在于这两门语言的目标。我认为Robert实现LFE的主要目标在于提供一个可变的语法可扩展的Erlang版本,如此一来人们就可以在需要时改变语言。同时我坚信Robert喜欢实现编程语言,他应该很享受实现LFE的过程。我当然也乐于实现Joxa,然而,当坐下来实现Joxa的时候我怀有一些非常特定的目标:

  1. 我需要一个用于开发DSL(Domain Specific Language,领域特定语言)的平台
  2. 我想要一个更具交互性和动态的开发环境。类似于Slime和Swank那种[9]
  3. 我希望充分利用所有已经存在的相当优秀的Lisp工具

上述每点都可以在Erlang里面解决。例如,我可以用Leex和Yecc[10]实现DSL,但我实现DSL的最好体验总是来自Lisp:使用Lisp函数和Macro来打造这些DSL。不过我使用Erlang有很长时间了,我不愿意放弃Erlang VM上面的优良功能来换成Lisp的种种优点。唯一的解决方法似乎只有使用一门基于Erlang VM之上的Lisp语言。

显而易见的首先选择是LFE,于是我花了几周时间深入研究这门语言和它的内部实现。最后我得到这个结论:它并没有满足我的需求。剩下的唯一退路就是我自己重新创造一门语言(同时也有一点怀疑自己不太明智)。

从整体来看,LFE更像一门披着Lisp外衣的Erlang,相当于给原来Erlang语法添加了括号和Macro,这与Eric Merritt理想中的Erlang VM上的Lisp语言相去甚远,于是他创造了Joxa,而Joxa的语法及风格受到Clojure的影响更大。为什么Clojure能受到Eric的如此青睐呢?它到底有什么出众之处呢?下面我们来了解一下。

1.2 Clojure,JVM上的函数式Lisp编程语言

Clojure是一门动态的强类型编程语言,作者是Rich Hickey。它寄居在JVM之上,设计成能够与JVM/Java良好互操作,既利用了JVM所提供的成熟高效的运行环境,也兼容众多流行的Java库与框架,同时它采用了Lisp语法和Macro,非常便于表达DSL,加上一套函数式的持久数据结构,并提供并发机制及惰性语义,使得简洁优雅语言成为函数式编程,并发编程的良好载体,同时重用了成熟流行的JVM平台,使得它便于在现有Java程序员中推广并流行,在这一点上区别于以往所有独立开发的函数式语言。此外它也吸收了Java中的面向对象思想和CLOS[11],发展出Protocol及多重方法。另外,Clojure自带一系列丰富的标准库,定义了一套项目管理规范,并提供了优秀的项目工具及REPL,使得它在开发环境,交互式开发方面成为佼佼者。

Clojure设计成为Java的一个库包,Clojure代码会编译成JVM byte code,正因为它以一种非侵入性的方式运行在JVM之上,所以在函数式的语言层面,会有一些其它函数式语言不可能出现的“瑕疵”,例如函数没有尾递归优化。兼容JVM平台的已有代码,在重用/连接已有项目方面既是一种优势,但有时混合函数式与命令式代码也会产生实际冲突。在并发方面,语言提供的多种并发原语,delay, future, promise,agent,STM等虽然强大,但从语言整体来看比较复杂。Clojure的很多地方可以体会到作者有意保持简单与功能(复杂)的平衡,在设计上做了务实折衷的克制。与此相反,另外一个基于JVM的语言Scala在设计上就显得博爱放任,看到各个好的特性就收入到语言当中,宛如中国古代的皇帝举国征选妃嫔。

相比各种“主流”编程语言,Clojure至今仍是小众语言,虽然如此,它的推出仍然不可谓不成功,既培养了一个健康壮大的社区,也在市场上占有一定的流行度,产生了一批具有相当影响力的项目,如流式数据处理框架Storm等。Clojure成功地向人们展示了这几个可能性:

  1. 在JVM平台实现一个函数式,并发的动态编程语言
  2. 通过融合持久数据结构,Protocol等优异特性,复兴Lisp
  3. 如何语言设计上在功能、简单与务实之间取得折衷平衡并树立起自身的特色

正因为有些如此之多的优点,Clojure才对程序员们有着如此之大的吸引力。也难怪身为老Lisp爱好者的Eric Merritt在创造Joxa时会受到Clojure的较大的影响。下面我们来谈谈Joxa的设计。

1.3 Joxa, Erlang VM上的新Lisp编程语言

对照上述多种语言的实现,Joxa的设计主要有如下几个要点:

  1. 上层语言为Lisp,主要目标为用于写DSL(或者作为其它上层Lisp的元语言),语言的核心部分要简洁
  2. 底层将Joxa代码编译成Erlang VM代码,将Joxa代码映射到Erlang上的对应语法结构,比如Joxa里面的函数即为Erlang函数
  3. 语言核心之外提供REPL,方便编译/执行脚本的命令行工具等

其中Lisp的语法可以参考简洁,优雅的Clojure,由于Erlang VM与JVM有着非常多的差异,正如Erlang语言与Java语言有着非常多的差异,所以可以预期的是,Joxa在语法上面不能完全保持与Clojure一致,同时这里面有一个目标用户的问题:Joxa更多的是为了Clojure程序员转向Erlang平台而设计,还是为了Erlang程序员转向Lisp而设计。若为前者,就尽量保留可能多的Clojure语法及规范,若为后者则将语法尽可能向Erlang靠拢比较理想。这时Joxa选择了后一种,即认为Joxa主要是解决Erlang现有的问题,所以从语法上来考虑,最后出来的结果很可能是一种Lisp与Erlang的独一无二的新结合。所有的Lisp语言从结构上来看,都具有一种类似数学的体系结构,包括以下几个部分:

  1. 一切表达式皆为List,List有两种,原子及函数调用。代码即数据(总结为同像性)
  2. 7个基本原语(又称之为特殊Form)加上可以操纵语言本身的Macro,两者作为核心,在此之上演化出整个语言

这就像数学体系,最核心的部分是几条基本原理,然后通过逻辑推导,演化出其它数学分支以构成整个体系,可以不断向外扩展。Joxa将会有同样的结构,核心部分将保持尽可能的简洁,只包括基本原语及Macro,极简的核心既节省开发成本,也给外延留下尽可能大的空间。此处的外延包括针对特定问题领域而言的DSL,也包括其它上层的Lisp语言,从本质上来说这两者本来就没有区别,只不过因为针对的范围有大有小所以说法不同。从语法设计上,Joxa会跟LFE有如下的不同:

  1. Joxa会是Lisp-1,而LFE是Lisp-2
  2. Joxa的语法会向Lisp靠拢,而LFE更像Erlang
  3. Joxa中Macro求值语义与Lisp更为一致,而LFE的Macro求值语义与函数求值语言不同

为了保持与Erlang VM现有的平台等保持无缝兼容,以充分利用现有的Erlang VM的开发规范与代码库等,第2点是必需的。将Joxa建立在Erlang VM平台的生态环境之上,固然是因为作者对Erlang VM的熟悉与喜欢,客观上也可以充分发挥Erlang生态的优势。从上面的叙述也可以看到,众多Erlang VM上的非Erlang编程语言也采用了这种“无缝兼容”设计,虽然它们在实现层面会有一些不同之处。这一点同时确定了Joxa将会保留Erlang的一些语言特性,例如按文件划分的模块化,函数式风格,代码要求先通过编译等。

第3点与开发环境相关,REPL是各种Lisp方言已经是司空见惯了,Erlang在设计的时候也吸收了这个概念,但是实现得不如Lisp的REPL那么好用,比如强制输入为表达式(每行的后面必须输入”.”号),Record不能用等。Joxa的REPL会参考Clojure与Erlang的REPL,结合前者的完整性和后者的功能,在易用性给予特别的关注。同时针对编译、脚本化等开发流程中的各个阶段都提供编辑器、命令行工具等支持。

2. 设计与实现细节

下面我们来详细讨论Joxa的设计与实现。根据上述的设计要点,要将Joxa代码要编译成Erlang VM代码,必需先熟悉Erlang代码的编译过程,在此过程中找出合适的切入点。

2.1 Erlang编译过程

一个经典的编译过程可以分为如下图所示的多个阶段:

传统编译过程的各阶段
图1 经典编译过程的各阶段[12]

经典的编译过程可以分为词法分析,语法分析,语义分析,中间代码生成,中间代码优化,机器码生成等多个阶段。Erlang的代码编译过程跟经典的编译过程基本一致,也可以分成类似的多个阶段,各个阶段的输入输出如下图所示:

Erlang编译过程的各阶段
图2 Erlang编译过程各阶段的输入输出

其中Core Erlang为于Erlang代码与VM内部中间代码之间的一层,它是在1999年前后提出的一种BEAM(Erlang VM的最新实现)上的语言,它被设计为:

  1. 语法清晰简单,严格的更高阶函数式语言
  2. 尽可能规范化,以便相关代码遍历工具的开发
  3. 从Erlang代码向Core Erlang代码的翻译应该直白,从Core Erlang向VM内部实现中间代码的翻译也应该简单
  4. 有良好定义的文本表示形式,语法简单无歧义,便于人阅读,调试及测试

由于Core Erlang是清晰简单,有良好定义的文本语言,便于作为目标语言,而且Erlang的代码优化和错误检测大多都在Core Erlang层进行,如果我们要在Erlang VM打造新编程语言,那么将新语言的代码编译成Core Erlang(或AST),将会是一个很好的解决方案。很多Erlang VM上的语言都选择了这种方案,比如LFE,但也有语言选择了编译成Erlang AST,比如Elixir,精通Elixir Macro的人对Erlang AST应该比较熟悉。相对于Core Erlang,Erlang AST更接近于Erlang本身,层次也更高。Core Erlang相关的功能定义在cerl.erl这个模块里面,包括对如模块、函数等各种Erlang语言结构的初始化、操纵等功能的一系列函数。

2.2 一个简单例子

下面举一个简单的Hello World程序作为例子[13],让读者对Erlang AST与Core Erlang有一个感性认识。原始的Erlang代码如下:

1
2
3
4
-module(test).
-export([hello_world/0]).
hello_world() ->
    io:format("Hello World").

对应的Core Erlang代码如下所示:

1
2
3
4
5
6
module 'test' ['hello_world'/0]
    attributes []
'hello_world'/0 =
    fun () ->
        call 'io':'format'
            (Hello World)

对比两份代码,可以看到Core Erlang与Erlang之间的映射还是很直观的。将原始的Erlang代码编译为Erlang AST,可以得到:

1
2
3
4
5
6
7
[{attribute,1,module,test},
 {attribute,2,export,[{hello_world,0}]},
 {function,2,hello_world,0,
   [{clause,2,[],[],
     [{call,3,
       {remote,3,{atom,3,io},{atom,3,format}},
         [{string,3,"Hello World"}]}]}]}]

编译为Core Erlang AST即得到:

1
2
3
4
5
6
7
8
9
10
11
12
{c_module,[],
  {c_literal,[],test},
    [{c_var,[],{hello_world,0}}],
      [],
     [{ {c_var,[],{hello_world,0}},
       {c_fun,[2,{file,[]}],
         [],
         {c_call,[3,{file,[]}],
           {c_literal,[3,{file,[]}],io},
           {c_literal,[3,{file,[]}],format},
           [{c_literal,[3,{file,[]}],
              "Hello World"}]}}}]}

对比两者,容易看出Erlang AST更高层更抽象,Core Erlang AST更底层更规范。

2.3 编译器

下面我们继续来讨论Joxa的编译过程,由于Core Erlang(及AST)可以由Erlang编译器编译成最终的机器码,我们只需将Joxa代码编译成Core Erlang AST便可实现将Joxa编译成机器码整个编译过程,从编译领域的分类来看,目标生成的代码是Core Erlang AST,操纵Core Erlang AST可以直接调用cerl.erl的接口函数,因此编译器后端这一块相对是比较简单的,重点在于前端部分:即将Joxa代码编译成Core Erlang AST。由于Joxa是Lisp语法,Lisp代码以括号划分边界的代码树的方式来表示,本身就已经有良好的结构,所以前端部分也比较简单。区别于LFE或Elixir用Leex或Yecc来生成LALR[14]式Lexer与Parser,Joxa采用了手写PEG[15] Lexer和Parser的方式。PEG编译器的代码量较小,Joxa编译器是在Erlang PEG生成器Neotoma生成代码的基础上写成的。(本节涉及到很多编译领域的术语或技术,由于本文主要是介绍Joxa,篇幅所限故不会详细解释这些术语或技术,有兴趣的读者可以自行寻找相关的资料做进一步了解)

特别值得一提的是,Joxa的编译过程是自举的,即Joxa编译器本身是由Joxa代码编写的,这与LFE或Elixir的编译器用Erlang编写不同。Joxa的自举要求先有一份以Core Erlang AST格式存在的具有正常编译功能的代码,这部分代码在Joxa的Github代码库中,相对根目录的路径是src/ast(后面给出所有的代码路径都相对于根目录)。通过用Erlang编译器将这份AST代码编译成BEAM代码,然后就得到一个能直接在BEAM上执行的Joxa编译器,然后就可以运行此编译器,将编译器的Joxa源代码编译成Core Erlang AST格式。整个流程和依赖如下图所示:

Joxa的自举及编译流程
图3 Joxa的自举及编译流程

由上图可以看到整个流程三个步骤是一个循环,要成功实现自举,必然要先实现其中的一个部分,在此基础上才能实现其中其它两个部分。在Joxa的编译器实现中,AST这部分先由作者Eric人手先写出基本的语法解析功能,然后再编写对应功能的编译器的Joxa代码,用AST编译出来可执行的编译器,去验证对应的Joxa代码,然后再按此流程不断添加更多的功能,错误一般出现在编译Joxa代码的时候,此时遇到的错误是由新添加的AST代码还是Joxa代码引起的,有时并不容易定位出来。虽然Core Erlang简单清晰,但手写Core Erlang AST是相当繁琐的,而且由于Joxa语法本身还在不断演变,从头开发一个这样的自举编译器,其难度可以猜想是比较大的。我曾经为Joxa添加过Map语法的支持,对此开发流程的复杂性有较深的体会。编程语言的自举也可以按另外一个思路来做:先用另外一门常见的语言,比如C语言来写编译器,然后当语言的语法发展到比较稳定成熟的时候,再使用这门语言的本身来实现自身的编译器,由于已经有了一个能够工作经过充分检验的C编译器,所以自举的实现就有了一个可靠的保障,大大降低其难度。

编译器这部分的Joxa代码的路径是src/joxa-cmp-*.jxa(其中*符号表示通配)。按照编译器前端和后端的分类法,下面我们讨论一下各主要文件的代码分布。PEG的词法分析部分需要构造一系列对应于词素(lexeme)的正则表达式,首先需要有正则表达式的元操作的函数定义,所谓“元操作”,用各种编程语言里面的正则表达式的术语来说,即是元字符,比如”*“符号用于“匹配0个或多个”。在PEG里面元操作是通过函数来表达的,这部分的代码在src/joxa-cmp-peg.jxa。词素,比如注释或数字,它们的定义放在src/joxa-cmp-lexer.jxasrc/joxa-cmp-parser.jxa则包含Parser的代码。编译器的主要逻辑放在src/joxa-compiler.jxa,它调用Parser来解析读入的字符流,成功解析之后调用make-forms函数递归遍历解析得到的语法树来生成Core Erlang AST,在编译过程中会执行对函数调用的合法性检查,Macro的递归展开等动作。后端的代码按语义的分类分成下述多个文件:

1
2
3
4
5
6
7
8
9
├── joxa-cmp-binary.jxa           # Binary
├── joxa-cmp-call.jxa             # 函数调用
├── joxa-cmp-case.jxa             # case语句
├── joxa-cmp-defs.jxa             # 函数、宏定义
├── joxa-cmp-expr.jxa             # 表达式
├── joxa-cmp-joxa-info.jxa        # 模块info
├── joxa-cmp-literal.jxa          # 常量,常量表达式
├── joxa-cmp-ns.jxa               # namespace
└── joxa-cmp-spec.jxa             # spec

以上即为Joxa编译器实现各部分代码的所在文件。整个编译器实现从代码量上来说并不大。

2.4 数据类型

与Elixir在Erlang数据类型的基础上添加了Range、正则表达式、Unicode字符串等新数据类型不同,Joxa支持的数据类型与Erlang保持一致,并没有添加新的数据类型,所有的数据类型包括如下几种[16]

  1. 简单类型:不定长整数,浮点数,原子
  2. 系统类型:PID, Port, Reference
  3. 集合类型: Tuple, Record,Map, List, Binary

各种数据类型的字面量语法请参考Joxa的在线文档。值得一提的是,围绕Record的各种操作,Joxa在语法上做了包装,便于解耦Record的内部实现与接口,提高了可用性,Elixir在这个方面走得更远,引入了Clojure的Protocol。另外一个常用的集合类型set是通过Erlang库提供的,并没有赋予特别的语法。

2.5 特殊Form及标准库基础原语

Joxa里面的特殊Form及标准库中的基础原语包括以下几个:

  • let*, let
    用于绑定变量,不同于Erlang中的绑定操作或Clojure的let操作,let*并不支持Pattern Matching或解构,Pattern Matching或解构需要通过case,标准库中的let是一个用let*case实现的对应支持Pattern Matching的版本
  • case
    整个Joxa语言中为数很少的一个支持Pattern Matching的原语之一,与Erlang里面在函数签名,变量匹配,case语句等各种语法结构都可以做Pattern Matching不同
  • receive
    接收消息,但没有对应的send原语,这可以通过调用Erlang模块或OTP库接口实现,支持Pattern Matching
  • do
    分组表达式成一块,类似于Lisp里面的progn
  • apply
    以列表函数调用指定函数,类似于Lisp的apply
  • fn
    构造匿名函数,类似于Erlang的fun,或Lisp的lambda
  • defn, defn+
    定义模块内可见,模块外可见函数
  • defspec
    用于定义前置声明
  • defmacro, defmacro+, quote, quasiquote, ~, ~@, gensym, macroexpand-1
    Macro操作,下一节再展开讨论
  • use, require, as
    namespace相关操作,源自于Clojure里面的对应物,要注意的是不同于Clojure默认会在所有namespace自动导入clojure.core,Joxa并不会自动导入joxa-core
  • try*, try
    两者catch用于异常捕取,用法跟Erlang里面的对应物类似,两者的区别在于是否支持Pattern Matching,类似于let*let
  • 特殊常量,都以函数方式进行调用

      ($filename)       ;; 当前文件的文件名(连后缀)
      ($namespace)      ;; 当前的namespace
      ($line-number)    ;; 当前的行号
      ($function-name)  ;; 当前的函数名
    
  • 其它如attrwhen等原语就不一一列举了。

2.6 Macro

作为Lisp类语言的杀手级特性,以及表达DSL的终极利器,一直以来Macro在Lisp类语言中都有着重要的地位。Joxa中的Macro原语与Common Lisp或Clojure等之前的Lisp语言保持了一致,详细列出如下:

1
2
3
4
5
6
7
defmacro     -- 定义模块内部Macro
defmacro+    -- 定义对模块外部可见Macro
quote        -- 抑制求值
quasiquote   -- 对应Common Lisp里面的back quote,或Clojure里面的syntax quote,部分求值
~            -- unquote,对符号后面元素进行求值
~@           -- unquote-splicing,对符号后面的List元素进行求值并展开到当前位置
gensym       -- 动态生成新变量,用于保证Macro健康(或称Macro卫生)

另外为方便调试,标准库中提供了macroexpand-1函数,用于单次展开Macro,这个函数也沿袭于传统的Lisp语言,但是并没有提供macroexpand(macroexpand-all)。

在Joxa里面使用Macro,跟之前的Lisp语言并没有什么不同,以一个标准库joxa-core模块里的代码为例:

1
2
3
4
5
6
7
8
9
10
11
12
(defmacro+ let (args &rest body)
  (let* (process-arg-body
        (fn (arg)
            (case arg
              ([r e]
               `(case ~e
                  (~r ~@body)))
              ((r . (e . rest))
               `(case ~e
                  (~r ~(process-arg-body rest))))
              (detail (erlang/error {:malformed-let-expression detail})))))
    (process-arg-body args)))

Joxa在语法上直接定义为Lisp风格,因此在Macro的定义及使用上面,与传统一脉相承并无修改。在这个Macro定义里面,除了Pattern Matching,以及递归调用process-arg-body之外,与传统Lisp语言并无不同,熟悉传统Lisp的人可以很快就读懂。对比的来看,在Elixir这样的非Lisp语言中引入Macro,由于上层语言的语法与AST并不一致,所以程序员必需记住/区分上层语言与AST两种环境,因此相对较为复杂,比如,在Elixir Macro的签名处Pattern Matching Erlang AST,就在以Elixir的语法编写的Macro定义中,暴露了底层的AST格式。这种复杂性虽然从设计上来说是必需的折衷,但在习惯了Lisp Macro的人看来可能不会太喜欢。Joxa作者Eric在2015年一次接受《This is not a Monad tutorial》的采访中就表示过不喜欢Elixir Macro的复杂性。

2.7 标准库概览

Joxa的标准库只包括少数几个基本函数以及对OTP的简单包装。详细列出如下:

  • joxa-core
    基本操作: !=, lte, gte, and, or, +, -, incr, decr, if, when, unless, try, let, define
  • joxa-eunit
    eunit相关函数封装
  • joxa-lists
    list相关的功能函数: dolist, hd, tl, foldl, map, lists-binding, #, all, any
  • joxa-records
    Record相关函数
  • joxa-shell
    REPL函数的简单实现
  • joxa-otp, joxa-otp-gen-server, joxa-otp-supervisor, joxa-otp-application
    Erlang OTP相关接口的封装函数

代码规模很小,跟Elixir的标准库相比差得很远。其功能比较简陋,称之为标准库也许太大,或者称之为帮助函数更加准确。由于Joxa可以直接调用Erlang代码,因此功能缺失之处可由其它Erlang库补充。

2.8 开发环境及工具链

目前Joxa只有一个名为joxa的命令行工具,用于编译Joxa源代码,启动REPL,这个工具的功能也比较简陋,跟Clojure的REPL还有很大的距离。源代码中有一个Emacs的Major Mode配置文件emacs/joxa-mode.el,可以在用Emacs开发Joxa时设置缩进,关键字高亮,键绑定等。上面提到的与Slime和Swank集成,则尚未开发。

2.9 项目状态

Joxa从2011年底开始开发,一直到2013年初都比较活跃,这之后代码提交量变得相当少,在当前这个时间点(2015年8月)回头看看提交日志,已经有一年多的时间没有任何更新。虽然还未完成原来的设计目标,wiki上面的计划也有很多开发要做,但是由于作者Eric工作上比较忙,而Joxa社区实在太弱小,除作者之外并没有其它的人员贡献过大量代码,因此短期之内似乎项目状态不会重新变得活跃。在Google Group上有Joxa的邮件组,在近一年多时间内也相当少人发言。在应用上,除了作者Eric将Joxa用于编写他的创业项目之外,目前市面上没有看到其它的应用[17]。综合来看,Joxa的项目状态是比较停滞的。

3. 总结

Joxa是一种基于Erlang VM的现代Lisp语言,有着简洁清晰的Lisp语法,支持强大的Macro,是在Erlang VM编写DSL的一个很好的载体,它无缝兼容Erlang VM平台,是一门功能全面的通用编程语言。它在语言设计及编译器实现方面质量优良,但目前完成度不高,工具链并不完整,市面上也少见应用。作为一门较新的基于Erlang VM的编程语言,它有待进一步的发展完善。

注:
[1] Eric Merritt是《Erlang and OTP in Action》(中文译本《Erlang/OTP并发编程实战》)一书的作者之一,Erlware项目联合创始人,Afiniate公司的CTO。
[2] 翻译自邮件原文
It doesn’t actually mean anything. Many years ago it was an acronym for some project I wanted to start ‘Java oriented something or other’. I never made that project but I bought the domain and have kept it these years. Four letter domains are pretty uncommon these days, so I just decided to use it as the name for the language. Thats all.
[3] 作为Erlang语言联合创始人以及Joe Armstrong的长期亲密战友,Robert Virding自从当年在爱立信计算机科学实验室开始,长期以来在Erlang的设计,标准库,编译器,发展推广等方方面面都做了杰出的贡献。
[4] Lisp-1和Lisp-2的区别在于函数与变量是否共用同一命名空间,一个详细的解释可以参考文章《What’s Lisp-1, What’s Lisp-2? Bad Jargon or Good Jargon?》
[5] REPL是Read-Eval-Print Loop的缩写,最早被用于指代开发Lisp程序过程中,交互式命令行不断执行读取程序员的输入代码,对其进行求值并打印出求值结果的循环动作。后来这个概念被Python,Ruby及各种交互式命令行工具吸收并推广开来。
[6] Tony Arcieri是一位美国的软件工程师,他的博客见这里
[7] José Valim是一位波兰的软件工程师,他最被人熟知的两个身份是Ruby On Rails的核心成员以及Elixir编程语言的创始人。
[8] 比如Joe Armstrong于2013年中写了博客文章《A Week with Elixir》盛赞了Elixir“结合了Ruby和Erlang的优良特性”,Dave Thomas于2014年发布了新书《Programming Elixir》向有其它语言经验的程序员提供了一本系统的教程。
[9] 译者注:Slime是Superior Lisp Interaction Mode for Emacs的缩写,它为Emacs提供了一整套交互式开发Common Lisp的功能集,包括编译,调试,文档查找等等,Slime是客户端,Swank是对应的服务器端,它们共同组成了一个强大的程序开发环境。
[10] 译者注:LeexYecc是Erlang语言的Lex和Yacc工具集。
[11] CLOS是the Common Lisp Object System的缩写,是指在Common Lisp中实现面向对象机制的一系列代码库。
[12] 此图来自编译领域的经典著作《Compilers: Principles, Techniques, & Tools》第三版,中译本《编译原理》。
[13] 这个例子来自Eric Merritt 2012年8月在Chicago Erlang User Group上的技术分享《Joxa: A Full Featured Lisp on the Erlang VM》,录像视频见这里.
[14] LALR是LookAhead LR的缩写,LR中的L表示对输入进行从左到右的扫描,R表示反向构造出一个最右的推导序列。LALR是流行的自底向上语法分析方法。
[15] PEG是Packrat Expression Parsing的缩写,它是一种相对较新的自顶向下语法分析方法。
[16] 其中Map的语法支持由我添加,写此文时未进入主干分支。
[17] 从推广应用的角度来看,在2011年中开始开发的Elixir在各个基于Erlang VM的新编程语言上是走得最前的。