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 的隔离使得二者可以单独改变而不影响对方

参考