听说你想写个 Lisp 解释器 - read

大家好，我是微微笑的蜗牛，🐌。

这个系列的文章，我们将来动手实现一个小型的 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 的值后返回。

具体操作为：

1. 首先对 p1 求值，如果为 true，则计算 e1 的值返回；否则继续求值 p2。
2. 若 p2 的值不为 true，继续求值 p3，以此类推，直至到 pn。
3. 若没有满足条件的 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，读取-计算-打印循环。

其模型如下图所示：

REPL 模型

我们将按照这个模型进行实现，其中最重要的两步为：

• 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)])

如下图所示：

image

再看一个嵌套的例子，比如代码："(a (b c))"，转换为 AST 后，结构如下：

.List([.Atom(a), .List([.Atom(b), .Atom(c)])])

如下图所示：

image

那么看起来规则挺简单的，遇到 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)

image

举个例子，比方说："(a (b))"，tokenize 之后的结果为：

[.pOpen, .text(a), .pOpen, .text(b), .pClose]

其解析过程如下图所示。PS：为了表示方便，图中直接使用了字符串，而非 token。

image

这样我们就得到了 SExpr 的结构，图示如下：

image

到此，Read 的过程就结束啦，相关代码可查看 github 。

总结

这篇文章主要介绍了如何通过词法分析生成 token 列表、解析 token 生成 ast，最终得到 SExpr 的结构。

下一篇文章我们将介绍如何利用 SExpr 结构进行计算，也就是 evaluation 的过程，敬请期待~

参考资料

• https://www.uraimo.com/files/MicroManual-LISP.pdf
• https://www.uraimo.com/2017/02/05/building-a-lisp-from-scratch-with-swift/
• https://github.com/silan-liu/swift-lisp/blob/main/SwiftLisp/Read.swift