构建 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 解释器。有了解释器,我们就可以用它来解决一般问题。

参考

Last updated