您所在的位置： &
王垠：怎样写一个解释器(2)
王垠：怎样写一个解释器(2)
王垠的博客
卖了好久关子了，说要写一个程序语言理论的入门读物，可是一直没有下笔。终于狠下心来兑现一部分承诺。今天就从解释器讲起吧。
模式匹配和递归：一个简单的计算器
既然计算器是一种最简单的解释器，那么我们为何不从计算器开始写？下面就是一个计算器，它可以计算四则运算的表达式。这些表达式可以任意的嵌套，比如 &(* (+ 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。它们应该是数字。你注意到我们在什么地方使用了递归吗？如果你再看一下&算术表达式&的定义：
&算术表达式&有两种形式：
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&
一个计算器就是这么简单。你可以试试这些例子，然后自己再做一些新的例子。
内容导航&第 1 页： &第 2 页： &第 3 页： &第 4 页： &第 5 页： &第 6 页：
关于&&的更多文章
《ios 5编程入门经典(第3版)――开发iphone与ipad应用》详尽透彻
网友评论TOP5
正是由于HTML5具有丰富的功能并且无处不在，所以它给
Java平台上的多语言混合编程正成为主流，单一的Java开
Visual Studio 11是继Visual Studio 2010之后，微软下
本书从一个网站制作过程入手，详细介绍基于ASP技术建设网站的全过程。全书共10章。第1章，网站制作规划与流程；第2章，IIS安装与
51CTO旗下网站如何使用Python编写一个Lisp解释器
我的图书馆
如何使用Python编写一个Lisp解释器
注意上面的惊叹号在Scheme中并不是一个特殊字符；它只是”set!“这个名字的一部分。(在Scheme中)只有括号是特殊字符。类似于(set!&x y)这样以特殊关键字开头的列表在Scheme中被称为一个特殊形式 (special form)；Scheme的优美之处就在于我们只需要六种特殊形式，以及另外的三种语法构造——变量、常量和过程调用。
发表评论：
TA的最新馆藏怎样写一个解释器
我的图书馆
怎样写一个解释器
写一个解释器，往往是设计和实现程序语言的第一步。解释器是简单却又深奥的东西，以至于好多人都不会写，也有人自认为会写，却没领会到里面的真谛，所以我决定写一篇这方面的入门读物。虽然我试图从最基本的原理讲起，尽量不依赖于其它知识，但这并不是一本编程入门教材。我假设你已经理解 Scheme 语言，以及函数式编程的基本要点。我不是函数式编程的传教士，然而它里面确实包含了一些很重要的方法。如果你完全不了解这些，那我建议你读一下
的第一，二章，或者
的前几章。注意不要读太多书，否则你就回不来了 ;-) 当然你也可以直接读这篇文章，有不懂的地方再去查资料。实现语言容易犯的一个错误，就是一开头就试图去实现很复杂的语言（比如 JavaScript 和 Python）。这样你往往很快就遭到挫败，最后不了了之。其实学习实现程序语言，最好是从简单的语言开始，很快写出一个可以用的解释器。然后，逐步往这个解释器里添加特性，同时保持正确。这样，你才能有条不紊地构造出复杂的解释器。这篇文章就是针对一个很简单的语言：传说中的 lambda calculus。写成了这个解释器之后，它可以作为一个高级的计算器来使用，还具有函数定义和调用的功能。Racket这里用的 Scheme 实现是 Racket，它可以在这里。为了让程序简洁，我用了一点点 Racket 的模式匹配（pattern matching）功能。我对 Scheme 的实现没有特别的偏好，但 Racket 方便易用，适合教学。如果你用其它的 Scheme 实现，可能得自己做一些调整。Racket 是一个 Scheme 语言的扩展，所以它实际上可以变化成很多种语言。如果你之前用过 DrRacket，那你的语言可能被你改成了 R5RS 之类的，如果下面的程序不能运行，你可能需要检查一下你的 DrRacket 的语言设置，把 Language 设置成 Racket。另外，Racket 程序的最上面都需要加上像 #lang racket 这样的语言标记，这样 Racket 才可以知道你想用那种语言的变种。解释器是什么首先我来谈一下，解释器到底是什么。说白了，解释器跟计算器差不多。解释器本质上是一个函数，它接受一个“表达式”作为输入，然后输出一个 “值”。就像这个样子：比如，你输入表达式 '(+ 1 2) ，它就输出值，整数 3。表达式是一种“表象”或者“符号”，而值却更加接近“本质”或者“意义”。解释器从符号出发，得到了它的意义，这也许就是它为什么叫做“解释器”。需要注意的是，这里的表达式是一个数据结构，而不是一个字符串。我们用一种叫“S表达式”的数据结构来表示表达式。比如表达式 '(+ 1 2) 其实是一个链表（list），它里面的内容是三个符号（symbol）：'+, '1 和 '2，而不是字符串'(+ 1 2)'。从结构化的数据里面提取信息很方便，而从字符串里提取信息很麻烦，容易出错。Scheme（Lisp）语言里面大量使用结构化的数据，而不是字符串，这就是 Lisp 系统比 Unix 先进的地方。从本质上讲，每个程序都是一台机器的“描述”，而解释器就是在“模拟”这台机器的运转，也就是在进行“计算”。所以从某种意义上讲，解释器就是计算的本质。当然，不同的解释器就会带来不同的计算。你可能没有想到，CPU 也是一个解释器，它解释执行机器语言。递归定义（recursive definition）解释器一般都是含有大量“递归”的程序，基本跟遍历二叉树的代码差不多。之所以包含递归，是因为它处理的数据结构（程序的语法树），本身就是“递归定义”的结构。比如 '(* (+ 1 2) (* (- 9 6) 4))，里面的每一个表达式里面可以有子表达式，子表达式里面还可以有子表达式…… 看似很复杂，其实它的定义不过是：“算术表达式”有两种形式：一个数一个 '(op e1 e2) 这样的结构，其中 e1 和 e2 分别又是两个“算术表达式”。看出来“递归”了吗？我们本来在定义“算术表达式”这个概念，而这个定义里面却用到了“算术表达式”这个概念本身。这就构造了一个“回路”，这种定义可以让我们构造任意深度的表达式。递归定义的数据，一般都可以用树来表达，比如上面的表达式 '(* (+ 1 2) (* (- 9 6) 4))，就对应如下的树状结构：递归定义的数据，总是需要递归的程序来处理。这就是为什么解释器是一个递归程序，因为它必须处理递归的数据。解释器接受一个表达式，递归调用它自己，算出各个子表达式的值，然后把各个递归调用的结果组合在一起，算出最后的值。这就像二叉树的“后序遍历”（post-order traversal），只不过我们的数据结构（语法树）比二叉树稍微复杂一些。一个简单的计算器既然计算器是一种最简单的解释器，那么我们为何不先写一个计算器，然后再推广到更多功能？下面就是一个计算器，它可以计算四则运算的表达式。这些表达式可以任意的嵌套，比如 '(* (+ 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 的值
分支匹配：操作符 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现在我来解释一下它的工作原理。代码里的 match 语句是一个模式匹配。它的形式是这样：现在我来解释一下它的工作原理。代码里的 match 语句是一个模式匹配。它的形式是这样：(match exp
[模式 结果]
[模式 结果]
...)它根据表达式 exp 的结构来进行分支操作。每一个分支由两部分组成，左边是一个模式，右边是一个结果。整个 match 语句的语义是：找到第一个匹配的模式，输出它右边的结果。左边的模式在匹配之后，可能会绑定一些变量，这些变量可以在右边的表达式里使用。这就跟其它语言（比如 Java）里面嵌套的if ... else if ... else ...差不多，只不过稍微简洁和方便一些。一般说来，数据的定义有多少种情况，用来处理它的模式就有多少情况。比如算术表达式有两种情况，要么是数字，要么是 (op e1 e2)，所以用来处理它的 match 语句就有两种模式。你所有的情况，我都能处理，这就是所谓“穷举法”。穷举的思想非常重要，你漏掉的任何一种情况，都非常有可能带来麻烦。所谓的“数学归纳法”，就是这种穷举法在自然数的递归定义上面的表现。因为你穷举了所有的自然数可能被构造的两种形式，所以你能确保定理对“任意自然数”成立。那么模式是如何工作的呢？比如，'(,op ,e1 ,e2) 就是一个模式（pattern），它被用来匹配输入值 exp。如果 exp 是 '(+ 1 2)，那么它与 '(,op ,e1 ,e2) 匹配的时候，就会把 op 绑定到 '+，把 e1 绑定到 '1，把 e2 绑定到 '2。这是因为它们结构相同：'(,op ,e1 ,e2)'( +
2)说白了，模式就是一个可以含有“名字”（像 op, e1 和 e2）的结构，像 '(,op ,e1 ,e2)。我们拿这个带有名字的结构，去匹配实际的数据（像 '(+ 1 2))。当它们一一对应之后，这些名字就自动被绑定到实际数据里相应位置的值。模式里面不但可以含有名字，也可以含有具体的数据。比如你可以构造一个模式 '(,op ,e1 42)，用来匹配第二个操作数固定为 42 的那些表达式。看见左边的模式，你就像直接看见了输入数据的形态，然后就可以对里面的元素进行操作。这样我们可以一次性的“拆散”（destruct）数据结构，把各个“成员”的值，绑定到多个变量，而不需要使用多个访问函数（accessor）。所以模式匹配是更加直观的编程方式，值得其它语言借鉴。很多函数式语言里都有类似的功能，比如 ML 和 Haskell。注意这里 e1 和 e2 里面的操作数还不是值，它们是表达式。我们递归的调用 interp1 自己，分别得到 e1 和 e2 的值 v1 和 v2。它们应该是数字。你注意到我们在什么地方使用了递归吗？如果你再看一下“算术表达式”的定义：“算术表达式”有两种形式：一个数一个 '(op e1 e2) 这样的结构（其中 e1 和 e2 是两个“算术表达式”）你就会发现这个定义里面“递归”的地方就是 e1 和 e2，所以 calc 在 e1 和 e2 上面递归的调用自己。如果你在数据定义的每个递归处都进行递归，那么你的递归程序就会穷举所有的情况。之后，我们根据操作符 op 的不同，对这两个值 v1 和 v2 分别进行操作。如果 op 是加号 '+，我们就调用 Scheme 的加法操作，作用于 v1 和 v2，并且返回运算所得的值。如果是减号，乘号，除号，我们也进行相应的操作，返回它们的值。一个计算器就是这么简单。你可以试试这些例子，然后自己再做一些新的例子。什么是 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 这么实用。完整的 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)])
[(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)])
[(Closure `(lambda (,x) ,e) env1)
(interp1 e (ext-env x v2 env1))]))]
[`(,op ,e1 ,e2)
算术表达式
(let ([v1 (interp1 e1 env)]
[v2 (interp1 e2 env)])
['+ (+ 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）表达式的各种情况。对基本算术操作的解释算术操作在解释器里是最简单也是最“基础”的东西，因为它们不能再被细分为更小的元素了。所以在接触函数，调用等复杂的结构之前，我们来看一看对算术操作的处理。以下就是这个解释器里处理基本算术的部分，它是 interp1 的最后一个分支。(match exp
[`(,op ,e1 ,e2)
(let ([v1 (interp1 e1 env)] 递归调用 interp1 自己，得到 e1 的值
[v2 (interp1 e2 env)]) 递归调用 interp1 自己，得到 e2 的值
分支：处理操作符 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)])
[(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]对函数的解释对函数的解释是一个比较难说清楚的问题。由于函数体内也许会含有外层函数的参数，比如 (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)])
[(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))另外在这里我们也看到环境用“函数式数据结构”表示的好处。闭包被调用时它的环境被扩展，但是这并不会影响原来的那个环境，我们得到的是一个新的环境。所以当函数调用返回之后，函数的参数绑定就自动“注销”了。如果你用一个非函数式的数据结构，在绑定参数时不生成新的环境，而是对已有环境进行赋值，那么这个赋值操作就会永久性的改变原来环境的内容。所以你在函数返回之后必须删除参数的绑定。这样不但麻烦，而且在复杂的情况下几乎不可能有效的控制。每一次当我使用赋值操作来修改环境，最后都会出现意想不到的麻烦。所以在写解释器，编译器的时候，我都只使用函数式数据结构来表示环境。下一步在懂得了这里讲述的基本的解释器构造之后，下一步可以做什么呢？其实从这个基本的解释器原型，你可以进一步发展出很多内容，比如：在这个解释器里加一些构造，比如递归和状态，你就可以得到一个完整的程序语言的解释器，比如 Scheme 或者 Python。对这个解释器进行“抽象”，你就可以对程序进行类型推导。感兴趣的话可以参考我实现的这个 ，或者 。对这个解释器进行一些改变，可以得到一个 partial evaluator，可以用于编译器优化。
? 著作权归作者所有
发表评论：
TA的最新馆藏