賣了好久關子了，說要寫一個程序語言理論的入門讀物，可是一直沒有下筆。終于狠下心來兌現一部分承諾。今天就從解釋器講起吧。

解釋器是比較深入的內容。雖然我試圖從最基本的原理講起，盡量讓這篇文章不依賴于其它的知識，但是這篇教程并不是針對函數式編程的入門，所以我假設你已經學會了最基本的 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)。其實歸納法跟遞歸完全是一回事。

我們今天的解釋器就是一個遞歸程序。它接受一個表達式，遞歸的調用它自己來處理各個子表達式，然后把各個遞歸的結果組合在一起，形成最后的結果。這有點像二叉樹遍歷，只不過我們的數據結構（程序）比二叉樹復雜一些。

#p#

模式匹配和遞歸：一個簡單的計算器

既然計算器是一種最簡單的解釋器，那么我們為何不從計算器開始寫？下面就是一個計算器，它可以計算四則運算的表達式。這些表達式可以任意的嵌套，比如 ‘(* (+ 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 

一個計算器就是這么簡單。你可以試試這些例子，然后自己再做一些新的例子。

#p#

什么是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 這么實用。

#p#

完整的 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）表達式的各種情況。 

#p#

對基本算術操作的解釋

算術操作在解釋器里是最簡單也是最“基礎”的東西，因為它們不能再被細分為更小的元素了。所以在接觸函數，調用等復雜的結構之前，我們來看一看對算術操作的處理。以下就是這個解釋器里處理基本算術的部分，它是 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] 

#p#

對函數的解釋

對函數的解釋是一個比較難說清楚的問題。由于函數體內也許會含有外層函數的參數，比如 (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 指出: shredderyin@gmail.com。我會盡力改進。

另外需要指出的是，學會這個解釋器并不等于理解了程序語言的理論。所以在學會了這些之后，還是要看一些語義學的書，就像我這篇博客里推薦的那本。

原文鏈接：http://blog.sina.com.cn/s/blog_5d90e82f01018ge9.html