Eval-Apply Loop

​
第十七课构建了一个简单 Scheme 的 Evaluator，本节将深入讨论 Scheme 真正的 Evaluator。
Scheme 解释器的五个组件
组件1：eval/apply core
eval 和 apply 是 Scheme 解释器中 Evaluator 的核心组件，它们一同定义 Scheme 语言的 semantics。
![](/assets/Screen Shot 2018-04-09 at 10.09.29 PM.jpg)
如上图所示，Scheme 解释器接收合法的表达式 (exp) 以及表达式所处的环境 (env) 后，会通过 eval procedure 来在这个环境中 evaluate 这个表达式。复杂表达式通常会包含另一个 application 表达式，这个表达式会被 eval procedure 进一步处理成更简单的表达式 (exp) 及其由新生成的 frame 以及之前的环境一同组成的新环境，然后再次被 eval procedure 进行处理。这个过程周而复始，直到表达式变成 primitive procedure 为止。
总结一下 eval 和 apply 的职责：
eval
根据表达式的类型来把表达式分发给对应的 procedure ，以下就是 eval 的具体代码实现
(define (m-eval exp env)
  (cond ((self-evaluating? exp) exp)
        ((variable? exp) (look-up-variable-value exp env))
        ((quoted? exp) (text-of-quotation exp))
        ((assignment? exp) (eval-assignment exp env))
        ((definition? exp) (eval-definition exp env))
        ((if? exp) (eval-if exp env))
        ((lambda? exp)
         (make-procedure (lambda-parameters exp) (lambda-body exp) env))
        ((begin? exp) (eval-sequence (begin-actions exp) env))
        ((cond? exp) (m-eval (cond-if exp) env))
        ((application? exp)
         (m-apply (m-eval (operator exp) env)
                (list-of-values (operands exp) env)))
        (else (error "Unknown expression type -- EVAL" exp))))
这里需要十分注意 eval 中各个类型表达式的 dispatch 顺序：
1.检查普通表达式，如self-evaluating 、variable 以及 quote 等等这些简单的表达式
2.检查特殊形式，如 assignment、define 这些有副作用的表达式，if、cond、begin 这些流程控制表达式，以及 lambda 表达式
3.application 表达式，它可以是编程者定义的任意 procedure，接收自定义的参数，执行自定义的过程。通常，如果一个表达式是复合表达式且不属于任意已知的特殊表达式，它就会被认为是一个 application 表达式。
apply
会首先 eval 表达式中的参数，即表达式的 operands，然后再将 eval 后的参数传递给表达式中的 procedure，即表达式的 operator，最后 eval 这个 procedure，这个 procedure 可以是 primitive procedures 也可以是用户自定义的一般 procedures。在计算模型引入 mutation 之后，Scheme 的 procedure 通常需要支持执行多个表达式，并以最后一个表达式的返回值来代表整体表达式的返回值，因此 m-apply 需要支持执行 body 中含有多个表达式的 procedure:
(define (m-apply procedure arguments)
  (cond ((primitive-procedure? procedure)
         (apply-primitive-procedure procedure arguments))
        ((compound-procedure? procedure)
         (eval-sequence
          (procedure-body procedure)
          (extend-environment (procedure-parameters procedure)
                              arguments
                              (procedure-environment procedure))))
        (else (error "Unknown procedure type -- APPLY" procedure))))
​
(define (eval-sequence exps env)
  (cond ((last-exp? exps) (m-eval (first-exp exps) env))
        (else (m-eval (first-exp exps) env)
              (eval-sequence (rest-exps exps) env))))
现在我们已经可以体会到 eval 和 apply 之间的互相踢皮球的合作模式，这有点像 EM 算法里的 E step 和 M step （没见过请忽略这句）...
但我们还没体会到 "eval 和 apply 定义了 Scheme 的 semantics" 。我们先用大白话解释一下 semantics 的意思。这里 semantics 指的是编程语言背后的意义，这个意义与具体的语法无关。比如要表达 “我爱你”，不同的语言有不同的语法，但被后的意义都是一个主体对另一个主体的感情。接下来我们将通过下一个组件的介绍来体会这句话。
组件2：syntax procedures
syntax procedures 决定语言的语法，即任意表达式的合法性。在 Scheme 解释器中，首先我们需要一些常用 procedure 来检测表达式的类型：
(define (self-evaluating? exp)
  (or (number? exp)
      (string? exp)
      (boolean? exp)))
