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