4.1 The Metacircular Evaluator - CloneableX/SICP-learning GitHub Wiki
Lisp 求值器会被实现为一个 Lisp 程序，这就如同一个循环。不过求值只是一个过程，由于 Lisp 也是一种可用于描述过程的工具，所以它十分适合用于描述求值过程。如果一个求值器是由它要运算的语言编写则称为 元循环（metacircular）。
元循环求值器本质上是环境计算模型的一个 Scheme 公式。环境模型包含下面两个基础部分：
- 计算复合形式（非特殊形式的复合表达式）时，优先计算子表达式，然后向计算数子表达式的值应用运算符子表达式的值。
- 向一组参数应用一个复合程式时，需要在一个新环境中运算程式体。为了构造此环境，需要一个框架继承程式对象的环境部分，此框架中存在程式形式参数与程式应用的参数的绑定关系。
上述两条规则描述了计算过程的本质，这个基本的循环中存在表达式在计算环境中向被应用参数程式的演化，然后再演化至运算于新环境中的新表达式，不断持续，直到运算的标识能够在整个环境中被找到，并且应用于一个能够直接调用的基础程式，具体形式如下图。整个运算循环是由其中的两个关键程式相互作用形成，分别是 eval 和 apply。
求值器的实现信赖于定义被运算表达式的语法程式。所以需要通过数据抽象创建独立于语言表示方式的求值器。例如，相比通过列表开头元素是否含有 set! 标识判断是否赋值操作，我们更愿意通过抽象的方式使用 assignment? 程式进行判断，以及通过 assignment-variable 和 assignment-value 获取赋值操作的其他部分数值。关于表达式的实现会在后面讲解。除此之外，还有一些特殊的程式，比如 make-procedure 能够构造复合程式，lookup-variable-value 能够访问变量值，以及 apply-primitive-procedure 能够向一组参数应用一个基础程式。
求值过程相当于 eval 和 apply 的交互过程。
eval 的参数为一个表达式和一个环境。它对表达式进行分类及导向其运算。eval 的作用是进行表达式语法类型的案例分析。为了保持 eval 程式的通用性，需要将表达式的类型判定抽象化，使其不需要针对不同表达式类型的表示方式进行特殊定制。每种类型的表达式都有一个谓词判断方法以及一个获取表达式其他部分的抽象方法。这些抽象语法使我们能够轻易使用类似的语法程式组合对编程语言的语法进行修改。
- 对于自运算的表达式（比如数字），
eval返回表达式本身 -
eval只能在环境中查找变量对应的值
- 对于加引号的表达式，
eval返回被引号包含的表达式部分 - 向变量赋值（或者定义）必须递归调用
eval计算分配给变量的新数值。环境也需要修改（或创建）变量与数值的绑定关系 -
if表达式需要通过特殊过程计算，如果谓词判断为真则直接运算结果，否则进行另一个表达式的运算 -
lambda表达式必须转换为可应用的程式，程式中包括参数及程式体，程式体指向运算此lambda表达式的环境 -
begin表达式按编写顺序执行一系列表达式 -
cond需要转换为内嵌的if表达式再进行运算
- 在程式应用时，
eval需要递归运算运算符部分和组合的运算数。程式本身和参数都会传递给apply，然后由apply处理实际的程式应用。
下列是 eval 的实现。
(define (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) (eval (cond->if exp) env))
((application? exp)
(apply (eval (operator exp) env)
(list-of-values (operands exp) env)))
(else
(error "Unknown expression type: EVAL" exp))))为了代码整洁，eval 通过 cond 进行案例分析的实现。上述实现方式的劣势在于无法在不修改 eval 实现代码的基础上扩展新的表达式类型，所以只能处理相对固定的表达式。在多数 Lisp 的实现中，都是通过数据导向风格进行表达式类型的分发。这种方式能够允许用户在不修改 eval 代码的情况下实现对表达式类型的扩展。
apply 接收两个参数，一个参数为程式，另一个参数为程式将要应用的参数列表。apply 将程式分为两种类型，一种能够通过 apply-primitive-procedure 应用的基础类型，另一种是需要按程式体顺序执行的复合程式。复合程式体运算的环境以存储程式的框架为基础环境进行构建，在此框架中维护了程式参数与应用时参数值的绑定关系。下列为 apply 的实现。
(define (apply procedure arguments)
(cond ((primitive-procedure? procedure)
(apply-primitive-procedure procedure arguments))
((componound-procedure? procedure)
(eval-sequence
(procedure-body procedure)
(extend-environment
(procedure-parameters procedure)
arguments
(procedure-environment procedure))))
(else
(error "Unknown procedure type: APPLY" procedure))))eval 在运算一个程式时，它会通过 list-of-values 生成程式应用时的参数列表。list-of-values 的参数为计算数组合，list-of-values 需要运算每个计算数并返回对应的值列表。
(define (list-of-values exps env)
(if (no-operands? exps)
'()
(cons (eval (first-operand exps) env)
(list-of-values (rest-operands exps) env))))eval-if 将计算 if 表达式的谓词部分，如果运算结果为 true，eval-if 将计算紧接着的表达式，否则将计算另一个表达式。
(define (eval-if exp env)
(if (true? (eval (if-predicate exp) env))
(eval (if-consequent exp) env)
(eval (if-alternative exp) env)))通过 eval-if 中的 true? 强调实现语言与被实现语言间的关联问题。if-predicate 在被实现的语言中发生运算，所以需要调用针对相应语言的值进行判断。true? 谓词解释器会将参数转换为实现语言中 if 能够判断的数值，也就是说元循环中表示的真值与 Scheme 底层的真值可能并不相同。
eval-sequence 用于 apply 中运算程式体中的一系列表达式，以及用于 eval 中计算 begin 中的一系列表达式。它的参数是一组表达式和一个环境，并且要按表达式出现的顺序进行运算，返回的结果是最后一个表达式的值。
(define (eval-sequence exps env)
(cond ((last-exp? exps)
(eval (first-exp exps) env))
(else
(eval (first-exp exps) env)
(eval-sequence (rest-exps exps) env))))下列程式将处理变量的赋值操作。它通过 eval 查找被赋值的数值及传递的变量，并将对应数值和变量通过 set-variable-value! 注册至目标环境中。
(define (eval-assignment exp env)
(set-variable-value! (assignment-variable exp)
(eval (assignment-value exp) env)
env)
'ok)定义变量的实现方式与上述程式类似。
(define (eval-definition exp env)
(define-variable! (definition-variable exp)
(eval (definition-value exp) env)
env)
'ok)在定义变量和赋值变量操作的结尾我们返回的结果为 ok 标识。
求值器就是第二章中提到过的标识微分程序，因为它们都操作标识表达式。同时它们要计算表达式的结果都需要递归运算表达式中的元素，并将结果按表达式类型进行整合。而且它们都通过数据抽象的方式将运算的通用规则与具体的表达式表示方式解耦。在微分程序中需要通过代数表达式的前缀判断表达式类型，对于求值器程序也是同样的道理。所以在求值器中，表达式的语法仅由程式分类和表达式其余部分决定。
下面是我们新开发的编程语言中的语法约定。
- 只有数字和字符串能够自运算
(define (self-evaluating? exp)
(cond ((number? exp) true)
((string? exp) true)
(else false)))- 变量通过标识方式表示
(define (variable? exp) (symbol? exp))- 有引号的表达式语法为
(quote <text-of-quotation>)
(define (quoted? exp) (tagged-list? exp 'quote))
(define (text-of-quotation exp) (cadr exp))quoted? 通过 tagged-list? 实现，tagged-list? 能够判断列表是否以指定标识开头。
(define (tagged-list? exp tag)
(if (pair? exp)
(eq? (car exp) tag)
false))- 赋值语法为
(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))))-
lambda表达式是以lambda标识开头的列表
(define (lambda? exp) (tagged-list? exp 'lambda))
(define (lambda-parameters exp) (cadr exp))
(define (lambda-body exp) (cddr exp))接下来还需要提供 make-lambda 给 definition-value 使用。
(define (make-lambda parameters body)
(cons 'lambda (cons parameters body)))- 条件表达式由
if开头，并存在一个谓词、一个谓词为真时要运算的结果及另一个结果（可选）。如果表达式没有另一个结果可以将false作为另一个结果返回。
(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 转换时使用。
(define (make-if predicate consequent alternative)
(list 'if predicte consequent alternative))-
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 进行转换的程式。
(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))- 程式应用是复合程式，所以不属于之前的任意表达式类型。表达式的
car为运算符，cdr为运算数列表
(define (application? exp) (pair? exp))
(define (operator exp) (car exp))
(define (operands exp) (cdr exp))
(define (no-operands? ops) (null? ops))
(define (first-operand ops) (car ops))
(define (rest-operands ops) (cdr ops))当前实现的语言中的一些特殊形式会被定义在包含其他特殊形式的表达式内部。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 转换为 if 实现的方式有利于简化求值器，因为这样能够有效减少需要直接运算的特殊形式。
在我们实现的语法程序中需要包含提取 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-cluases clauses)
(if (null? clauses)
'false
(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 表达式也是派生表达式。
为了定义其他的表达式语法，求值器实现也需要定义被用到的数据结构，它们通常是执行程序的一部分，比如程式、环境、true 及 false 的表现形式。
对于条件表达式，只要不是 false 对象则为 true
(define (true? x) (not (eq? x false)))
(define (false? x) (eq? x false))为了处理基础程式，先假设下列程式可以使用
-
(apply-primitive-procedure <proc> <args>)对传递的参数值应用指定的程式，并返回应用结果 -
(primitive-procedure? <proc>)检测<proc>是否为基础程式
处理基础程式的原理会在后面讨论。
复合程式由参数、程式体和环境构成，并通过 make-procedure 构建。
(define (make-procedure parameters body env)
(list 'procedure parameters body env))
(define (compound-procedure? p)
(tagged-list? p 'procedure))
(define (procedure-parameters p) (cadr p))
(define (procedure-body p) (caddr p))
(define (procedure-environment p) (cadddr p))求值器需要维护环境，就像第三章中描述的一般，环境由一组框架组成，每个框架都是一个绑定相关变量及对应变量值的表，所以通过下列操作便可维护环境。
-
(lookup-variable-value <var> <env>)返回在环境<env>中与标识<var>绑定的变量值，如果变量尚未绑定将抛出错误 -
(extend-environment <variables> <values> <base-env>)返回一个新环境，并通过变量名列表<variables>，以及对应的变量值列表<values>和闭包环境<base-env>构建一个新的框架 -
(define-variable! <var> <value> <env>)在环境<env>的第一个框架中添加变量<var>与变量值<value>的绑定关系 -
(set-variable-value! <var> <value> <env>)修改环境<env>中变量<var>的绑定关系，将变量<var>与变量值<value>绑定，如果变量尚未绑定将抛出错误
为了实现上述操作，需要通过框架列表的形式表示环境，并且某个环境的闭包环境通过 cdr 可从列表中获取，空的环境就是空列表。
(define (enclosing-environment env) (cdr env))
(define (first-frame env) (car env))
(define the-empty-environment '())环境的每个框架都是一对列表，一个列表是框架中绑定的变量，另一个列表是对应的变量值。
(define (make-frame variables values)
(cons variables values))
(define (frame-variables frame) (car frame))
(define (frame-values frame) (cdr frame))
(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 arguments supplied" vars vals)
(error "Too few arguments supplied" vars vals))))为了查找环境中的变量，需要搜索首个框架中变量列表。如果查找到目标变量，则返回变量值列表中对应的元素；否则，继续查找当前环境的闭包环境，一直持续下去，直到出现空环境，此时将抛出变量未绑定的错误。
(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" var)
(let ((frame (first-frame env)))
(scan (frame-variables frame)
(frame-values frame)))))
(env-loop env))为了在指定环境中为某个变量设定新变量值，需要通过 lookup-variable-value 查找变量并修改对应的数值。
(define (set-variable-value! var val env)
(define (env-loop env)
(define (scan vars vals)
(cond ((null? vars)
(env-loop (enclosing-environment env)))
((eq? var (car vars)) (set-car! vals val))
(else (scan (cdr vars) (cdr vals))))
(if (eq? env the-empty-environment)
(error "Unbound variable: SET!" var)
(let ((frame (first-frame env)))
(scan (frame-variables frame)
(frame-values frame)))))
(env-loop env))定义一个变量时，首先会搜索首个框架中是否存在该变量，如果变量存在则改变变量与变量值的绑定关系（如同 set-variable-value! 一样），如果绑定关系不存在，则在首个框架中添加新变量。
(define (define-vairable! var val env)
(let ((frame (first env)))
(define (scan vars vals)
(cond ((null? vars)
(add-binding-to-frame! var val frame))
((eq? var (car vars)) (set-car! vals val))
(else (scan (cdr vars) (cdr vals)))))
(scan (frame-variables frame) (frame-values frame))))目前我们实现的环境只是环境多种实现方案中的一种。当通过数据抽象将求值器与具体的表现形式解耦后，我们可以根据自己的意愿修改环境的表现形式。在生产级的 Lisp 系统中，求值器中环境操作（特别是变量查询）的效率对整个系统的性能有着重要的影响。目前的实现方式虽然简洁明了，但因为效率低下所以无法直接应用于生产级系统中。
给定求值器，我们就拥有了关于 Lisp 表达式运算过程的描述。将求值器通过程序的方式实现有利于我们像运转程序一样运转它。这向我们提供了一个运转于 Lisp 中，能够按 Lisp 表达式运算过程运转的模型。它可被视作求值器规则的实验性框架，这是后面章节要讨论的事情。
求值器最终会将表达式拆分至基础程式，所以运行求值器就是创建一个基于 Lisp 底层系统调用基础程式模型的机制。
这项机制是一个关于基础程式名称的绑定关系描述，所以在 eval 运算基础程式运算符时会先查找进行 apply 的程式对象。因此，我们需要创建一个全局环境，全局环境中维护着基础程式与基础程式名称的关联关系。当然，全局环境中也包括 true 和 false 标识，只有这样才能够在表达式运算时使用对应变量。
(define (setup-environment)
(let ((initial-env
(extent-enviroment (primitive-procedure-names)
(primitive-procedure-objects)
the-empty-environment)))
(define-variable! 'true true initial-env)
(define-variable! 'false false initial-env)
initial-env))
(define the-global-environment (setup-environment))整个过程中并不关心基础程式对象的具体形式，只需要 apply 能够通过 primitive-procedure? 和 apply-primitive-procedure 甄别和应用基础程式即可。我们设计的编程语言中将 primitive 作为列表首个元素表示基础程式，其余部分包含着该程式在 Lisp 底层的实现。
(define (primitive-procedure? proc)
(tagged-list? proc 'primitive))
(define (primitive-implementation proc) (cadr proc))setup-environment 可以从列表中获取基础程式的名称和实现。
(define primitive-procedures
(list (list 'car car)
(list 'cdr cdr)
(list 'cons cons)
(list 'null? null?)
<more primitive>))
(define (primitive-procedure-names)
(map car primitive-procedures))
(define (primitive-procedure-objects)
(map (lambda (proc) (list 'primitive (cadr proc)))
primitive-procedures))为了应用基础程式，还需要通过 Lisp 底层系统将程式实现作为参数应用。
(define (apply-primitive-procedure proc args)
(apply-in-underlying-scheme
(primitive-implementation proc) args))为了方便观察运行时的元循环求值器情况，需要使用驱动循环，驱动循环是一种来自 Lisp 底层系统的读取-运算-打印循环。它首先会打印提示，然后读取输入的表达式，接着在全局环境中运算表达式，最后将运算结果打印输出。我们在每个输出结果的前面都打印了输出提示，以避免与其中输出打印的表达式结果混淆。
(define input-prompt ";;; M-Eval input:")
(define output-prompt ";;; M-Eval value:")
(define (driver-loop)
(prompt-for-input input-prompt)
(let ((input (read)))
(let ((output (eval input the-global-environment)))
(announce-output output-prompt)
(user-print output)))
(driver-loop))
(define (prompt-for-input string)
(newline) (newline) (display string) (newline))
(define (announce-output string)
(newline) (display string) (newline))在 driver-loop 程式中使用了一个特殊的打印程式 user-print，通过这个程式能够避免打印复合程式的环境部分，否则会出现一个极长（甚至循环的）列表。
(define (user-print object)
(if (compound-procedure? object)
(display (list 'compound-procedure
(procedure-parameters object)
(procedure-body object)
'<procedure-env>))
(display object)))现在只需要初始化全局环境再开启驱动循环便可能运行求值器。下面是一些交互效果。
(define the-global-environment (setup-environment))
(driver-loop)
;;; M-Eval input:
(define (append x y)
(if (null? x)
y
(cons (car x) (append (cdr x) y))))
;;; M-Eval value:
ok
;;; M-Eval input:
(append '(a b c) '(d e f))
;;; M-Eval value:
(a b c d e f)在思考 Lisp 程式运算 Lisp 表达式时，另一个相似的概念对我们会有所帮助。从实操角度出发，程序就是一台被抽象机器（也许该机器无限大）的描述。例如，思考下列计算阶乘的程序。
(define (factorial n)
(if (= n 1) 1 (* (factorial (- n 1)) n)))我们可以将上述程序视作由减法、乘法、相等检测、一个双位开关和另一个阶乘机器共同组成。并且阶乘机器是无限的，因为它包含不属于它的另一个阶乘机器。下图展示了阶乘机器的各个组成部分及运作流程。
与之类似，我们也可以将求值器视作一个特殊的机器，不过此机器的输入是另一台机器的描述。当提供输入后，求值器会自我配置并按输入机器的描述模拟。例如，如果我们将 factorial 的定义作为求值器的输入，求值器的阶乘运算过程如下图。
从这个角度出发，求值器就是一台通用机器，它能够模拟其他通过 Lisp 程序描述的机器，这个结论十分惊人。试想象电路的求值器，它也是一个电路，不过能将其他电路的编码输入其中。如果输入一个过滤器电子元器件的描述，电路求值器会按过滤器的描述运作。尽管电路求值器存在无法想象的复杂度，但程序求值器却如此简单。
求值器另一个惊人的方面是它扮演着数据对象和程序语言之间的桥梁。如果求值器程序正在运转，此时用户又向求值器输入了一个表达式，并期待着表达式结果的输出。从用户的角度来看，类似 (* x x) 的输入表达式就是编程语言中的表达式，并且求值器应该运行它。不过从求值器的角度来看，表达式就是一个按规则排列并且可维护的列表（一个由 * x x 标识组成的列表）。
所以用户看来的程序只是求值器的数据。实际上，忽略这两种视角的区别会得到一些便利，它能够使用户拥有将 Lisp 表达式明确作为数据对象运算的能力，只需要用户在程序中调用基础程式 eval 即可。许多 Lisp 方言都提供了基础程式 eval，接收参数依然是一个表达式和一个环境，并最终运算得出表达式的结果。所以 (eval '(* 5 5) user-initial-environment) 和 (eval (cons '* (list 5 5)) user-initial-environment) 的结果都是 25。
环境模型和元循环求值器都是依次执行表达式定义并一次只扩展一个定义的环境框架。这为程序开发提供了极大的便利，因为利用这个机制程序员可以在程式中定义新程式。不过，如果你仔细考虑通过代码块结构实现内嵌程式，会发现按名称进行的环境扩展并不是定义局部变量的最佳实现。
思考下列内嵌定义程式。
(define (f x)
(define (even? x) (if (= n 0) true (odd? (- n 1))))
(define (odd? n) (if (= n 0) false (even? (- n 1))))
<rest of body of f>)上述程式在程式体中定义了 odd? 程式，并在 odd? 的实现中调用同样定义于程式体的 even? 程式。odd? 作用范围是整个 f 的程式体中，不仅仅是从 f 程式体开始至 odd? 定义出现时为止。也就是说，当我们认为 odd? 是基于 even? 程式进行定义时，最合理的思路是将两个程式视作在定义时都被添加至环境中。更抽象地表述，代码块结果定义的程式名称能够在被定义的整个程式体内部使用。
碰巧的是，我们实现的解释器也能够正确运算 f 表达式，不过这是一个意外情况。当内部程式定义首次出现时，在程式没有被调用前内部程式并不会被运算。所以 odd? 会在 even? 执行时被定义，实际上顺序求值器得出的结果与前面谈到的并行定义内部程式实现的运算结果一致。
不过，通过一个简单的方法便能够使内部定义的名字出现在同一作用域，相当于定义局部变量时在执行任意值表达式之前便能够将其注册至当前环境中。实现的方法是使用 lambda 表达式进行语法转换，在运算 lambda 表达式体之前，需要扫描表达式体中的所有内部定义并处理它们。内部定义的变量通过 let 创建，并通过赋值绑定变量与数值的关系。例如，当出现下列程式时
(lambda <vars>
(define u <e1>)
(define v <e2>)
<e3>)将被转换为如下程式。
(lambda <vars>
(let ((u '*unassigned*)
(v '*unassigned*))
(set! u <e1>)
(set! v <e2>)
<e3>))上述表达式中的 *unassigned* 为特殊标识，变量值为此标识的变量被使用时将抛出尚未被赋值的错误。
另一种扫描内部定义的策略与上面展示的语法转换不同，它限制被定义的变量值要在不使用任何变量值的情况下进行运算。
之前实现的求值器虽然简单却效率低下，原因为表达式的语法分析和执行混杂在一起。因此，如果一个程序被多次执行，语法也会被分析多次。例如，思考使用下列的 factorial 定义运算 (facotrial 4)。
(define (factorial n)
(if (= n 1) 1 (* (factorial (- n 1)) n )))每次 factorial 被调用时，求值器都需要判断程式体中的 if 表达式以及抽取其中的谓词。接着只是运算谓词并分派它的数值。每次运算 (* (factorial (- n 1)) n) 表达式或 (factorial (- n 1)) 和 (- n 1) 表达式时，求值器都需要在 eval 中进行案例分析，再决定如何应用表达式，并且还需要提取表达式的运算符和运算数。可见语法分析的过程十分消耗资源，如果再重复运行无疑是巨大的浪费。
我们可以将求值器改造为只对同一表达式执行一次语法分析，以此达到提高效率的目的。所以我们需要将 eval 拆分为两个部分，执行程式的部分参数为环境并完成整个运算，而另一部分 analyze 语法分析的结果将会被保存起来，所以当程式被多次调用时语法分析也只会进行一次。
由于 eval 被拆分为分析和执行两部分，所以实现被改写为如下形式。
(define (eval exp env) ((analyze exp) env))analyze 的计算结果是被执行的程式，并应用于当前环境。analyze 与之前 eval 的案例分析基本一致，不同的是只需要进行语法分析，而不需要完成运算。
(define (analyze exp)
(cond ((self-evaluating? exp) (analyze-self-evaluating exp))
((quoted? exp) (analyze-quoted exp))
((variable? exp) (analyze-variable exp))
((assignment? exp) (analyze-assignment exp))
((definition? exp) (analyze-definition exp))
((if? exp) (analyze-if exp))
((lambda? exp) (analyze-lambda exp))
((begin? exp) (analyze-sequence (begin-actions exp)))
((cond? exp) (analyze (cond->if exp)))
((application? exp) (analyze-application exp))
(else (error "Unknown expression type: ANALYZE" exp))))其中最简单的语法分析程式是自运算表达式，它将返回一个忽略环境参数的可执行程式，该程式会返回被计算的表达式。
(define (analyze-self-evaluating exp)
(lambda (env) exp))对于被引号包围的表达式，需要提取引号中的表达式部分，不过此时只是语法分析不需要执行。
(define (analyze-quoted exp)
(let ((qval (text-of-quotation exp)))
(lambda (env) qval)))查找变量值需要在执行过程中处理，因为它依赖于提供的环境。
(define (analyze-variable exp)
(lambda (env) (lookup-variable-value exp env)))analyze-assignment 只有在执行阶段才会真正的赋值，不过 assignment-value 也会进行语法分析（递归式地），正因为此时该表达式已经进行过一次语法分析，所以对整体执行效率将带来显著的提高。它与定义操作的语法分析类似。
(define (analyze-assignment exp)
(let ((var (assignment-variable exp))
(vproc (analyze (assignment-value exp))))
(lambda (env)
(set-variable-value! var (vproc env) env)
'ok)))
(define (analyze-definition exp)
(let ((var (definition-variable exp))
(vproc (analyze (definition-value exp))))
(lambda (env)
(define-variable! var (vproc env) env)
'ok)))对于 if 表达式，需要提取其中的谓词、正确条件下的表达式及错误条件下的表达式。
(define (analyze-if exp)
(let ((pproc (analyze (if-predicate exp)))
(cproc (analyze (if-consequent exp)))
(aproc (analyze (if-alternative exp))))
(lambda (env) (if (true? (pproc env))
(cproc env)
(aproc env)))))对 lambda 表达式的语法分析也会带来较大的效率提高。因为即使程式计算时多次应用了 lambda 表达式，但语法分析时只需要对 lambda 表达式进行一次分析。
(define (analyze-lambda exp)
(let ((vars (lambda-parameters exp))
(bproc (analyze-sequence (lambda-body exp))))
(lambda (env) (make-procedure vars bproc env))))一组表达式的语法分析会有更多内容。其中的每个表达式都需要分析，并调用执行程式。执行程式既要接收环境参数，又要在该环境参数的基础上依次调用执行每个程式。
(define (analyze-sequence exps)
(define (sequentially proc1 proc2)
(lambda (env) (proc1 env) (proc2 env)))
(define (loop first-proc rest-procs)
(if (null? rest-procs)
first-proc
(loop (sequentially first-proc (car rest-procs))
(cdr rest-procs))))
(let ((procs (map analyze exps)))
(if (null? procs) (error "Empty sequence: ANALYZE"))
(loop (car procs) (cdr procs))))在分析基础程式时，需要分析运算符和运算数，并构造一个可执行程式调用运算符的执行程式和运算数的执行程式。并将这些内容传递给 execute-application，它与 apply 类似，不过它们的不同点是此时复合程式的程式体已经完成了语法分析，此时不再进行更多的语法分析。
(define (analyze-application exp)
(let ((fproc (analyze (operator exp)))
(aprocs (map analyze (operands exp))))
(lambda (env)
(execute-application
(fproc env)
(map (lambda (aproc) (aproc env))
aprocs)))))
(define (execute-application proc args)
(cond ((primitive-procedure? proc)
(apply-primitive-procedure proc args))
((componound-procedure? proc)
((procedure-body proc)
(extend-environment
(procedure-parameters proc)
args
(procedure-environment proc))))
(else
(error "Unknown procedure type: EXECUTE-APPLICATION"
proc))))我们新实现的求值器与之前实现时使用的数据结构、程式语法和运行时支持程式都是相同的。