怎样写一个解释器
轉載: 怎樣寫一個解釋器
寫一個解釋器，通常是設計和實現程序語言的第一步。解釋器是簡單卻又深奧的東西，以至于好多人都不會寫，所以我決定寫一篇這方面的入門讀物。
雖然我試圖從最基本的原理講起，盡量不依賴于其它知識，但這并不是一本編程入門教材。我假設你已經理解 Scheme 語言，以及基本的編程技巧（比如遞歸）。如果你完全不了解這些，那我建議你讀一下 SICP 的第一，二章，或者 HtDP 的前幾章，習題可以不做。注意不要讀太多書，否則你就回不來了 ;-) 當然你也可以直接讀這篇文章，有不懂的地方再去查資料。
實現語言容易犯的一個錯誤，就是一開頭就試圖去實現很復雜的語言（比如 JavaScript 或者 Python）。這樣你很快就會因為這些語言的復雜性，以及各種歷史遺留的設計問題而受到挫折，最后不了了之。學習實現語言，最好是從最簡單，最干凈的語言開始，迅速寫出一個可用的解釋器。之后再逐步往里面添加特性，同時保持正確。這樣你才能有條不紊地構造出復雜的解釋器。
因為這個原因，這篇文章只針對一個很簡單的語言，名叫“R2”。它可以作為一個簡單的計算器用，還具有變量定義，函數定義和調用等功能。
我們的工具：Racket
本文的解釋器是用 Scheme 語言實現的。Scheme 有很多的“實現”，這里我用的實現叫做 Racket，它可以在這里免費下載。為了讓程序簡潔，我用了一點點 Racket 的模式匹配（pattern matching）功能。我對 Scheme 的實現沒有特別的偏好，但 Racket 方便易用，適合教學。如果你用其它的 Scheme 實現，可能得自己做一些調整。
Racket 具有宏（macro），所以它其實可以變成很多種語言。如果你之前用過 DrRacket，那它的“語言設置”可能被你改成了 R5RS 之類的。所以如果下面的程序不能運行，你可能需要檢查一下 DrRacket 的“語言設置”，把 Language 設置成 “Racket”。
Racket 允許使用方括號而不只是圓括號，所以你可以寫這樣的代碼：
方括號跟圓括號可以互換，唯一的要求是方括號必須和方括號匹配。通常我喜歡用方括號來表示“無動作”的數據（比如上面的 [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) 的值的時候，它分成兩步操作：
1.把 x 綁定到 1，這樣函數體內才能看見這個綁定。
2.進入 f 的函數體，對 x * 2 進行求值。
這就像一個人做出這兩個動作：
1.把插頭插進插座 。
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 函數”的語言。出于教學的考慮，這個解釋器并沒有考慮實用的需求，所以它并不能作為“工業應用”。在這里，我指出它的一些不足之處。
1.缺少必要的語言構造。我們的語言里缺少好些實用語言必須的構造：遞歸，數組，賦值操作，字符串，自定義數據結構，…… 作為一篇基礎性的讀物，我不能把這些都加進來。如果你對這些有興趣，可以看看其它書籍，或者等待我的后續作品。
2.不合法代碼的檢測和報告。你也許發現了，這個解釋器的 match 表達式，全都假定了輸入都是合法的程序，它并沒有檢查不合法的情況。如果你給它一個不合法的程序，它的行為會變得詭異。一個實用的解釋器，必須加入對代碼格式進行全面檢測，報告不合法的代碼結構。
3.低效率的數據結構。在 association list 里面查找變量，是線性的復雜度。當程序有很多變量的時候就有性能問題。一個實用的解釋器，需要更高效的數據結構。這種數據結構不一定非得是函數式的。你也可以用非函數式的數據結構（比如哈希表），經過一定的改造，達到同樣的性質，卻具有更高的效率。 ? 另外，你還可以把環境轉化成一個數組。給環境里的每個變量分配一個下標（index），在這個數組里就可以找到它的值。如果你用數組表示環境，那么這個解釋器就向編譯器邁進了一步。
4.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 上面進行分支匹配。這樣解釋器不用擔心歧義問題，而且會帶來效率的提升。
總結
- 上一篇： rpgmakermv导出html,Rpg
- 下一篇： 《挑战程序设计竞赛》2.2 贪心法-其它