构建 Scheme 解释器

我们用编程语言写的每一句表达式，都有它的含义，将表达式推导转化成它的实际含义的过程，被称为 evaluation。而实现这个推导转化过程的程序，就是解释器（interpreter）。
解释器的基本构造
解释器通常由 Lexical Analyzer、Parser、Evaluator & Environment、Printer 四个部分组成，它们的关系如下图所示：
![](/assets/Screen Shot 2018-04-07 at 4.23.21 PM.jpg)
解释器的输入一般为一句合法的表达式的字符串，如 "(average 4 (+ 5 5))"，该字符串将依次经过这四个组件处理
Lexical Analyzer: 将字符串转化成有意义的单词，称作 token
Parser：将各单词组合成便于推导转化的树状结构 （tree structure）
Evaluator & Environment：结合环境中的其它变量，将输入的树状结构推导转化成最终的结果值
Printer：将结果值转化成字符串输出到屏幕上
本节课的重心将放在 Evaluator 这部分，由于是写一个 Scheme 的解释器，因此 Lexical Analyzer 和 Parser 这两部分可以直接利用 Scheme 本身的相关组件。由于要构建的语言和 Scheme 本身比较像，为了与 Scheme 本身区分，我们的新语言名称叫作 Scheme*，与 Scheme 内置的方法功能重复的方法也都类似地会使用 * 以示区分。
构造 Scheme* 解释器
Arithmetic calculator
首先，我们尝试 evaluate 以下的加法表达式：
(plus* 24 (plus* 5 6))
主要代码如下所示，核心过程为 eval
(define (tag-check e sym)
  (and (pair? e) (eq? (car e) sym)))
