轉

怎樣寫一個解釋器——王垠

2018年02月24日 11:36:02 田樹東 閱讀數：931

怎樣寫一個解釋器

寫一個解釋器，通常是設計和實現程序語言的第一步。解釋器是簡單卻又深奧的東西，以至于好多人都不會寫，所以我決定寫一篇這方面的入門讀物。

雖然我試圖從最基本的原理講起，盡量不依賴于其它知識，但這并不是一本編程入門教材。我假設你已經理解 Scheme 語言，以及基本的編程技巧（比如遞歸）。如果你完全不了解這些，那我建議你讀一下?SICP?的第一，二章，或者?HtDP?的前幾章，習題可以不做。注意不要讀太多書，否則你就回不來了 ;-) 當然你也可以直接讀這篇文章，有不懂的地方再去查資料。

實現語言容易犯的一個錯誤，就是一開頭就試圖去實現很復雜的語言（比如 JavaScript 或者 Python）。這樣你很快就會因為這些語言的復雜性，以及各種歷史遺留的設計問題而受到挫折，最后不了了之。學習實現語言，最好是從最簡單，最干凈的語言開始，迅速寫出一個可用的解釋器。之后再逐步往里面添加特性，同時保持正確。這樣你才能有條不紊地構造出復雜的解釋器。

因為這個原因，這篇文章只針對一個很簡單的語言，名叫“R2”。它可以作為一個簡單的計算器用，還具有變量定義，函數定義和調用等功能。

我們的工具：Racket

本文的解釋器是用 Scheme 語言實現的。Scheme 有很多的“實現”，這里我用的實現叫做 Racket，它可以在這里免費下載。為了讓程序簡潔，我用了一點點 Racket 的模式匹配（pattern matching）功能。我對 Scheme 的實現沒有特別的偏好，但 Racket 方便易用，適合教學。如果你用其它的 Scheme 實現，可能得自己做一些調整。

Racket 具有宏（macro），所以它其實可以變成很多種語言。如果你之前用過 DrRacket，那它的“語言設置”可能被你改成了 R5RS 之類的。所以如果下面的程序不能運行，你可能需要檢查一下 DrRacket 的“語言設置”，把 Language 設置成 “Racket”。

Racket 允許使用方括號而不只是圓括號，所以你可以寫這樣的代碼：

(let ([x 1]

[y 2])

(+ x y))

方括號跟圓括號可以互換，唯一的要求是方括號必須和方括號匹配。通常我喜歡用方括號來表示“無動作”的數據（比如上面的?[x 1],?[y 2]），這樣可以跟函數調用和其它具有“動作”的代碼，產生“視覺差”。這對于代碼的可讀性是一個改善，因為到處都是圓括號的話，確實有點太單調。

另外，Racket 程序的最上面都需要加上像?#lang?racket?這樣的語言選擇標記，這樣 Racket 才可以知道你想用哪個語言變種。

解釋器是什么

準備工作就到這里。現在我來談一下，解釋器到底是什么。說白了，解釋器跟計算器差不多。解釋器是一個函數，你輸入一個“表達式”，它就輸出一個 “值”，像這樣：

比如，你輸入表達式?'(+ 1 2)?，它就輸出值，整數3。表達式是一種“表象”或者“符號”，而值卻更加接近“本質”或者“意義”。解釋器從符號出發，得到它的意義，這也許就是它為什么叫做“解釋器”。

需要注意的是，表達式是一個數據結構，而不是一個字符串。我們用一種叫“S表達式”（S-expression）的結構來存儲表達式。比如表達式?'(+ 1 2)?其實是一個鏈表（list），它里面的內容是三個符號（symbol）：+,?1?和?2，而不是字符串"(+ 1 2)"。

從S表達式這樣的“結構化數據”里提取信息，方便又可靠，而從字符串里提取信息，麻煩而且容易出錯。Scheme（Lisp）語言里面大量使用結構化數據，少用字符串，這就是 Lisp 系統比 Unix 系統先進的地方之一。

從計算理論的角度講，每個程序都是一臺機器的“描述”，而解釋器就是在“模擬”這臺機器的運轉，也就是在進行“計算”。所以從某種意義上講，解釋器就是計算的本質。當然，不同的解釋器就會帶來不同的計算。你可能沒有想到，CPU 也是一個解釋器，它專門解釋執行機器語言。

抽象語法樹（Abstract Syntax Tree）

我們用S表達式所表示的代碼，本質上是一種叫做“樹”（tree）的數據結構。更具體一點，這叫做“抽象語法樹”（Abstract Syntax Tree，簡稱 AST）。下文為了簡潔，我們省略掉“抽象”兩個字，就叫它“語法樹”。

跟普通的樹結構一樣，語法樹里的節點，要么是一個“葉節點”，要么是一顆“子樹”。葉節點是不能再細分的“原子”，比如數字，字符串，操作符，變量名。而子樹是可以再細分的“結構”，比如算術表達式，函數定義，函數調用，等等。

舉個簡單的例子，表達式?'(* (+ 1 2) (+ 3 4))，就對應如下的語法樹結構：

