Eval：求值过程
剖析元循环求值器中 mc-eval 的工作原理，逐行讲解 Scheme 如何对各种表达式求值。
本课接下来的概念在第一次学习时可能会令人困惑，所以遇到难以理解的句子，请仔细反复阅读！同样重要的是记住：元循环求值器的核心在于抽象，所以如果你一时看不懂某个东西是怎么实现的，它很可能在后面的章节中会讲到。
Eval
(define (eval-1 exp)
(cond ((constant? exp) exp)
((symbol? exp) (eval exp)) ; 使用底层 Scheme 的 EVAL
((quote-exp? exp) (cadr exp))
((if-exp? exp)
(if (eval-1 (cadr exp))
(eval-1 (caddr exp))
(eval-1 (cadddr exp))))
((lambda-exp? exp) exp)
((pair? exp) (apply-1 (eval-1 (car exp)) ; 对运算符求值
(map eval-1 (cdr exp))))
(else (error "bad expr: " exp))))这段代码看起来眼熟吗？应该眼熟——它就是你在第 6 课学过的 Racket-1/Scheme-1 解释器的一部分！看第 3 行，你会发现 eval-1 用的是 Scheme 的 eval 过程。在第 6 课里，你不必太在意这些细节，因为 Scheme 的 eval 过程替你包办了所有细节。但 Scheme 的 eval 背后又有哪些细节呢？
现在就来研究 mc-eval 是怎么写的。看一看，并和 eval-1 作比较：
(define (mc-eval exp env)
(cond ((self-evaluating? exp) exp)
((variable? exp) (lookup-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) (mc-eval (cond->if exp) env))
((application? exp)
(mc-apply (mc-eval (operator exp) env)
(list-of-values (operands exp) env)))
(else
(error "Unknown expression type -- EVAL" exp))))定义 mc-eval，就是要让它承担底层 Scheme 中 eval 的职责：解释 Scheme 的语法规则，并把每一次调用分解为相应的动作。看不懂也没关系。我们会逐行过一遍这段代码。
mc-eval 做什么？
过程 mc-eval 接受一个表达式和一个环境作为实参。它对表达式进行分类，并引导其求值过程。为了保持过程的通用性，我们用抽象的方式判断表达式的类型，不对各类表达式的具体表示方式作任何承诺。每类表达式都有一个用于检验它的谓词，以及选取其组成部分的抽象手段。
当 mc-eval 处理过程应用时，它用 list-of-values 生成该过程所要应用的实参表。list-of-values 以组合式的运算数为实参，逐个求值，并返回相应值组成的表：
(define (list-of-values exps env)
(if (no-operands? exps)
'()
(cons (mc-eval (first-operand exps) env)
(list-of-values (rest-operands exps) env))))从左到右？还是从右到左？ 给定若干运算数，list-of-values 会递归构造出一个嵌套的 cons 结构，其中包含对每个运算数的 mc-eval 调用。注意，我们无法从这个定义看出元循环求值器是从左到右还是从右到左求值运算数的。它的求值顺序是从底层 Scheme 继承来的：如果 list-of-values 中传给 cons 的实参是从左到右求值的，那么 list-of-values 就从左到右求值运算数；反之，如果传给 cons 的实参从右到左求值，那么运算数就从右到左求值。
请写一个版本的 list-of-values，无论底层 Scheme 的求值顺序如何，都保证从左到右求值运算数。再写一个从右到左求值运算数的版本。
下面逐行看看条件语句中每个分支的作用。
自求值表达式
对于自求值表达式，例如数，mc-eval 直接返回表达式自身。对于变量，mc-eval 必须在环境中查找它的值。
-
只有数和字符串是自求值的：
(define (self-evaluating? exp) (cond ((number? exp) true) ((string? exp) true) (else false)))
记住，单词不是字符串。字符串使用双引号（例如 "Hello, world!"）。
-
变量用符号表示：
(define (variable? exp) (symbol? exp))
特殊形式
特殊形式：句子与单词
对于被引用的表达式，mc-eval 返回被引用的表达式。
回忆一下，Scheme 的解析器会自动把表达式 '(some text here) 转换成序对 (quote (some text here))。
换句话说，引用都形如 (quote <被引用的文本>)：
(define (quoted? exp)
(tagged-list? exp 'quote))
(define (text-of-quotation exp) (cadr exp)) ; 只返回文本本身，以表的形式打印输出quoted? 基于过程 tagged-list? 定义，后者判断一个表是否以指定符号开头：
(define (tagged-list? exp tag)
(if (pair? exp)
(eq? (car exp) tag)
false))特殊形式：Lambda
lambda 表达式必须被打包成可应用的过程：把 λ 表达式指定的形参和过程体，连同求值时所处的环境一起封装起来。
λ 表达式是以符号 lambda 开头的表：
(define (lambda? exp) (tagged-list? exp 'lambda))
(define (lambda-parameters exp) (cadr exp))
(define (lambda-body exp) (cddr exp))λ 表达式有一个构造函数，definition-value 会用到它：
(define (make-lambda parameters body)
(cons 'lambda (cons parameters body)))特殊形式：序列
-
eval-sequence被apply用来求值过程体中的一系列表达式，也被eval用来求值begin表达式中的一系列表达式。它接受一个表达式序列和一个环境作为实参，按表达式出现的顺序依次求值。返回值是最后一个表达式的值。(define (eval-sequence exps env) (cond ((last-exp? exps) (mc-eval (first-exp exps) env)) (else (mc-eval (first-exp exps) env) (eval-sequence (rest-exps exps) env)))) -
begin把一系列表达式打包成单个表达式。begin表达式要求按表达式出现的顺序求值整个序列。我们为begin表达式定义了语法操作，用于从begin表达式中取出实际的表达式序列，还有返回序列中第一个表达式和其余表达式的选择器。(define (begin? exp) (tagged-list? exp 'begin)) (define (begin-actions exp) (cdr exp)) (define (last-exp? seq) (null? (cdr seq))) (define (first-exp seq) (car seq)) (define (rest-exps seq) (cdr seq))
有一个构造函数 sequence->exp（供 cond->if 使用），它把序列转换成单个表达式，必要时用 begin 包装：
(define (sequence->exp seq)
(cond ((null? seq) seq)
((last-exp? seq) (first-exp seq))
(else (make-begin seq))))
(define (make-begin seq) (cons 'begin seq))特殊形式：条件表达式
-
eval-if在给定环境中求值if表达式的谓词部分。如果结果为真，eval-if求值 consequent（ consequent 分支）；否则求值 alternative（备选分支）：(define (eval-if exp env) (if (true? (mc-eval (if-predicate exp) env)) (mc-eval (if-consequent exp) env) (mc-eval (if-alternative exp) env)))
eval-if 中 true? 的使用，凸显了被实现语言与实现语言之间衔接的问题。if-predicate 在被实现的语言中求值，因此产生的是该语言中的一个值。而解释器中的谓词 true? 负责把这个值转换成实现语言中可以用 if 检验的值：元循环表示中的真值可能与底层 Scheme 的真值表示不同。
true? 和 false? 的定义如下：
(define (true? x)
(not (eq? x false)))
(define (false? x)
(eq? x false))-
if表达式的各个部分需要特殊处理：谓词为真时求值 consequent，否则求值 alternative。(define (if? exp) (tagged-list? exp 'if)) (define (if-predicate exp) (cadr exp)) (define (if-consequent exp) (caddr exp)) (define (if-alternative exp) (if (not (null? (cdddr exp))) (cadddr exp) 'false))
if 表达式有一个构造函数，供 cond->if 把 cond 表达式转换成 if 表达式时使用：
(define (make-if predicate consequent alternative)
(list 'if predicate consequent alternative))- 情况分析（
cond）先被转换成一串嵌套的if表达式，然后再求值。
例如：
(cond ((> x 0) x)
((= x 0) (display 'zero) 0)
(else (- x)))可以表示为：
(if (> x 0)
x
(if (= x 0)
(begin (display 'zero)
0)
(- x)))有一些语法过程用于提取 cond 表达式的各个部分，还有一个过程 cond->if 把 cond 表达式转换成 if 表达式。情况分析以 cond 开头，带有一个由「谓词-动作」子句组成的表。如果子句的谓词是符号 else，该子句就是 else 子句。
(define (cond? exp) (tagged-list? exp 'cond))
(define (cond-clauses exp) (cdr exp))
(define (cond-else-clause? clause)
(eq? (cond-predicate clause) 'else))
(define (cond-predicate clause) (car clause))
(define (cond-actions clause) (cdr clause))
(define (cond->if exp)
(expand-clauses (cond-clauses exp)))
(define (expand-clauses clauses)
(if (null? clauses)
'false ; 没有 else 子句
(let ((first (car clauses))
(rest (cdr clauses)))
(if (cond-else-clause? first)
(if (null? rest)
(sequence->exp (cond-actions first))
(error "ELSE clause isn't last -- COND->IF"
clauses))
(make-if (cond-predicate first)
(sequence->exp (cond-actions first))
(expand-clauses rest))))))像 cond 这样我们选择用语法变换来实现的表达式，称为派生表达式（derived expressions）。let 表达式也是派生表达式。
特殊形式：赋值与定义
给变量赋值（或定义变量）时，必须递归调用 eval 来计算要与该变量关联的新值。环境也必须被修改，以改变（或创建）该变量的绑定。
下面的过程处理对变量的赋值。它调用 eval 找出要赋的值，然后把变量和所得的值传给 set-variable-value!，在指定环境中建立定义。
(define (eval-assignment exp env)
(set-variable-value! (assignment-variable exp)
(mc-eval (assignment-value exp) env)
env)
'ok)变量的定义用类似的方式处理：
(define (eval-definition exp env)
(define-variable! (definition-variable exp)
(mc-eval (definition-value exp) env)
env)
'ok)按照惯例，赋值或定义以符号 ok 作为返回值。
现在来看看赋值表达式是怎么表示的。
赋值形如 (set! <var> <value>)：
(define (assignment? exp)
(tagged-list? exp 'set!))
(define (assignment-variable exp) (cadr exp))
(define (assignment-value exp) (caddr exp))定义形如 (define <var> <value>)，或者形如：
(define (var parameter1 ... parametern)
body)后一种形式（标准过程定义）可以改写为：
(define var
(lambda (parameter1 ... parametern)
body))相应的语法过程如下：
(define (definition? exp)
(tagged-list? exp 'define))
(define (definition-variable exp)
(if (symbol? (cadr exp))
(cadr exp)
(caadr exp)))
(define (definition-value exp)
(if (symbol? (cadr exp))
(caddr exp)
(make-lambda (cdadr exp) ; 形参
(cddr exp)))) ; 过程体And 与 Or
回忆一下第 1 单元中特殊形式 and 和 or 的定义：
and：表达式从左到右求值。只要有任意表达式求值为假，就返回false，其余表达式不再求值。如果所有表达式都求值为真，则返回最后一个表达式的值。如果没有表达式，则返回真。or：表达式从左到右求值。只要有任意表达式求值为真值，就返回该值，其余表达式不再求值。如果所有表达式都求值为假，或者没有表达式，则返回false。
请为求值器添加 and 和 or 作为新的特殊形式：定义相应的语法过程，以及求值过程 eval-and 和 eval-or。或者，说明如何把 and 和 or 实现为派生表达式。
再访 mc-eval 的定义
我们再看一遍 mc-eval 的定义。现在它是否说得通了？
(define (mc-eval exp env)
(cond ((self-evaluating? exp) exp)
((variable? exp) (lookup-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) (mc-eval (cond->if exp) env))
((application? exp)
(mc-apply (mc-eval (operator exp) env)
(list-of-values (operands exp) env)))
(else
(error "Unknown expression type -- EVAL" exp))))等等，等等，什么是 apply？我完全不知道那是什么！
我们将在下一小节探索它。
以下哪些过程的定义中使用了 mc-eval？可能有多个正确答案，请逐一检查每个选项。
要点
在本小节中，你了解了 Scheme 如何使用 mc-eval 及其他过程对表达式求值。
接下来？
进入下一小节，看看 Scheme 如何应用已求值的表达式！