這是一篇解釋器的入門教程掀宋。雖然我試圖從最基本的原理講起婚夫，盡量讓這篇文章不依賴于其它知識激才，但是這篇教程并不是針對編程的入門知識鳍贾，所以我假設你已經(jīng)學會了最基本的 Scheme 和函數(shù)式編程梦抢。我不是很推崇函數(shù)式編程般贼，但它里面確實包含了很重要的一些方法。如果你完全不了解這些，可以讀一下 SICP 的第一哼蛆，二章（或者接下去讀 The Little Schemer)蕊梧。當然你也可以繼續(xù)讀這篇文章，有不懂的地方再去查資料腮介。我在這里也會講遞歸和模式匹配的原理肥矢。如果你已經(jīng)了解這些東西，這里的內(nèi)容也許可以加深你的理解叠洗。
解釋器是一種簡單卻又深奧的東西甘改，以至于好多人都不會寫，或者自認為會寫卻又不真正的會寫惕味。在這個領域里有一些歷史遺留下來的誤解楼誓，以至于很少有人真正的知道如何寫出正確的解釋器。很多“語言專家”或者“邏輯學家”的解釋器代碼里面有各種各樣的錯誤名挥，卻又以謬傳謬疟羹，搞得無比復雜。這誤解的淵源之深禀倔，真是一言難盡榄融。
你必須從最簡單的語言開始，逐步增加語言的復雜度救湖，才能構(gòu)造出正確的解釋器愧杯。這篇文章就是告訴你如何寫出一個最簡單的語言 (lambda calculus) 的解釋器，并且?guī)в谢镜牡乃阈g功能鞋既，可以作為一個高級計算器來使用力九。
一般的程序語言課程往往從語法分析(parsing)開始，折騰 lex 和 yacc 等麻煩卻不中用的工具邑闺，解決一些根本不需要存在的問題跌前。Parsing 的作用其實只是把字符串解碼成程序的語法樹（AST）結(jié)構(gòu)放可。麻煩好久得到了 AST 之后翎卓，真正的困難才開始！而很多人在寫完 parser 之后就已經(jīng)倒下了仇哆。鑒于這個原因靶衍，這里我用所謂的“S-expression”來表示程序的語法樹（AST）結(jié)構(gòu)灾炭。S-expression （加上 Lisp 對它發(fā)自“本能”的處理能力）讓我們可以直接跳過 parse 的步驟，進入關鍵的主題：語義(semantics)颅眶。
這里用的 Scheme 實現(xiàn)是 Racket蜈出。為了讓程序簡潔，我使用了 Racket 的模式匹配（pattern matching）帚呼。我對 Racket 沒有特別的好感掏缎。但它安裝比較方便皱蹦，而且是免費的。如果你用其它的 Scheme 實現(xiàn)的話眷蜈，恐怕要自己做一些調(diào)整沪哺。
首先我們來談一下解釋器是什么。說白了解釋器跟計算器差不多酌儒。它們都接受一個“表達式”辜妓，輸出一個 “結(jié)果”。比如忌怎，得到 '(+ 1 2) 之后就輸出 3籍滴。不過解釋器的表達式要比計算器的表達式復雜一些。解釋器接受的表達式叫做“程序”榴啸，而不只是簡單的算術表達式孽惰。從本質(zhì)上講，每個程序都是一臺機器的“描述”鸥印，而解釋器就是在“模擬”這臺機器的運轉(zhuǎn)勋功，也就是在進行“計算”。所以從某種意義上講库说，解釋器就是計算的本質(zhì)狂鞋。當然，不同的解釋器就會帶來不同的計算潜的。
需要注意的是骚揍，我們的解釋器接受的參數(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ì)實際上是“任何用于處理語言的機器”辛掠。
解釋器一般都是“遞歸程序”谢谦。之所以是遞歸的原因释牺，在于它處理的數(shù)據(jù)結(jié)構(gòu)（程序）本身是“遞歸定義”的結(jié)構(gòu)。算術表達式就是一個這樣的結(jié)構(gòu)回挽，比如：'(* (+ 1 2) (* (- 9 6) 4))没咙。每一個表達式里面可以含有子表達式，子表達式里面還可以有子表達式千劈，如此無窮無盡的嵌套祭刚。看似很復雜墙牌，其實它的定義不過是：
“算術表達式”有兩種形式：
一個數(shù)
一個'(op e1 e2)這樣的結(jié)構(gòu)（其中e1和e2是兩個“算術表達式”）
看出來哪里在“遞歸”了嗎涡驮？我們本來在定義“算術表達式”這個概念，而它的定義里面用到了“算術表達式”這個概念本身喜滨！這就構(gòu)造了一個“回路”捉捅，讓我們可以生成任意深度的表達式。
很多其它的數(shù)據(jù)虽风，包括自然數(shù)棒口，都是可以用遞歸來定義的。比如常見的對自然數(shù)的定義是：
“自然數(shù)”有兩種形式：
零
某個“自然數(shù)”的后繼
看到了嗎焰情？“自然數(shù)”的定義里面出現(xiàn)了它自己陌凳！這就是為什么我們有無窮多個自然數(shù)。
所以可以說遞歸是無所不在的内舟，甚至有人說遞歸就是自然界的終極原理合敦。遞歸的數(shù)據(jù)總是需要遞歸的程序來處理。雖然遞歸有時候表現(xiàn)為另外的形式验游，比如循環(huán)(loop)充岛，但是“遞歸”這個概念比“循環(huán)”更廣泛一些。有很多遞歸程序不能用循環(huán)來表達耕蝉，比如我們今天要寫的解釋器就是一個遞歸程序崔梗，它就不能用循環(huán)來表達。所以寫出正確的遞歸程序垒在，對于設計任何系統(tǒng)都是至關重要的蒜魄。其實遞歸的概念不限于程序設計。在數(shù)學證明里面有個概念叫“歸納法”(induction)场躯，比如“數(shù)學歸納法”(mathematical induction)谈为。其實歸納法跟遞歸完全是一回事。
我們今天的解釋器就是一個遞歸程序踢关。它接受一個表達式伞鲫，遞歸的調(diào)用它自己來處理各個子表達式，然后把各個遞歸的結(jié)果組合在一起签舞，形成最后的結(jié)果秕脓。這有點像二叉樹遍歷柒瓣，只不過我們的數(shù)據(jù)結(jié)構(gòu)（程序）比二叉樹復雜一些。
既然計算器是一種最簡單的解釋器吠架，那么我們?yōu)楹尾粡挠嬎闫鏖_始寫芙贫？下面就是一個計算器，它可以計算四則運算的表達式诵肛。這些表達式可以任意的嵌套屹培，比如'(* (+ 1 2) (+ 3 4))。我想從這個簡單的例子來講一下模式匹配(pattern matching) 和遞歸 (recursion) 的原理怔檩。
下面就是這個計算器的代碼褪秀。它接受一個表達式，輸出一個數(shù)字作為結(jié)果薛训，正如上一節(jié)所示媒吗。
(definecalc
(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 語句是一個模式匹配遇伞。它的形式是這樣：
(matchexp
[模式 結(jié)果]
[模式 結(jié)果]
? ...? ...
)? ?
它根據(jù)表達式 exp 的“結(jié)構(gòu)”來進行“分支”操作辙喂。每一個分支由兩部分組成，左邊的是一個“模式”鸠珠，右邊的是一個結(jié)果巍耗。左邊的模式在匹配之后可能會綁定一些變量，它們可以在右邊的表達式里面使用渐排。
一般說來炬太，數(shù)據(jù)的“定義”有多少種情況，用來處理它的“模式”就有多少情況驯耻。比如算術表達式有兩種情況亲族，數(shù)字或者(op e1 e2)。所以用來處理它的match語句就有兩種模式可缚∧跛“你所有的情況，我都能處理”城看，這就是“窮舉法”。窮舉的思想非常重要杏慰，你漏掉的任何一種情況测柠，都非常有可能帶來麻煩炼鞠。所謂的“數(shù)學歸納法”，就是這種窮舉法在自然數(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))索烹。當它們一一對應之后工碾，這些名字就自動被綁定到實際數(shù)據(jù)里相應位置的值。模式里面不但可以含有名字百姓，也可以含有具體的數(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。它們應該是數(shù)字地沮。
你注意到我們在什么地方使用了遞歸嗎嗜浮？如果你再看一下“算術表達式”的定義：
“算術表達式”有兩種形式：
一個數(shù)
一個'(op e1 e2)這樣的結(jié)構(gòu)（其中e1和e2是兩個“算術表達式”）
你就會發(fā)現(xiàn)這個定義里面“遞歸”的地方就是e1和e2羡亩，所以calc在e1和e2上面遞歸的調(diào)用自己。如果你在數(shù)據(jù)定義的每個遞歸處都進行遞歸危融，那么你的遞歸程序就會窮舉所有的情況畏铆。
之后，我們根據(jù)操作符op的不同吉殃，對這兩個值v1和v2分別進行操作辞居。如果op是加號'+，我們就調(diào)用 Scheme 的加法操作蛋勺，作用于v1和v2瓦灶，并且返回運算所得的值。如果是減號迫卢，乘號倚搬，除號，我們也進行相應的操作乾蛤，返回它們的值每界。
所以你就可以得到如下的測試結(jié)果：
(calc'(+ 1 2))
;; =>3
(calc'(* 2 3))
;; =>6
(calc'(* (+ 1 2) (+ 3 4)))
;; =>21
一個計算器就是這么簡單。你可以試試這些例子家卖，然后自己再做一些新的例子眨层。
現(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)建解釋器的最關鍵步驟就是把這三個東西搞清楚官扣。構(gòu)造任何一個語言的解釋器一般都是從這三個元素開始，在確保它們完全正確之后才慢慢加入其它的元素羞福。
有一個很簡單的思維方式可以讓你直接看到這三元素的本質(zhì)惕蹄。記得我說過，每個程序都是一個“機器的描述”嗎？所以每個 lambda calculus 的表達式也是一個機器的描述焊唬。這種機器跟電子線路非常相似恋昼。lambda calculus 的程序和機器有這樣的一一對應關系：一個變量就是一根導線。一個函數(shù)就是某種電子器件的“樣板”赶促，有它自己的輸入和輸出端子，自己的邏輯挟炬。一個調(diào)用都是在設計中插入一個電子器件的“實例”鸥滨，把它的輸入端子連接到某些已有的導線，這些導線被叫做“參數(shù)”谤祖。所以一個 lambda calculus 的解釋器實際上就是一個電子線路的模擬器婿滓。所以如果你聽說有些芯片公司開始用類似 Haskell 的語言（比如 Bluespec System Verilog）來設計硬件，也就不奇怪了粥喜。
需要注意的是凸主，跟一般語言不同，lambda calculus 的函數(shù)只有一個參數(shù)额湘。這其實不是一個嚴重的限制卿吐，因為 lambda calculus 的函數(shù)可以被作為值傳遞 (這叫 first-class function)，所以你可以用嵌套的函數(shù)定義來表示兩個以上參數(shù)的函數(shù)锋华。比如嗡官，(lambda (x) (lambda (y) y))就可以表示一個兩個參數(shù)的函數(shù)，它返回第二個參數(shù)毯焕。不過當它被調(diào)用的時候衍腥，你需要兩層調(diào)用，就像這樣：
(((lambda (x) (lambda (y) y))1)2)
;; =>2
雖然看起來丑一點纳猫，但是它讓我們的解釋器達到終極的簡單婆咸。簡單對于設計程序語言的人是至關重要的。一開頭就追求復雜的設計芜辕，往往導致一堆糾纏不清的問題尚骄。
lambda calculus 不同于普通語言的另外一個特點就是它沒有數(shù)字等基本的數(shù)據(jù)類型，所以你不能直接用 lambda calculus 來計算像(+ 1 2)這樣的表達式物遇。但是有意思的是乖仇，數(shù)字卻可以被 lambda calculus 的三個基本元素“編碼”(encoding) 出來。這種編碼可以用來表示自然數(shù)询兴，布爾類型乃沙，pair，list诗舰，以至于所有的數(shù)據(jù)結(jié)構(gòu)警儒。它還可以表示 if 條件語句等復雜的語法結(jié)構(gòu)。常見的一種這樣的編碼叫做 Church encoding。所以 lambda calculus 其實可以產(chǎn)生出幾乎所有程序語言的功能蜀铲。中國的古話“三生萬物”边琉，也許就是這個意思。
求值順序记劝，call-by-name, call-by-value
當解釋一個程序的時候变姨，我們可以有好幾種不同的“求值順序”(evaluation order)。這有點像遍歷二叉樹有好幾種不同的順序一樣（中序厌丑，前序定欧，后序）。只不過這里的順序更加復雜一些怒竿。比如下面的程序：
((lambda(x) (* x x)) (+12))
我們可以先執(zhí)行最外層的調(diào)用砍鸠，把 (+ 1 2) 傳遞進入函數(shù)，得到 (* (+ 1 2) (+ 1 2))耕驰。所以求值順序是：
((lambda (x) (* x x)) (+12))
=>(*(+12) (+12))
=>(*3(+12))
=>(*33)
=>9
但是我們也可以先算出 (+ 1 2) 的結(jié)果爷辱，然后再把它傳進這個函數(shù)。所以求值順序是：
((lambda (x) (* x x)) (+12))
=>((lambda (x) (* x x)) 3)
=>(*33)
=>9
我們把第一種方式叫做 call-by-name (CBN)朦肘，因為它把參數(shù)的“名字”（也就是表達式自己）傳進函數(shù)饭弓。我們把第二種方式叫做 call-by-value (CBV)，因為它先把參數(shù)的名字進行解釋厚骗，得到它們的“值”之后示启，才把它們傳進函數(shù)。
這兩種解釋方式的效率是不一樣的领舰。從上面的例子夫嗓，你可以看出 CBN 比 CBV 多出了一步。為什么呢冲秽？因為函數(shù)(lambda (x) (* x x))里面有兩個x舍咖，所以(+ 1 2)被傳進函數(shù)的時候被復制了一份。之后我們需要對它的每一拷貝都進行一次解釋锉桑，所以(+ 1 2)被計算了兩次排霉！
鑒于這個原因，幾乎所有的程序語言都采用 CBV民轴，而不是 CBN攻柠。CBV 常常被叫做“strict”或者“applicative order”。雖然 CBN 效率低下后裸，與它等價的一種順序 call-by-need 卻沒有這個問題瑰钮。call-by-need 的基本原理是對 CBN 中被拷貝的表達式進行“共享”和“記憶”。當一個表達式的一個拷貝被計算過了之后微驶，其它的拷貝自動得到它的值浪谴，從而避免重復求值开睡。call-by-need 也叫“l(fā)azy evaluation”，它是 Haskell 語言所用的語義苟耻。
求值順序不只停留于 call-by-name, call-by-value, call-by-need篇恒。人們還設計了很多種其它的求值順序，雖然它們大部分都不能像 call-by-value 和 call-by-need 這么實用凶杖。
下面是我們今天要完成的解釋器胁艰，它只有39行（不包括空行和注釋）。你可以先留意一下各個部分的注釋智蝠，它們標注各個部件的名稱蝗茁，并且有少許講解。這個解釋器實現(xiàn)的是 CBV 順序的 lambda calculus寻咒，外加基本的算術。加入基本算術的原因是為了可以讓初學者寫出比較有趣一點的程序颈嚼，不至于一開頭就被迫去學 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
[(notp) 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ù)字，算術表達式）
(define interp1
(lambda (expenv)
(matchexp; 模式匹配exp的以下情況（分支）
? ? ? [(? symbol? x) (lookup x env)]? ? ? ? ? ? ? ? ? ? ; 變量
? ? ? [(? number? x) x]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ; 數(shù)字
? ? ? [`(lambda (,x) ,e)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ; 函數(shù)
(Closureexpenv)]
? ? ? [`(,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)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ; 算術表達式
(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)
(interp1expenv0)))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
這里有一些測試的例子宣吱。你最好先玩一下再繼續(xù)往下看窃这，或者自己寫一些新的例子。學習程序的最好辦法就是玩弄這個程序征候，給它一些輸入杭攻，觀察它的行為。有時候這比任何語言的描述都要直觀和清晰疤坝。
(interp'(+ 1 2))
;; => 3
(interp '(*23))
;; =>6
(interp'(* 2 (+ 3 4)))
;; => 14
(interp '(* (+12) (+34)))
;; =>21
(interp'(((lambda (x) (lambda (y) (* x y))) 2) 3))
;; => 6
(interp '((lambda (x) (*2x))3))
;; =>6
(interp'((lambda (y) (((lambda (y) (lambda (x) (* y 2))) 3) 0)) 4))
;; => 6
;; (interp '(12))
;; => match: no matching clausefor1
在接下來的幾節(jié)兆解，我們來看看這個解釋器里主要的分支（match）表達式的各種情況。
算術操作在解釋器里是最簡單也是最“基礎”的東西卒煞，因為它們不能再被細分為更小的元素了痪宰。所以在接觸函數(shù)，調(diào)用等復雜的結(jié)構(gòu)之前，我們來看一看對算術操作的處理衣撬。以下就是這個解釋器里處理基本算術的部分乖订，它是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是什么，我們下面很快就講铜邮。
我想用兩個小節(jié)來簡單介紹一下變量仪召，函數(shù)和環(huán)境。稍后的幾節(jié)我們再來看它們是如何實現(xiàn)的松蒜。
變量(variable)的產(chǎn)生是數(shù)學史上的最大突破之一扔茅。因為變量可以被綁定到不同的值，從而使得函數(shù)的實現(xiàn)成為可能秸苗。比如數(shù)學函數(shù)f(x) = x*2召娜，其中x是一個變量，它把輸入的值傳遞到函數(shù)的主體x*2里面惊楼。如果沒有變量玖瘸，函數(shù)就不可能實現(xiàn)。
對變量的最基本的操作是對它的“綁定”（binding）和“取值”（evaluate）胁后。什么是綁定呢店读？拿上面的函數(shù)f(x)作為例子吧。當x等于 1 的時候攀芯，f(x)的值是 2屯断，而當x等于 2 的時候，f(x)的值是 4侣诺。在上面的句子里殖演，我們對x進行了兩次綁定。第一次x被綁定到了 1年鸳，第二次被綁定到了 2趴久。你可以把“綁定”理解成這樣一個動作，就像當你把插頭插進電源插座的那一瞬間搔确。插頭的插腳就是f(x)里面的那個x彼棍，而x*2里面的x灭忠，則是電線的另外一端。所以當你把插頭插進插座座硕，電流就通過這根電線到達另外一端弛作。如果電線導電性能良好，兩頭的電壓應該幾乎相等华匾。有點跑題了…… 反正只要記住一點：綁定就是插進插座的那個“動作”映琳。
那么“取值”呢？再想一下前面的例子蜘拉，當我們用伏特表測電線另外一端的電壓的時候萨西，我們就是在對這個變量進行取值。有時候這種取值的過程不是那么明顯旭旭，比如電流如果驅(qū)動了風扇的電動機谎脯。雖然電線的另外一頭沒有顯示電壓，其實電流已經(jīng)作用于電動機的輸入端子持寄，進入線圈穿肄。所以你也可以說其實是電動機在對變量進行取值。
我們的解釋器是一個挺笨的程序际看，它只能一步一步的做事情。比如矢否，當它需要求f(1)的值的時候仲闽，它做以下兩步操作：1) 把x綁定到 1; 2) 進入f的函數(shù)體對x*2進行求值。這就像一個人做出這兩個動作：1)把插頭插進插座僵朗，2) 走到電線的另外一頭測量它的電壓赖欣，并且把結(jié)果乘以 2。在第一步和第二步之間验庙，我們?nèi)绾斡涀的值呢顶吮？它必須被傳遞到那個用來處理函數(shù)體的遞歸解釋器里面。這就是為什么我們需要“環(huán)境”粪薛，也就是interp1的第二個參數(shù)env悴了。
環(huán)境記錄變量的值，并且把它們傳遞到它們的“可見區(qū)域”违寿，用術語說就叫做“作用域”(scope)湃交。通常作用域是整個函數(shù)體，但是有一個例外藤巢，就是當函數(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
[(notp) 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ì)在我們的解釋器里是至關重要的，因為當我們擴展了一個環(huán)境之后属拾，其它部分的代碼仍然可以原封不動的訪問擴展前的那個舊的環(huán)境。當我們講到調(diào)用的時候也許你就會發(fā)現(xiàn)這個性質(zhì)的用處逞频。
你也可以用另外的栋齿，更高效的數(shù)據(jù)結(jié)構(gòu)（比如 splay tree）來表示環(huán)境。你甚至可以用函數(shù)來表示環(huán)境基协。唯一的要求就是澜驮，它是變量到值的“映射”(map)惋鸥。你把x映射到 1，待會兒查詢x的值耐量，它應該仍然是 1滤港，而不會消失掉或者別的值。也就是說选浑，這幾個函數(shù)要滿足這樣的一種“界面約定”：如果e是(ext-env 'x 1 env)返回的環(huán)境模叙，那么(lookup 'x e)應該返回 1。只要滿足這樣的界面約定的函數(shù)都可以被叫做ext-env和lookup，以至于可以它們用來完全替代這里的函數(shù)而不會導致其它代碼的修改叔壤。這叫做“抽象”口叙，也就是“面向?qū)ο笳Z言”的精髓所在妄田。
了解了變量驮捍，函數(shù)和環(huán)境东且，讓我們來看看解釋器對變量的操作本讥，也就是interp1的match的第一種情況拷沸。它非常簡單，就是在環(huán)境中查找變量的值综慎。這里的(? symbol? x)是一個特殊的模式勤庐，它使用 Scheme 函數(shù)symbol?來判斷輸入是否匹配愉镰，如果是的就把它綁定到x，查找它的值录择，然后返回這個值隘竭。
[(? symbol? x) (lookup x env)]
注意由于我們的解釋器是遞歸的讼渊，所以這個值也許會被返回到更高層的表達式爪幻，比如(* x 2)。
對數(shù)字的解釋也很簡單仇轻。由于在 Scheme 里面名字 '2 就是數(shù)字 2（我認為這是 Scheme 設計上的一個小錯誤）奶甘，所以我們不需要對數(shù)字的名字做特殊的處理臭家，把它們原封不動的返回吭产。
[(? number? x) x]
對函數(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(tǒng)的作用域以外草描。所以我們必須把函數(shù)做成“閉包”(closure)策严。閉包是一種特殊的數(shù)據(jù)結(jié)構(gòu)妻导，它由兩個元素組成：函數(shù)的定義和當前的環(huán)境。所以我們對(lambda (x) e)這樣一個函數(shù)的解釋就是這樣：
[`(lambda(,x) ,e)
? (Closure exp env)]
注意這里的exp就是`(lambda (,x) ,e)自己术浪。我們只是把它包裝了一下胰苏，把它與當前的環(huán)境一起放到一個數(shù)據(jù)結(jié)構(gòu)(閉包)里份名，并不進行任何復雜的運算僵腺。這里我們的閉包用的是一個 Racket 的 struct 結(jié)構(gòu)壶栋，也就是一個記錄類型(record)贵试。你也可以用其它形式來表示閉包，比如有些解釋器教程提倡用函數(shù)來表示閉包豌蟋。其實用什么形式都無所謂梧疲，只要能存儲exp和env的值。我比較喜歡使用struct缭受，因為它的界面簡單清晰米者。
為什么需要保存當前的環(huán)境呢宇智？因為當這個函數(shù)被作為一個值返回的時候普筹，我們必須記住里面的外層函數(shù)的參數(shù)的綁定。比如妻顶，(lambda (y) (lambda (x) (* y 2)))讳嘱。當它被作用于 1 之后酿愧，我們會得到內(nèi)層的函數(shù)(lambda (x) (* y 2))嬉挡。當這個函數(shù)被經(jīng)過一陣周折之后再被調(diào)用的時候庞钢，y應該等于幾呢？正確的做法應該是等于1颜懊。這種把外層參數(shù)的值記錄在內(nèi)層函數(shù)的閉包里的做法，叫做“l(fā)exical scoping”或者“static scoping”匠璧。
如果你不做閉包夷恍，而是把函數(shù)體直接返回炊苫，那么在(lambda (x) (* y 2))被調(diào)用的位置侨艾，你可能會另外找到一個y唠梨，從而使用它的值。在調(diào)用的時候“動態(tài)”解析變量的做法茬故，叫做“dynamic scoping”磺芭。事實證明 dynamic scoping 的做法是嚴重錯誤的醉箕，它導致了早期語言里面出現(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) ...)里的晴楔。當紅色部分被作用于 3 之后税弃。(lambda (x) (* y 2))被作為一個值返回。然后它被作用于 0（x被綁定到 0幔翰，被忽略）导匣，所以(* y 2)應該等于 6茸时。但是如果我們的解釋器是 dynamic scoping可都，那么最后的結(jié)果就會等于 8渠牲。這是因為最外層的y開頭被綁定到了 4，而 dynamic scoping 沒有記住內(nèi)層的y的值瘫镇，所以使用了外層那個y的值铣除。
為什么 Lexical scoping 更好呢尚粘？你可以從很簡單的直覺來理解。當你構(gòu)造一個“內(nèi)部函數(shù)”的時候秉继，如果它引用了外面的變量尚辑，比如這個例子里的y盔腔，那么從外層的y到這個函數(shù)的內(nèi)部铲觉，出現(xiàn)了一條“信道”（channel）撵幽。你可以把這個內(nèi)部函數(shù)想象成一個電路元件盐杂，它的內(nèi)部有一個節(jié)點y連接到一根從外部來的電線y。當這個元件被返回厉斟，就像這個元件被挖出來送到別的地方去用擦秽。但是在它被使用的地方（調(diào)用）感挥，這個y節(jié)點應該從哪里得到輸入呢越败？顯然你不應該使用調(diào)用處的某個y究飞，因為這個y和之前的那個y，雖然都叫y媒峡，卻不是“同一個y”丝蹭，也就是同名異義奔穿。它們甚至可以代表不同的類型的東西贱田。所以這個y應該仍然連接原來的那根y電線嘴脾。當這個內(nèi)部元件移動的時候译打，就像這跟電線被無限的延長奏司，但是它始終連接到原來的節(jié)點韵洋。
好，我們終于到了最后的關頭食拜，函數(shù)調(diào)用负甸。函數(shù)調(diào)用都是(e1 e2)這樣的形式惑惶，所以我們需要先分別求出e1和e2的值带污。這跟基本運算的時候需要先求出兩個操作數(shù)的值相似香到。
函數(shù)調(diào)用就像把一個電器的插頭插進插座，使它開始運轉(zhuǎn)充易。比如盹靴，當(lambda (x) (* x 2))被作用于 1 時稿静，我們把x綁定到 1改备，然后解釋它的函數(shù)體(* x 2)蔓倍。但是這里有一個問題偶翅，如果函數(shù)體內(nèi)有未綁定的變量聚谁，它應該取什么值呢垦巴？從上面閉包的討論骤宣，你已經(jīng)知道了憔披，其實操作數(shù)e1被求值之后應該是一個閉包芬膝，所以它的里面應該有未綁定變量的值。所以筹误，我們就把這個閉包中保存的環(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里面的變量存在于“當前環(huán)境”浅役。我們把e1里面的環(huán)境env1取出來用于計算函數(shù)體觉既，是因為函數(shù)體并不是在當前環(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)境闽颇。所以當函數(shù)調(diào)用返回之后，函數(shù)的參數(shù)綁定就自動“注銷”了兵多。如果你用一個非函數(shù)式的數(shù)據(jù)結(jié)構(gòu)，在綁定參數(shù)時不生成新的環(huán)境橄仆，而是對已有環(huán)境進行賦值剩膘，那么這個賦值操作就會永久性的改變原來環(huán)境的內(nèi)容。所以你在函數(shù)返回之后必須刪除參數(shù)的綁定盆顾。這樣不但麻煩怠褐，而且在復雜的情況下幾乎不可能有效的控制。每一次當我使用賦值操作來修改環(huán)境您宪，最后都會出現(xiàn)意想不到的麻煩奈懒。所以在寫解釋器，編譯器的時候宪巨，我都只使用函數(shù)式數(shù)據(jù)結(jié)構(gòu)來表示環(huán)境磷杏。
在懂得了這里講述的基本的解釋器構(gòu)造之后，下一步可以做什么呢捏卓？其實從這個基本的解釋器原型极祸，你可以進一步發(fā)展出很多內(nèi)容，比如：
在這個解釋器里加一些構(gòu)造怠晴，比如遞歸和狀態(tài)遥金，你就可以得到一個完整的程序語言的解釋器，比如 Scheme 或者 Python蒜田。
對這個解釋器進行“抽象”汰规，你就可以對程序進行類型推導。感興趣的話可以參考我實現(xiàn)的這個 Hindley-Milner系統(tǒng)物邑，或者 Python 類型推導溜哮。
對這個解釋器進行一些改變，就可以得到一個非常強大的 online partial evaluator色解，可以用于編譯器優(yōu)化茂嗓。
另外需要指出的是，學會這個解釋器并不等于理解了程序語言的理論科阎。所以在學會了這些之后述吸，還是要看一些語義學的書。
