Kapok 的设计与实现: Protocol

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

Protocol 是什么

为了更好地进行程序的编写,编程语言往往需要引入一些抽象,比如一个函数是一系列操作的封装,一个模块是一堆函数的封装,然后出于通用性的需要,又定义了函数签名来区分具有相同参数类型和参数个数的函数,对于具有相同函数签名的模块,在 Erlang 我们定义了行为(Behavior)。类似地,Protocol 也是一种对数据类型和基于数据类型上实现的一些函数的抽象。在面向对象编程语言(OOP)非常流行的今天,这种抽象更多地被称为类与接口。

下面简单举例来说明 Protocol 是什么。在 Erlang 里面,如果我们要编写一段代码来处理不同的数据类型,往往需要在一大块集中代码里面针对每一种数据类型进行不同的处理。假设我们正在编写一个 Json 模块,这个模块要处理 list, binary, number 三种类型的 encode(编码)操作,那么就有代码:

1
2
3
4
5
6
7
8
-module(json)

encode(Item) when is_list(Item) ->
  % ...
encode(Item) when is_binary(Item) ->
  % ...
encode(Item) when is_number(Item) ->
  % ...

如果要添加更多的数据类型,那么就在模块内部添加对应那个数据类型的分支。但是如果你没有这个模块的源代码就无法添加,而且经过长时间添加多个类型支持后这个模块变得非常大,难于维护。Elixir 引入了 Protocol,针对上述的 encode 操作,可以定义成一个 Protocol,代码如下:

1
2
3
defprotocol JSON do
  def encode(item)
end

对于任何实现了JSON Protocol 的数据类型对象data,都可以直接调用下述函数:

1
JSON.encode(data)

这些数据类型的JSON Protocol 实现可以分散放在各个文件中,没有要集中维护的问题,当你需要添加一个新的数据类型的支持时,也不需要已有模块的源代码。

1
2
3
4
5
6
7
8
9
10
11
defimpl JSON, for: List do
  def encode(item) # ...
end

defimpl JSON, for: BitString do
  def encode(item) # ...
end

defimpl JSON, for: Number do
  def encode(item) # ...
end

通过 Protocol 这样一个抽象,我们可以在函数式的编程语言中,定义对数据类型绑定一系列的接口,然后针对这些通用的接口来进行编程。针对接口编程一个常常被提到的用法是,在需要快速编写原型的时候,使用简单的数据类型进行接口编程,先快速实现功能,等到程序稳定下来,后期需要进行性能优化的时候,再将接口下面的数据类型更换成更高效的实现,这个过程中所有的接口使用代码都不需要修改。

Elixir 中 Protocol 的实现

Protocol,或者说类接口,它的广义的概念可以追溯到 20 世纪 80 年代开始流行的面向对象编程语言,比如 C++,甚至更早之前 60~70 年代就已经存在的 Lisp,从那个年代流传至今的很多 Lisp 方言中,都或多或少有着这种抽象,比如 Common Lisp 中的 Sequence 的概念。而在 Erlang VM 上实现了 Protocol 的 Elixir 语言,它则是参考了 Clojure 的 Protocol 定义和实现。下面简单描述一下 Elixir 的 Protocol 实现。

从上面的例子我们可以看到,Protocol 的本质是将数据类型和接口分开定义,并在运行时进行动态绑定。上述例子中,对于 List 类型,定义了对应的 encode 实现,调用 Protocol 的接口JSON.encode(data)时,如果 data 是 List 类型,就进行动态分发,执行对应的 encode 实现。那么如何实现这种动态绑定或者说分发呢?由于 Erlang 是一个函数式编程语言,Erlang VM 的基本语义中也只支持模块和函数,因为 Protocol 的每个实现可以分开,而 Erlang VM 中基础的编译单元是模块,一个简单的映射方法就是将每个 Protocol 实现映射为一个模块。而对于接口模块JSON,很自然地也成为一个单独的模块。那么就只剩下一个问题了,即如何实现当调用JSON.encode()时,将执行路径转到defimpl JSON, for: List模块的encode()函数,这里可以实现为在运行时拼接模块名,然后调用具体模块的函数。上述的 Elixir 代码中的例子,将编译成对应的 Erlang 代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
      Elixir                                  Erlang
defprotocol JSON do                     -module(JSON).
  def encode(item)         生成          encode(item) ->
