怎样写一个解释器
写一个解释器，是设计和实现程序语言的第一步。解释器是简单却又深奥的东西，以至于好多人都不会写。也有人自认为会写，却没领会到里面的真谛，所以我决定写一篇这方面的入门读物。虽然我试图从最基本的原理讲起，尽量不依赖于其它知识，但这并不是一本编程入门教材。我假设你已经理解 Scheme 语言，以及函数式编程的基本要点。
我不是函数式编程的传教士，然而它里面确实包含了一些很重要的方法。如果你完全不了解这些，那我建议你读一下 SICP 的第一，二章，或者 HtDP 的前几章，习题可以不做。注意不要读太多书，否则你就回不来了 ;-) 当然你也可以直接读这篇文章，有不懂的地方再去查资料。
实现语言容易犯的一个错误，就是一开头就试图去实现很复杂的语言（比如 JavaScript 或者 Python）。这样你很快就会因为这些语言的复杂性和各种奇葩问题而受到挫折，最后不了了之。其实学习实现程序语言，最好是从最简单，最干净的语言开始，很快写出一个可以用的解释器。然后逐步往这个解释器里添加特性，同时保持它的正确。这样你才能有条不紊地构造出复杂的解释器。
因为这个原因，这篇文章只针对一个很简单的语言。它可以作为一个简单的计算器来使用，还具有变量定义，函数定义和调用的功能。
我们的工具：Racket
本文的代码是使用 Scheme 语言实现的。Scheme 语言有很多的“实现”，这里我用的 Scheme 实现，叫做 Racket，它可以在这里免费下载。为了让程序简洁，我用了一点点 Racket 的模式匹配（pattern matching）功能。我对 Scheme 的实现没有特别的偏好，但 Racket 方便易用，适合教学。如果你用其它的 Scheme 实现，可能得自己做一些调整。
Racket 是一个 Scheme 语言的扩展，所以它实际上可以变化成很多种语言。如果你之前用过 DrRacket，那你的语言可能被你改成了 R5RS 之类的，如果下面的程序不能运行，你可能需要检查一下你的 DrRacket 的“语言设置”，把 Language 设置成 Racket。
相对于 Scheme 的语法，Racket 允许你使用方括号，而不只是圆括号。这样你可以写这样的代码：
(let ([x 1]
[y 2])
(+ x y))
方括号跟圆括号完全可以互换，只不过 Racket 要求方括号必须匹配方括号，不能混起来。通常，我喜欢用方括号来表示“无动作”的数据（比如上面的 [x 1], [y 2]），这样可以跟函数调用和其它具有“动作”的代码，产生“视觉对比度”。这对于 Scheme 代码的可读性，是一个不错的改善，因为到处都是圆括号的话，确实有点太单调了。
另外，Racket 程序的最上面都需要加上像 #lang racket 这样的语言选择标记，这样 Racket 才可以知道你想用哪种语言的变种。
解释器是什么
准备工作就到这里吧。现在我来谈一下，解释器到底是什么。说白了，解释器跟计算器差不多。解释器本质上是一个函数，它接受一个“表达式”作为输入，然后输出一个 “值”。就像这个样子：
比如，你输入表达式 '(+ 1 2) ，它就输出值，整数 3。表达式是一种“表象”或者“符号”，而值却更加接近“本质”或者“意义”。解释器从符号出发，得到了它的意义，这也许就是它为什么叫做“解释器”。
需要注意的是，这里的表达式是一个数据结构，而不是一个字符串。我们用一种叫“S表达式”的结构来表示表达式。比如表达式 '(+ 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 进行求值，然后根据 x 的值的结构来进行分支。每个分支由两部分组成，左边是一个模式，右边是一个结果。整个 match 语句的语义是这样：从上到下依次考虑，找到第一个可以匹配 x 的值的模式，返回它右边的结果。左边的模式在匹配之后，可能会绑定一些变量，这些变量可以在右边的表达式里使用。
模式匹配在逻辑上很像 Scheme 的 cond 表达式，或者 Java 的嵌套条件语句 if ... else if ... else ...。然而跟这些条件语句里的“条件”不同，每条 match 语句左边的模式，可以准确而形象地描述出数据结构的形状，而且可以在匹配的同时对结构里的成员进行“绑定”。这样我们可以方便的访问结构里面的成员，而不需要使用访问函数（accessor）。而且模式可以含有多层嵌套的子结构，所以它能够一次性的表示很复杂的数据结构。
举个实在点的例子。我的代码里用了这样一个 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。看起来有点奇怪，不过习惯了就好了。
模式匹配对书写解释器和编译器的代码相当有用，因为程序的语法树往往具有各种嵌套的结构。不用模式匹配的话，往往要写很多冗长的代码，才能描述出期望的结构。而且由于结构的嵌套比较深，很容易漏掉边界情况，造成bug。模式匹配可以直观的描述我们期望的结构，避免漏掉边界情况，而且可以方便的访问内部成员。
由于这个原因，很多源于 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) 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, 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 种情况（变量，函数，let，调用，数字，算术表达式）
(define interp1
(lambda (exp env)
(match exp ; 对exp进行模式匹配
[(? symbol? x) (lookup x env)] ; 变量
[(? number? x) x] ; 数字
[`(lambda (,x) ,e) ; 函数
(Closure exp env)]
[`(let ([,x ,e1]) ,e2) ; 绑定
(let ([v1 (interp1 e1 env)])
(interp1 e2 (ext-env x v1 env)))]
[`(,e1 ,e2) ; 调用
(let ([v1 (interp1 e1 env)]
[v2 (interp1 e2 env)])
(match v1
[(Closure `(lambda (,x) ,e) env-save)
(interp1 e (ext-env x v2 env-save))]))]
[`(,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) (* 2 x)) 3))
;; => 6
(interp
'(let ([x 2])
(let ([f (lambda (y) (* x y))])
(f 3))))
;; => 6
(interp
'(let ([x 2])
(let ([f (lambda (y) (* x y))])
(let ([x 4])
(f 3)))))
;; => 6
注意最后的三个例子，它们在语义上是等价的。我们稍后会利用它们来解释“作用域”（scope）这个概念。在接下来的几节，我们来仔细看看这个解释器的各个部分。
对基本算术操作的解释
算术操作一般都是程序里的“原子操作”，因为它们不能再被细分为多个步骤，所以我们来看一看对算术操作的处理。以下就是处理基本算术的部分，它是 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) 作为例子吧。当我们调用 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) 的值的时候，它做以下两步操作：
把
x绑定到 1。函数体内能够看见这个绑定。进入
f的函数体，对x * 2进行求值。
这就像一个人做出这两个动作：
- 把插头插进插座 。
- 走到电线的另外一头测量它的电压，并且把结果乘以 2。
在第一步和第二步之间，我们如何记住 x 的值呢？我们通过那个叫做 env 的参数，把它传递进一个递归的解释器调用里面。是哪个递归调用呢？是那个对函数体进行求值的调用： (interp1 e (ext-env x v2 env-save))。这就是为什么我们需要“环境”，也就是 interp1 的第二个参数： env。环境记录变量的绑定，并且把它们传递到“可见区域”。用术语说，这就叫做“作用域”（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) 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) 加到最前面去。值得注意的一点是，环境被扩展以后，其实是形成了一个新的环境，原来的环境并没有被改变。
比如，上面的 ((y . 2) (z . 5)) 并没有丢失，只不过是被放到一个更大的列表里面了。这样不进行“修改”（mutation）操作的数据结构，叫做“函数式数据结构”。它只是生成新的数据，其中一部分指向老的结构。这种“不修改”（immutable）的性质，在我们的解释器里是很重要的，因为当我们扩展了一个环境之后，其它部分的代码仍然可以原封不动的访问以前的环境。当我们讲到调用的时候，也许你就会发现这个性质的用处。
你也可以用其它的，更高效的数据结构（比如平衡树，串接起来的哈希表）来表示环境。你甚至可以用函数来表示环境。这里为了代码简单，我们选择了最笨，然而却是正确，容易理解的数据结构。
对变量的解释
了解了变量，函数和环境，我们来看看解释器对变量的“取值”操作，也就是 match 的第一种情况。这其实就是在环境中查找变量的值。这里的 (? symbol? x) 是一种特殊的模式，它使用 Scheme 函数 symbol? 来判断输入是否匹配，如果是的就把它绑定到 x，查找它的值，然后返回这个值。
[(? symbol? x) (lookup x env)]
对数字的解释
对数字的解释也很简单。由于在 Scheme 里面名字 '2 就是数字 2（我认为这是 Scheme 设计上的一个小错误），所以我们不需要对数字的名字做特殊的处理，把它们原封不动的返回。
[(? number? x) x]
Lexical Scoping 和 Dynamic Scoping
对函数的解释是一个微妙的问题，很容易弄错，这是由于函数体内也许会含有外层的变量：自由变量。我们举个例子来解释这个问题。
下面这段代码，它的值应该是多少呢？
(let ([x 2])
(let ([f (lambda (y) (* x y))])
(let ([x 4])
(f 3))))
在这里，f 函数体 (lambda (y) (* x y)) 里的那个 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 里面输入等价的代码，它的结果却是12！
(let ((x 2))
(let ((f (lambda (y) (* x y))))
(let ((x 4))
(funcall f 3))))
;; 把代码输入 Emacs 的 *scratch* buffer，把光标放在代码最后，然后按 C-x C-e
;; => 12
如果你把 Emacs Lisp 代码最内层对 x 的绑定修改为其它的值，输出会随之改变。奇怪吧？Scheme 和 Emacs Lisp，到底有什么不一样呢？
其实 Scheme 和 Emacs，使用的是两种完全不同的作用域方式。Scheme 的方式叫做 lexical scoping （或者 static scoping），而 Emacs 的方式叫做 dynamic scoping。那么哪一种方式更好呢？或者其实用哪一种都无所谓？答案是，dynamic scoping 是非常错误的做法，历史的教训告诉我们，它会带来许许多多的莫名其妙的 bug，导致这种语言几乎没法用。这是为什么呢？
原因在于，像 (let ((x 4)) …) 这样的变量绑定，只应该影响它内部“看得见”的 x 的值。当我们调用 (let ((x 4)) (f 3)) 的时候，我们并没有在绑定内部看见任何 x ，所以我们“直觉”的认为，(let ((x 4)) …) 不应该引起 (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。
对函数的解释
为了实现 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 (interp1 e1 env)] ; 计算函数 e1 的值
[v2 (interp1 e2 env)]) ; 计算参数 e2 的值
(match v1
[(Closure `(lambda (,x) ,e) env-save) ; 用模式匹配的方式取出闭包里的各个子结构
(interp1 e (ext-env x v2 env-save))] ; 在闭包的环境env-save中把x绑定到v2，解释函数体
))]
函数调用都是 (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）里面看得见。我们把 v1 里面的环境 env-save 取出来用于计算函数体，是因为函数体并不是在当前环境定义的。它的代码在别的地方，而那个地方看得见的环境，是 env-save。
如果我们用 env 来解释函数体，那我们的语言就成了 dynamic scoping。实验：你可以把 (interp1 e (ext-env x v2 env-save)) 里面的 env-save 改成 env，再试试我们之前讨论过的代码，它的输出就会是 12。那就是我们之前讲过的，dynamic scoping 的结果。
(let ([x 2])
(let ([f (lambda (y) (* x y))])
(let ([x 4])
(f 3))))
;; => 12
你也许发现了，如果我们的语言是 dynamic scoping，那就没必要使用闭包了，因为我们根本不需要闭包里面保存的环境。这样一来，一个 dynamic scoping 的解释器，其实可以简化成这样：
(define interp1
(lambda (exp env)
(match exp
... ...
[`(lambda (,x) ,e) ; 函数：直接返回自己的表达式
exp]
... ...
[`(,e1 ,e2)
(let ([v1 (interp1 e1 env)]
[v2 (interp1 e2 env)])
(match v1
[`(lambda (,x) ,e) ; 调用：直接使用函数的表达式本身
(interp1 e (ext-env x v2 env))]))]
... ...
)))
注意到这个解释器里的函数有多容易实现吗？它就是这个函数的表达式自己。用函数的表达式自己来表示它的值，是很直接很简单的做法，也是大部分人一开头就会想到的。然而这样实现出来的语言，就自然而然采用了 dynamic scoping。这就是为什么很多早期的 Lisp 语言，比如 Emacs Lisp，都使用 dynamic scoping。这并不是因为它们的设计者在 dynamic scoping 和 lexical scoping 两者之中做出了选择，而是因为 dynamic scoping 是最直接，任何人最先会想到的做法。
另外，在这里我们也看到环境用“函数式数据结构”表示的好处。闭包被调用时它的环境被扩展，但是这并不会影响原来的那个环境，我们得到的是一个新的环境。所以当函数调用返回之后，函数的参数绑定就自动“注销”了。如果你用一个非函数式的数据结构，在绑定参数时不生成新的环境，而是对已有环境进行赋值，那么这个赋值操作就会永久性的改变原来环境的内容。所以你在函数返回之后必须删除参数的绑定。这样不但麻烦，而且在复杂的情况下很容易出错。
下一步
在懂得了这里讲述的基本的解释器构造之后，下一步可以做什么呢？其实从这个基本的解释器原型，你可以进一步发展出很多内容，比如：
- 在这个解释器里加一些构造，比如赋值操作，数组操作，类定义，等等。你就可以得到一个完整的程序语言的解释器，比如 Scheme 或者 Python。
- 对这个解释器进行“抽象”，让它不返回一个值，而是返回一个“类型”，你就可以对程序进行类型推导。感兴趣的话可以参考我实现的这个 Hindley-Milner 系统，或者 Python 类型推导。
- 对这个解释器进行一些改变，让它在遇到未知变量的时候，返回一个表达式，而不是一个值，你就可以得到一个 partial evaluator，可以用于编译器优化。
解释器的概念是如此的有用，你可以用它变化出很多有趣和有用的东西。