大家好，我是微微笑的蜗牛，🐌。
这个系列的文章，我们将来动手实现一个小型的 Lisp 解释器，使用 Swift 编写。至于写解释器的缘由呢，是因为前些天看到一篇国外的文章，里面比较详细的介绍了如何编写自己的 Lisp 解释器。以前也没有弄过这方面的东西，出于学习的目的，读完文章后，动手实践了一番。
说起来，只读文章和动手写的差别还是相当大的。在读文章时，你会发现大概思路我都懂了，但是细细一想，对有些小细节如何实现还是有点疑惑；而在实践过程中，必须得去弄清楚每个细节（不然就是照抄代码了🤩），从中会发现一些意外并令人惊喜的点，甚至突然有种热血沸腾的感觉。
比如 lambda 的实现，它是一个匿名函数，那如何实现在声明后就立即调用的呢？这个点其实有点困扰我，因为我在实现代码中并没有看到直接调用。后来仔细一调试，才发现其精妙之处。
下面，就让我们开始这段旅程吧~
LISP 简介
Lisp 是一种古老的语言，其全称为 List Processor，它是一种函数式编程语言，该语言的主要数据结构就是 list。现在由它也衍生出了很多变种，比如 Common Lisp、Scheme 等。
Lisp 中开创了一些先驱概念，比如 REPL，读取-求值-循环输出。我们的解释器就构建在该模型之上。
Lisp 的代码组成很简单，只包括 (、)、字符三种类型。它由原子 atom 或者列表 list 组成。
- 原子：包括符号和数值，比如
"hello"，2。 - 列表：用
()表示，内部可有 0~n 个表达式，也可以嵌套列表，比如"(a b c)"，"(a b (c d))"，表达式之间用空格隔开。
另外，函数调用也是列表形式：
// f 是函数名，a, b, c 分别是三个参数
(f a b c)
接下来，我们会根据 MicroManual-LISP 的定义来实现它。不过，也不是全部。先来看看 Lisp 中定义的操作符。
操作符
quote
- 定义：
// 返回 x
(quote x)
- 说明：取出数据 x。如果 x 是表达式，x 的值无需计算，原样返回。
atom
- 定义：
// 当 x 是 atom 或者是空 list 时返回 true；否则返回空表 ()
(atom x)
- 说明：判断表达式是否是原子。若是
atom或者是空列表()，则返回true；否则返回空列表（）。
equal
- 定义：
// 判断 x，y 是否相等
(equal x y)
- 说明：判断两个表达式是否相等。如果相等，则返回
true；若不等，则返回空列表()。 - 举例：
// true
(equal a a)
// ()
(equal a ())
car
- 定义：
// x 是一个列表，返回第一个元素
(car x)
- 说明：取出列表中的第一个元素，x 必须是
列表。 - 举例：
// 结果：x
(car (x y))
cdr
- 定义
// x 是一个列表，返回除第一个元素外，其余的元素组成的列表。也就是剔除掉第一个元素
(car x)
- 说明：返回列表中除第一个元素外，其余的元素组成的列表。注意参数必须是
列表。 - 举例：
// 结果：(y z)
(car (x y z))
cons
- 定义：
(cons e list)
- 说明：将元素
e和list组合起来返回新的列表。注意：第二个参数必须是列表。 - 举例：
// (x y z)
(cons (x) (y z))
cond
- 定义
// p、e 为表达式
(cond (p1 e1) ...(pn en))
- 说明：对参数中的 p 逐个求值，直至返回 true，此时计算 e 的值后返回。
具体操作为：
- 首先对 p1 求值，如果为 true，则计算 e1 的值返回；否则继续求值 p2。
- 若 p2 的值不为 true，继续求值 p3，以此类推，直至到 pn。
- 若没有满足条件的 p，则返回空列表 ()。
- 举例
// second
(cond ((equal a b) (quote first)) ((atom a) (quote second)))
计算步骤如下：
- 首先对
p0 = (equal a b)求值，两者不相等，返回()。 - 然后继续对
p1 = (atom a)求值，此时返回true。那么计算对应表达式e1 = (quote second)的值，结果是second，然后将其返回。
lambda
- 定义
// v1~vn 是参数，它的值会被 e1~en 替换，e 是函数体表达式
((lambda (v1 ... vn) e) e1 ... en)
- 说明：lambda 用于定义匿名函数，注意匿名函数是会立即执行的。
(v1 ... vn) 是参数，e 是函数体表达式，e1 ... en 的对应参数的值。
在计算 e 表达式时，参数会被替换为具体的值，也就是 v1 = e1，...，vn = en。
- 举例：
比如下面这个函数：参数为 x，函数体为 (car x)，传入参数值为 (c a b)。
// 结果 c
((lambda (x) (car x)) (c a b))
将参数值 (c a b) 带入 x，那么最终计算的表达式为：(car (c a b))，结果为 c。
defun
- 定义：
// v1~vn 是参数，e 是函数体表达式
(defun test(v1 ... vn) e)
- 说明：表示方法定义，跟
lambda很类似。只不过它有方法名，需主动调用。 - 举例：
定义 test 方法，带有一个参数 x：
(defun test (x) (car x))
调用 test 方法，传入 (a b)：
(test (a b))
REPL
全称是 Read - Evaluate - Print Loop，读取-计算-打印循环。
其模型如下图所示：
我们将按照这个模型进行实现，其中最重要的两步为：
-
Read：读取输入的代码，提取 Token，然后解析为抽象语法树 AST。 -
Evaluate：计算表达式，返回结果。
这篇文章，我们主要来介绍 Read 的实现。
Read 又分为两步：
-
词法分析：
Tokenize，也称之为「Token 化」。将代码解析为一个个的 Token，输出 「Token 列表」。由于 Lisp 中只有三种符号：
(、)、字符串（字母+数字），那么 Token 的取值也很简单，只包含这三种。 语法分析：Parse，将上一步得到的 「Token 列表」进行结构化，输出 AST。
数据结构定义
由于 Lisp 代码就是各种表达式，而它仅仅只有 atom 和 list 两种类型，且 list 内部可嵌套。那么它的数据结构相对简单：
// 表达式定义
public enum SExpr {
// 原子
case Atom(String)
// 列表，可嵌套
case List([SExpr])
}
Tokenize
识别输入代码，将其分割为一个个的有效 token。上面我们说过，token 只有三种类型，可用枚举来进行定义。
enum Token {
// 左括号
case pOpen
// 右括号
case pClose
// 字符串
case text(String)
}
而解析 token 的过程，只需逐个遍历每个字符进行处理。
遍历过程中，只会有如下几种情形：
-
'('，此时添加pOpen到 token 列表。但要注意
(前面还可能存在字符串，比如cons(B C)，此时需将字符串cons作为一个字符串token添加到列表。// "cons(B C)"，当遍历到 ( 时，cons 需作为一个 token if tmpText != "" { res.append(.text(tmpText)) tmpText = "" } res.append(.pOpen) -
')'，此时添加pClose到 token 列表。同样注意字符串处理，比如
(B)，当遇到)时，需添加字符串B到列表。// "(B)"，遍历到 )，B 作为一个 token if tmpText != "" { res.append(.text(tmpText)) tmpText = "" } res.append(.pClose) -
' '，空格是分隔 token 的标记，多个空格只会被看成一个。当遇到空格时，说明可能有 token 定义结束。这里主要用于处理字符串 token。
// "A B"，遍历到到 A 后面的空格，A 作为一个 token if tmpText != "" { res.append(.text(tmpText)) tmpText = "" } -
其他就是字符了，逐个累加字符。在上面三种情况中，将其添加到 token 列表。
tmpText.append(c)
经过这几种情况的处理，我们可以得到一个 token 列表。
举个例子："(a b c)"，得到的 token 列表为：
[.pOpen, .text(a), .text(b), .text(c), .pClose]
Parse
接下来是进行 token 列表的解析，将其结构化为 AST，其实也就是转换为上面定义的 SExpr 的结构。
最主要的就是列表左右括号配对处理，内嵌列表的递归处理。
举一个简单的例子，比如代码："(a b c)"，转换为 AST 后，应是如下结构：
.List([.Atom(a), .Atom(b), .Atom(c)])
如下图所示：
再看一个嵌套的例子，比如代码："(a (b c))"，转换为 AST 后，结构如下：
.List([.Atom(a), .List([.Atom(b), .Atom(c)])])
如下图所示：
那么看起来规则挺简单的，遇到 list，将其变为 .List；遇到 atom，将其变为 .Atom。正所谓是，逢山开山，遇水淌水。
总结一下转换规则：
- 对于列表
list，转换为.List(xx)； - 对于原子
atom，转换为.Atom(xx)。
那么如何实现呢？
在遍历 token 时，只有如下三种情形：
当遇到
.pOpen，也就是(时，说明是列表的开始，初始化一个空列表.List([])作为父节点，继续递归处理其后的token列表。-
当遇到
.pClose，也就是)时，说明是列表的结束，返回配对()组成的表达式。此时会回到
.pOpen后续逻辑的处理，因为是递归函数的返回。将表达式添加到「当前上下文的父节点」中，然后继续往后遍历剩余token。 当遇到
text时，转换成.Atom(text)，添加到当前父节点即可。
解析过程如下所示，其中 parser 表示解析函数。
// 入参：token 列表，父节点
// 返回参数：剩余 token 列表，子节点
parser(tokens, parentNode) -> (remainTokens, node)
举个例子，比方说："(a (b))"，tokenize 之后的结果为：
[.pOpen, .text(a), .pOpen, .text(b), .pClose]
其解析过程如下图所示。PS：为了表示方便，图中直接使用了字符串，而非 token。
这样我们就得到了 SExpr 的结构，图示如下：
到此，Read 的过程就结束啦，相关代码可查看 github 。
总结
这篇文章主要介绍了如何通过词法分析生成 token 列表、解析 token 生成 ast，最终得到 SExpr 的结构。
下一篇文章我们将介绍如何利用 SExpr 结构进行计算，也就是 evaluation 的过程，敬请期待~
