最近文章总没人看，必须起个炫酷的题目才行呐。
今天拜读了王垠大神的一篇经典作品《怎样写一个解释器》，读完后顿觉清风拂面、耳聪目明、如临仙境。我对“解释器”这一神秘概念长达数年的迷恋，今天终于得以一探究竟。
从非科班出身的我看来，解释器就是一个能够解释执行某种源代码的程序，例如Python解释器、JavaScript解释器等等。然而如何实现一个解释器却是我等草民从来没有想过的。正如吃过猪肉，何必还要看过猪跑。
然而探寻计算机的本质乃是我等草根程序员的一大梦想，这梦想无关金钱，是心底最纯粹的愿望。
幸运的是，垠神孜孜不倦的为我们提供精彩的科普文章，打破学术壁垒，把精深的理论变换为通俗易懂的文字。说实话，多年前，我就是受到垠神的文章影响，才决定走编程这条路，进而发现这个美妙的天地。好了，对垠神的吹捧到此为止，他的付款链接挂了，所以这篇文章就当做小小的广告费吧。
解释器的原理
无论是Python还是JavaScript，要想解释执行源代码，必须先读取文本程序，解析成抽象语法树（Abstract Syntax Tree, AST），然后再解释执行。
例如，对于如下的AST，很容易解释出它想要的结果。我们只需要递归地求根节点的值，就可以得到表达式的结果，即(1+2)*(3+4)=21。
显然，实际中的表达式不会只包含四则运算，还会有函数调用、变量绑定等等。
等等！请注意我的措辞，为什么是变量绑定而不是变量声明或变量赋值？而且，我没有提到分支语句、循环语句，不是省略，而是真的没有这些功能！
这里需要解释一波了，不然读者肯定有些摸不着头脑。本文，也即垠神文中所讲的解释器是纯函数式编程语言的解释器，并非我们日常见到的Python、JavaScript等集合了函数式编程和面向对象编程的全能语言。
在我看来，纯粹的函数式编程有一个有趣的特点，代码只有一句。这一句话内部的操作全部以递归的方式展开，非常神奇。因此，函数式编程中不需要分支语句和循环语句，因为代码并非按照从上到下的流程执行的。当需要某些类似于分支和循环的功能的时候，这些功能会以函数的形式提供出来。
实现解释器的过程就是创建一门新的编程语言
很显然，每一种新的编程语言必然配套一个解释器（或者编译器），那么到底是先有编程语言还是先有解释器，似乎和“鸡生蛋、蛋生鸡”的问题并无两样。
那我们就当做先发明一门编程语言好了，这个语言叫“R2”，它提供的语法如下：
变量：x
函数：(lambda (x) e)
绑定：(let ([x e1]) e2)
调用：(e1 e2)
算术：(• e2 e2)
什么？你说看不懂这些语法是什么意思？垠神发明的语言岂是凡夫俗子能够看懂的，笑。
现在的程序员啊，都是too young too naive，什么语言火学什么，前些年学Java、学PHP，最近又开始学Python、学JavaScript。然而真正看透一切的人，学的是Lisp！你看看人家王垠、Paul Graham、John Maccarthy，哪一个不是大名鼎鼎。
所以看到这几条语法不要慌，这就是Lisp最基础的语法。不过呢，我也不打算在这里讲，想深入了解的请参考教程《Yet Another Scheme Tutorial》。毕竟从紫藤大爷那里受益匪浅，不给打个广告说不过去。
假如我们已经实现了一个R2的解释器，那么它可以执行R2的源代码，像下面这个样子：
(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源代码（记住函数式程序只有一行）。
接下来，让我们欣赏一下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语言的解释器的精髓在哪里。不客气的说，用Racket来实现一个Racket的阉割版R2，似乎不足为道。其实王垠在文中也说了，如果不考虑Lexical Scope的话，可以用更简短的代码实现。那么，为什么要考虑Lexical Scope，如何实现Lexical Scope，就成了代码的精妙之处。
有过Java开发经验的同学应该有这样的印象：Java的匿名内部类和局部内部类只能访问外部的final变量。而其它语言则没有这样奇葩的限制。这个规则在几年间始终困扰着我，直到看完王垠的文章，才恍然大悟。
显然，Java是没有闭包的概念的。与Java不同，JavaScript有闭包的概念，当我们写出这样的代码：
var a = 1
var b = function() {
return a + 1
}
a = 2
b() // => 2
结果是2而不是3。说明函数b在定义时同它当时所在的环境打包在一起，称为闭包。后面再修改a的值，也已经无法影响闭包中的a，所以结果是2而不是3。
这种行为用专用术语来讲，就是Lexical Scope，或Static Scope。与此相对，还有Dynamic Scope，以Java为例，当我们写出这样的代码：
class A {
public int a = 1;
public void onClick() {
System.out.println(a + 1);
}
}
A a = new A();
a.a = 2;
a.onClick(); // => 3
结果是3而不是2。说明函数onClick在定义时并没有固定住a的值，所以当我们修改a的值后，可以随时体现到输出结果中。这就是Dynamic Scope的表现。
现在，我们再来思考Java的那个“奇葩的规定”。只允许匿名内部类和局部内部类访问外部的final变量，不就相当于强行把Dynamic Scope中可能改变的变量固定住了？换句话说，Java的设计者想要实现Lexical Scope的效果，但却没有从根本上实现，而是用了一种取巧的方式，来实现与Lexical Scope一致的效果。至于他们为什么非要实现Lexical Scope，显然是因为Dynamic Scope有诸多弊端，比如变量之间互相影响之类的，我的理解非常有限，就不擅自点评了。
花这么长篇幅分析了一通Lexical Scope与Dynamic Scope，以及闭包的概念。或许大家还是很难理解，毕竟这些东西都太抽象了。事实上，让我真正理解这些概念的，是在我读懂了上面的R2解释器源码的一刹那。看看闭包是如何实现的，函数的调用是如何实现的，就容易理解了。
如果你真的懒得读，那就听一下我给出的更加通俗易懂的解释吧。事实上，闭包就是一个函数，但不仅仅是一个函数，闭包是把函数和当前的环境变量打包在了一起。所谓的环境变量，就是到目前为止，当前作用域中所能访问到的所有变量的集合。记住，是当前作用域中，也就是函数定义时所处的作用域中，所有变量的集合。这也是称其为Lexical Scope的原因，作用域与代码结构保持一致，而与运行时无关。当函数真正被调用的时候，闭包中与其绑定的环境变量就可以被函数内部所使用。所以，函数内部的表达式中引用的变量要么是函数参数，要么在闭包的环境变量中定义过，否则就会出错。
好了，解释了半天，我猜大家还是一头雾水，而我已经黔驴技穷了。写这篇文章的初衷，也并非真的想讲清楚如何实现一个解释器，而是希望大家能够抱有一丝兴趣，去读读王垠的原文。还有一些介绍Lisp以及函数式编程的博客，给了我极大的启发，一并附在文末，希望感兴趣的同学看一看，发现这个奇妙的世界。也不枉我耽误宝贵的看动漫时间来写这篇文了。
Update in 2018-02-01
非常抱歉，由于笔者水平有限，文中出现了严重的错误，现纠正如下。
在最后一节中，我分析了Java和JavaScript的不同表现。然而，事实上我并非JavaScript的资深用户，以至于出现了非常低级的错误。
var a = 1
var b = function() {
return a + 1
}
a = 2
b() // => 2
这段JavaScript代码的输出结果其实不是2，而是3。也就是说，在函数b定义之后，对变量a的更改仍然影响到了b函数体内的a，与我文中所说不一致。
于是我重新考虑这个问题。定义函数b时，变量a连同函数b的函数体形成一个闭包，这一点不应该有错。与之类似地，文中定义的R2的代码也可以构建闭包
(r2
'(let ([x 2])
(let ([f (lambda (y) (* x y))])
(let ([x 4])
(f 3)))))
;; => 6
也是在定义函数之后修改了函数内用到的变量，而这里闭包中的x却没有被后来的赋值操作影响，为什么JavaScript闭包中的a却受到影响了呢。
以下仅发表我的看法，如有不同意见欢迎不吝赐教。
我认为JavaScript形成闭包和R2形成闭包并无本质的不同，但是变量的存在形式却有所差异。R2是一个纯函数式编程语言，不存在全局变量的概念，因而所有变量只存在于自己的作用域中，没有访问其它平行作用域的途径。事实上，所有变量的传递都是值拷贝，因此所有的变量都是常量。然而JavaScript并非纯函数式编程语言，变量是可以通过参数传递的，所以在上面的例子中，无论是闭包中的a还是外面的a，其实都是同一个变量，指向同一处内存地址，外部的改变自然可以影响闭包内的值。
这样看来，JavaScript和Java相比区别似乎不那么大了。唯一的不同是，Java认为生成闭包后，闭包中的值不应该被其它方法修改，否则会使显得程序混乱，所以强制规定闭包中引用的变量必须为final。
结论似乎有点牵强，毕竟只是我个人的猜测。欢迎大家提出不同意见，一起交流。
最后，感谢@翻翻儿 指出文中的错误，不然不知道要误导多少人。
推荐资料
怎样写一个解释器 王垠
《Yet Another Scheme Tutorial》 紫藤貴文
Lisp的本质 Slava Akhmechet
函数式程序设计的另类指南 Slava Akhmechet