(define (sum? e) (tag-check e 'plus*))
​
(define (eval exp)
  (cond
    ((number? exp) exp)
    ((sum? exp) (eval-sum exp))
    (else
      (error "unknown expression" exp))))
​
(define (eval-sum exp)
  (+ (eval (cadr exp)) (eval (caddr exp))))
​
(eval '(plus* 24 (plus* 5 6)))
在表达式 '(plus* 24 (plus* 5 6)) 被读入 Scheme 解释器时，它就已经被 Scheme 的 Lexical Analyzer 和 Parser 处理成了如下树状结构：
![](/assets/Screen Shot 2018-04-07 at 4.23.54 PM.jpg)
eval 过程通过判断表达式的第一个 token 的类型，来决定要对其进行什么样的操作 --- 如果是 number，就直接返回对应数值，如果是 plus*，则将表达式交给 eval-sum 去递归推导转化成最终结果。
上文代码利用数据驱动及防御式的编程方式组织 eval 过程，同时利用递归的方式将复杂表达式一层一层剥开，直到最简单的表达式，然后再将结果一层一层组合，最终推导得到计算表达式的结果。这就是一个最简单的 evaluator。
Names
接下来，我们要在 sheme* 中加入 names，也就是 define* 表达式：
(define* x* (plus* 4 5))
(plus* x* 2)
首先，我们需要一种 Table ADT，可以让我们存放和获取每个 name 与 value 的 binding 关系。
; make-table             void -> table
; table-get              table, symbol -> (binding | null)
; table-put!             table, symbol, anytype -> undef
; binding-value          binding -> anytype
假设这个 Table ADT 存在，scheme* 解释器就拥有支持 name binding 的能力：
(define (define? exp) (tag-check exp 'define*))
​
(define (eval exp)
  (cond
    ((number? exp) exp)
    ((sum? exp) (eval-sum exp))
    ((symbol? exp) (lookup exp))
    ((define? exp) (eval-define exp))
    (else
      (error "unknown expression" exp))))
​
(define environment (make-table))
​
(define (lookup name)
  (let ((binding (table-get environment name)))
    (if (null? binding)
        (error "unbound variable: " name)
        (binding-value binding))))
​
(define (eval-define exp)
  (let ((name (cadr exp))
        (defined-to-be (caddr exp)))
    (table-put! environment name (eval define-to-be)) 'undefined))
define* 表达式与之前的 plus* 表达式不同。plus* 表达式会 evaluate 它的两个参数，我们称这种表达式为一般表达式；define* 表达式只会 evaluate 第二个参数，把第一个参数当作 symbol，我们称不 evaluate 所有输入参数的表达式为特殊表达式 (special forms)。
Conditionals and If
scheme* 少不了 predicates 和条件语句 if
(define (greater? exp) (tag-check exp 'greater*))
(define (if? exp) (tag-check exp 'if*))
​
(define (eval exp)
  (cond
    ((number? exp) exp)
    ((sum? exp) (eval-sum exp))
    ((symbol? exp) (lookup exp))
    ((define? exp) (eval-define exp))
    (else
      (error "unknown expression" exp))))
​
(define (eval-greater exp)
  (> (eval (cadr exp)) (eval (caddr exp))))
​
(define (eval-if exp)
  (let ((predicate   (cadr exp))
        (consequent  (caddr exp))
        (alternative (cadddr exp)))
    (let ((test (eval predicate)))
      (cond
        ((eq? test #t) (eval consequent))
        ((eq? test #f) (eval alternative))
        (else          (error "predicate not a conditional: " predicate))))))
Store operators in the environment
既然有了 greater*, sum* 肯定少不了 lessThan*、equal*、difference*、mod* 等各种操作，如果逐一添加就会显得代码十分冗余。仔细观察可以发现，这些操作都有一个特点：先 evaluate 参数，然后对这些参数执行相应操作。这种模式就是上文提到的一般表达式，也称为 application。
为了达到目的，我们需要把这些操作存到环境中：
(define scheme-apply apply) ; 保存 scheme 内置的 apply
​
(define (apply operator operands)
  (if (primitive? operator)
      (scheme-apply (get-scheme-procedure operator) operands)
      (error "operator not a procedure: " operator)))
​
(define prim-tag 'primitive)
(define (make-primitive scheme-proc) (list prim-tag scheme-proc))
(define (primitive? e)               (tag-check e prim-tag))
(define (get-scheme-procedure prim)  (cadr prim))
​
(define environment (make-table))
(table-put! environment 'plus*     (make-primitive +))
(table-put! environment 'greater*  (make-primitive >))
(table-put! environment 'true* #t)
然后将一般表达式统一起来：
(define (eval exp)
  (cond
    ((number? exp)       exp)
    ((symbol? exp)       (lookup exp))
    ((define? exp)       (eval-define exp))
    ((if? exp)           (eval-if exp))
    ((application? exp)  (apply (eval (car exp))
                                (map eval (cdr exp))))
    (else
      (error "unknown expression " exp))))
这是 scheme* 解释器已经初具雏形，递归地 evaluate 表达式，特殊表达式在前，一般表达式在后。
Environment as explicit parameter
虽然已经有了 global environment，但很多情况下我们仍然需要 local environment 的支持。拥有 local environment 意味着 local environment 需要成为过程的输入参数，这样就可以使得同样的过程在不同的 local environment 中执行：
(define (eval exp env)
  (cond
    ((number? exp)       exp)
    ((symbol? exp)       (lookup exp env))
    ((define? exp)       (eval-define exp env))
    ((if? exp)           (eval-if exp env))
    ((application? exp)  (apply (eval (car exp) env)
                                 (map (lambda (e) (eval e env))
                                      (cdr exp))))
    (else
      (error "unknown expression " exp))))
​
(define (lookup name env)
  (let ((binding (table-get env name)))
    (if (null? binding)
        (error "unbound variable: " name)
        (binding-value binding))))
​
(define (eval-define exp env)
  (let ((name (cadr exp))
        (defined-to-be (caddr exp)))
    (table-put! env name (eval defined-to-be env))
    'undefined))
​
(define (eval-if exp env)
  (let ((predicate    (cadr exp))
        (consequent   (caddr exp))
        (alternative  (cadddr exp)))
    (table-put! env name (eval defined-to-be env))
    'undefined))
这里比较费解的地方在于 (application? exp) 后的内容。由于一个 application 的所有参数也需要在同一个 environment 中 evaluate，因此这里利用了 lambda 和 map 依次在同一个 environment 中 evaluate 每个参数。
Add new procedures
在 Scheme 中，我们可以用 lambda 自定义 procedures，lambda 表达式会返回一个在 environment model 中被称为 double bubble 的 compound procedure。本节，我们也将在 Scheme* 解释器中支持 lambda* 特殊表达式。
lambda* 表达式有三个重要成部分，参数、函数体以及环境，因此在 eval lambda* 的时候，需要在返回的数据结构中保存这三部分信息。在这里我们称这个数据结构为 compound，也就是上文到的 double bubble 或 compound procedure：
(define (lambda? e) (tag-check e 'lambda*))
​
(define (eval exp env)
  (cond
    ((number? exp)       exp)
    ((symbol? exp)       (lookup exp env))
    ((define? exp)       (eval-define exp env))
    ((if? exp)           (eval-if exp env))
    ((lambda? exp)       (eval-lambda exp env))
    ((application? exp)  (apply (eval (car exp) env)
                                 (map (lambda (e) (eval e env))
                                      (cdr exp))))
    (else
      (error "unknown expression " exp))))
​
(define (eval-lambda exp env)
  (let ((args (cadr exp))
        (body (caddr exp)))
    (make-compound args body env)))
​
​
;; ADT that implements the "double bubble"
;; 这里 compound 由 parameters、body、env 三部分构成，ADT 同时提供三者的 selectors
(define compound-tag 'compound)
(define (make-compound parameters body env)
    (list compound-tag parameters body env))
(define (compound? exp) (tag-check exp compound-tag))
(define (parameters compound) (cadr compound))
(define (body compound) (caddr compound))
(define (env compound) (caddr compound))
在 eval lambda* 表达式时，我们并没有执行实际操作，而只是老老实实地把自定义 procedures 的元素保存在 list 结构中，然后返回这个 list。当然，这里是否使用 list 并不重要，这对解释器的使用者透明。
那我们如何 eval compound 呢？实际上就是实现在环境模型一节中介绍的过程：
1.创建一个新的 Frame，设为 A
2.将 A 的外环境指针指向 P 的外环境指针所指的环境，此时 A 及其外环境一起构成新的环境，设为 E
3.在 A 中，将 P 的参数与它的值绑定起来
4.在 E 中执行 P 的程序体
(define (apply operator operands)
  (cond ((primitive? operator)
         (scheme-apply (get-scheme-procedure operator)
                       operands))
        ((compound? operator)
         (eval (body operator)
               (extend-env-with-new-frame
                 (parameters operator)
                 operands
                 (env operator))))
       (else
         (error "operator not a procedure: " operator))))
​
(define (extend-env-with-new-frame names values env)
  (let ((new-frame (make-table)))
    (make-bindings! names values new-frame)
    (cons new-frame env))) ; 注意：这里 new-frame 在 env 之前，体现 lookup 顺序
​
(define (make-bindings names values table)
  (for-each
    (lambda (name value) (table-put! table name value))
    names values))
​
; the initial global environment
(define GE
  (extend-env-with-new-frame
    (list 'true* 'plus* 'greater*)
    (list #t (make-primitive +) (make-primitive >))
    nil))
​
; lookup searches the list of frames for the first match
(define (lookup name env)
  (if (null? env)
      (error "unbound variable: " name)
      (let ((binding (table-get (car env) name)))
        (if (null? binding)
            (lookup name (cdr env))
            (binding-value binding)))))
​
; define changes the first frame in the environment
(define (eval-define exp env)
  (let ((name           (cadr exp))
        (defined-to-be  (caddr exp)))
    (table-put! (car env) name (eval defined-to-be env))
    'undefined)
实现上，所谓的外环境指针并不真实存在，而是通过 const 将内外环境合成一个 list，利用 list 结构的先后顺序来保证 lookup 从内环境到外环境的顺序一致。
举例：
(eval '(define* twice*
  (lambda* (x*) (plus* x* x*))) GE)
执行完以上 define* 语句后，GE 变为：
![](/assets/Screen Shot 2018-04-07 at 4.24.05 PM.jpg)
这时候，twice* 进入 GE 后，就可以调用 twice procedure
(eval '(twice* 4) GE)
首先 '(twice* 4) 是 application，因此得到
(apply (eval 'twice* GE)
  (map (lambda (e) (eval e GE)) '(4)))
map 表达式在 GE 中 evaluate twice* 的参数 --- 4：
(apply (eval 'twice* GE) '(4))
GE 中可以找 'twice*
(apply (list 'compound '(x*) '(plus* x* x*) GE) '(4))
apply 发现后面的表达式是 compound procedure
(eval '(plus* x* x*)
  (extend-env-with-new-frame '(x*) '(4) GE))
仔细阅读 GE 的代码，实际上 environment 并不是 table，而是 list<table>，extend-env-with-new-frame 实际上就是在当前 env 的基础之上，在 list 的前面 const 一个 table，代表 new frame。假设 table ADT 已经存在：
(eval '(plus* x* x*)
  ((list 'table 'new-frame) (list 'table 'GE)))
> 8
这里需要注意，如果 (eval '(twice* 4) 时的 env 并不是 GE，则以上过程将变成
(eval '(twice* 4) AE) ; another environment
(apply (eval 'twice* AE)
  (map (lambda (e) (eval e AE)) '(4)))
(apply (eval 'twice* GE) '(4))
(apply (list 'compound '(x*) '(plus* x* x*) GE) '(4))
(eval '(plus* x* x*)
  (extend-env-with-new-frame '(x*) '(4) GE))
(eval '(plus* x* x*)
  ((list 'table 'new-frame) (list 'table 'GE)))
> 8
其中 apply 中 eval 'twice* 的过程中，env 使用的是 GE，而不是 AE。本节的 GE 示意图中就可以看出，这里的 GE 是 'twice* 被 define* 的环境，而不是 eval 'twice* 时的环境。这也是我们在环境模型中强调的重要特性。同时，这与非 “strict mode” 下的 Javascript 的闭包 (closure) 很相似，但略有区别：
function printWindow () {
    console.log(this.window);
}
​
printWindow.apply(null, null);
> Window {postMessage: f, blur: f, focus: f, ... }
printWindow.apply({ window: "hello world" }, null)
> "hello world"
这里 window 是浏览器中 Javascript Engine 的 GE 中的对象，如果没有给出 this binding，则 this 就是 GE；但如果给出 this binding，则 this 就是给定的 this binding，它的 lookup 不会被委托 (delegate) 到 GE。环境是否以声明时的外环境为最后委托人是语言的 evaluation model 设计中的取舍点，不同语言会有不同的做法。
小结
本节构建了 scheme* 的解释器，同时也定义 scheme* language 的语法，它们也是 scheme 解释器和 scheme language 的子集。我们不仅可以用 scheme 来构建 scheme 的解释器，也可以用其它语言来构建 scheme 解释器。有了解释器，我们就可以用它来解决一般问题。
参考
​Youtube: SICP-2004-Lecture-17​
​MIT6.006-SICP-2005-lecture-notes-17-1​
​MIT6.006-SICP-2005-lecture-notes-17-2​

MIT - 6.001 - SICP - Previous

面向对象 - Scheme 实现

Next - MIT - 6.001 - SICP

Eval-Apply Loop

Last modified 3yr ago

Copy link

Outline