王垠：怎样写一个解释器

卖了好久关子了，说要写一个程序语言理论的入门读物，可是一直没有下笔。终于狠下心来兑现一部分承诺。今天就从解释器讲起吧。

解释器是比较深入的内容。虽然我试图从最基本的原理讲起，尽量让这篇文章不依赖于其它的知识，但是这篇教程并不是针对函数式编程的入门，所以我假设 你已经学会了最基本的 Scheme 和函数式编程。如果你完全不了解这些，可以读一下《 SICP | 计算机程序的构造和解释》

的第一，二章。当然你也可以继续读这篇文章，有不懂的地方再去查资料。我在这里也会讲递归和模式匹配的原理。如果你已经了解这些东西，这里的内容也许可以加深你的理解。

解释器其实不是很难的东西，可是好多人都不会写，因为在他们心目中解释器就像一个 Python 解释器那样复杂。如果你想开头就写一个 Python 解释器，那你多半永远也写不出来。你必须从最简单的语言开始，逐步增加语言的复杂度，才能构造出正确的解释器。这篇文章就是告诉你如何写出一个最简单的语 言 (lambda calculus) 的解释器，并且带有基本的的算术功能，可以作为一个高级计算器来使用。

一般的编译器课程往往从语法分析(parsing)开始，折腾 lex 和 yacc 等工具。Parsing 的作用其实只是把字符串解码成程序的语法树（AST）结构。麻烦好久得到了 AST 之后，真正的困难才开始！而很多人在写完 parser 之后就已经倒下了。鉴于这个原因，这里我用“S-expression”来表示程序的语法树（AST）结构。S-expression 让我们可以直接跳过 parse 的步骤，进入关键的主题：语义(semantics)。

这里用的 Scheme 实现是 Racket。为了让程序简洁，我使用了 Racket 的模式匹配（pattern matching）。如果你用其它的 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 语句是一个模式匹配。它的形式是这样：  
            
            

                 
            
            

                (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。它们应该是数字。你注意到我们在什么地方使用了递归吗？如果你再看一下“算术表达式”的定义：

“算术表达式”有两种形式：

1) 一个数

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 
            
        
    

一个计算器就是这么简单。你可以试试这些例子，然后自己再做一些新的例子。

什么是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)])  
            
            

                               (cond  
            
            

                                  [(
                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)])  
            
            

                        (match v1  
            
            

                          [(Closure `(
                lambda
                 (,x) ,e) env1)  
            
            

                           (interp1 e (ext-env x v2 env1))]))]  
            
            

                     [`(,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) (
                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 的值  
            
            

                        (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) 作为例子吧。当 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)])  
            
            

                                        (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) 放到最前面去。值得注意的一点是，环境被扩展以后其实是形成了一个新的环境，原来的环境并没有被“改变”。比如上面红色的部分就是原来的数据结构，只不过 它被放到另一个更大的结构里面了。这叫做“函数式数据结构”。这个性质在我们的解释器里是至关重要的，因为当我们扩展了一个环境之后，其它部分的代码仍然 可以原封不动的访问扩展前的那个旧的环境。当我们讲到调用的时候也许你就会发现这个性质的用处。

你也可以用另外的，更高效的数据结构（比如 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)])  
            
            

                        (match v1  
            
            

                          [(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
                    )) 
                
            
        
    

另外在这里我们也看到环境用“函数式数据结构”表示的好处。闭包被调用时它的环境被扩展，但是这并不会影响原来的那个环境，我们得到的是一个新的环 境。所以当函数调用返回之后，函数的参数绑定就自动“注销”了。如果你用一个非函数式的数据结构，在绑定参数时不生成新的环境，而是对已有环境进行赋值， 那么这个赋值操作就会永久性的改变原来环境的内容。所以你在函数返回之后必须删除参数的绑定。这样不但麻烦，而且在复杂的情况下几乎不可能有效的控制。每 一次当我使用赋值操作来修改环境，最后都会出现意想不到的麻烦。所以在写解释器，编译器的时候，我都只使用函数式数据结构来表示环境。

总结

好了，这就算是我的解释器入门教程的初稿了。如果有问题的话，欢迎给我发 email 指出: shredderyin@gmail.com。我会尽力改进。

另外需要指出的是，学会这个解释器并不等于理解了程序语言的理论。所以在学会了这些之后，还是要看一些语义学的书，就像我这篇博客里推荐的那本。

原文链接：http://blog.sina.com.cn/s/blog_5d90e82f01018ge9.html

原文：http://my.oschina.net/u/1398304/blog/374823