大家好，我是微微笑的蝸牛，??。
這個(gè)系列的文章，我們將來動(dòng)手實(shí)現(xiàn)一個(gè)小型的 Lisp 解釋器，使用 Swift 編寫。至于寫解釋器的緣由呢，是因?yàn)榍靶┨炜吹揭黄?a target="_blank">國外的文章，里面比較詳細(xì)的介紹了如何編寫自己的 Lisp 解釋器。以前也沒有弄過這方面的東西，出于學(xué)習(xí)的目的，讀完文章后，動(dòng)手實(shí)踐了一番。
說起來，只讀文章和動(dòng)手寫的差別還是相當(dāng)大的。在讀文章時(shí)，你會(huì)發(fā)現(xiàn)大概思路我都懂了，但是細(xì)細(xì)一想，對有些小細(xì)節(jié)如何實(shí)現(xiàn)還是有點(diǎn)疑惑；而在實(shí)踐過程中，必須得去弄清楚每個(gè)細(xì)節(jié)（不然就是照抄代碼了??），從中會(huì)發(fā)現(xiàn)一些意外并令人驚喜的點(diǎn)，甚至突然有種熱血沸騰的感覺。
比如 lambda 的實(shí)現(xiàn)，它是一個(gè)匿名函數(shù)，那如何實(shí)現(xiàn)在聲明后就立即調(diào)用的呢？這個(gè)點(diǎn)其實(shí)有點(diǎn)困擾我，因?yàn)槲以趯?shí)現(xiàn)代碼中并沒有看到直接調(diào)用。后來仔細(xì)一調(diào)試，才發(fā)現(xiàn)其精妙之處。
下面，就讓我們開始這段旅程吧~
LISP 簡介
Lisp 是一種古老的語言，其全稱為 List Processor，它是一種函數(shù)式編程語言，該語言的主要數(shù)據(jù)結(jié)構(gòu)就是 list?，F(xiàn)在由它也衍生出了很多變種，比如 Common Lisp、Scheme 等。
Lisp 中開創(chuàng)了一些先驅(qū)概念，比如 REPL，讀取-求值-循環(huán)輸出。我們的解釋器就構(gòu)建在該模型之上。
Lisp 的代碼組成很簡單，只包括 (、)、字符三種類型。它由原子 atom 或者列表 list 組成。
- 原子：包括符號和數(shù)值，比如
"hello"，2。 - 列表：用
()表示，內(nèi)部可有 0~n 個(gè)表達(dá)式，也可以嵌套列表，比如"(a b c)"，"(a b (c d))"，表達(dá)式之間用空格隔開。
另外，函數(shù)調(diào)用也是列表形式：
// f 是函數(shù)名，a, b, c 分別是三個(gè)參數(shù)
(f a b c)
接下來，我們會(huì)根據(jù) MicroManual-LISP 的定義來實(shí)現(xiàn)它。不過，也不是全部。先來看看 Lisp 中定義的操作符。
操作符
quote
- 定義：
// 返回 x
(quote x)
- 說明：取出數(shù)據(jù) x。如果 x 是表達(dá)式，x 的值無需計(jì)算，原樣返回。
atom
- 定義：
// 當(dāng) x 是 atom 或者是空 list 時(shí)返回 true；否則返回空表 ()
(atom x)
- 說明：判斷表達(dá)式是否是原子。若是
atom或者是空列表()，則返回true；否則返回空列表（）。
equal
- 定義：
// 判斷 x，y 是否相等
(equal x y)
- 說明：判斷兩個(gè)表達(dá)式是否相等。如果相等，則返回
true；若不等，則返回空列表()。 - 舉例：
// true
(equal a a)
// ()
(equal a ())
car
- 定義：
// x 是一個(gè)列表，返回第一個(gè)元素
(car x)
- 說明：取出列表中的第一個(gè)元素，x 必須是
列表。 - 舉例：
// 結(jié)果：x
(car (x y))
cdr
- 定義
// x 是一個(gè)列表，返回除第一個(gè)元素外，其余的元素組成的列表。也就是剔除掉第一個(gè)元素
(car x)
- 說明：返回列表中除第一個(gè)元素外，其余的元素組成的列表。注意參數(shù)必須是
列表。 - 舉例：
// 結(jié)果：(y z)
(car (x y z))
cons
- 定義：
(cons e list)
- 說明：將元素
e和list組合起來返回新的列表。注意：第二個(gè)參數(shù)必須是列表。 - 舉例：
// (x y z)
(cons (x) (y z))
cond
- 定義
// p、e 為表達(dá)式
(cond (p1 e1) ...(pn en))
- 說明：對參數(shù)中的 p 逐個(gè)求值，直至返回 true，此時(shí)計(jì)算 e 的值后返回。
具體操作為：
- 首先對 p1 求值，如果為 true，則計(jì)算 e1 的值返回；否則繼續(xù)求值 p2。
- 若 p2 的值不為 true，繼續(xù)求值 p3，以此類推，直至到 pn。
- 若沒有滿足條件的 p，則返回空列表 ()。
- 舉例
// second
(cond ((equal a b) (quote first)) ((atom a) (quote second)))
計(jì)算步驟如下：
- 首先對
p0 = (equal a b)求值，兩者不相等，返回()。 - 然后繼續(xù)對
p1 = (atom a)求值，此時(shí)返回true。那么計(jì)算對應(yīng)表達(dá)式e1 = (quote second)的值，結(jié)果是second，然后將其返回。
lambda
- 定義
// v1~vn 是參數(shù)，它的值會(huì)被 e1~en 替換，e 是函數(shù)體表達(dá)式
((lambda (v1 ... vn) e) e1 ... en)
- 說明：lambda 用于定義匿名函數(shù)，注意匿名函數(shù)是會(huì)立即執(zhí)行的。
(v1 ... vn) 是參數(shù)，e 是函數(shù)體表達(dá)式，e1 ... en 的對應(yīng)參數(shù)的值。
在計(jì)算 e 表達(dá)式時(shí)，參數(shù)會(huì)被替換為具體的值，也就是 v1 = e1，...，vn = en。
- 舉例：
比如下面這個(gè)函數(shù)：參數(shù)為 x，函數(shù)體為 (car x)，傳入?yún)?shù)值為 (c a b)。
// 結(jié)果 c
((lambda (x) (car x)) (c a b))
將參數(shù)值 (c a b) 帶入 x，那么最終計(jì)算的表達(dá)式為：(car (c a b))，結(jié)果為 c。
defun
- 定義：
// v1~vn 是參數(shù)，e 是函數(shù)體表達(dá)式
(defun test(v1 ... vn) e)
- 說明：表示方法定義，跟
lambda很類似。只不過它有方法名，需主動(dòng)調(diào)用。 - 舉例：
定義 test 方法，帶有一個(gè)參數(shù) x：
(defun test (x) (car x))
調(diào)用 test 方法，傳入 (a b)：
(test (a b))
REPL
全稱是 Read - Evaluate - Print Loop，讀取-計(jì)算-打印循環(huán)。
其模型如下圖所示：
我們將按照這個(gè)模型進(jìn)行實(shí)現(xiàn)，其中最重要的兩步為：
-
Read：讀取輸入的代碼，提取 Token，然后解析為抽象語法樹 AST。 -
Evaluate：計(jì)算表達(dá)式，返回結(jié)果。
這篇文章，我們主要來介紹 Read 的實(shí)現(xiàn)。
Read 又分為兩步：
-
詞法分析：
Tokenize，也稱之為「Token 化」。將代碼解析為一個(gè)個(gè)的 Token，輸出 「Token 列表」。由于 Lisp 中只有三種符號：
(、)、字符串（字母+數(shù)字），那么 Token 的取值也很簡單，只包含這三種。 語法分析：Parse，將上一步得到的 「Token 列表」進(jìn)行結(jié)構(gòu)化，輸出 AST。
數(shù)據(jù)結(jié)構(gòu)定義
由于 Lisp 代碼就是各種表達(dá)式，而它僅僅只有 atom 和 list 兩種類型，且 list 內(nèi)部可嵌套。那么它的數(shù)據(jù)結(jié)構(gòu)相對簡單：
// 表達(dá)式定義
public enum SExpr {
// 原子
case Atom(String)
// 列表，可嵌套
case List([SExpr])
}
Tokenize
識別輸入代碼，將其分割為一個(gè)個(gè)的有效 token。上面我們說過，token 只有三種類型，可用枚舉來進(jìn)行定義。
enum Token {
// 左括號
case pOpen
// 右括號
case pClose
// 字符串
case text(String)
}
而解析 token 的過程，只需逐個(gè)遍歷每個(gè)字符進(jìn)行處理。
遍歷過程中，只會(huì)有如下幾種情形：
-
'('，此時(shí)添加pOpen到 token 列表。但要注意
(前面還可能存在字符串，比如cons(B C)，此時(shí)需將字符串cons作為一個(gè)字符串token添加到列表。// "cons(B C)"，當(dāng)遍歷到 ( 時(shí)，cons 需作為一個(gè) token if tmpText != "" { res.append(.text(tmpText)) tmpText = "" } res.append(.pOpen) -
')'，此時(shí)添加pClose到 token 列表。同樣注意字符串處理，比如
(B)，當(dāng)遇到)時(shí)，需添加字符串B到列表。// "(B)"，遍歷到 )，B 作為一個(gè) token if tmpText != "" { res.append(.text(tmpText)) tmpText = "" } res.append(.pClose) -
' '，空格是分隔 token 的標(biāo)記，多個(gè)空格只會(huì)被看成一個(gè)。當(dāng)遇到空格時(shí)，說明可能有 token 定義結(jié)束。這里主要用于處理字符串 token。
// "A B"，遍歷到到 A 后面的空格，A 作為一個(gè) token if tmpText != "" { res.append(.text(tmpText)) tmpText = "" } -
其他就是字符了，逐個(gè)累加字符。在上面三種情況中，將其添加到 token 列表。
tmpText.append(c)
經(jīng)過這幾種情況的處理，我們可以得到一個(gè) token 列表。
舉個(gè)例子："(a b c)"，得到的 token 列表為：
[.pOpen, .text(a), .text(b), .text(c), .pClose]
Parse
接下來是進(jìn)行 token 列表的解析，將其結(jié)構(gòu)化為 AST，其實(shí)也就是轉(zhuǎn)換為上面定義的 SExpr 的結(jié)構(gòu)。
最主要的就是列表左右括號配對處理，內(nèi)嵌列表的遞歸處理。
舉一個(gè)簡單的例子，比如代碼："(a b c)"，轉(zhuǎn)換為 AST 后，應(yīng)是如下結(jié)構(gòu)：
.List([.Atom(a), .Atom(b), .Atom(c)])
如下圖所示：
再看一個(gè)嵌套的例子，比如代碼："(a (b c))"，轉(zhuǎn)換為 AST 后，結(jié)構(gòu)如下：
.List([.Atom(a), .List([.Atom(b), .Atom(c)])])
如下圖所示：
那么看起來規(guī)則挺簡單的，遇到 list，將其變?yōu)?.List；遇到 atom，將其變?yōu)?.Atom。正所謂是，逢山開山，遇水淌水。
總結(jié)一下轉(zhuǎn)換規(guī)則：
- 對于列表
list，轉(zhuǎn)換為.List(xx)； - 對于原子
atom，轉(zhuǎn)換為.Atom(xx)。
那么如何實(shí)現(xiàn)呢？
在遍歷 token 時(shí)，只有如下三種情形：
當(dāng)遇到
.pOpen，也就是(時(shí)，說明是列表的開始，初始化一個(gè)空列表.List([])作為父節(jié)點(diǎn)，繼續(xù)遞歸處理其后的token列表。-
當(dāng)遇到
.pClose，也就是)時(shí)，說明是列表的結(jié)束，返回配對()組成的表達(dá)式。此時(shí)會(huì)回到
.pOpen后續(xù)邏輯的處理，因?yàn)槭?strong>遞歸函數(shù)的返回。將表達(dá)式添加到「當(dāng)前上下文的父節(jié)點(diǎn)」中，然后繼續(xù)往后遍歷剩余token。 當(dāng)遇到
text時(shí)，轉(zhuǎn)換成.Atom(text)，添加到當(dāng)前父節(jié)點(diǎn)即可。
解析過程如下所示，其中 parser 表示解析函數(shù)。
// 入?yún)ⅲ簍oken 列表，父節(jié)點(diǎn)
// 返回參數(shù)：剩余 token 列表，子節(jié)點(diǎn)
parser(tokens, parentNode) -> (remainTokens, node)
舉個(gè)例子，比方說："(a (b))"，tokenize 之后的結(jié)果為：
[.pOpen, .text(a), .pOpen, .text(b), .pClose]
其解析過程如下圖所示。PS：為了表示方便，圖中直接使用了字符串，而非 token。
這樣我們就得到了 SExpr 的結(jié)構(gòu)，圖示如下：
到此，Read 的過程就結(jié)束啦，相關(guān)代碼可查看 github 。
總結(jié)
這篇文章主要介紹了如何通過詞法分析生成 token 列表、解析 token 生成 ast，最終得到 SExpr 的結(jié)構(gòu)。
下一篇文章我們將介紹如何利用 SExpr 結(jié)構(gòu)進(jìn)行計(jì)算，也就是 evaluation 的過程，敬請期待~