其中，*，兩個+，1，2，3，4?都是葉節點，而那三個紅色節點，都表示子樹結構：'(+ 1 2)，'(+ 3 4)，'(* (+ 1 2) (+ 3 4))。

樹遍歷算法

在基礎的數據結構課程里，我們都學過二叉樹的遍歷操作，也就是所謂先序遍歷，中序遍歷和后序遍歷。語法樹跟二叉樹，其實沒有很大區別，所以你也可以在它上面進行遍歷。解釋器的算法，就是在語法樹上的一種遍歷操作。由于這個淵源關系，我們先來做一個遍歷二叉樹的練習。做好了之后，我們就可以把這段代碼擴展成一個解釋器。

這個練習是這樣：寫出一個函數，名叫tree-sum，它對二叉樹進行“求和”，把所有節點里的數加在一起，返回它們的和。舉個例子，(tree-sum '((1 2) (3 4)))，執行后應該返回?10。注意：這是一顆二叉樹，所以不會含有長度超過2的子樹，你不需要考慮像?((1 2) (3 4 5))?這類情況。需要考慮的例子是像這樣：(1 2)，(1 (2 3)),?((1 2) 3)?((1 2) (3 4))，……

（為了達到最好的學習效果，你最好試一下寫出這個函數再繼續往下看。）

好了，希望你得到了跟我差不多的結果。我的代碼是這個樣子：

#lang racket

(define tree-sum

(lambda (exp)

(match exp ; 對輸入exp進行模式匹配

[(? number? x) x] ; exp是一個數x嗎？如果是，那么返回這個數x

[`(,e1 ,e2) ; exp是一個含有兩棵子樹的中間節點嗎？

(let ([v1 (tree-sum e1)] ; 遞歸調用tree-sum自己，對左子樹e1求值

[v2 (tree-sum e2)]) ; 遞歸調用tree-sum自己，對右子樹e2求值

(+ v1 v2))]))) ; 返回左右子樹結果v1和v2的和

你可以通過以下的例子來測試它的正確性：

(tree-sum '(1 2))

;; => 3

(tree-sum '(1 (2 3)))

;; => 6

(tree-sum '((1 2) 3))

;; => 6

(tree-sum '((1 2) (3 4)))

;; => 10

（完整的代碼和示例，可以在這里下載。）

這個算法很簡單，我們可以把它用文字描述如下：

如果輸入?exp?是一個數，那就返回這個數。

否則如果?exp?是像?(,e1 ,e2)?這樣的子樹，那么分別對?e1?和?e2?遞歸調用?tree-sum，進行求和，得到?v1?和?v2，然后返回?v1 + v2?的和。

你自己寫出來的代碼，也許用了 if 或者 cond 語句來進行分支，而我的代碼里面使用的是 Racket 的模式匹配（match）。這個例子用 if 或者 cond 其實也可以，但我之后要把這代碼擴展成一個解釋器，所以提前使用了 match。這樣跟后面的代碼對比的時候，就更容易看出規律來。接下來，我就簡單講一下這個 match 表達式的工作原理。

模式匹配

現在不得不插入一點 Racket 的技術細節，如果你已經學會使用 Racket 的模式匹配，可以跳過這一節。你也可以通過閱讀 Racket 模式匹配的文檔來代替這一節。但我建議你不要讀太多文檔，因為我接下去只用到很少的模式匹配功能，我把它們都解釋如下。

模式匹配的形式一般是這樣：

(match x

[模式 結果]

[模式 結果]

... ...

)

它先對?x?求值，然后根據值的結構來進行分支。每個分支由兩部分組成，左邊是一個模式，右邊是一個結果。整個 match 語句的語義是這樣：從上到下依次考慮，找到第一個可以匹配?x?的值的模式，返回它右邊的結果。左邊的模式在匹配之后，可能會綁定一些變量，這些變量可以在右邊的表達式里使用。

模式匹配是一種分支語句，它在邏輯上就是 Scheme（Lisp） 的?cond?表達式，或者 Java 的嵌套條件語句?if ... else if ... else ...。然而跟條件語句里的“條件”不同，每條 match 語句左邊的模式，可以準確而形象地描述數據結構的形狀，而且可以在匹配的同時，對結構里的成員進行“綁定”。這樣我們可以在右邊方便的訪問結構成員，而不需要使用訪問函數（accessor）或者?foo.x?這樣的屬性語法（attribute）。而且模式可以有嵌套的子結構，所以它能夠一次性的表示復雜的數據結構。

舉個實在點的例子。我的代碼里用了這樣一個 match 表達式：

(match exp

[(? number? x) x]

[`(,e1 ,e2)

(let ([v1 (tree-sum e1)]

[v2 (tree-sum e2)])

(+ v1 v2))])

第二行里面的?'(,e1 ,e2)?是一個模式（pattern），它被用來匹配?exp?的值。如果?exp?是?'(1 2)，那么它與'(,e1 ,e2)匹配的時候，就會把?e1?綁定到?'1，把?e2?綁定到?'2。這是因為它們結構相同：

`(,e1 ,e2)

'( 1 2)

說白了，模式就是一個可以含有“名字”（像?e1?和?e2）的結構，像?'(,e1 ,e2)。我們拿這個帶有名字的結構，去匹配實際數據，像?'(1 2)。當它們一一對應之后，這些名字就被綁定到數據里對應位置的值。

第一行的“模式”比較特殊，(? number? x)?表示的，其實是一個普通的條件判斷，相當于?(number? exp)，如果這個條件成立，那么它把?exp?的值綁定到?x，這樣右邊就可以用?x?來指代?exp。對于無法細分的結構（比如數字，布爾值），你只能用這種方式來“匹配”。看起來有點奇怪，不過習慣了就好了。

模式匹配對解釋器和編譯器的書寫相當有用，因為程序的語法樹往往具有嵌套的結構。不用模式匹配的話，往往要寫冗長，復雜，不直觀的代碼，才能描述出期望的結構。而且由于結構的嵌套比較深，很容易漏掉邊界情況，造成錯誤。模式匹配可以直觀的描述期望的結構，避免漏掉邊界情況，而且可以方便的訪問結構成員。

由于這個原因，很多源于 ML 的語言（比如 OCaml，Haskell）都有模式匹配的功能。因為 ML（Meta-Language）原來設計的用途，就是用來實現程序語言的。Racket 的模式匹配也是部分受了 ML 的啟發，實際上它們的原理是一模一樣的。

好了，樹遍歷的練習就做到這里。然而這跟解釋器有什么關系呢？下面我們只把它改一下，就可以得到一個簡單的解釋器。

一個計算器

計算器也是一種解釋器，只不過它只能處理算術表達式。我們的下一個目標，就是寫出一個計算器。如果你給它?'(* (+ 1 2) (+ 3 4))，它就輸出?21。可不要小看這個計算器，稍后我們把它稍加改造，就可以得到一個更多功能的解釋器。

上面的代碼里，我們利用遞歸遍歷，對樹里的數字求和。那段代碼里，其實已經隱藏了一個解釋器的框架。你觀察一下，一個算術表達式?'(* (+ 1 2) (+ 3 4))，跟二叉樹?'((1 2) (3 4))?有什么不同？發現沒有，這個算術表達式比起二叉樹，只不過在每個子樹結構里多出了一個操作符：一個?*?和兩個?+?。它不再是一棵二叉樹，而是一種更通用的樹結構。

這點區別，也就帶來了二叉樹求和與解釋器算法的區別。對二叉樹進行求和的時候，在每個子樹節點，我們都做加法。而對表達式進行解釋的時候，在每一個子樹節點，我們不一定進行加法。根據子樹的“操作符”不同，我們可能會選擇加，減，乘，除四種操作。

好了，下面就是這個計算器的代碼。它接受一個表達式，輸出一個數字作為結果。

#lang racket ; 聲明用 Racket 語言

(define calc

(lambda (exp)

(match exp ; 分支匹配：表達式的兩種情況

[(? number? x) x] ; 是數字，直接返回

[`(,op ,e1 ,e2) ; 匹配提取操作符op和兩個操作數e1,e2

(let ([v1 (calc e1)] ; 遞歸調用 calc 自己，得到 e1 的值

[v2 (calc e2)]) ; 遞歸調用 calc 自己，得到 e2 的值

(match op ; 分支匹配：操作符 op 的 4 種情況

['+ (+ v1 v2)] ; 如果是加號，輸出結果為 (+ v1 v2)

['- (- v1 v2)] ; 如果是減號，乘號，除號，相似的處理

['* (* v1 v2)]

['/ (/ v1 v2)]))])))

你可以得到如下的結果：

(calc '(+ 1 2))

;; => 3

(calc '(* 2 3))

;; => 6

(calc '(* (+ 1 2) (+ 3 4)))

;; => 21

（完整的代碼和示例，可以在這里下載。）

跟之前的二叉樹求和代碼比較一下，你會發現它們驚人的相似，因為解釋器本來就是一個樹遍歷算法。不過你發現它們有什么不同嗎？它們的不同點在于：

算術表達式的模式里面，多出了一個“操作符”（op）葉節點：(,op ,e1 ,e2)

對子樹 e1 和 e2 分別求值之后，我們不是返回?(+ v1 v2)，而是根據?op?的不同，返回不同的結果：

(match op

['+ (+ v1 v2)]

['- (- v1 v2)]

['* (* v1 v2)]

['/ (/ v1 v2)])

最后你發現，一個算術表達式的解釋器，不過是一個稍加擴展的樹遍歷算法。

R2：一個很小的程序語言

實現了一個計算器，現在讓我們過渡到一種更強大的語言。為了方便稱呼，我給它起了一個萌萌噠名字，叫 R2。R2 比起之前的計算器，只多出四個元素，它們分別是：變量，函數，綁定，調用。再加上之前介紹的算術操作，我們就得到一個很簡單的程序語言，它只有5種不同的構造。用 Scheme 的語法，這5種構造看起來就像這樣：

• 變量：x
• 函數：(lambda (x) e)
• 綁定：(let ([x e1]) e2)
• 調用：(e1 e2)
• 算術：(? e2 e2)

（其中，? 是一個算術操作符，可以選擇?+,?-,?*,?/?其中之一）

一般程序語言還有很多其它構造，可是一開頭就試圖去實現所有那些，只會讓人糊涂。最好是把這少數幾個東西搞清楚，確保它們正確之后，才慢慢加入其它元素。

這些構造的語義，跟 Scheme 里面的同名構造幾乎一模一樣。如果你不清楚什么是”綁定“，那你可以把它看成是普通語言里的”變量聲明“。

需要注意的是，跟一般語言不同，我們的函數只接受一個參數。這不是一個嚴重的限制，因為在我們的語言里，函數可以被作為值傳遞，也就是所謂“first-class function”。所以你可以用嵌套的函數定義來表示有兩個以上參數的函數。

舉個例子，?(lambda (x) (lambda (y) (+ x y)))?是個嵌套的函數定義，它也可以被看成是有兩個參數（x?和?y）的函數，這個函數返回?x?和?y?的和。當這樣的函數被調用的時候，需要兩層調用，就像這樣：

(((lambda (x) (lambda (y) (+ x y))) 1) 2)

;; => 3

這種做法在PL術語里面，叫做咖喱（currying）。看起來啰嗦，但這樣我們的解釋器可以很簡單。等我們理解了基本的解釋器，再實現真正的多參數函數也不遲。

另外，我們的綁定語法?(let ([x e1]) e2)，比起 Scheme 的綁定也有一些局限。我們的 let 只能綁定一個變量，而 Scheme 可以綁定多個，像這樣?(let ([x 1] [y 2]) (+ x y))。這也不是一個嚴重的限制，因為我們可以啰嗦一點，用嵌套的 let 綁定：

(let ([x 1])

(let ([y 2])

(+ x y)))

R2 的解釋器

下面是我們今天要完成的解釋器，它可以運行一個 R2 程序。你可以先留意一下各部分的注釋。

#lang racket

;;; 以下三個定義 env0, ext-env, lookup 是對環境（environment）的基本操作：

;; 空環境

(define env0 '())

;; 擴展。對環境 env 進行擴展，把 x 映射到 v，得到一個新的環境

(define ext-env

(lambda (x v env)

(cons `(,x . ,v) env)))

;; 查找。在環境中 env 中查找 x 的值。如果沒找到就返回 #f

(define lookup

(lambda (x env)

(let ([p (assq x env)])

(cond

[(not p) #f]

[else (cdr p)]))))

;; 閉包的數據結構定義，包含一個函數定義 f 和它定義時所在的環境

(struct Closure (f env))

;; 解釋器的遞歸定義（接受兩個參數，表達式 exp 和環境 env）

;; 共 5 種情況（變量，函數，綁定，調用，數字，算術表達式）

(define interp

(lambda (exp env)

(match exp ; 對exp進行模式匹配

[(? symbol? x) ; 變量

(let ([v (lookup x env)])

(cond

[(not v)

(error "undefined variable" x)]

[else v]))]

[(? number? x) x] ; 數字

[`(lambda (,x) ,e) ; 函數

(Closure exp env)]

[`(let ([,x ,e1]) ,e2) ; 綁定

(let ([v1 (interp e1 env)])

(interp e2 (ext-env x v1 env)))]

[`(,e1 ,e2) ; 調用

(let ([v1 (interp e1 env)]

[v2 (interp e2 env)])

(match v1

[(Closure `(lambda (,x) ,e) env-save)

(interp e (ext-env x v2 env-save))]))]

[`(,op ,e1 ,e2) ; 算術表達式

(let ([v1 (interp e1 env)]

[v2 (interp e2 env)])

(match op

['+ (+ v1 v2)]

['- (- v1 v2)]

['* (* v1 v2)]

['/ (/ v1 v2)]))])))

;; 解釋器的“用戶界面”函數。它把 interp 包裝起來，掩蓋第二個參數，初始值為 env0

(define r2

(lambda (exp)

(interp exp env0)))

這里有一些測試例子：

(r2 '(+ 1 2))

;; => 3

(r2 '(* 2 3))

;; => 6

(r2 '(* 2 (+ 3 4)))

;; => 14

(r2 '(* (+ 1 2) (+ 3 4)))

;; => 21

(r2 '((lambda (x) (* 2 x)) 3))

;; => 6

(r2

'(let ([x 2])

(let ([f (lambda (y) (* x y))])

(f 3))))

;; => 6

(r2

'(let ([x 2])

(let ([f (lambda (y) (* x y))])

(let ([x 4])

(f 3)))))

;; => 6

（完整的代碼和示例，可以在這里下載。)

在接下來的幾節，我們來仔細看看這個解釋器的各個部分。

對基本算術操作的解釋

算術操作一般都是程序里最基本的構造，它們不能再被細分為多個步驟，所以我們先來看看對算術操作的處理。以下就是 R2 解釋器處理算術的部分，它是?interp?的最后一個分支。

(match exp

... ...

[`(,op ,e1 ,e2)

(let ([v1 (interp e1 env)] ; 遞歸調用 interp 自己，得到 e1 的值

[v2 (interp e2 env)]) ; 遞歸調用 interp 自己，得到 e2 的值

(match op ; 分支：處理操作符 op 的 4 種情況

['+ (+ v1 v2)] ; 如果是加號，輸出結果為 (+ v1 v2)

['- (- v1 v2)] ; 如果是減號，乘號，除號，相似的處理

['* (* v1 v2)]

['/ (/ v1 v2)]))])

你可以看到它幾乎跟剛才寫的計算器一模一樣，不過現在?interp?的調用多了一個參數?env?而已。這個?env?是所謂“環境”，我們下面很快就講。

對數字的解釋

對數字的解釋很簡單，把它們原封不動返回就可以了。

[(? number? x) x]

變量和函數

變量和函數是解釋器里最麻煩的部分，所以我們來仔細看看。

變量（variable）的產生，是數學史上的最大突破之一。因為變量可以被綁定到不同的值，從而使函數的實現成為可能。比如數學函數?f(x) = x * 2，其中?x?是一個變量，它把輸入的值傳遞到函數體?x * 2?里面。如果沒有變量，函數就不可能實現。

對變量最基本的操作，是對它的“綁定”（binding）和“取值”（evaluate）。什么是綁定呢？拿上面的函數?f(x)?作為例子。當我們調用?f(1)?時，函數體里面的?x?等于 1，所以?x * 2?的值是 2，而當我們調用?f(2)?時，函數體里面的?x?等于 2，所以?x * 2?的值是 4。這里，兩次對?f?的調用，分別對?x?進行了兩次綁定。第一次?x?被綁定到了 1，第二次被綁定到了 2。

你可以把“綁定”理解成這樣一個動作，就像當你把插頭插進電源插座的那一瞬間。插頭的插腳就是?f(x)?里面的那個?x，而?x * 2?里面的?x，則是電線的另外一端。所以當你把插頭插進插座，電流就通過這根電線到達另外一端。如果電線導電性能良好，兩頭的電壓應該相等。

環境

我們的解釋器只能一步一步的做事情。比如，當它需要求?f(1)?的值的時候，它分成兩步操作：

把?x?綁定到 1，這樣函數體內才能看見這個綁定。

進入?f?的函數體，對?x * 2?進行求值。

這就像一個人做出這兩個動作：

把插頭插進插座 。

到電線的另外一頭，測量它的電壓，并且把結果乘以 2。

在第一步和第二步之間，我們如何記住?x?的值呢？通過所謂“環境”！我們用環境記錄變量的值，并且把它們傳遞到變量的“可見區域”。變量的可見區域，用術語說叫做“作用域”（scope）。

在我們的解釋器里，用于處理環境的代碼如下：

;; 空環境

(define env0 '())

;; 對環境 env 進行擴展，把 x 映射到 v

(define ext-env

(lambda (x v env)

(cons `(,x . ,v) env)))

;; 取值。在環境中 env 中查找 x 的值

(define lookup

(lambda (x env)

(let ([p (assq x env)])

(cond

[(not p) #f]

[else (cdr p)]))))

這里我們用一種最簡單的數據結構，Scheme 的 association list，來表示環境。Association list 看起來像這個樣子：((x . 1) (y . 2) (z . 5))。它是一個兩元組（pair）的鏈表，左邊的元素是 key，右邊的元素是 value。寫得直觀一點就是：

((x . 1)

(y . 2)

(z . 5))

查表操作就是從頭到尾搜索，如果左邊的 key 是要找的變量，就返回整個 pair。簡單吧？效率很低，但是足夠完成我們現在的任務。

ext-env?函數擴展一個環境。比如，如果原來的環境?env1?是?((y . 2) (x . 1))?那么?(ext-env x 3 env1)，就會返回?((x . 3) (y . 2) (x . 1))。也就是把?(x . 3)?加到?env1?的最前面去。

那我們什么時候需要擴展環境呢？當我們進行綁定的時候。綁定可能出現在函數調用時，也可能出現在 let 綁定時。我們選擇的數據結構，使得環境自然而然的具有了作用域（scope）的特性。

環境其實是一個堆棧（stack）。內層的綁定，會出現在環境的最上面，這就是在“壓棧”。這樣我們查找變量的時候，會優先找到最內層定義的變量。

舉個例子：

(let ([x 1]) ; env='()。綁定x到1。

(let ([y 2]) ; env='((x . 1))。綁定y到2。

(let ([x 3]) ; env='((y . 2) (x . 1))。綁定x到3。

(+ x y)))) ; env='((x . 3) (y . 2) (x . 1))。查找x，得到3；查找y，得到2。

;; => 5

這段代碼會返回5。這是因為最內層的綁定，把?(x . 3)?放到了環境的最前面，這樣查找?x?的時候，我們首先看到?(x . 3)，然后就返回值3。之前放進去的?(x . 1)?仍然存在，但是我們先看到了最上面的那個(x . 3)，所以它被忽略了。

這并不等于說?(x . 1)?就可以被改寫或者丟棄，因為它仍然是有用的。你只需要看一個稍微不同的例子，就知道這是怎么回事：

(let ([x 1]) ; env='()。綁定x到1。

(+ (let ([x 2]) ; env='((x . 1))。綁定x到2。

x) ; env='((x . 2) (x . 1))。查找x，得到2。

x)) ; env='((x . 1))。查找x，得到1。

;; => 3 ; 兩個不同的x的和，1+2等于3。

這個例子會返回3。它是第3行和第4行里面兩個?x?的和。由于第3行的?x?處于內層 let 里面，那里的環境是?((x . 2) (x . 1))，所以查找?x?的值得到2。第4行的?x?在內層 let 外面，但是在外層 let 里面，那里的環境是?((x . 1))，所以查找?x?的值得到1。這很符合直覺，因為?x?總是找到最內層的定義。

值得注意的是，環境被擴展以后，形成了一個新的環境，而原來的環境并沒有被改變。比如，上面的?((y . 2) (x . 1))并沒有刪除或者修改，只不過是被“引用”到一個更大的列表里去了。

這樣不對已有數據進行修改（mutation）的數據結構，叫做“函數式數據結構”。函數式數據結構只生成新的數據，而不改變或者刪除老的。它可能引用老的結構，然而卻不改變老的結構。這種“不修改”（immutable）的性質，在我們的解釋器里是很重要的，因為當我們擴展一個環境，進入遞歸，返回之后，外層的代碼必須仍然可以訪問原來外層的環境。

當然，我們也可以用另外的，更高效的數據結構（比如平衡樹，串接起來的哈希表）來表示環境。如果你學究一點，甚至可以用函數來表示環境。這里為了代碼簡單，我們選擇了最笨，然而正確，容易理解的數據結構。

對變量的解釋

了解了變量，函數和環境，我們來看看解釋器對變量的“取值”操作，也就是?match?的第一種情況。

[(? symbol? x) (lookup x env)]

這就是在環境中，沿著從內向外的“作用域順序”，查找變量的值。

這里的?(? symbol? x)?是一種特殊的模式，它使用 Scheme 函數?symbol??來判斷輸入是否是一個符號，如果是，就把它綁定到?x，然后你就可以在右邊用?x?來指稱這個輸入。

對綁定的解釋

現在我們來看看對 let 綁定的解釋：

[`(let ([,x ,e1]) ,e2)

(let ([v1 (interp e1 env)]) ; 解釋右邊表達式e1，得到值v1

(interp e2 (ext-env x v1 env)))] ; 把(x . v1)擴充到環境頂部，對e2求值

通過代碼里的注釋，你也許已經可以理解它在做什么。我們先對表達式?e1?求值，得到?v1。然后我們把?(x . v1)?擴充到環境里，這樣?(let ([x e1]) ...)?內部都可以看到?x?的值。然后我們使用這個擴充后的環境，遞歸調用解釋器本身，對 let 的主體?e2?求值。它的返回值就是這個 let 綁定的值。

Lexical Scoping 和 Dynamic Scoping

下面我們準備談談函數定義和調用。對函數的解釋是一個微妙的問題，很容易弄錯，這是由于函數體內也許會含有外層的變量，叫做“自由變量”。所以在分析函數的代碼之前，我們來了解一下不同的“作用域”（scoping）規則。

我們舉個例子來解釋這個問題。下面這段代碼，它的值應該是多少呢？

(let ([x 2])

(let ([f (lambda (y) (* x y))])

(let ([x 4])

(f 3))))

在這里，f?函數體?(lambda (y) (* x y))?里的那個?x，就是一個“自由變量”。x?并不是這個函數的參數，也不是在這個函數里面定義的，所以我們必須到函數外面去找?x?的值。

我們的代碼里面，有兩個地方對?x?進行了綁定，一個等于2，一個等于4，那么?x?到底應該是指向哪一個綁定呢？這似乎無關痛癢，然而當我們調用?(f 3)?的時候，嚴重的問題來了。f?的函數體是?(* x y)，我們知道?y?的值來自參數 3，可是?x?的值是多少呢？它應該是2，還是4呢？

在歷史上，這段代碼可能有兩種不同的結果，這種區別一直延續到今天。如果你在 Scheme （Racket）里面寫以上的代碼，它的結果是6。

;; Scheme

(let ([x 2])

(let ([f (lambda (y) (* x y))])

(let ([x 4])

(f 3))))

;; => 6

現在我們來看看，在 Emacs Lisp 里面輸入等價的代碼，得到什么結果。如果你不熟悉 Emacs Lisp 的用法，那你可以跟我做：把代碼輸入 Emacs 的那個叫?*scratch*?的 buffer。把光標放在代碼最后，然后按 C-x C-e，這樣 Emacs 會執行這段代碼，然后在 minibuffer 里顯示結果：

結果是12！如果你把代碼最內層的?x?綁定修成其它的值，輸出會隨之改變。

奇怪吧？Scheme 和 Emacs Lisp，到底有什么不一樣呢？實際上，這兩種看似差不多的 “Lisp 方言”，采用了兩種完全不同的作用域方式。Scheme 的方式叫做 lexical scoping （或者 static scoping），而 Emacs 的方式叫做 dynamic scoping。

那么哪一種方式更好呢？或者用哪一種都無所謂？答案是，dynamic scoping 是非常錯誤的做法。歷史的教訓告訴我們，它會帶來許許多多莫名其妙的 bug，導致 dynamic scoping 的語言幾乎完全沒法用。這是為什么呢？

原因在于，像?(let ((x 4)) …)?這樣的變量綁定，只應該影響它內部“看得見”的?x?的值。當我們看見?(let ((x 4)) (f 3))?的時候，并沒有在 let 的內部看見任何叫“x” 的變量，所以我們“直覺”的認為，(let ((x 4)) …)?對?x?的綁定，不應該引起?(f 3)?的結果變化。

然而對于 dynamic scoping，我們的直覺卻是錯誤的。因為?f?的函數體里面有一個?x，雖然我們沒有在?(f 3)?這個調用里面看見它，然而它卻存在于?f?定義的地方。要知道，f?定義的地方也許隔著幾百行代碼，甚至在另外一個文件里面。而且調用函數的人憑什么應該知道，?f?的定義里面有一個自由變量，它的名字叫做?x？所以 dynamic scoping 在設計學的角度來看，是一個反人類的設計 :)

相反，lexical scoping 卻是符合人們直覺的。雖然在?(let ((x 4)) (f 3))?里面，我們把?x?綁定到了 4，然而?f?的函數體并不是在那里定義的，我們也沒在那里看見任何?x，所以?f?的函數體里面的?x，仍然指向我們定義它的時候看得見的那個?x，也就是最上面的那個?(let ([x 2]) ...)，它的值是 2。所以?(f 3)?的值應該等于 6，而不是12。

對函數的解釋

為了實現 lexical scoping，我們必須把函數做成“閉包”（closure）。閉包是一種特殊的數據結構，它由兩個元素組成：函數的定義和當前的環境。我們把閉包定義為一個 Racket 的 struct 結構：

(struct Closure (f env))

有了這個數據結構，我們對?(lambda (x) e)?的解釋就可以寫成這樣：

[`(lambda (,x) ,e)

(Closure exp env)]

注意這里的?exp?就是 ``(lambda (,x) ,e)` 自己。

有意思的是，我們的解釋器遇到?(lambda (x) e)，幾乎沒有做任何計算。它只是把這個函數包裝了一下，把它與當前的環境一起，打包放到一個數據結構（Closure）里面。這個閉包結構，記錄了我們在函數定義的位置“看得見”的那個環境。稍候在調用的時候，我們就能從這個閉包的環境里面，得到函數體內的自由變量的值。

對調用的解釋

好了，我們終于到了最后的關頭，函數調用。為了直觀，我們把函數調用的代碼拷貝如下：

[`(,e1 ,e2)

(let ([v1 (interp e1 env)] ; 計算函數 e1 的值

[v2 (interp e2 env)]) ; 計算參數 e2 的值

(match v1

[(Closure `(lambda (,x) ,e) env-save) ; 用模式匹配的方式取出閉包里的各個子結構

(interp e (ext-env x v2 env-save))]))] ; 在閉包的環境env-save中把x綁定到v2，解釋函數體

函數調用都是?(e1 e2)?這樣的形式，e1?表示函數，e2?是它的參數。我們需要先分別求出函數?e1?和參數?e2?的值。

函數調用就像把一個電器的插頭插進插座，使它開始運轉。比如，當?(lambda (x) (* x 2))?被作用于 1 時，我們把?x綁定到 1，然后解釋它的函數體?(* x 2)。但是這里有一個問題，函數體內的自由變量應該取什么值呢？從上面閉包的討論，你已經知道了，自由變量的值，應該從閉包的環境查詢。

操作數?e1?的值?v1?是一個閉包，它里面包含一個函數定義時保存的環境?env-save。我們把這個環境?env-save?取出來，那我們就可以查詢它，得到函數體內自由變量的值。然而函數體內不僅有自由變量，還有對函數參數的使用，所以我們必須擴展這個?env-save?環境，把參數的值加進去。這就是為什么我們使用?(ext-env x v2 env-save)，而不只是?env-save。

你可能會奇怪，那么解釋器的環境?env?難道這里就不用了嗎？是的。我們通過?env?來計算?e1?和?e2?的值，是因為?e1?和?e2?里面的變量，在“當前環境”（env）里面看得見。可是函數體的定義，在當前環境下是看不見的。它的代碼在別的地方，而那個地方看得見的環境，被我們存在閉包里了，它就是?env-save。所以我們把?v1?里面的閉包環境?env-save?取出來，用于計算函數體的值。

有意思的是，如果我們用?env，而不是env-save?來解釋函數體，那我們的語言就變成了 dynamic scoping。現在來實驗一下：你可以把?(interp e (ext-env x v2 env-save))?里面的?env-save?改成?env，再試試我們之前討論過的代碼，它的輸出就會變成 12。那就是我們之前講過的，dynamic scoping 的結果。

(r2

'(let ([x 2])

(let ([f (lambda (y) (* x y))])

(let ([x 4])

(f 3)))))

;; => 12

你也許發現了，如果我們的語言是 dynamic scoping，那就沒必要使用閉包了，因為我們根本不需要閉包里面保存的環境。這樣一來，dynamic scoping 的解釋器就可以寫成這樣：

(define interp

(lambda (exp env)

(match exp

... ...

[`(lambda (,x) ,e) ; 函數：直接返回自己的表達式

exp]

... ...

[`(,e1 ,e2)

(let ([v1 (interp e1 env)]

[v2 (interp e2 env)])

(match v1

[`(lambda (,x) ,e) ; 調用：直接使用函數的表達式本身

(interp e (ext-env x v2 env))]))]

... ...

)))

注意到這個解釋器的函數有多容易實現嗎？它就是這個函數的表達式自己，原封不動。用函數的表達式本身來表示它的值，是很直接很簡單的做法，也是大部分人一開頭就會想到的。然而這樣實現出來的語言，就不知不覺地采用了 dynamic scoping。

這就是為什么很多早期的 Lisp 語言，比如 Emacs Lisp，都使用 dynamic scoping。這并不是因為它們的設計者在 dynamic scoping 和 lexical scoping 兩者之中做出了選擇，而是因為使用函數的表達式本身來作為它的值，是最直接，一般人都會首先想到的做法。

另外，在這里我們也看到環境用“函數式數據結構”表示的好處。閉包被調用時它的環境被擴展，但是這并不會影響原來的那個環境，我們得到的是一個新的環境。所以當函數調用返回之后，函數的參數綁定就自動“注銷”了。

如果你用一個非函數式的數據結構，在綁定參數時不生成新的環境，而是對已有環境進行賦值，那么這個賦值操作就會永久性的改變原來環境的內容。所以你在函數返回之后必須刪除參數的綁定。這樣不但麻煩，而且在復雜的情況下很容易出錯。

思考題：可能有些人看過 lambda calculus，這些人可能知道?(let ([x e1]) e2)?其實等價于一個函數調用：((lambda (x) e2) e1)。現在問題來了，我們在討論函數和調用的時候，很深入的討論了關于 lexical scoping 和 dynamic scoping 的差別。既然 let 綁定等價于一個函數定義和調用，為什么之前我們討論對綁定的時候，沒有討論過 lexical scoping 和 dynamic scoping 的問題，也沒有制造過閉包呢？

不足之處

現在你已經學會了如何寫出一個簡單的解釋器，它可以處理一個相當強的，具有“first-class 函數”的語言。出于教學的考慮，這個解釋器并沒有考慮實用的需求，所以它并不能作為“工業應用”。在這里，我指出它的一些不足之處。

缺少必要的語言構造。我們的語言里缺少好些實用語言必須的構造：遞歸，數組，賦值操作，字符串，自定義數據結構，…… 作為一篇基礎性的讀物，我不能把這些都加進來。如果你對這些有興趣，可以看看其它書籍，或者等待我的后續作品。

不合法代碼的檢測和報告。你也許發現了，這個解釋器的 match 表達式，全都假定了輸入都是合法的程序，它并沒有檢查不合法的情況。如果你給它一個不合法的程序，它的行為會變得詭異。一個實用的解釋器，必須加入對代碼格式進行全面檢測，報告不合法的代碼結構。

低效率的數據結構。在 association list 里面查找變量，是線性的復雜度。當程序有很多變量的時候就有性能問題。一個實用的解釋器，需要更高效的數據結構。這種數據結構不一定非得是函數式的。你也可以用非函數式的數據結構（比如哈希表），經過一定的改造，達到同樣的性質，卻具有更高的效率。 ? 另外，你還可以把環境轉化成一個數組。給環境里的每個變量分配一個下標（index），在這個數組里就可以找到它的值。如果你用數組表示環境，那么這個解釋器就向編譯器邁進了一步。

S表達式的歧義問題。為了教學需要，我們的解釋器直接使用S表達式來表達語法樹，用模式匹配來進行分支遍歷。在實際的語言里，這種方式會帶來比較大的問題。因為S表達式是一種通用的數據結構，用它表示的東西，看起來都差不多的樣子。一旦程序的語法構造多起來，直接對S表達式進行模式匹配，會造成歧義。 ?

比如?(,op ,e1 ,e2)?，你以為它只匹配二元算術操作，比如?(+ 1 2)。但它其實也可以匹配一個 let 綁定：?(let ([x 1]) (* x 2))。這是因為它們頂層元素的數目是一樣的。為了消除歧義，你得小心的安排模式的順序，比如你必須把?(let ([,x ,e1]) ,e2)?的模式放在?(,op ,e1, e2)?前面。所以最好的辦法，是不要直接在S表達式上寫解釋器，而是先寫一個“parser”，這個parser把S表達式轉換成 Racket 的 struct 結構。然后解釋器再在 struct 上面進行分支匹配。這樣解釋器不用擔心歧義問題，而且會帶來效率的提升。

總結

以上是生活随笔為你收集整理的怎样写一个解释器——王垠的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。