​
(define (tagged-list? exp tag)
  (and (pair? exp) (eq? (car exp) tag)))
​
(define (quoted? exp) (tagged-list? exp 'quote))
(define (text-of-quotation exp) (cadr exp))
​
(define (variable? exp) (symbol? exp))
(define (assignment? exp) (tagged-list? exp 'set!))
(define (assignment-variable exp) (cadr exp))
(define (assignment-value exp) (caddr exp))
​
; ... definition
(define (definition? exp) (tagged-list? exp 'define))
​
(define (lambda? exp) (tagged-list? exp 'lambda))
(define (lambda-parameters lambda-exp) (cadr lambda-exp))
(define (lambda-body lambda-exp) (cddr lambda-exp))
(define (make-lambda params body) (cons 'lambda (cons params body)))
​
;... if, cond, begin, ..
(define (application? exp) (pair? exp))
(define (operators app) (car app))
(define (operands app) (cdr app))
完整代码可见参考文献。这些 syntax procedures 定义了 Scheme 的各种合法表达式的语法。仔细思考不难发现，在解释器中，Scheme 语言的 semantics 和 syntax 是互相解耦的，只要我们改变了这些 syntax procedures，就可以改变 Scheme 的 syntax，但对它的 semantics 却没有影响。接下来举几个例子：
例1：(CALL <proc> ARGS <arg1> <arg2> ...)
假设 Scheme 的设计者希望用更具体的表达式来执行一个 procedure，如标题所示，我们需要对原先的解释器代码作哪些改动呢？
(define (application? exp) (tagged-list? 'CALL))
(define (operator app) (cadr app))
(define (operands app) (cdddr app))
搞定！我们只修改了 syntax，而语言的 semantics 不受影响。
例2：Syntactic Sugar - let -> lambda
我们还可以添加语法糖，比如将 let binding 转化成 lambda：
(let ((<name> <val1>)
       (<name> <val2>))
   <body>)
 ; =>
 ((lambda (<name1> <name2>) <body>)
          (<val1> <val2>))
我们又需要改变什么呢？
在 m-eval 的 cond 中增加处理 let 表达式的情况，并把处理的工作 dispatch 给 let->combination procedure
实现 let 表达式到 lambda 表达式的转化，即 let->combination
(define (m-eval exp env)
  (cond ((...))
        ...
        ((let? exp)
         (m-eval (let->combination exp) env))
        ((application? exp)
         ...
        (else ...)))
​
​
(define (let? exp) (tagged-list? exp 'let))
(define (let-bound-variables let-exp)
  (map car (cadr let-exp)))
(define (let-values let-exp)
  (map cadr (cadr let-exp)))
(define (let-body let-exp)
  (sequence-> exp (cddr let-exp)))
​
(define (let->combination let-exp)
  (let ((names (let-bound-variables let-exp))
        (values (let-values let-exp))
        (body (let-body let-exp)))
    (cons (list 'lambda names body) values)))
我们知道在 Scheme 中，除了原始数据类型，剩下的东西都是 list，那么从 let 表达式转化成 lambda 表达式的过程，实际上就是一个 list 到另一个 list 的转化过程，如下面这个表达式：
(let ((x 23)
      (y 15))
  (do-something x y))
经过 let-combination 转化后就会变成：
((lambda (x y)
   (do-somthing x y))
 23 15)
let 表达式示意图
![](/assets/Screen Shot 2018-04-09 at 10.09.56 PM.jpg)
lambda 表达式示意图
![](/assets/Screen Shot 2018-04-09 at 10.10.26 PM.jpg)
例3：Syntactic Sugar - named procedures
在当前环境下，如果我们要在环境中定义 procedure，即 named procedure，我们必须这么写：
(define m-sum (lambda (x y) (+ x y))
如果我们想更简单一点：
(define (m-sum x y) (+ x y))
那世界就更美好一点。怎么做？
首先看一下处理 definition 的 procedure:
(define (eval-definition exp env)
  (define-variable! (definition-variable exp)
                    (m-eval (definition-value exp) env)
                    env))
(define (definition-variable exp) (cadr exp))
(define (definition-value exp) (caddr exp))
与前面的例子相似，我们只需要修改 syntax 而不需要改动 semantics，这里我们希望 definition-variable 和 definition-value 同时兼容两种形式：
(define (definition-variable exp)
  (if (symbol? (cadr exp)) (cadr exp) (caadr exp)))
(define (define-value exp)
  (if (symbol? (cadr exp))
      (caddr exp)
      (make-lambda (cdadr exp) (cddr exp))))
搞定！现在相信你对 “eval 和 apply 定义了 Scheme 的 semantics” 这句话能够有所体会。当我们需要修改语法时，只需要增删改处理不同类别表达式的 procedures。
组件3：environment manipulation
之前我们提到环境模型的实现时，假设背后已经存在一个 table ADT，现在来看一下具体的实现。
首先重新整理一遍对环境的需求：
支持往环境中添加新的 binding
环境拥有外环境指针，能根据外环境指针找到它的外环境 (enclosing environment)，以支持环境链。
我们可以用 list 来完成这些需求。
抽象地看，我们心中的环境模型如下图所示：
![](/assets/Screen Shot 2018-04-09 at 10.10.50 PM.jpg)
具体地看，我们心中的环境模型如下图所示：
![](/assets/Screen Shot 2018-04-09 at 10.11.12 PM.jpg)
extend-environment 时，抽象地看，我们心中的环境模型如下图所示：
![](/assets/Screen Shot 2018-04-09 at 10.11.34 PM.jpg)
extend-environment 时，具体地看，我们心中的环境模型如下图所示：
![](/assets/Screen Shot 2018-04-09 at 10.12.09 PM.jpg)
对应的代码如下：
(define (make-frame variables values) (cons variables values))
(define (add-binding-to-frame! var val frame)
  (set-car! frame (cons var (car frame)))
  (set-cdr! frame (cons val (cdr frame))))
(define (extend-environment vars vals base-env)
  (if (= (length vars) (length vals))
      (cons (make-frame vars vals) base-env)
      (if (< (length vars) (length vals))
          (error "Too many args supplied" vars vals)
          (error "Too few args supplied" vars vals))))
使用时，需要从环境链中搜索出对应的 binding:
; helper
(define (enclosing-environment env) (cdr env))
(define (first-frame env) (car env))
(define the-empty-environment '())
(define (frame-variables frame) (car frame))
(define (frame-values frame) (cdr frame))
​
(define (lookup-variable-value var env)
  (define (env-loop env)
    (define (scan vars vals)
      (cond ((null? vars) (env-loop (enclosing-environment env)))
            ((eq? var (car vars)) (car vals))
            (else (scan (cdr vars) (cdr vals)))))
    (if (eq? env the-empty-environment)
        (error "Unbound variable -- LOOKUP" var)
        (let ((frame (first-frame env)))
          (scan (frame-variables frame) (frame-values frame)))))
  (env-loop env))
组件4：primitives and initial env
Global Environment 以及其中的 primitive procedures 是功能完整的 Scheme 解释器不可缺少的一部分，否则我们需要重复制造许多轮子：
(define primitive-procedures
  (list (list 'car car)
        (list 'cdr cdr)
        (list 'cons cons)
        (list 'null? null?)
        (list '+ +)
        (list '> >)
        (list '= =)
        (list '* *)
        ; ... more primitives
  ))
​
(define (setup-environment)
  (let ((initial-env (extend-environment 
                      (primitive-procedure-names)
                      (primitive-procedure-objects)
                      the-empty-environment)))
    (define-variable! 'true #t initial-env)
    (define-variable! 'false #f initial-env)
    initial-env))
(define the-global-environment (setup-environment))
组件5：read-eval-print loop
和解释器的 evaluator 交互，需要 read-eval-print loop (REPL) 组件，它读取用户输入、eval 表达式、打印结果然后再次等待用户输入，不断循环。
(define (driver-loop)
  (prompt-for-input input-prompt)
  (let ((input (read))
    (let ((output (m-eval input the-global-env)))
      (announce-output output-prompt)
      (user-print output)))
  (driver-loop))
Scoping
不论是何种语言都有 Scoping 的概念，以 Scheme 为例：当我们 evaluate procedures 的时候，在 procedure body 中会遇到两种不同的 symbol:
bound parameters: 在 procedure 的参数中定义过的 symbol
free variables: 在 procedure 的参数中未定义过的 symbol
我们如何找到 free variables 对应的值就是所谓的 scoping。
Lexical Scoping
Lexical Scoping 指的就是在 procedure 被定义时的环境中寻找 free variables 的 bindings。具体可以看一下 make-procedure 的实现：
(define (make-procedure parameters body env)
  (list 'procedure parameters body env))
make-procedure 在创建 procedure 的过程中把当前环境也保存在其中，它将被用于寻找 free variables 的 bindings。在 Lexical binding 的情形中：
> (define (foo x y)
    (lambda (z) (+ x y z)))
> (define bar (foo 1 2))
> (bar 3)
6
其中 foo 的内环境是 x = 1, y = 2，外环境是 GE；bar 的内环境是 z = 3，外环境是 foo 的内环境。因此在 eval (bar 3) 的时候，会在 bar 的内环境中找到 z，bar 的外环境 （即 foo 的内环境）中找到 free variables - x, y 对应的值。
Dynamic Scoping
Dynamic scoping 指的就是在 procedure 被调用时的环境中寻找 free variables 的 bindings。在 dynamic scoping 的情形中：
> (define (pooh x)
    (bear 20))
> (define x 3)
> (define (bear y)
    (+ x y))
> (pooh 9)
29
> (bear 20)
23
在 eval 表达式 (pooh 9) 和表达式 (bear 20) 的过程中，bear procedure 的调用环境不同，因此得到的 free variable x 的值不同，eval 的结果也就不同。如果你熟悉 ECMAScript，阅读完本节后，ECMAScript 中的 this binding 对你来说应该很容易理解。
Dynamic Scoping Scheme
显然，目前构建的 Scheme 解释器采用的是 Lexical Scoping，如果我们想造一个 Dynamic Scoping 的 Scheme，需要怎么做呢？本节课一直强调的一句话是 "eval 和 apply 定义了 Scheme 的 semantics"，显然 Scoping 属于 semantics，因此要改变 Scoping 当然应当修改 eval 和 apply。
首先 make-procedure 不需要保留环境
(define (make-procedure parameters body)
  (list 'procedure parameters body))
​
(define (m-eval exp env)
  (cond
    ;...
    ((lambda? exp)
      (make-procedure (lambda-parameters exp)
        (lambda-body exp))) ; 去除 env
    ;...
    ((application? exp)
     (d-apply (m-eval (operator exp) env)
              (list-of-values (operands exp) env)
              env))         ; 新增 env
    (else (error "Unkown expression -- M-EVAL" exp))))
然后再修改 d-apply ，在 extend-environment 的时候使用 calling environment 而不是 procedure environment
(define (d-apply procedure arguments calling-env)
  (cond ((primitive-procedure? procedure)
         (apply-primitive-procedure procedure arguments))
        ((compound-procedure? procedure)
         (eval-sequence
           (procedure-body procedure)
           arguments
           calling-env)))
        (else (error "Unkown procedure" procedure))))
搞定！这里我们再次体会到了 semantics 与 syntax 的分离的好处，改变 semantics 中的 scoping 的同时 syntax 不受丝毫影响。
小结
eval 和 apply 定义了 Scheme 的 semantics
syntax procedures 定义了 Scheme 的 syntax
semantics 和 syntax 的隔离使得二者可以单独改变而不影响对方
参考
​Youtube: SICP-2004-Lecture-18​
​MIT6.006-SICP-2005-Lecture-notes-18​
​MIT6.006-SICP-2005-Lecture-codes​

MIT - 6.001 - SICP - Previous

构建 Scheme 解释器

Next - MIT - 6.001 - SICP

Normal Order (Lazy) Evaluation

Last modified 3yr ago

Copy link

Outline