怎样写一个解释器
这是一篇解释器的入门教程。虽然我试图从最基本的原理讲起，尽量让这篇文章不依赖于其它知识，但是这篇教程并不是针对编程的入门知识，所以我假设你已经学会了最基本的 Scheme 和函数式编程。我不是很推崇函数式编程，但它里面确实包含了很重要的一些方法。如果你完全不了解这些，可以读一下 SICP 的第一，二章（或者接下去读 The Little Schemer)。当然你也可以继续读这篇文章，有不懂的地方再去查资料。我在这里也会讲递归和模式匹配的原理。如果你已经了解这些东西，这里的内容也许可以加深你的理解。
解释器是一种简单却又深奥的东西，以至于好多人都不会写，或者自认为会写却又不真正的会写。在这个领域里有一些历史遗留下来的误解，以至于很少有人真正的知道如何写出正确的解释器。很多“语言专家”或者“逻辑学家”的解释器代码里面有各种各样的错误，却又以谬传谬，搞得无比复杂。这误解的渊源之深，真是一言难尽。
你必须从最简单的语言开始，逐步增加语言的复杂度，才能构造出正确的解释器。这篇文章就是告诉你如何写出一个最简单的语言 (lambda calculus) 的解释器，并且带有基本的的算术功能，可以作为一个高级计算器来使用。
一般的程序语言课程往往从语法分析(parsing)开始，折腾 lex 和 yacc 等麻烦却不中用的工具，解决一些根本不需要存在的问题。Parsing 的作用其实只是把字符串解码成程序的语法树（AST）结构。麻烦好久得到了 AST 之后，真正的困难才开始！而很多人在写完 parser 之后就已经倒下了。鉴于这个原因，这里我用所谓的“S-expression”来表示程序的语法树（AST）结构。S-expression （加上 Lisp 对它发自“本能”的处理能力）让我们可以直接跳过 parse 的步骤，进入关键的主题：语义(semantics)。
这里用的 Scheme 实现是 Racket。为了让程序简洁，我使用了 Racket 的模式匹配（pattern matching）。我对 Racket 没有特别的好感。但它安装比较方便，而且是免费的。如果你用其它的 Scheme 实现的话，恐怕要自己做一些调整。
解释器是什么
首先我们来谈一下解释器是什么。说白了解释器跟计算器差不多。它们都接受一个“表达式”，输出一个 “结果”。比如，得到 '(+ 1 2) 之后就输出 3。不过解释器的表达式要比计算器的表达式复杂一些。解释器接受的表达式叫做“程序”，而不只是简单的算术表达式。从本质上讲，每个程序都是一台机器的“描述”，而解释器就是在“模拟”这台机器的运转，也就是在进行“计算”。所以从某种意义上讲，解释器就是计算的本质。当然，不同的解释器就会带来不同的计算。
需要注意的是，我们的解释器接受的参数是一个表达式的“数据结构”，而不是一个字符串。这里我们用一种叫“S-expression”的数据结构来表示表达式。比如表达式 '(+ 1 2) 里面的内容是三个符号：'+, '1 和 '2，而不是字符串“(+ 1 2)”。从结构化的数据里面提取信息很方便，而从字符串里提取信息很麻烦，而且容易出错。
从广义上讲，解释器是一个通用的概念。计算器实际上是解释器的一种形式，只不过它处理的语言比程序的解释器简单很多。也许你会发现，CPU 和人脑，从本质上来讲也是解释器，因为解释器的本质实际上是“任何用于处理语言的机器”。
递归定义 (recursive definition)
解释器一般都是“递归程序”。之所以是递归的原因，在于它处理的数据结构（程序）本身是“递归定义”的结构。算术表达式就是一个这样的结构，比如：'(* (+ 1 2) (* (- 9 6) 4))。每一个表达式里面可以含有子表达式，子表达式里面还可以有子表达式，如此无穷无尽的嵌套。看似很复杂，其实它的定义不过是： “算术表达式”有两种形式：
1. 一个数
2. 一个 '(op e1 e2) 这样的结构（其中 e1 和 e2 是两个“算术表达式”）
看出来哪里在“递归”了吗？我们本来在定义“算术表达式”这个概念，而它的定义里面用到了“算术表达式”这个概念本身！这就构造了一个“回路”，让我们可以生成任意深度的表达式。
很多其它的数据，包括自然数，都是可以用递归来定义的。比如常见的对自然数的定义是： “自然数”有两种形式：
1. 零
2. 某个“自然数”的后继
看到了吗？“自然数”的定义里面出现了它自己！这就是为什么我们有无穷多个自然数。
所以可以说递归是无所不在的，甚至有人说递归就是自然界的终极原理。递归的数据总是需要递归的程序来处理。虽然递归有时候表现为另外的形式，比如循环(loop)，但是“递归”这个概念比“循环”更广泛一些。有很多递归程序不能用循环来表达，比如我们今天要写的解释器就是一个递归程序，它就不能用循环来表达。所以写出正确的递归程序，对于设计任何系统都是至关重要的。其实递归的概念不限于程序设计。在数学证明里面有个概念叫“归纳法”(induction)，比如“数学归纳
法”(mathematical induction)。其实归纳法跟递归完全是一回事。
我们今天的解释器就是一个递归程序。它接受一个表达式，递归的调用它自己来处理各个子表达式，然后把各个递归的结果组合在一起，形成最后的结果。这有点像二叉树遍历，只不过我们的数据结构（程序）比二叉树复杂一些。
模式匹配和递归：一个简单的计算器
既然计算器是一种最简单的解释器，那么我们为何不从计算器开始写？下面就是一个计算器，它可以计算四则运算的表达式。这些表达式可以任意的嵌套，比如 '(* (+ 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 语句是一个模式匹配。它的形式是这样：