end                                        case item of
                                         data when is_list(data) ->
                                           'JSON.List':encode(data);
                                         data when is_binary(data) ->
                                           'JSON.BitString':encode(data);
                                         data when is_number(data) ->
                                           'JSON.Number':encode(data)
                                         data when is_struct_X(data) ->
                                           'JSON.X': encode(data)
                                       ...

这里的 struct_X 表示除了几个基本数据类型以外的用户自定义 struct 类型,其中 X 为 struct 的名字,即对应 Elixir 中的代码

1
2
3
defmodule X do
  defstruct # ...
end

对于各个数据的类型的实现,可以映射为各个 Erlang 模块:

1
2
3
4
5
6
7
8
9
10
11
12
      Elixir                                         Erlang
defimpl JSON, for: List do            生成      -module('JSON.List').
  def encode(item) # ...                        encode(item) ->
end                                               %% ...

defimpl JSON, for: BitString do                 -module('JSON.BitString').
  def encode(item) # ...                        encode(item) ->
end                                               %% ...

defimpl JSON, for: Number do                    -module('JSON.Number').
  def encode(item) # ...                        encode(item) ->
end                                               %% ...

注意其中的模块名是由 Protocol 名字,即这个例子中的 JSON,和具体的数据类型名,即这个例子中的 List, BitString, Number 等,两者拼接而成。

Kapok 中 Protocol 的实现

既然 Elixir 已经实现了 Protocol,而且 Kapok 和 Elixir 都兼容于 Erlang VM,那么除了另外捣腾一套 Protocol 的用法和实现之外,比较好的做法就是兼容 Elixir 的实现,从而达到重用所有 Elixir 己经有的库和代码的效果。Elixir 中定义了每个 Protocol 模块都必需具备的接口函数,具体列出如下,它们都是通过 defprocotol 宏来实现的:

  • __protocol__/1 当参数是:name,返回 Protocol 名字 当参数是:functions,返回一个元素为 Protocol 接口函数和参数个数的关键字列表 当参数是:impls,返回一个实现的列表

  • impl_for/1 接收一个 struct,返回为此 struct 实现当前 Protocol 的模块名,如果不存在这样的实现模块则返回:nil

  • impl_for!/1 类似于上面的impl_for/1,区别在于当实现模块不存在时不返回:nil而是抛出异常

在 Kapok 中,也定义类似的 Macrodefprotocol来生成这些接口函数。类似地,对于 Elixir 中的defstruct, defimpl Macro,Kapok 也定义了对应的 Macro 来生成对应的 struct 结构,和实现函数接口。

以上所述的种种 Protocol 结构都是通过 Macro,这个强大的 Lisp 编程方式,来实现的。通过 Macro 处理手写代码,生成新代码,我们可以在 Kapok 实现一套类似于 Elixir Protocol 原语,无缝对接到已有的 Elixir 代码和库中。

Kapok 的 Protocol 使用示例

最后附上一个 Kapok 代码示例,展示一下 Protocol 在 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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
;; 定义一个用于此示例的 Protocol
(defprotocol pr
  "A protocol to print something."
  ;; 此 Protocol 唯一接口用来打印某个数据
  (print [self]))

;; 为 Atom 数据类型实现 pr Protocol
(defimpl pr Atom
  (require io)

  (defn print [atom]
    (io.format "print an atom: #'~p'~n" [atom])))

;; 为 List 数据类型实现 pr Protocol
(defimpl pr List
  ;; 在 print 的实现代码中,直接使用了 Elixir 的 Enum Protocol
  ;; 所以这里用了一行代码引入 Elixir.Enum 模块
  (require (Elixir.Enum :as enum)
           io)

  (defn print [list]
    (io.format "print a char list: #\"")
    ;; 直接在 List 上调用 enum.map,直接使用 Elixir 库代码
    (enum.map list
              (fn [x] (io.format "~c" [x])))
    (io.format "\"~n")))

(ns protocol-examples
  (require pr))

(defn main []
  ;; 下面先后声明了 Atom 和 List 两种数据类型的实例,并调用 pr.print 接口
  (let [data #abc]
    (pr.print data))
  (let [data #"abc"]
    (pr.print data)))
;; 得到输出
print an atom: #'abc'
print a char list: #"abc"

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 在函数参数的最后面引入 Keyword List。如果将 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 函数的输入输出。

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 的时候,我也不知道这个项目要做到何时,做到什么程度。然后事情冥冥中就这样发生了,而我将沿着这条路继续向前走。王家卫电影《一代宗师》里面,宫先生说“念念不忘,必有回响”,行知做人跟练武一样,秉着意念坚持下去,终究能有一点回响。