轉載▼
| 分類： 程式語言 |
賣了好久關子了，說要寫一個程式語言理論的入門讀物，可是一直沒有下筆。終于狠下心來兌現一部分承諾。今天就從解釋器講起吧。
解釋器是比較深入的内容。雖然我試圖從最基本的原理講起，盡量讓這篇文章不依賴于其它的知識，但是這篇教程并不是針對函數式程式設計的入門，是以我假設你已經學會了最基本的 Scheme 和函數式程式設計。如果你完全不了解這些，可以讀一下 SICP 的第一，二章。當然你也可以繼續讀這篇文章，有不懂的地方再去查資料。我在這裡也會講遞歸和模式比對的原理。如果你已經了解這些東西，這裡的内容也許可以加深你的了解。
解釋器其實不是很難的東西，可是好多人都不會寫，因為在他們心目中解釋器就像一個 Python 解釋器那樣複雜。如果你想開頭就寫一個 Python 解釋器，那你多半永遠也寫不出來。你必須從最簡單的語言開始，逐漸增加語言的複雜度，才能構造出正确的解釋器。這篇文章就是告訴你如何寫出一個最簡單的語言 (lambda calculus) 的解釋器，并且帶有基本的的算術功能，可以作為一個進階電腦來使用。
一般的編譯器課程往往從文法分析(parsing)開始，折騰 lex 和 yacc 等工具。Parsing 的作用其實隻是把字元串解碼成程式的文法樹（AST）結構。麻煩好久得到了 AST 之後，真正的困難才開始！而很多人在寫完 parser 之後就已經倒下了。鑒于這個原因，這裡我用“S-expression”來表示程式的文法樹（AST）結構。S-expression 讓我們可以直接跳過 parse 的步驟，進入關鍵的主題：語義(semantics)。
這裡用的 Scheme 實作是 Racket。為了讓程式簡潔，我使用了 Racket 的 模式比對（pattern matching）。如果你用其它的 Scheme 實作的話，恐怕要自己做一些調整。
解釋器是什麼
首先我們來談一下解釋器是什麼。說白了解釋器跟電腦差不多。它們都接受一個“表達式”，輸出一個 “結果”。比如，得到 '(+ 1 2) 之後就輸出 3。不過解釋器的表達式要比電腦的表達式複雜一些。解釋器接受的表達式叫做“程式”，而不隻是簡單的算術表達式。 從本質上講，每個程式都是一台機器的“描述”，而解釋器就是在“模拟”這台機器的運轉，也就是在進行“計算”。是以從某種意義上講，解釋器就是計算的本質。當然，不同的解釋器就會帶來不同的計算。
需要注意的是，我們的解釋器接受的參數是一個表達式的“資料結構”，而不是一個字元串。這裡我們用一種叫“S-expression”的資料結構來表示表達式。比如表達式 '(+ 1 2) 裡面的内容是三個符号：'+, '1 和 '2，而不是字元串“(+ 1 2)”。從結構化的資料裡面提取資訊很友善，而從字元串裡提取資訊很麻煩，而且容易出錯。
從廣義上講，解釋器是一個通用的概念。電腦實際上是解釋器的一種形式，隻不過它處理的語言比程式的解釋器簡單很多。也許你會發現，CPU 和人腦，從本質上來講也是解釋器，因為解釋器的本質實際上是“任何用于處理語言的機器”。
遞歸定義 (recursive definition)
解釋器一般都是“遞歸程式”。之是以是遞歸的原因，在于它處理的資料結構（程式）本身是“遞歸定義”的結構。算術表達式就是一個這樣的結構，比如：'(* (+ 1 2) (* (- 9 6) 4))。每一個表達式裡面可以含有子表達式，子表達式裡面還可以有子表達式，如此無窮無盡的嵌套。看似很複雜，其實它的定義不過是：
“算術表達式”有兩種形式：
1) 一個數
2) 一個 '(op e1 e2) 這樣的結構（其中 e1 和 e2 是兩個“算術表達式”）
看出來哪裡在“遞歸”了嗎？我們本來在定義“算術表達式”這個概念，而它的定義裡面用到了“算術表達式”這個概念本身！這就構造了一個“回路”，讓我們可以生成任意深度的表達式。
很多其它的資料，包括自然數，都是可以用遞歸來定義的。比如常見的對自然數的定義是：
“自然數”有兩種形式：
1) 零
2) 某個“自然數”的後繼
看到了嗎？“自然數”的定義裡面出現了它自己！這就是為什麼我們有無窮多個自然數。
是以可以說遞歸是無所不在的，甚至有人說遞歸就是自然界的終極原理。遞歸的資料總是需要遞歸的程式來處理。雖然遞歸有時候表現為另外的形式，比如循環(loop)，但是“遞歸”這個概念比“循環”更廣泛一些。有很多遞歸程式不能用循環來表達，比如我們今天要寫的解釋器就是一個遞歸程式，它就不能用循環來表達。是以寫出正确的遞歸程式，對于設計任何系統都是至關重要的。其實遞歸的概念不限于程式設計。在數學證明裡面有個概念叫“歸納法”(induction)，比如“數學歸納法”(mathematical induction)。其實歸納法跟遞歸完全是一回事。
我們今天的解釋器就是一個遞歸程式。它接受一個表達式，遞歸的調用它自己來處理各個子表達式，然後把各個遞歸的結果組合在一起，形成最後的結果。這有點像二叉樹周遊，隻不過我們的資料結構（程式）比二叉樹複雜一些。
模式比對和遞歸：一個簡單的電腦
既然電腦是一種最簡單的解釋器，那麼我們為何不從電腦開始寫？下面就是一個電腦，它可以計算四則運算的表達式。這些表達式可以任意的嵌套，比如 '(* (+ 1 2) (+ 3 4))。我想從這個簡單的例子來講一下模式比對(pattern matching) 和遞歸 (recursion) 的原理。
下面就是這個電腦的代碼。它接受一個表達式，輸出一個數字作為結果，正如上一節所示。
(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)]))])))
這裡的 match 語句是一個模式比對。它的形式是這樣：
(match exp
[模式 結果]
[模式 結果]
... ...
)
它根據表達式 exp 的“結構”來進行“分支”操作。每一個分支由兩部分組成，左邊的是一個“模式”，右邊的是一個結果。左邊的模式在比對之後可能會綁定一些變量，它們可以在右邊的表達式裡面使用。
一般說來，資料的“定義”有多少種情況，用來處理它的“模式”就有多少情況。比如算術表達式有兩種情況，數字或者 (op e1 e2)。是以用來處理它的 match 語句就有兩種模式。“你所有的情況，我都能處理”，這就是“窮舉法”。窮舉的思想非常重要，你漏掉的任何一種情況，都非常有可能帶來麻煩。 所謂的“數學歸納法”，就是這種窮舉法在自然數的遞歸定義上面的表現。因為你窮舉了所有的自然數可能被構造的兩種形式，是以你能確定定理對“任意自然數”成立。
那麼模式是如何工作的呢？比如 '(,op ,e1 ,e2) 就是一個模式（pattern），它被用來比對輸入的 exp。模式比對基本的原理就是比對與它“結構相同”的資料。比如，如果 exp 是 '(+ 1 2)，那麼 '(,op ,e1 ,e2) 就會把 op 綁定到 '+，把 e1 綁定到 '1，把 e2 綁定到 '2。這是因為它們結構相同：
'(,op ,e1 ,e2)
'( + 1 2)
說白了，模式就是一個可以含有“名字”（像 op, e1 和 e2）的“資料結構”，像 '(,op ,e1 ,e2)。我們拿這個帶有名字的結構去“比對”實際的資料（像 '(+ 1 2))。當它們一一對應之後，這些名字就自動被綁定到實際資料裡相應位置的值。模式裡面不但可以含有名字，也可以含有具體的資料。比如你可以構造一個模式 '(,op ,e1 42)，用來比對第二個操作數固定為 42 的那些表達式。
看見左邊的模式，你就像直接“看見”了輸入資料的形态，然後對裡面的元素進行操作。它可以讓我們一次性的“拆散”(destruct) 資料結構，把各個部件（域）的值綁定到多個變量，而不需要使用多個通路函數。是以模式比對是非常直覺的程式設計方式，值得每種語言借鑒。很多函數式語言裡都有類似的功能，比如 ML 和 Haskell。
注意這裡 e1 和 e2 裡面的操作數還不是值，它們是表達式。我們遞歸的調用 interp1 自己，分别得到 e1 和 e2 的值 v1 和 v2。它們應該是數字。
你注意到我們在什麼地方使用了遞歸嗎？如果你再看一下“算術表達式”的定義：
“算術表達式”有兩種形式：
1) 一個數
2) 一個 '(op e1 e2) 這樣的結構（其中 e1 和 e2 是兩個“算術表達式”）
你就會發現這個定義裡面“遞歸”的地方就是 e1 和 e2，是以 calc 在 e1 和 e2 上面遞歸的調用自己。如果你在資料定義的每個遞歸處都進行遞歸，那麼你的遞歸程式就會窮舉所有的情況。
之後，我們根據操作符 op 的不同，對這兩個值 v1 和 v2 分别進行操作。如果 op 是加号 '+，我們就調用 Scheme 的加法操作，作用于 v1 和 v2，并且傳回運算所得的值。如果是減号，乘号，除号，我們也進行相應的操作，傳回它們的值。
是以你就可以得到如下的測試結果：
(calc '(+ 1 2))
;; => 3
(calc '(* 2 3))
;; => 6
(calc '(* (+ 1 2) (+ 3 4)))
;; => 21
一個電腦就是這麼簡單。你可以試試這些例子，然後自己再做一些新的例子。
什麼是 lambda calculus？
現在讓我們過渡到一種更強大的語言：lambda calculus。它雖然名字看起來很吓人，但是其實非常簡單。它的三個元素分别是是：變量，函數，調用。用傳統的表達法，它們看起來就是：
變量：x
函數：λx.t
調用：t1 t2
每個程式語言裡面都有這三個元素，隻不過具體的文法不同，是以你其實每天都在使用 lambda calculus。用 Scheme 作為例子，這三個元素看起來就像：
變量：x
函數：(lambda (x) e)
調用：(e1 e2)
一般的程式語言還有很多其它的結構，可是這三個元素卻是缺一不可的。是以建構解釋器的最關鍵步驟就是把這三個東西搞清楚。構造任何一個語言的解釋器一般都是從這三個元素開始，在確定它們完全正确之後才慢慢加入其它的元素。
有一個很簡單的思維方式可以讓你直接看到這三元素的本質。記得我說過，每個程式都是一個 “機器的描述”嗎？是以每個 lambda calculus 的表達式也是一個機器的描述。這種機器跟電子線路非常相似。lambda calculus 的程式和機器有這樣的一一對應關系：一個變量就是一根導線。一個函數就是某種電子器件的“樣闆”，有它自己的輸入和輸出端子，自己的邏輯。一個調用都是在設計中插入一個電子器件的“執行個體”，把它的輸入端子連接配接到某些已有的導線，這些導線被叫做“參數”。是以一個 lambda calculus 的解釋器實際上就是一個電子線路的模拟器。是以如果你聽說有些晶片公司開始用 類似 Haskell 的語言（比如 Bluespec System Verilog）來設計硬體，也就不奇怪了。
需要注意的是，跟一般語言不同，lambda calculus 的函數隻有一個參數。這其實不是一個嚴重的限制，因為 lambda calculus 的函數可以被作為值傳遞 (這叫 first-class function)，是以你可以用嵌套的函數定義來表示兩個以上參數的函數。比如，(lambda (x) (lambda (y) y)) 就可以表示一個兩個參數的函數，它傳回第二個參數。不過當它被調用的時候，你需要兩層調用，就像這樣：
(((lambda (x) (lambda (y) y)) 1) 2)
;; => 2
雖然看起來醜一點，但是它讓我們的解釋器達到終極的簡單。簡單對于設計程式語言的人是至關重要的。一開頭就追求複雜的設計，往往導緻一堆糾纏不清的問題。
lambda calculus 不同于普通語言的另外一個特點就是它沒有數字等基本的資料類型，是以你不能直接用 lambda calculus 來計算像 (+ 1 2) 這樣的表達式。但是有意思的是，數字卻可以被 lambda calculus 的三個基本元素“編碼”(encoding) 出來。這種編碼可以用來表示自然數，布爾類型，pair，list，以至于所有的資料結構。它還可以表示 if 條件語句等複雜的文法結構。常見的一種這樣的編碼叫做 Church encoding。是以 lambda calculus 其實可以産生出幾乎所有程式語言的功能。中國的古話“三生萬物”，也許就是這個意思。
求值順序，call-by-name, call-by-value
當解釋一個程式的時候，我們可以有好幾種不同的“求值順序”(evaluation order)。這有點像周遊二叉樹有好幾種不同的順序一樣（中序，前序，後序）。隻不過這裡的順序更加複雜一些。比如下面的程式：
((lambda (x) (* x x)) (+ 1 2))
我們可以先執行最外層的調用，把 (+ 1 2) 傳遞進入函數，得到 (* (+ 1 2) (+ 1 2))。是以求值順序是：
((lambda (x) (* x x)) (+ 1 2))
=> (* (+ 1 2) (+ 1 2))
=> (* 3 (+ 1 2))
=> (* 3 3)
=> 9
但是我們也可以先算出 (+ 1 2) 的結果，然後再把它傳進這個函數。是以求值順序是：
((lambda (x) (* x x)) (+ 1 2))
=> ((lambda (x) (* x x)) 3)
=> (* 3 3)
=> 9
我們把第一種方式叫做 call-by-name (CBN)，因為它把參數的“名字”（也就是表達式自己）傳進函數。我們把第二種方式叫做 call-by-value (CBV)，因為它先把參數的名字進行解釋，得到它們的“值”之後，才把它們傳進函數。
這兩種解釋方式的效率是不一樣的。從上面的例子，你可以看出 CBN 比 CBV 多出了一步。為什麼呢？因為函數 (lambda (x) (* x x)) 裡面有兩個 x，是以 (+ 1 2) 被傳進函數的時候被複制了一份。之後我們需要對它的每一拷貝都進行一次解釋，是以 (+ 1 2) 被計算了兩次！
鑒于這個原因，幾乎所有的程式語言都采用 CBV，而不是 CBN。CBV 常常被叫做“strict”或者“applicative order”。雖然 CBN 效率低下，與它等價的一種順序 call-by-need 卻沒有這個問題。call-by-need 的基本原理是對 CBN 中被拷貝的表達式進行“共享”和“記憶”。當一個表達式的一個拷貝被計算過了之後，其它的拷貝自動得到它的值，進而避免重複求值。call-by-need 也叫“lazy evaluation”，它是 Haskell 語言所用的語義。
求值順序不隻停留于 call-by-name, call-by-value, call-by-need。人們還設計了很多種其它的求值順序，雖然它們大部分都不能像 call-by-value 和 call-by-need 這麼實用。
完整的 lambda calculus 解釋器
下面是我們今天要完成的解釋器，它隻有39行（不包括空行和注釋）。你可以先留意一下各個部分的注釋，它們标注各個部件的名稱，并且有少許講解。這個解釋器實作的是 CBV 順序的 lambda calculus，外加基本的算術。加入基本算術的原因是為了可以讓初學者寫出比較有趣一點的程式，不至于一開頭就被迫去學 Church encoding。
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; 以下三個定義 env0, ent-env, lookup 是對環境（environment）的基本操作：
;; 空環境
(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) x]
[else (cdr p)]))))
;; 閉包的資料結構定義，包含一個函數定義 f 和它定義時所在的環境
(struct Closure (f env))
;; 解釋器的遞歸定義（接受兩個參數，表達式 exp 和環境 env）
;; 共 5 種情況（變量，函數，調用，數字，算術表達式）
(define interp1
(lambda (exp env)
(match exp ; 模式比對 exp 的以下情況（分支）
[(? symbol? x) (lookup x env)] ; 變量
[(? number? x) x] ; 數字
[`(lambda (,x) ,e) ; 函數
(Closure exp env)]
[`(,e1 ,e2) ; 調用
(let ([v1 (interp1 e1 env)]
[v2 (interp1 e2 env)])
(match v1
[(Closure `(lambda (,x) ,e) env1)
(interp1 e (ext-env x v2 env1))]))]
[`(,op ,e1 ,e2) ; 算術表達式
(let ([v1 (interp1 e1 env)]
[v2 (interp1 e2 env)])
(match op
['+ (+ v1 v2)]
['- (- v1 v2)]
['* (* v1 v2)]
['/ (/ v1 v2)]))])))
;; 解釋器的“使用者界面”函數。它把 interp1 包裝起來，掩蓋第二個參數，初始值為 env0 (define interp
(lambda (exp)
(interp1 exp env0)))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
測試例子
這裡有一些測試的例子。你最好先玩一下再繼續往下看，或者自己寫一些新的例子。學習程式的最好辦法就是玩弄這個程式，給它一些輸入，觀察它的行為。有時候這比任何語言的描述都要直覺和清晰。
(interp '(+ 1 2))
;; => 3
(interp '(* 2 3))
;; => 6
(interp '(* 2 (+ 3 4)))
;; => 14
(interp '(* (+ 1 2) (+ 3 4)))
;; => 21
(interp '(((lambda (x) (lambda (y) (* x y))) 2) 3))
;; => 6
(interp '((lambda (x) (* 2 x)) 3))
;; => 6
(interp '((lambda (y) (((lambda (y) (lambda (x) (* y 2))) 3) 0)) 4))
;; => 6
;; (interp '(1 2))
;; => match: no matching clause for 1
在接下來的幾節，我們來看看這個解釋器裡主要的分支（match）表達式的各種情況。
對基本算術操作的解釋
算術操作在解釋器裡是最簡單也是最“基礎”的東西，因為它們不能再被細分為更小的元素了。是以在接觸函數，調用等複雜的結構之前，我們來看一看對算術操作的處理。以下就是這個解釋器裡處理基本算術的部分，它是 interp1 的最後一個分支。
(match exp
... ...
[`(,op ,e1 ,e2)
(let ([v1 (interp1 e1 env)] ; 遞歸調用 interp1 自己，得到 e1 的值
[v2 (interp1 e2 env)]) ; 遞歸調用 interp1 自己，得到 e2 的值
(match op ; 分支：處理操作符 op 的 4 種情況
['+ (+ v1 v2)] ; 如果是加号，輸出結果為 (+ v1 v2)
['- (- v1 v2)] ; 如果是減号，乘号，除号，相似的處理
['* (* v1 v2)]
['/ (/ v1 v2)]))])
你可以看到它幾乎跟剛才寫的電腦一模一樣，不過現在 interp1 的調用多了一個參數 env 而已。這個 env 是什麼，我們下面很快就講。
變量和函數
我想用兩個小節來簡單介紹一下變量，函數和環境。稍後的幾節我們再來看它們是如何實作的。
變量(variable)的産生是數學史上的最大突破之一。因為變量可以被綁定到不同的值，進而使得 函數的實作成為可能。比如數學函數 f(x) = x * 2，其中 x 是一個變量，它把輸入的值傳遞到函數的主體“x * 2”裡面。如果沒有變量，函數就不可能實作。
對變量的最基本的操作是對它的“綁定”（binding）和“取值”（evaluate）。什麼是綁定呢？拿上面的函數 f(x) 作為例子吧。當 x 等于 1 的時候，f(x) 的值是 2，而當 x 等于 2 的時候，f(x) 的值是 4。在上面的句子裡，我們對 x 進行了兩次綁定。第一次 x 被綁定到了 1，第二次被綁定到了 2。你可以把“綁定”了解成這樣一個動作，就像當你把插頭插進電源插座的那一瞬間。插頭的插腳就是 f(x) 裡面的那個 x，而 x * 2 裡面的 x，則是電線的另外一端。是以當你把插頭插進插座，電流就通過這根電線到達另外一端。如果電線導電性能良好，兩頭的電壓應該幾乎相等。有點跑題了…… 反正隻要記住一點：綁定就是插進插座的那個“動作”。
那麼“取值”呢？再想一下前面的例子，當我們用伏特表測電線另外一端的電壓的時候，我們就是在對這個變量進行取值。有時候這種取值的過程不是那麼明顯，比如電流如果驅動了風扇的電動機。雖然電線的另外一頭沒有顯示電壓，其實電流已經作用于電動機的輸入端子，進入線圈。是以你也可以說其實是電動機在對變量進行取值。
環境
我們的解釋器是一個挺笨的程式，它隻能一步一步的做事情。比如，當它需要求 f(1) 的值的時候，它做以下兩步操作：1) 把 x 綁定到 1; 2) 進入 f 的函數體對 x * 2 進行求值。這就像一個人做出這兩個動作：1)把插頭插進插座，2) 走到電線的另外一頭測量它的電壓，并且把結果乘以 2。在第一步和第二步之間，我們如何記住 x 的值呢？它必須被傳遞到那個用來處理函數體的遞歸解釋器裡面。這就是為什麼我們需要“ 環境”，也就是 interp1 的第二個參數 env。
環境記錄變量的值，并且把它們傳遞到它們的“可見區域”，用術語說就叫做“作用域”(scope)。通常作用域是整個函數體，但是有一個例外，就是當函數體内有嵌套的函數定義的時候，内部的那個函數如果有同樣的參數名，那麼外層的參數名就會被“屏蔽”（shadow）掉。這樣内部的函數體就看不到外層的參數了，隻看到它自己的。比如 (lambda (x) (lambda (x) (* x 2)))，裡面的那個 x 看到的就是内層函數的 x，而不是外層的。
在我們的解釋器裡，用于處理環境的主要部件如下：
;; 空環境
(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) x]
[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 擴充一個環境。比如，如果原來的環境是 ((y . 2) (z . 5)) 那麼 (ext-env x 1 ((y . 2) (z . 5)))，就會得到 ((x . 1) (y . 2) (z . 5))。也就是把 (x . 1) 放到最前面去。值得注意的一點是，環境被擴充以後其實是形成了一個新的環境，原來的環境并沒有被“改變”。比如上面紅色的部分就是原來的資料結構，隻不過它被放到另一個更大的結構裡面了。這叫做“函數式資料結構”。這個性質在我們的解釋器裡是至關重要的，因為當我們擴充了一個環境之後，其它部分的代碼仍然可以原封不動的通路擴充前的那個舊的環境。當我們講到調用的時候也許你就會發現這個性質的用處。
你也可以用另外的，更高效的資料結構（比如 splay tree）來表示環境。你甚至可以用函數來表示環境。唯一的要求就是，它是變量到值的“映射”(map)。你把 x 映射到 1，待會兒查詢 x 的值，它應該仍然是 1，而不會消失掉或者别的值。也就是說，這幾個函數要滿足這樣的一種“界面約定”：如果 e 是 (ext-env 'x 1 env) 傳回的環境，那麼 (lookup 'x e) 應該傳回 1。隻要滿足這樣的界面約定的函數都可以被叫做 ext-env 和 lookup，以至于可以它們用來完全替代這裡的函數而不會導緻其它代碼的修改。這叫做“抽象”，也就是“面向對象語言”的精髓所在。
對變量的解釋
了解了變量，函數和環境，讓我們來看看解釋器對變量的操作，也就是 interp1 的 match 的第一種情況。它非常簡單，就是在環境中查找變量的值。這裡的 (? symbol? x) 是一個特殊的模式，它使用 Scheme 函數 symbol? 來判斷輸入是否比對，如果是的就把它綁定到 x，查找它的值，然後傳回這個值。
[(? symbol? x) (lookup x env)]
注意由于我們的解釋器是遞歸的，是以這個值也許會被傳回到更高層的表達式，比如 (* x 2)。
對數字的解釋
對數字的解釋也很簡單。由于在 Scheme 裡面名字 '2 就是數字 2（我認為這是 Scheme 設計上的一個小錯誤），是以我們不需要對數字的名字做特殊的處理，把它們原封不動的傳回。
[(? number? x) x]
對函數的解釋
對函數的解釋是一個比較難說清楚的問題。由于函數體内也許會含有外層函數的參數，比如 (lambda (y) (lambda (x) (* y 2))) 裡面的 y 是外層函數的參數，卻出現在内層函數定義中。如果内層函數被作為值傳回，那麼 (* y 2) 就會跑到 y 的作用域以外。是以我們必須把函數做成“ 閉包”(closure)。閉包是一種特殊的資料結構，它由兩個元素組成：函數的定義和目前的環境。是以我們對 (lambda (x) e) 這樣一個函數的解釋就是這樣：
[`(lambda (,x) ,e)
(Closure exp env)]
注意這裡的 exp 就是 `(lambda (,x) ,e) 自己。我們隻是把它包裝了一下，把它與目前的環境一起放到一個資料結構(閉包)裡，并不進行任何複雜的運算。這裡我們的閉包用的是一個 Racket 的 struct 結構，也就是一個記錄類型(record)。你也可以用其它形式來表示閉包，比如有些解釋器教程提倡用函數來表示閉包。其實用什麼形式都無所謂，隻要能存儲 exp 和 env 的值。我比較喜歡使用 struct，因為它的界面簡單清晰。
為什麼需要儲存目前的環境呢？因為當這個函數被作為一個值傳回的時候，我們必須記住裡面的外層函數的參數的綁定。比如，(lambda (y) (lambda (x) (* y 2)))。當它被作用于 1 之後，我們會得到内層的函數 (lambda (x) (* y 2))。當這個函數被經過一陣周折之後再被調用的時候，y 應該等于幾呢？正确的做法應該是等于1。這種把外層參數的值記錄在内層函數的閉包裡的做法，叫做“lexical scoping”或者“static scoping”。
如果你不做閉包，而是把函數體直接傳回，那麼在 (lambda (x) (* y 2)) 被調用的位置，你可能會另外找到一個 y，進而使用它的值。在調用的時候“動态”解析變量的做法，叫做“dynamic scoping”。事實證明 dynamic scoping 的做法是嚴重錯誤的，它導緻了早期語言裡面出現的各種很難發現的bug。 很多早期的語言是 dynamic scoping，就是因為它們隻儲存了函數的代碼，而沒有儲存它定義處的環境。這樣要簡單一些，但是帶來太多的麻煩。早期的 Lisp，現在的 Emacs Lisp 和 TeX 就是使用 dynamic scoping 的語言。
為了示範 lexical scoping 和 dynamic scoping 的差別。你可以在我們的解釋器裡執行以下代碼：
(interp '((lambda (y) (( (lambda (y) (lambda (x) (* y 2))) 3) 0)) 4))
其中紅色的部分就是上面提到的例子。在這裡，(* y 2) 裡的 y，其實是最裡面的那個 (lambda (y) ...) 裡的。當紅色部分被作用于 3 之後。 (lambda (x) (* y 2)) 被作為一個值傳回。然後它被作用于 0（x 被綁定到 0，被忽略），是以 (* y 2) 應該等于 6。但是如果我們的解釋器是 dynamic scoping，那麼最後的結果就會等于 8。這是因為最外層的 y 開頭被綁定到了 4，而 dynamic scoping 沒有記住内層的 y 的值，是以使用了外層那個 y 的值。
為什麼 Lexical scoping 更好呢？你可以從很簡單的直覺來了解。當你構造一個“内部函數”的時候，如果它引用了外面的變量，比如這個例子裡的 y，那麼從外層的 y 到這個函數的内部，出現了一條“信道”（channel）。你可以把這個内部函數想象成一個電路元件，它的内部有一個節點 y 連接配接到一根從外部來的電線 y。當這個元件被傳回，就像這個元件被挖出來送到别的地方去用。但是在它被使用的地方（調用），這個 y 節點應該從哪裡得到輸入呢？顯然你不應該使用調用處的某個 y，因為這個 y 和之前的那個 y，雖然都叫 y，卻不是“同一個 y”，也就是同名異義。它們甚至可以代表不同的類型的東西。是以這個 y 應該仍然連接配接原來的那根 y 電線。當這個内部元件移動的時候，就像這跟電線被無限的延長，但是它始終連接配接到原來的節點。
對函數調用的解釋
好，我們終于到了最後的關頭，函數調用。函數調用都是 (e1 e2) 這樣的形式，是以我們需要先分别求出 e1 和 e2 的值。這跟基本運算的時候需要先求出兩個操作數的值相似。
函數調用就像把一個電器的插頭插進插座，使它開始運轉。比如，當 (lambda (x) (* x 2)) 被作用于 1 時，我們把 x 綁定到 1，然後解釋它的函數體 (* x 2)。但是這裡有一個問題，如果函數體内有未綁定的變量，它應該取什麼值呢？從上面閉包的讨論，你已經知道了，其實操作數 e1 被求值之後應該是一個閉包，是以它的裡面應該有未綁定變量的值。是以，我們就把這個閉包中儲存的環境(env1)取出來，擴充它，把 x 綁定到 v2，然後用這個擴充後的環境來解釋函數體。
是以函數調用的代碼如下：
[`(,e1 ,e2)
(let ([v1 (interp1 e1 env)]
[v2 (interp1 e2 env)])
(match v1
[(Closure `(lambda (,x) ,e) env1) ; 用模式比對的方式取出閉包裡的各個子結構
(interp1 e (ext-env x v2 env1))] ; 在 閉包的環境中把 x 綁定到 v2，解釋函數體
))]
你可能會奇怪，那麼解釋器的環境 env 難道這裡就不用了嗎？是的。我們通過 env 來計算 e1 和 e2 的值，是因為 e1 和 e2 裡面的變量存在于“目前環境”。我們把 e1 裡面的環境 env1 取出來用于計算函數體，是因為函數體并不是在目前環境定義的，它的代碼在别的地方。如果我們用 env 來解釋函數體，那就成了 dynamic scoping。
實驗：你可以把 (interp1 e (ext-env x v2 env1)) 裡面的 env1 改成 env，再試試我們之前讨論過的代碼，它的輸出就會是 8：
(interp '((lambda (y) (( (lambda (y) (lambda (x) (* y 2))) 3) 0)) 4))
另外在這裡我們也看到環境用“函數式資料結構”表示的好處。閉包被調用時它的環境被擴充，但是這并不會影響原來的那個環境，我們得到的是一個 新的環境。是以當函數調用傳回之後，函數的參數綁定就自動“登出”了。如果你用一個非函數式的資料結構，在綁定參數時不生成新的環境，而是對已有環境進行指派，那麼這個指派操作就會永久性的改變原來環境的内容。是以你在函數傳回之後必須删除參數的綁定。這樣不但麻煩，而且在複雜的情況下幾乎不可能有效的控制。每一次當我使用指派操作來修改環境，最後都會出現意想不到的麻煩。是以在寫解釋器，編譯器的時候，我都隻使用函數式資料結構來表示環境。
總結
好了，這就算是我的解釋器入門教程的初稿了。如果有問題的話，歡迎給我發 email 指出: [email protected]。我會盡力改進。
另外需要指出的是，學會這個解釋器并不等于了解了程式語言的理論。是以在學會了這些之後，還是要看一些語義學的書，就像我這篇 部落格裡推薦的那本。
![D. Ehab the Xorcist(構造+思維)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)