寫(xiě)一個(gè)解釋器八匠，通常是設(shè)計(jì)和實(shí)現(xiàn)程序語(yǔ)言的第一步遭笋。解釋器是簡(jiǎn)單卻又深?yuàn)W的東西秽褒，以至于好多人都不會(huì)寫(xiě)壶硅，所以我決定寫(xiě)一篇這方面的入門讀物。
雖然我試圖從最基本的原理講起销斟，盡量不依賴于其它知識(shí)庐椒，但這并不是一本編程入門教材。我假設(shè)你已經(jīng)理解 Scheme 語(yǔ)言票堵，以及基本的編程技巧（比如遞歸）扼睬。如果你完全不了解這些逮栅，那我建議你讀一下?SICP?的第一悴势，二章，或者?HtDP?的前幾章措伐，習(xí)題可以不做特纤。注意不要讀太多書(shū)，否則你就回不來(lái)了 ;-) 當(dāng)然你也可以直接讀這篇文章侥加，有不懂的地方再去查資料捧存。
實(shí)現(xiàn)語(yǔ)言容易犯的一個(gè)錯(cuò)誤，就是一開(kāi)頭就試圖去實(shí)現(xiàn)很復(fù)雜的語(yǔ)言（比如 JavaScript 或者 Python）担败。這樣你很快就會(huì)因?yàn)檫@些語(yǔ)言的復(fù)雜性昔穴，以及各種歷史遺留的設(shè)計(jì)問(wèn)題而受到挫折，最后不了了之提前。學(xué)習(xí)實(shí)現(xiàn)語(yǔ)言吗货，最好是從最簡(jiǎn)單，最干凈的語(yǔ)言開(kāi)始狈网，迅速寫(xiě)出一個(gè)可用的解釋器宙搬。之后再逐步往里面添加特性笨腥，同時(shí)保持正確。這樣你才能有條不紊地構(gòu)造出復(fù)雜的解釋器勇垛。
因?yàn)檫@個(gè)原因脖母，這篇文章只針對(duì)一個(gè)很簡(jiǎn)單的語(yǔ)言，名叫“R2”闲孤。它可以作為一個(gè)簡(jiǎn)單的計(jì)算器用谆级，還具有變量定義，函數(shù)定義和調(diào)用等功能讼积。
我們的工具：Racket
本文的解釋器是用 Scheme 語(yǔ)言實(shí)現(xiàn)的哨苛。Scheme 有很多的“實(shí)現(xiàn)”，這里我用的實(shí)現(xiàn)叫做 Racket币砂，它可以在這里免費(fèi)下載建峭。為了讓程序簡(jiǎn)潔，我用了一點(diǎn)點(diǎn) Racket 的模式匹配（pattern matching）功能决摧。我對(duì) Scheme 的實(shí)現(xiàn)沒(méi)有特別的偏好亿蒸，但 Racket 方便易用，適合教學(xué)掌桩。如果你用其它的 Scheme 實(shí)現(xiàn)边锁，可能得自己做一些調(diào)整。
Racket 具有宏（macro）波岛，所以它其實(shí)可以變成很多種語(yǔ)言茅坛。如果你之前用過(guò) DrRacket，那它的“語(yǔ)言設(shè)置”可能被你改成了 R5RS 之類的则拷。所以如果下面的程序不能運(yùn)行贡蓖，你可能需要檢查一下 DrRacket 的“語(yǔ)言設(shè)置”，把 Language 設(shè)置成 “Racket”煌茬。
Racket 允許使用方括號(hào)而不只是圓括號(hào)斥铺，所以你可以寫(xiě)這樣的代碼：
(let([x1][y2])(+xy))
方括號(hào)跟圓括號(hào)可以互換，唯一的要求是方括號(hào)必須和方括號(hào)匹配坛善。通常我喜歡用方括號(hào)來(lái)表示“無(wú)動(dòng)作”的數(shù)據(jù)（比如上面的?[x 1],?[y 2]）晾蜘，這樣可以跟函數(shù)調(diào)用和其它具有“動(dòng)作”的代碼，產(chǎn)生“視覺(jué)差”眠屎。這對(duì)于代碼的可讀性是一個(gè)改善剔交，因?yàn)榈教幎际菆A括號(hào)的話，確實(shí)有點(diǎn)太單調(diào)改衩，容易打瞌睡岖常。
另外，Racket 程序的最上面都需要加上像?#lang?racket?這樣的語(yǔ)言選擇標(biāo)記燎字，這樣 Racket 才可以知道你想用哪個(gè)語(yǔ)言變種腥椒。
解釋器是什么
準(zhǔn)備工作就到這里“⒄現(xiàn)在我來(lái)談一下，解釋器到底是什么笼蛛。說(shuō)白了洒放，解釋器跟計(jì)算器差不多。解釋器是一個(gè)函數(shù)滨砍，你輸入一個(gè)“表達(dá)式”往湿，它就輸出一個(gè) “值”，像這樣：
比如惋戏，你輸入表達(dá)式?'(+ 1 2)?领追，它就輸出值，整數(shù)3响逢。表達(dá)式是一種“表象”或者“符號(hào)”绒窑，而值卻更加接近“本質(zhì)”或者“意義”。我們“解釋”了符號(hào)舔亭，得到它的意義些膨，這也許就是為什么它叫做“解釋器”。
需要注意的是钦铺，表達(dá)式是一個(gè)數(shù)據(jù)結(jié)構(gòu)订雾，而不是一個(gè)字符串。我們用一種叫“S 表達(dá)式”（S-expression）的結(jié)構(gòu)來(lái)存儲(chǔ)表達(dá)式矛洞。比如表達(dá)式?'(+ 1 2)?其實(shí)是一個(gè)鏈表（list）洼哎，它里面的內(nèi)容是三個(gè)符號(hào)（symbol）：+,?1?和?2，而不是字符串"(+ 1 2)"沼本。
從 S 表達(dá)式這樣的“結(jié)構(gòu)化數(shù)據(jù)”里提取信息噩峦，方便又可靠，而從字符串里提取信息擅威，麻煩而且容易出錯(cuò)壕探。Scheme（Lisp）語(yǔ)言里面大量使用結(jié)構(gòu)化數(shù)據(jù)，少用字符串郊丛，這是 Lisp 系統(tǒng)比 Unix 系統(tǒng)先進(jìn)的地方之一。
從計(jì)算理論的角度講瞧筛，每個(gè)程序都是一臺(tái)機(jī)器的“描述”厉熟，而解釋器就是在“模擬”這臺(tái)機(jī)器的運(yùn)轉(zhuǎn)，也就是在進(jìn)行“計(jì)算”较幌。所以從某種意義上講揍瑟，解釋器就是計(jì)算的本質(zhì)。當(dāng)然乍炉，不同的解釋器就會(huì)帶來(lái)不同的計(jì)算绢片。
CPU 也是一個(gè)解釋器滤馍，它專門解釋執(zhí)行機(jī)器語(yǔ)言。如果你深刻理解了解釋器底循，就可以從本質(zhì)上看出各種 CPU 的設(shè)計(jì)為什么是那個(gè)樣子巢株，它們有什么優(yōu)缺點(diǎn)，而不只是被動(dòng)的作為它們的使用者熙涤。
抽象語(yǔ)法樹(shù)（Abstract Syntax Tree）
用 S 表達(dá)式所表示的代碼阁苞，本質(zhì)上是一種叫做“樹(shù)”（tree）的數(shù)據(jù)結(jié)構(gòu)。更具體一點(diǎn)祠挫，這叫做“抽象語(yǔ)法樹(shù)”（Abstract Syntax Tree那槽，簡(jiǎn)稱 AST）。下文為了簡(jiǎn)潔等舔，我們省略掉“抽象”兩個(gè)字骚灸，就叫它“語(yǔ)法樹(shù)”。
跟普通的樹(shù)結(jié)構(gòu)一樣慌植，語(yǔ)法樹(shù)里的節(jié)點(diǎn)逢唤，要么是一個(gè)“葉節(jié)點(diǎn)”，要么是一顆“子樹(shù)”涤浇。葉節(jié)點(diǎn)是不能再細(xì)分的“原子”鳖藕，比如數(shù)字，字符串只锭，操作符著恩，變量名。而子樹(shù)是可以再細(xì)分的“結(jié)構(gòu)”蜻展，比如算術(shù)表達(dá)式喉誊，函數(shù)定義，函數(shù)調(diào)用纵顾，等等伍茄。
舉個(gè)簡(jiǎn)單的例子，表達(dá)式?'(* (+ 1 2) (+ 3 4))施逾，就對(duì)應(yīng)如下的語(yǔ)法樹(shù)結(jié)構(gòu)：
其中敷矫，*，兩個(gè)+汉额，1曹仗，2，3蠕搜，4?都是葉節(jié)點(diǎn)怎茫，而那三個(gè)紅色節(jié)點(diǎn)，都表示子樹(shù)結(jié)構(gòu)：'(+ 1 2)妓灌，'(+ 3 4)轨蛤，'(* (+ 1 2) (+ 3 4))蜜宪。
樹(shù)遍歷算法
在基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)課程里，我們都學(xué)過(guò)二叉樹(shù)的遍歷操作祥山，也就是所謂先序遍歷圃验，中序遍歷和后序遍歷。語(yǔ)法樹(shù)跟二叉樹(shù)枪蘑，其實(shí)沒(méi)有很大區(qū)別损谦，所以你也可以在它上面進(jìn)行遍歷。解釋器的算法岳颇，就是在語(yǔ)法樹(shù)上的一種遍歷操作照捡。由于這個(gè)淵源關(guān)系，我們先來(lái)做一個(gè)遍歷二叉樹(shù)的練習(xí)话侧。做好了之后栗精，我們就可以把這段代碼擴(kuò)展成一個(gè)解釋器。
這個(gè)練習(xí)是這樣：寫(xiě)出一個(gè)函數(shù)瞻鹏，名叫tree-sum悲立，它對(duì)二叉樹(shù)進(jìn)行“求和”，把所有節(jié)點(diǎn)里的數(shù)加在一起新博，返回它們的和薪夕。舉個(gè)例子，(tree-sum '((1 2) (3 4)))赫悄，執(zhí)行后應(yīng)該返回?10原献。注意：這是一顆二叉樹(shù)，所以不會(huì)含有長(zhǎng)度超過(guò) 2 的子樹(shù)埂淮，你不需要考慮像?((1 2) (3 4 5))?這類情況姑隅。需要考慮的例子是像這樣：(1 2)，(1 (2 3)),?((1 2) 3)?((1 2) (3 4))倔撞，……
（為了達(dá)到最好的學(xué)習(xí)效果讲仰，你最好試一下寫(xiě)出這個(gè)函數(shù)再繼續(xù)往下看。）
好了痪蝇，希望你得到了跟我差不多的結(jié)果鄙陡。我的代碼是這個(gè)樣子：
#langracket(definetree-sum(lambda(exp)(matchexp; 對(duì)輸入exp進(jìn)行模式匹配[(?number?x)x]; exp是一個(gè)數(shù)x嗎？如果是霹俺，那么返回這個(gè)數(shù)x[`(,e1,e2); exp是一個(gè)含有兩棵子樹(shù)的中間節(jié)點(diǎn)嗎柔吼？(let([v1(tree-sume1)]; 遞歸調(diào)用tree-sum自己，對(duì)左子樹(shù)e1求值[v2(tree-sume2)]); 遞歸調(diào)用tree-sum自己丙唧，對(duì)右子樹(shù)e2求值(+v1v2))]))); 返回左右子樹(shù)結(jié)果v1和v2的和
你可以通過(guò)以下的例子來(lái)測(cè)試它的正確性：
(tree-sum'(12));; => 3(tree-sum'(1(23)));; => 6(tree-sum'((12)3));; => 6(tree-sum'((12)(34)));; => 10
（完整的代碼和示例，可以在這里下載觅玻。）
這個(gè)算法很簡(jiǎn)單想际，我們可以把它用文字描述如下：
如果輸入?exp?是一個(gè)數(shù)培漏，那就返回這個(gè)數(shù)。
否則如果?exp?是像?(,e1 ,e2)?這樣的子樹(shù)胡本，那么分別對(duì)?e1?和?e2?遞歸調(diào)用?tree-sum牌柄，進(jìn)行求和，得到?v1?和?v2侧甫，然后返回?v1 + v2?的和珊佣。
你自己寫(xiě)出來(lái)的代碼，也許用了 if 或者 cond 語(yǔ)句來(lái)進(jìn)行分支披粟，而我的代碼里面使用的是 Racket 的模式匹配（match）咒锻。這個(gè)例子用 if 或者 cond 其實(shí)也可以，但我之后要把這代碼擴(kuò)展成一個(gè)解釋器守屉，所以提前使用了 match惑艇。這樣跟后面的代碼對(duì)比的時(shí)候，就更容易看出規(guī)律來(lái)拇泛。接下來(lái)滨巴，我就簡(jiǎn)單講一下這個(gè) match 表達(dá)式的工作原理。
模式匹配
現(xiàn)在不得不插入一點(diǎn) Racket 的技術(shù)細(xì)節(jié)俺叭，如果你已經(jīng)學(xué)會(huì)使用 Racket 的模式匹配恭取，可以跳過(guò)這一節(jié)。你也可以通過(guò)閱讀 Racket 模式匹配的文檔來(lái)代替這一節(jié)熄守。但我建議你不要讀太多文檔蜈垮，因?yàn)槲医酉氯ブ挥玫胶苌俚哪Ｊ狡ヅ涔δ埽野阉鼈兌冀忉屓缦隆?/p>
模式匹配的形式一般是這樣：
(matchx[模式結(jié)果][模式結(jié)果]......)
它先對(duì)?x?求值柠横，然后根據(jù)值的結(jié)構(gòu)來(lái)進(jìn)行分支窃款。每個(gè)分支由兩部分組成，左邊是一個(gè)模式牍氛，右邊是一個(gè)結(jié)果晨继。整個(gè) match 語(yǔ)句的語(yǔ)義是這樣：從上到下依次考慮，找到第一個(gè)可以匹配?x的值的模式搬俊，返回它右邊的結(jié)果紊扬。左邊的模式在匹配之后，可能會(huì)綁定一些變量唉擂，這些變量可以在右邊的表達(dá)式里使用餐屎。
模式匹配是一種分支語(yǔ)句，它在邏輯上就是 Scheme（Lisp） 的?cond?表達(dá)式玩祟，或者 Java 的嵌套條件語(yǔ)句?if ... else if ... else ...腹缩。然而跟條件語(yǔ)句里的“條件”不同，每條 match 語(yǔ)句左邊的模式，可以準(zhǔn)確而形象地描述數(shù)據(jù)結(jié)構(gòu)的形狀藏鹊，而且可以在匹配的同時(shí)润讥，對(duì)結(jié)構(gòu)里的成員進(jìn)行“綁定”。這樣我們可以在右邊方便的訪問(wèn)結(jié)構(gòu)成員盘寡，而不需要使用訪問(wèn)函數(shù)（accessor）或者?foo.x?這樣的屬性語(yǔ)法（attribute）楚殿。而且模式可以有嵌套的子結(jié)構(gòu)，所以它能夠一次性的表示復(fù)雜的數(shù)據(jù)結(jié)構(gòu)竿痰。
舉個(gè)實(shí)在點(diǎn)的例子脆粥。我的代碼里用了這樣一個(gè) match 表達(dá)式：
(matchexp[(?number?x)x][`(,e1,e2)(let([v1(tree-sume1)][v2(tree-sume2)])(+v1v2))])
第二行里面的?'(,e1 ,e2)?是一個(gè)模式（pattern），它被用來(lái)匹配?exp?的值影涉。如果?exp?是'(1 2)变隔，那么它與'(,e1 ,e2)匹配的時(shí)候，就會(huì)把?e1?綁定到?'1常潮，把?e2?綁定到?'2弟胀。這是因?yàn)樗鼈兘Y(jié)構(gòu)相同：
`(,e1,e2)'(12)
說(shuō)白了，模式就是一個(gè)可以含有“名字”（像?e1?和?e2）的結(jié)構(gòu)喊式，像?'(,e1 ,e2)孵户。我們拿這個(gè)帶有名字的結(jié)構(gòu)，去匹配實(shí)際數(shù)據(jù)岔留，像?'(1 2)夏哭。當(dāng)它們一一對(duì)應(yīng)之后，這些名字就被綁定到數(shù)據(jù)里對(duì)應(yīng)位置的值献联。
第一行的“模式”比較特殊竖配，(? number? x)?表示的，其實(shí)是一個(gè)普通的條件判斷里逆，相當(dāng)于(number? exp)进胯，如果這個(gè)條件成立，那么它把?exp?的值綁定到?x原押，這樣右邊就可以用?x?來(lái)指代?exp胁镐。對(duì)于無(wú)法細(xì)分的結(jié)構(gòu)（比如數(shù)字，布爾值）诸衔，你只能用這種方式來(lái)“匹配”盯漂。看起來(lái)有點(diǎn)奇怪笨农，不過(guò)習(xí)慣了就好了就缆。
模式匹配對(duì)解釋器和編譯器的書(shū)寫(xiě)相當(dāng)有用，因?yàn)槌绦虻恼Z(yǔ)法樹(shù)往往具有嵌套的結(jié)構(gòu)谒亦。不用模式匹配的話竭宰，往往要寫(xiě)冗長(zhǎng)空郊，復(fù)雜，不直觀的代碼羞延，才能描述出期望的結(jié)構(gòu)渣淳。而且由于結(jié)構(gòu)的嵌套比較深脾还，很容易漏掉邊界情況伴箩，造成錯(cuò)誤。模式匹配可以直觀的描述期望的結(jié)構(gòu)鄙漏，避免漏掉邊界情況嗤谚，而且可以方便的訪問(wèn)結(jié)構(gòu)成員。
由于這個(gè)原因怔蚌，很多源于 ML 的語(yǔ)言（比如 OCaml巩步，Haskell）都有模式匹配的功能。因?yàn)?ML（Meta-Language）原來(lái)設(shè)計(jì)的用途桦踊，就是用來(lái)實(shí)現(xiàn)程序語(yǔ)言的椅野。Racket 的模式匹配也是部分受了 ML 的啟發(fā)，實(shí)際上它們的原理是一模一樣的籍胯。
好了竟闪，樹(shù)遍歷的練習(xí)就做到這里。然而這跟解釋器有什么關(guān)系呢杖狼？下面我們只把它改一下炼蛤，就可以得到一個(gè)簡(jiǎn)單的解釋器。
一個(gè)計(jì)算器
計(jì)算器也是一種解釋器蝶涩，只不過(guò)它只能處理算術(shù)表達(dá)式理朋。我們的下一個(gè)目標(biāo)，就是寫(xiě)出一個(gè)計(jì)算器绿聘。如果你給它?'(* (+ 1 2) (+ 3 4))嗽上，它就輸出?21∠ㄈ粒可不要小看這個(gè)計(jì)算器兽愤，稍后我們把它稍加改造，就可以得到一個(gè)更多功能的解釋器鲜屏。
上面的代碼里烹看，我們利用遞歸遍歷，對(duì)樹(shù)里的數(shù)字求和洛史。那段代碼里惯殊，其實(shí)已經(jīng)隱藏了一個(gè)解釋器的框架。你觀察一下也殖，一個(gè)算術(shù)表達(dá)式?'(* (+ 1 2) (+ 3 4))土思，跟二叉樹(shù)?'((1 2) (3 4))?有什么不同务热？發(fā)現(xiàn)沒(méi)有，這個(gè)算術(shù)表達(dá)式比起二叉樹(shù)己儒，只不過(guò)在每個(gè)子樹(shù)結(jié)構(gòu)里多出了一個(gè)操作符：一個(gè)?*?和兩個(gè)?+?崎岂。它不再是一棵二叉樹(shù)，而是一種更通用的樹(shù)結(jié)構(gòu)闪湾。
這點(diǎn)區(qū)別冲甘，也就帶來(lái)了二叉樹(shù)求和與解釋器算法的區(qū)別。對(duì)二叉樹(shù)進(jìn)行求和的時(shí)候途样，在每個(gè)子樹(shù)節(jié)點(diǎn)江醇，我們都做加法。而對(duì)表達(dá)式進(jìn)行解釋的時(shí)候何暇，在每一個(gè)子樹(shù)節(jié)點(diǎn)陶夜，我們不一定進(jìn)行加法。根據(jù)子樹(shù)的“操作符”不同裆站，我們可能會(huì)選擇加条辟，減，乘宏胯，除四種操作羽嫡。
好了，下面就是這個(gè)計(jì)算器的代碼胳嘲。它接受一個(gè)表達(dá)式厂僧，輸出一個(gè)數(shù)字作為結(jié)果。
#langracket; 聲明用 Racket 語(yǔ)言(definecalc(lambda(exp)(matchexp; 分支匹配：表達(dá)式的兩種情況[(?number?x)x]; 是數(shù)字了牛，直接返回[`(,op,e1,e2); 匹配提取操作符op和兩個(gè)操作數(shù)e1,e2(let([v1(calce1)]; 遞歸調(diào)用 calc 自己颜屠，得到 e1 的值[v2(calce2)]); 遞歸調(diào)用 calc 自己，得到 e2 的值(matchop; 分支匹配：操作符 op 的 4 種情況['+(+v1v2)]; 如果是加號(hào)鹰祸，輸出結(jié)果為 (+ v1 v2)['-(-v1v2)]; 如果是減號(hào)甫窟，乘號(hào)，除號(hào)蛙婴，相似的處理['*(*v1v2)]['/(/v1v2)]))])))
你可以得到如下的結(jié)果：
(calc'(+12));; => 3(calc'(*23));; => 6(calc'(*(+12)(+34)));; => 21
（完整的代碼和示例粗井，可以在這里下載。）
跟之前的二叉樹(shù)求和代碼比較一下街图，你會(huì)發(fā)現(xiàn)它們驚人的相似浇衬，因?yàn)榻忉屍鞅緛?lái)就是一個(gè)樹(shù)遍歷算法。不過(guò)你發(fā)現(xiàn)它們有什么不同嗎餐济？它們的不同點(diǎn)在于：
算術(shù)表達(dá)式的模式里面耘擂，多出了一個(gè)“操作符”（op）葉節(jié)點(diǎn)：(,op ,e1 ,e2)
對(duì)子樹(shù) e1 和 e2 分別求值之后，我們不是返回?(+ v1 v2)絮姆，而是根據(jù)?op?的不同醉冤，返回不同的結(jié)果：
(matchop['+(+v1v2)]['-(-v1v2)]['*(*v1v2)]['/(/v1v2)])
最后你發(fā)現(xiàn)秩霍，一個(gè)算術(shù)表達(dá)式的解釋器，不過(guò)是一個(gè)稍加擴(kuò)展的樹(shù)遍歷算法蚁阳。
R2：一個(gè)很小的程序語(yǔ)言
實(shí)現(xiàn)了一個(gè)計(jì)算器铃绒，現(xiàn)在讓我們過(guò)渡到一種更強(qiáng)大的語(yǔ)言。為了方便稱呼螺捐，我給它起了一個(gè)萌萌噠名字颠悬，叫 R2。R2 比起之前的計(jì)算器归粉，只多出四個(gè)元素椿疗，它們分別是：變量，函數(shù)糠悼，綁定，調(diào)用浅乔。再加上之前介紹的算術(shù)操作倔喂，我們就得到一個(gè)很簡(jiǎn)單的程序語(yǔ)言，它只有5種不同的構(gòu)造靖苇。用 Scheme 的語(yǔ)法席噩，這5種構(gòu)造看起來(lái)就像這樣：
變量：x
函數(shù)：(lambda (x) e)
綁定：(let ([x e1]) e2)
調(diào)用：(e1 e2)
算術(shù)：(? e2 e2)
（其中，? 是一個(gè)算術(shù)操作符贤壁，可以選擇?+,?-,?*,?/?其中之一）
一般程序語(yǔ)言還有很多其它構(gòu)造悼枢，可是一開(kāi)頭就試圖去實(shí)現(xiàn)所有那些，只會(huì)讓人糊涂脾拆。最好是把這少數(shù)幾個(gè)東西搞清楚馒索，確保它們正確之后，才慢慢加入其它元素名船。
這些構(gòu)造的語(yǔ)義绰上，跟 Scheme 里面的同名構(gòu)造幾乎一模一樣。如果你不清楚什么是”綁定“渠驼，那你可以把它看成是普通語(yǔ)言里的”變量聲明“蜈块。
需要注意的是，跟一般語(yǔ)言不同迷扇，我們的函數(shù)只接受一個(gè)參數(shù)百揭。這不是一個(gè)嚴(yán)重的限制，因?yàn)樵谖覀兊恼Z(yǔ)言里蜓席，函數(shù)可以被作為值傳遞器一，也就是所謂“first-class function”。所以你可以用嵌套的函數(shù)定義來(lái)表示有兩個(gè)以上參數(shù)的函數(shù)瓮床。
舉個(gè)例子盹舞，?(lambda (x) (lambda (y) (+ x y)))?是個(gè)嵌套的函數(shù)定義产镐，它也可以被看成是有兩個(gè)參數(shù)（x?和?y）的函數(shù)，這個(gè)函數(shù)返回?x?和?y?的和踢步。當(dāng)這樣的函數(shù)被調(diào)用的時(shí)候癣亚，需要兩層調(diào)用，就像這樣：
(((lambda(x)(lambda(y)(+xy)))1)2);; => 3
這種做法在PL術(shù)語(yǔ)里面获印，叫做咖喱（currying）述雾。看起來(lái)啰嗦兼丰，但這樣我們的解釋器可以很簡(jiǎn)單玻孟。等我們理解了基本的解釋器，再實(shí)現(xiàn)真正的多參數(shù)函數(shù)也不遲鳍征。
另外黍翎，我們的綁定語(yǔ)法?(let ([x e1]) e2)，比起 Scheme 的綁定也有一些局限艳丛。我們的 let 只能綁定一個(gè)變量匣掸，而 Scheme 可以綁定多個(gè)，像這樣?(let ([x 1] [y 2]) (+ x y))氮双。這也不是一個(gè)嚴(yán)重的限制碰酝，因?yàn)槲覀兛梢詥乱稽c(diǎn)，用嵌套的 let 綁定：
(let([x1])(let([y2])(+xy)))
R2 的解釋器
下面是我們今天要完成的解釋器戴差，它可以運(yùn)行一個(gè) R2 程序送爸。你可以先留意一下各部分的注釋。
#langracket;;; 以下三個(gè)定義 env0, ext-env, lookup 是對(duì)環(huán)境（environment）的基本操作：;; 空環(huán)境(defineenv0'());; 擴(kuò)展暖释。對(duì)環(huán)境 env 進(jìn)行擴(kuò)展袭厂，把 x 映射到 v，得到一個(gè)新的環(huán)境(defineext-env(lambda(xvenv)(cons`(,x.,v)env)));; 查找饭入。在環(huán)境中 env 中查找 x 的值嵌器。如果沒(méi)找到就返回 #f(definelookup(lambda(xenv)(let([p(assqxenv)])(cond[(notp)#f][else(cdrp)]))));; 閉包的數(shù)據(jù)結(jié)構(gòu)定義，包含一個(gè)函數(shù)定義 f 和它定義時(shí)所在的環(huán)境(structClosure(fenv));; 解釋器的遞歸定義（接受兩個(gè)參數(shù)谐丢，表達(dá)式 exp 和環(huán)境 env）;; 共 5 種情況（變量爽航，函數(shù)，綁定乾忱，調(diào)用讥珍，數(shù)字，算術(shù)表達(dá)式）(defineinterp(lambda(expenv)(matchexp; 對(duì)exp進(jìn)行模式匹配[(?symbol?x); 變量(let([v(lookupxenv)])(cond[(notv)(error"undefined variable"x)][elsev]))][(?number?x)x]; 數(shù)字[`(lambda(,x),e); 函數(shù)(Closureexpenv)][`(let([,x,e1]),e2); 綁定(let([v1(interpe1env)])(interpe2(ext-envxv1env)))][`(,e1,e2); 調(diào)用(let([v1(interpe1env)][v2(interpe2env)])(matchv1[(Closure`(lambda(,x),e)env-save)(interpe(ext-envxv2env-save))]))][`(,op,e1,e2); 算術(shù)表達(dá)式(let([v1(interpe1env)][v2(interpe2env)])(matchop['+(+v1v2)]['-(-v1v2)]['*(*v1v2)]['/(/v1v2)]))])));; 解釋器的“用戶界面”函數(shù)窄瘟。它把 interp 包裝起來(lái)衷佃，掩蓋第二個(gè)參數(shù)，初始值為 env0(definer2(lambda(exp)(interpexpenv0)))
這里有一些測(cè)試?yán)樱?/p>
(r2'(+12));; => 3(r2'(*23));; => 6(r2'(*2(+34)));; => 14(r2'(*(+12)(+34)));; => 21(r2'((lambda(x)(*2x))3));; => 6(r2'(let([x2])(let([f(lambda(y)(*xy))])(f3))));; => 6(r2'(let([x2])(let([f(lambda(y)(*xy))])(let([x4])(f3)))));; => 6
（完整的代碼和示例蹄葱，可以在這里下載氏义。)
在接下來(lái)的幾節(jié)锄列，我們來(lái)仔細(xì)看看這個(gè)解釋器的各個(gè)部分。
對(duì)基本算術(shù)操作的解釋
算術(shù)操作一般都是程序里最基本的構(gòu)造惯悠，它們不能再被細(xì)分為多個(gè)步驟邻邮，所以我們先來(lái)看看對(duì)算術(shù)操作的處理。以下就是 R2 解釋器處理算術(shù)的部分克婶，它是?interp?的最后一個(gè)分支筒严。
(matchexp......[`(,op,e1,e2)(let([v1(interpe1env)]; 遞歸調(diào)用 interp 自己，得到 e1 的值[v2(interpe2env)]); 遞歸調(diào)用 interp 自己情萤，得到 e2 的值(matchop; 分支：處理操作符 op 的 4 種情況['+(+v1v2)]; 如果是加號(hào)相满，輸出結(jié)果為 (+ v1 v2)['-(-v1v2)]; 如果是減號(hào)斥杜，乘號(hào)，除號(hào)乍楚，相似的處理['*(*v1v2)]['/(/v1v2)]))])
你可以看到它幾乎跟剛才寫(xiě)的計(jì)算器一模一樣痛单，不過(guò)現(xiàn)在?interp?的調(diào)用多了一個(gè)參數(shù)?env?而已德撬。這個(gè)?env?是所謂“環(huán)境”银酬，我們下面很快就講末贾。
對(duì)數(shù)字的解釋
對(duì)數(shù)字的解釋很簡(jiǎn)單，把它們?cè)獠粍?dòng)返回就可以了勋陪。
[(? number? x) x]
變量和函數(shù)
變量和函數(shù)是解釋器里最麻煩的部分，所以我們來(lái)仔細(xì)看看硫兰。
變量（variable）的產(chǎn)生诅愚，是數(shù)學(xué)史上的最大突破之一。因?yàn)樽兞靠梢员唤壎ǖ讲煌闹到儆常瑥亩购瘮?shù)的實(shí)現(xiàn)成為可能违孝。比如數(shù)學(xué)函數(shù)?f(x) = x * 2，其中?x?是一個(gè)變量泳赋，它把輸入的值傳遞到函數(shù)體?x * 2?里面雌桑。如果沒(méi)有變量，函數(shù)就不可能實(shí)現(xiàn)祖今。
對(duì)變量最基本的操作校坑，是對(duì)它的“綁定”（binding）和“取值”（evaluate）。什么是綁定呢千诬？拿上面的函數(shù)?f(x)?作為例子耍目。當(dāng)我們調(diào)用?f(1)?時(shí)，函數(shù)體里面的?x?等于 1徐绑，所以?x * 2?的值是 2邪驮，而當(dāng)我們調(diào)用?f(2)?時(shí)，函數(shù)體里面的?x?等于 2傲茄，所以?x * 2?的值是 4毅访。這里沮榜，兩次對(duì)?f?的調(diào)用，分別對(duì)?x?進(jìn)行了兩次綁定喻粹。第一次?x?被綁定到了 1蟆融，第二次被綁定到了 2。
你可以把“綁定”理解成這樣一個(gè)動(dòng)作磷斧，就像當(dāng)你把插頭插進(jìn)電源插座的那一瞬間振愿。插頭的插腳就是?f(x)?里面的那個(gè)?x，而?x * 2?里面的?x弛饭，則是電線的另外一端冕末。所以當(dāng)你把插頭插進(jìn)插座，電流就通過(guò)這根電線到達(dá)另外一端侣颂。如果電線導(dǎo)電性能良好档桃，兩頭的電壓應(yīng)該相等。
環(huán)境
我們的解釋器只能一步一步的做事情憔晒。比如藻肄，當(dāng)它需要求?f(1)?的值的時(shí)候，它分成兩步操作：
把?x?綁定到 1拒担，這樣函數(shù)體內(nèi)才能看見(jiàn)這個(gè)綁定嘹屯。
進(jìn)入?f?的函數(shù)體，對(duì)?x * 2?進(jìn)行求值从撼。
這就像一個(gè)人做出這兩個(gè)動(dòng)作：
把插頭插進(jìn)插座 州弟。
到電線的另外一頭，測(cè)量它的電壓低零，并且把結(jié)果乘以 2婆翔。
在第一步和第二步之間，我們?nèi)绾斡涀?x?的值呢掏婶？通過(guò)所謂“環(huán)境”啃奴！我們用環(huán)境記錄變量的值，并且把它們傳遞到變量的“可見(jiàn)區(qū)域”雄妥。變量的可見(jiàn)區(qū)域最蕾，用術(shù)語(yǔ)說(shuō)叫做“作用域”（scope）。
在我們的解釋器里茎芭，用于處理環(huán)境的代碼如下：
;; 空環(huán)境(defineenv0'());; 對(duì)環(huán)境 env 進(jìn)行擴(kuò)展揖膜，把 x 映射到 v(defineext-env(lambda(xvenv)(cons`(,x.,v)env)));; 取值。在環(huán)境中 env 中查找 x 的值(definelookup(lambda(xenv)(let([p(assqxenv)])(cond[(notp)#f][else(cdrp)]))))
這里我們用一種最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)梅桩，Scheme 的 association list壹粟，來(lái)表示環(huán)境。Association list 看起來(lái)像這個(gè)樣子：((x . 1) (y . 2) (z . 5))。它是一個(gè)兩元組（pair）的鏈表趁仙，左邊的元素是 key洪添，右邊的元素是 value。寫(xiě)得直觀一點(diǎn)就是：
((x.1)(y.2)(z.5))
查表操作就是從頭到尾搜索雀费，如果左邊的 key 是要找的變量干奢，就返回整個(gè) pair。簡(jiǎn)單吧盏袄？效率很低忿峻，但是足夠完成我們現(xiàn)在的任務(wù)。
ext-env?函數(shù)擴(kuò)展一個(gè)環(huán)境辕羽。比如逛尚，如果原來(lái)的環(huán)境?env1?是?((y . 2) (x . 1))?那么(ext-env x 3 env1)，就會(huì)返回?((x . 3) (y . 2) (x . 1))刁愿。也就是把?(x . 3)?加到env1?的最前面去绰寞。
那我們什么時(shí)候需要擴(kuò)展環(huán)境呢？當(dāng)我們進(jìn)行綁定的時(shí)候铣口。綁定可能出現(xiàn)在函數(shù)調(diào)用時(shí)滤钱，也可能出現(xiàn)在 let 綁定時(shí)。我們選擇的數(shù)據(jù)結(jié)構(gòu)脑题，使得環(huán)境自然而然的具有了作用域（scope）的特性件缸。
環(huán)境其實(shí)是一個(gè)堆棧（stack）。內(nèi)層的綁定叔遂，會(huì)出現(xiàn)在環(huán)境的最上面停团，這就是在“壓棧”掏熬。這樣我們查找變量的時(shí)候，會(huì)優(yōu)先找到最內(nèi)層定義的變量秒梅。
舉個(gè)例子：
(let([x1]); env='()旗芬。綁定x到1。(let([y2]); env='((x . 1))捆蜀。綁定y到2疮丛。(let([x3]); env='((y . 2) (x . 1))。綁定x到3辆它。(+xy)))); env='((x . 3) (y . 2) (x . 1))誊薄。查找x，得到3锰茉；查找y呢蔫，得到2。;; => 5
這段代碼會(huì)返回5飒筑。這是因?yàn)樽顑?nèi)層的綁定片吊，把?(x . 3)?放到了環(huán)境的最前面绽昏，這樣查找?x的時(shí)候，我們首先看到?(x . 3)俏脊，然后就返回值3全谤。之前放進(jìn)去的?(x . 1)?仍然存在，但是我們先看到了最上面的那個(gè)(x . 3)爷贫，所以它被忽略了认然。
這并不等于說(shuō)?(x . 1)?就可以被改寫(xiě)或者丟棄，因?yàn)樗匀皇怯杏玫穆选Ｄ阒恍枰匆粋€(gè)稍微不同的例子卷员，就知道這是怎么回事：
(let([x1]); env='()。綁定x到1卷胯。(+(let([x2]); env='((x . 1))子刮。綁定x到2。x); env='((x . 2) (x . 1))窑睁。查找x挺峡，得到2。x)); env='((x . 1))担钮。查找x橱赠，得到1。;; => 3? ? ? ? ? ? ? ; 兩個(gè)不同的x的和箫津，1+2等于3狭姨。
這個(gè)例子會(huì)返回3。它是第3行和第4行里面兩個(gè)?x?的和苏遥。由于第3行的?x?處于內(nèi)層 let 里面饼拍，那里的環(huán)境是?((x . 2) (x . 1))，所以查找?x?的值得到2田炭。第4行的?x?在內(nèi)層 let 外面师抄，但是在外層 let 里面，那里的環(huán)境是?((x . 1))教硫，所以查找?x?的值得到1叨吮。這很符合直覺(jué)，因?yàn)閤?總是找到最內(nèi)層的定義瞬矩。
值得注意的是茶鉴，環(huán)境被擴(kuò)展以后，形成了一個(gè)新的環(huán)境景用，而原來(lái)的環(huán)境并沒(méi)有被改變涵叮。比如，上面的?((y . 2) (x . 1))?并沒(méi)有刪除或者修改，只不過(guò)是被“引用”到一個(gè)更大的列表里去了围肥。
這樣不對(duì)已有數(shù)據(jù)進(jìn)行修改（mutation）的數(shù)據(jù)結(jié)構(gòu)剿干，叫做“函數(shù)式數(shù)據(jù)結(jié)構(gòu)”。函數(shù)式數(shù)據(jù)結(jié)構(gòu)只生成新的數(shù)據(jù)穆刻，而不改變或者刪除老的置尔。它可能引用老的結(jié)構(gòu)，然而卻不改變老的結(jié)構(gòu)氢伟。這種“不修改”（immutable）的性質(zhì)榜轿，在我們的解釋器里是很重要的，因?yàn)楫?dāng)我們擴(kuò)展一個(gè)環(huán)境朵锣，進(jìn)入遞歸谬盐，返回之后，外層的代碼必須仍然可以訪問(wèn)原來(lái)外層的環(huán)境诚些。
當(dāng)然飞傀，我們也可以用另外的，更高效的數(shù)據(jù)結(jié)構(gòu)（比如平衡樹(shù)诬烹，串接起來(lái)的哈希表）來(lái)表示環(huán)境砸烦。如果你學(xué)究一點(diǎn)，甚至可以用函數(shù)來(lái)表示環(huán)境绞吁。這里為了代碼簡(jiǎn)單幢痘，我們選擇了最笨，然而正確家破，容易理解的數(shù)據(jù)結(jié)構(gòu)颜说。
對(duì)變量的解釋
了解了變量，函數(shù)和環(huán)境汰聋，我們來(lái)看看解釋器對(duì)變量的“取值”操作门粪，也就是?match?的第一種情況。
[(? symbol? x) (lookup x env)]
這就是在環(huán)境中烹困，沿著從內(nèi)向外的“作用域順序”庄拇，查找變量的值。
這里的?(? symbol? x)?是一種特殊的模式韭邓，它使用 Scheme 函數(shù)?symbol??來(lái)判斷輸入是否是一個(gè)符號(hào)，如果是溶弟，就把它綁定到?x女淑，然后你就可以在右邊用?x?來(lái)指稱這個(gè)輸入。
對(duì)綁定的解釋
現(xiàn)在我們來(lái)看看對(duì) let 綁定的解釋：
[`(let([,x,e1]),e2)(let([v1(interpe1env)]); 解釋右邊表達(dá)式e1辜御，得到值v1(interpe2(ext-envxv1env)))]; 把(x . v1)擴(kuò)充到環(huán)境頂部鸭你，對(duì)e2求值
通過(guò)代碼里的注釋，你也許已經(jīng)可以理解它在做什么。我們先對(duì)表達(dá)式?e1?求值袱巨，得到?v1阁谆。然后我們把?(x . v1)?擴(kuò)充到環(huán)境里，這樣?(let ([x e1]) ...)?內(nèi)部都可以看到?x?的值愉老。然后我們使用這個(gè)擴(kuò)充后的環(huán)境场绿，遞歸調(diào)用解釋器本身，對(duì) let 的主體?e2?求值嫉入。它的返回值就是這個(gè) let 綁定的值焰盗。
Lexical Scoping 和 Dynamic Scoping
下面我們準(zhǔn)備談?wù)労瘮?shù)定義和調(diào)用。對(duì)函數(shù)的解釋是一個(gè)微妙的問(wèn)題咒林，很容易弄錯(cuò)熬拒，這是由于函數(shù)體內(nèi)也許會(huì)含有外層的變量，叫做“自由變量”垫竞。所以在分析函數(shù)的代碼之前澎粟，我們來(lái)了解一下不同的“作用域”（scoping）規(guī)則。
我們舉個(gè)例子來(lái)解釋這個(gè)問(wèn)題欢瞪。下面這段代碼活烙，它的值應(yīng)該是多少呢？
(let([x2])(let([f(lambda(y)(*xy))])(let([x4])(f3))))
在這里引有，f?函數(shù)體?(lambda (y) (* x y))?里的那個(gè)?x瓣颅，就是一個(gè)“自由變量”。x?并不是這個(gè)函數(shù)的參數(shù)譬正，也不是在這個(gè)函數(shù)里面定義的宫补，所以我們必須到函數(shù)外面去找?x?的值。
我們的代碼里面曾我，有兩個(gè)地方對(duì)?x?進(jìn)行了綁定粉怕，一個(gè)等于2，一個(gè)等于4抒巢，那么?x?到底應(yīng)該是指向哪一個(gè)綁定呢贫贝？這似乎無(wú)關(guān)痛癢，然而當(dāng)我們調(diào)用?(f 3)?的時(shí)候蛉谜，嚴(yán)重的問(wèn)題來(lái)了稚晚。f的函數(shù)體是?(* x y)，我們知道?y?的值來(lái)自參數(shù) 3型诚，可是?x?的值是多少呢客燕？它應(yīng)該是2，還是4呢狰贯？
在歷史上也搓，這段代碼可能有兩種不同的結(jié)果赏廓，這種區(qū)別一直延續(xù)到今天。如果你在 Scheme （Racket）里面寫(xiě)以上的代碼傍妒，它的結(jié)果是6幔摸。
;; Scheme(let([x2])(let([f(lambda(y)(*xy))])(let([x4])(f3))));; => 6
現(xiàn)在我們來(lái)看看，在 Emacs Lisp 里面輸入等價(jià)的代碼颤练，得到什么結(jié)果。如果你不熟悉 Emacs Lisp 的用法昔案，那你可以跟我做：把代碼輸入 Emacs 的那個(gè)叫?*scratch*?的 buffer。把光標(biāo)放在代碼最后庆亡，然后按 C-x C-e捞稿，這樣 Emacs 會(huì)執(zhí)行這段代碼，然后在 minibuffer 里顯示結(jié)果：
結(jié)果是12彰亥！如果你把代碼最內(nèi)層的?x?綁定修成其它的值衰齐，輸出會(huì)隨之改變。
奇怪吧废酷？Scheme 和 Emacs Lisp抹缕，到底有什么不一樣呢澈蟆？實(shí)際上，這兩種看似差不多的 “Lisp 方言”卓研，采用了兩種完全不同的作用域方式趴俘。Scheme 的方式叫做 lexical scoping （或者 static scoping），而 Emacs 的方式叫做 dynamic scoping奏赘。
那么哪一種方式更好呢寥闪？或者用哪一種都無(wú)所謂？答案是磨淌，dynamic scoping 是非常錯(cuò)誤的做法橙垢。歷史的教訓(xùn)告訴我們，它會(huì)帶來(lái)許許多多莫名其妙的 bug伦糯，導(dǎo)致 dynamic scoping 的語(yǔ)言幾乎完全沒(méi)法用柜某。這是為什么呢？
原因在于敛纲，像?(let ((x 4)) …)?這樣的變量綁定喂击，只應(yīng)該影響它內(nèi)部“看得見(jiàn)”的?x?的值。當(dāng)我們看見(jiàn)?(let ((x 4)) (f 3))?的時(shí)候淤翔，并沒(méi)有在 let 的內(nèi)部看見(jiàn)任何叫“x” 的變量翰绊，所以我們“直覺(jué)”的認(rèn)為，(let ((x 4)) …)?對(duì)?x?的綁定旁壮，不應(yīng)該引起?(f 3)?的結(jié)果變化监嗜。
然而對(duì)于 dynamic scoping，我們的直覺(jué)卻是錯(cuò)誤的抡谐。因?yàn)?f?的函數(shù)體里面有一個(gè)?x裁奇，雖然我們沒(méi)有在?(f 3)?這個(gè)調(diào)用里面看見(jiàn)它，然而它卻存在于?f?定義的地方麦撵。要知道刽肠，f?定義的地方也許隔著幾百行代碼，甚至在另外一個(gè)文件里面躺涝。而且調(diào)用函數(shù)的人憑什么應(yīng)該知道坚嗜，?f的定義里面有一個(gè)自由變量，它的名字叫做?x银室？所以 dynamic scoping 在設(shè)計(jì)學(xué)的角度來(lái)看蜈敢，是一個(gè)反人類的設(shè)計(jì) :)
相反，lexical scoping 卻是符合人們直覺(jué)的否过。雖然在?(let ((x 4)) (f 3))?里面，我們把x?綁定到了 4癌佩，然而?f?的函數(shù)體并不是在那里定義的围辙，我們也沒(méi)在那里看見(jiàn)任何?x，所以?f?的函數(shù)體里面的?x桥胞，仍然指向我們定義它的時(shí)候看得見(jiàn)的那個(gè)?x贩虾，也就是最上面的那個(gè)?(let ([x 2]) ...)，它的值是 2策精。所以?(f 3)?的值應(yīng)該等于 6，而不是12询刹。
對(duì)函數(shù)的解釋
為了實(shí)現(xiàn) lexical scoping凹联，我們必須把函數(shù)做成“閉包”（closure）。閉包是一種特殊的數(shù)據(jù)結(jié)構(gòu)澳淑，它由兩個(gè)元素組成：函數(shù)的定義和當(dāng)前的環(huán)境杠巡。我們把閉包定義為一個(gè) Racket 的 struct 結(jié)構(gòu)：
(structClosure(fenv))
有了這個(gè)數(shù)據(jù)結(jié)構(gòu)，我們對(duì)?(lambda (x) e)?的解釋就可以寫(xiě)成這樣：
[`(lambda(,x),e)(Closureexpenv)]
注意這里的?exp?就是 ``(lambda (,x) ,e)` 自己兄一。
有意思的是，我們的解釋器遇到?(lambda (x) e)骂束，幾乎沒(méi)有做任何計(jì)算展箱。它只是把這個(gè)函數(shù)包裝了一下，把它與當(dāng)前的環(huán)境一起栖榨，打包放到一個(gè)數(shù)據(jù)結(jié)構(gòu)（Closure）里面婴栽。這個(gè)閉包結(jié)構(gòu)，記錄了我們?cè)诤瘮?shù)定義的位置“看得見(jiàn)”的那個(gè)環(huán)境准脂。稍候在調(diào)用的時(shí)候狸膏，我們就能從這個(gè)閉包的環(huán)境里面贤旷，得到函數(shù)體內(nèi)的自由變量的值。
對(duì)調(diào)用的解釋
好了盅藻，我們終于到了最后的關(guān)頭氏淑，函數(shù)調(diào)用。為了直觀炉擅，我們把函數(shù)調(diào)用的代碼拷貝如下：
[`(,e1,e2)(let([v1(interpe1env)]; 計(jì)算函數(shù) e1 的值[v2(interpe2env)]); 計(jì)算參數(shù) e2 的值(matchv1[(Closure`(lambda(,x),e)env-save); 用模式匹配的方式取出閉包里的各個(gè)子結(jié)構(gòu)(interpe(ext-envxv2env-save))]))]; 在閉包的環(huán)境env-save中把x綁定到v2眶俩，解釋函數(shù)體? ?
函數(shù)調(diào)用都是?(e1 e2)?這樣的形式仿便，e1?表示函數(shù)，e2?是它的參數(shù)闻坚。我們需要先分別求出函數(shù)?e1?和參數(shù)?e2?的值窿凤。
函數(shù)調(diào)用就像把一個(gè)電器的插頭插進(jìn)插座雳殊，使它開(kāi)始運(yùn)轉(zhuǎn)。比如仓洼，當(dāng)?(lambda (x) (* x 2))?被作用于 1 時(shí)哺呜，我們把?x?綁定到 1某残，然后解釋它的函數(shù)體?(* x 2)。但是這里有一個(gè)問(wèn)題，函數(shù)體內(nèi)的自由變量應(yīng)該取什么值呢耻瑟？從上面閉包的討論谆构，你已經(jīng)知道了搬素，自由變量的值，應(yīng)該從閉包的環(huán)境查詢粱哼。
操作數(shù)?e1?的值?v1?是一個(gè)閉包，它里面包含一個(gè)函數(shù)定義時(shí)保存的環(huán)境?env-save刻蚯。我們把這個(gè)環(huán)境?env-save?取出來(lái)躬充，那我們就可以查詢它口蝠，得到函數(shù)體內(nèi)自由變量的值妙蔗。然而函數(shù)體內(nèi)不僅有自由變量眉反，還有對(duì)函數(shù)參數(shù)的使用，所以我們必須擴(kuò)展這個(gè)?env-save?環(huán)境梳杏，把參數(shù)的值加進(jìn)去。這就是為什么我們使用?(ext-env x v2 env-save)塑悼，而不只是?env-save霞势。
你可能會(huì)奇怪，那么解釋器的環(huán)境?env?難道這里就不用了嗎颂鸿？是的。我們通過(guò)?env?來(lái)計(jì)算?e1和?e2?的值栽渴，是因?yàn)?e1?和?e2?里面的變量慢味，在“當(dāng)前環(huán)境”（env）里面看得見(jiàn)〕刍＃可是函數(shù)體的定義叫编，在當(dāng)前環(huán)境下是看不見(jiàn)的。它的代碼在別的地方霞篡，而那個(gè)地方看得見(jiàn)的環(huán)境，被我們存在閉包里了端逼，它就是?env-save寇损。所以我們把?v1?里面的閉包環(huán)境?env-save?取出來(lái)，用于計(jì)算函數(shù)體的值裳食。
有意思的是，如果我們用?env芙沥，而不是env-save?來(lái)解釋函數(shù)體诲祸，那我們的語(yǔ)言就變成了 dynamic scoping。現(xiàn)在來(lái)實(shí)驗(yàn)一下：你可以把?(interp e (ext-env x v2 env-save))里面的?env-save?改成?env救氯，再試試我們之前討論過(guò)的代碼甲抖，它的輸出就會(huì)變成 12。那就是我們之前講過(guò)的，dynamic scoping 的結(jié)果澳盐。
(r2'(let([x2])(let([f(lambda(y)(*xy))])(let([x4])(f3)))));; => 12
你也許發(fā)現(xiàn)了，如果我們的語(yǔ)言是 dynamic scoping，那就沒(méi)必要使用閉包了源武，因?yàn)槲覀兏静恍枰]包里面保存的環(huán)境。這樣一來(lái)，dynamic scoping 的解釋器就可以寫(xiě)成這樣：
(defineinterp(lambda(expenv)(matchexp......[`(lambda(,x),e); 函數(shù)：直接返回自己的表達(dá)式exp]......[`(,e1,e2)(let([v1(interpe1env)][v2(interpe2env)])(matchv1[`(lambda(,x),e); 調(diào)用：直接使用函數(shù)的表達(dá)式本身(interpe(ext-envxv2env))]))]......)))
注意到這個(gè)解釋器的函數(shù)有多容易實(shí)現(xiàn)嗎露戒？它就是這個(gè)函數(shù)的表達(dá)式自己旱眯，原封不動(dòng)。用函數(shù)的表達(dá)式本身來(lái)表示它的值丸氛，是很直接很簡(jiǎn)單的做法，也是大部分人一開(kāi)頭就會(huì)想到的旦签。然而這樣實(shí)現(xiàn)出來(lái)的語(yǔ)言罩阵，就不知不覺(jué)地采用了 dynamic scoping喧笔。
這就是為什么很多早期的 Lisp 語(yǔ)言日丹，比如 Emacs Lisp，都使用 dynamic scoping迄本。這并不是因?yàn)樗鼈兊脑O(shè)計(jì)者在 dynamic scoping 和 lexical scoping 兩者之中做出了選擇抓韩，而是因?yàn)槭褂煤瘮?shù)的表達(dá)式本身來(lái)作為它的值，是最直接，一般人都會(huì)首先想到的做法。
另外涛癌，在這里我們也看到環(huán)境用“函數(shù)式數(shù)據(jù)結(jié)構(gòu)”表示的好處。閉包被調(diào)用時(shí)它的環(huán)境被擴(kuò)展降允，但是這并不會(huì)影響原來(lái)的那個(gè)環(huán)境，我們得到的是一個(gè)新的環(huán)境褂微。所以當(dāng)函數(shù)調(diào)用返回之后著隆，函數(shù)的參數(shù)綁定就自動(dòng)“注銷”了流酬。
如果你用一個(gè)非函數(shù)式的數(shù)據(jù)結(jié)構(gòu)，在綁定參數(shù)時(shí)不生成新的環(huán)境拘泞，而是對(duì)已有環(huán)境進(jìn)行賦值纷纫，那么這個(gè)賦值操作就會(huì)永久性的改變?cè)瓉?lái)環(huán)境的內(nèi)容。所以你在函數(shù)返回之后必須刪除參數(shù)的綁定陪腌。這樣不但麻煩辱魁，而且在復(fù)雜的情況下很容易出錯(cuò)。
思考題：可能有些人看過(guò) lambda calculus诗鸭，這些人可能知道?(let ([x e1]) e2)?其實(shí)等價(jià)于一個(gè)函數(shù)調(diào)用：((lambda (x) e2) e1)∪敬兀現(xiàn)在問(wèn)題來(lái)了，我們?cè)谟懻摵瘮?shù)和調(diào)用的時(shí)候强岸，很深入的討論了關(guān)于 lexical scoping 和 dynamic scoping 的差別锻弓。既然 let 綁定等價(jià)于一個(gè)函數(shù)定義和調(diào)用，為什么之前我們討論對(duì)綁定的時(shí)候蝌箍，沒(méi)有討論過(guò) lexical scoping 和 dynamic scoping 的問(wèn)題青灼，也沒(méi)有制造過(guò)閉包呢？
不足之處
現(xiàn)在你已經(jīng)學(xué)會(huì)了如何寫(xiě)出一個(gè)簡(jiǎn)單的解釋器妓盲，它可以處理一個(gè)相當(dāng)強(qiáng)大的函數(shù)式語(yǔ)言杂拨。出于教學(xué)的考慮，這個(gè)解釋器并沒(méi)有考慮實(shí)用的需求悯衬，所以它并不能作為工業(yè)應(yīng)用弹沽。在這里，我指出它的一些不足之處。
缺少必要的語(yǔ)言構(gòu)造贷币。我們的語(yǔ)言里缺少好些實(shí)用語(yǔ)言必須的構(gòu)造：遞歸，數(shù)組亏狰，賦值操作役纹，字符串，自定義數(shù)據(jù)結(jié)構(gòu)暇唾，…… 作為一篇基礎(chǔ)性的讀物促脉，我不能把這些都加進(jìn)來(lái)。如果你對(duì)這些有興趣策州，可以看看其它書(shū)籍瘸味，或者等待我的后續(xù)作品。
不合法代碼的檢測(cè)和報(bào)告够挂。你也許發(fā)現(xiàn)了旁仿，這個(gè)解釋器的 match 表達(dá)式，全都假定了輸入都是合法的程序孽糖，它并沒(méi)有檢查不合法的情況枯冈。如果你給它一個(gè)不合法的程序，它不會(huì)馬上報(bào)錯(cuò)办悟，而是會(huì)真去算它尘奏，以至于導(dǎo)致奇怪的后果。一個(gè)實(shí)用的解釋器病蛉，必須加入對(duì)代碼格式進(jìn)行全面檢測(cè)炫加，在運(yùn)行之前就報(bào)告不合法的代碼結(jié)構(gòu)。
低效率的數(shù)據(jù)結(jié)構(gòu)铺然。在 association list 里面查找變量俗孝，是線性的復(fù)雜度。當(dāng)程序有很多變量的時(shí)候就有性能問(wèn)題魄健。一個(gè)實(shí)用的解釋器驹针，需要更高效的數(shù)據(jù)結(jié)構(gòu)。這種數(shù)據(jù)結(jié)構(gòu)不一定非得是函數(shù)式的诀艰。你也可以用非函數(shù)式的數(shù)據(jù)結(jié)構(gòu)（比如哈希表）柬甥，經(jīng)過(guò)一定的改造，達(dá)到同樣的性質(zhì)其垄，卻具有更高的效率苛蒲。 ? 另外，你還可以把環(huán)境轉(zhuǎn)化成一個(gè)數(shù)組绿满。給環(huán)境里的每個(gè)變量分配一個(gè)下標(biāo)（index）臂外，在這個(gè)數(shù)組里就可以找到它的值。如果你用數(shù)組表示環(huán)境，那么這個(gè)解釋器就向編譯器邁進(jìn)了一步漏健。
S 表達(dá)式的歧義問(wèn)題嚎货。為了教學(xué)需要，我們的解釋器直接使用 S 表達(dá)式來(lái)表達(dá)語(yǔ)法樹(shù)蔫浆，用模式匹配來(lái)進(jìn)行分支遍歷殖属。在實(shí)際的語(yǔ)言里，這種方式會(huì)帶來(lái)比較大的問(wèn)題瓦盛。因?yàn)?S 表達(dá)式是一種通用的數(shù)據(jù)結(jié)構(gòu)洗显，用它表示的東西，看起來(lái)都差不多的樣子原环。一旦程序的語(yǔ)法構(gòu)造多起來(lái)挠唆，直接對(duì) S 表達(dá)式進(jìn)行模式匹配，會(huì)造成歧義嘱吗。 ?
比如?(,op ,e1 ,e2)?玄组，你以為它只匹配二元算術(shù)操作，比如?(+ 1 2)谒麦。但它其實(shí)也可以匹配一個(gè) let 綁定：?(let ([x 1]) (* x 2))巧勤。這是因?yàn)樗鼈冺攲釉氐臄?shù)目是一樣的。為了消除歧義弄匕，你得小心的安排模式的順序颅悉，比如你必須把?(let ([,x ,e1]) ,e2)?的模式放在?(,op ,e1, e2)?前面。所以最好的辦法迁匠，是不要直接在 S 表達(dá)式上寫(xiě)解釋器剩瓶，而是先寫(xiě)一個(gè)“parser”，這個(gè) parser 把 S 表達(dá)式轉(zhuǎn)換成 Racket 的 struct 結(jié)構(gòu)城丧。然后解釋器再在 struct 上面進(jìn)行分支匹配延曙。這樣解釋器不用擔(dān)心歧義問(wèn)題，而且會(huì)帶來(lái)效率的提升亡哄。
