5.4 The Explicit Control Evaluator - CloneableX/SICP-learning GitHub Wiki

在 5.1 章节中我们将一些简单的 Scheme 程序转换为了寄存器机器描述。现在我们要将更复杂的程序转换为寄存器机器语言，也就是元循环求值器。在本章节我们将实现 显示控制求值器（explicit-control evaluator），该求值器将展示计算过程中的程式调用和参数传递如何在寄存器和堆栈中运行。同时，显示控制求值器也是 Scheme 的一种解释器，不过是通过类似机器语言的编程语言实现的而已。显示控制求值器能够使用寄存器机器模拟器运行。另外，它也是构建 Scheme 求值器机器语言的实现的基础，或者说它就是能够运算 Scheme 表达式的特殊机器。下图展示了硬件实现的部分，芯片就如同 Scheme 求值器一样运行。芯片设计师开始时要为寄存器机器设计数据路径和控制器规范，它们与本节的求值器描述相似，并在此基础上设计自动化技术构建集成电路布局。

寄存器和操作

在设计显示控制求值器时，必须识别出在该寄存器机器中会使用到的操作。我们通过抽象语法描述元循环求值器，主要是一些程式，比如 quoted?、make-procedure。在实现寄存器机器时，我们需要将这些程式以列表元素的方式组装，以此在寄存器机器中实现这些操作。不过，这会使求值器的实现变得冗长，同时掩盖了基本结构的细节。要厘清这种表现方式，我们将引入 4.1.2 节提出的语法程式，在 4.1.3 节和 4.1.4 节提出的环境相关程式及其他运行时数据的实现。为了完全定制一个能够以底层机器语言编程或在硬件上实现的求值器，我们需要通过更加基础的操作实现这些操作方法，也就是通过在 5.3 节的列表结构实现。

Scheme 求值器寄存器机器包含一个堆栈和 7 个寄存器，7 个寄存器分别是 exp、env、val、continue、proc、argl 和 unev。exp 用于持有可计算的表达式，env 持有正在执行计算的环境。在一次求值计算的结尾，val 持有在指定环境中表达式计算的结果。continue 寄存器用于实现递归，当运算存在子表达式的表达式时求值器需要被递归调用。寄存器 proc、argl 和 unev 将在求值组合式时使用。

我们不会提供数据路径，所以也不会展示寄存器和求值器操作方法的连接情况，也不会提供完整的机器操作列表。这些操作都隐含在求值器控制器的细节之中。

显示控制求值器的核心

求值器的核心元素是以 eval-dispatch 开头的指令序列。该指令序列功能与元循环求值器中的 eval 程式对应。当控制器从 eval-dispatch 开始运行时，它将计算 env 环境中的 exp 表达式。当求值结束时，控制器将跳转到 continue 记录的节点，而表达式计算结果存储于 val 寄存器中。与 eval 程式类似，eval-dispatch 也需要进行表达式类型分析。

eval-dispatch
  (test (op self-evaluating?) (reg exp))
  (branch (label ev-self-eval))
  (test (op variable?) (reg exp))
  (branch (label ev-variable))
  (test (op quoted?) (reg exp))
  (branch (label ev-quoted))
  (test (op assignment?) (reg exp))
  (branch (label ev-assignment))
  (test (op definition?) (reg exp))
  (branch (label ev-definition))
  (test (op if?) (reg exp))
  (branch (label ev-if))
  (test (op lambda?) (reg exp))
  (branch (label ev-lambda))
  (test (op begin?) (reg exp))
  (branch (label ev-begin))
  (test (op application?) (reg exp))
  (branch (label ev-application))
  (goto (label unknown-expression-type))

计算简单表达式

数字、字符串、变量、单引号及 lambda 表达式都没有子表达式需要计算。所以，对于这些种类的表达式只需要将计算结果存储在 val 寄存器中，并根据 continue 跳转继续运行即可。简单表达式的计算过程由下列控制器代码执行。

ev-self-eval
  (assign val (reg exp))
  (goto (reg continue))
ev-variable
  (assign val (op lookup-variable-value (reg exp) (reg env)))
  (goto (reg continue))
ev-quoted
  (assign val (op text-of-quotation) (reg exp))
  (goto (reg continue))
ev-lambda
  (assign unev (op lambda-parameters) (reg exp))
  (assign exp (op lambda-body) (reg exp))
  (assign val (op make-procedure) (reg unev) (reg exp) (reg env))
  (goto (reg continue))

其中 ev-lambda 通过 unev 和 exp 寄存器处理 lambda 表达式的参数和程式体，然后再与 env 中的环境一同通过 make-procedure 运算得出结果。

计算程式应用

程式应用由运算符和运算数组合而成。运算符是一个值为程式的子表达式，而运算数子表达式的运算结果将应用于运算符程式。元循环求值器中 eval 通过递归调用不断计算程式应用的子表达式，然后将结果传递给 apply，再由 apply 执行最终的程式应用。显示控制求值器也要采用类似的方案，其中的递归调用通过 goto 指令实现，然后递归调用前后的寄存器内容通过堆栈存储。所以在每次递归调用前，我们都需要仔细甄别哪些寄存器需要被存储在堆栈中。

程式应用的计算以对操作符转换为程式的计算开始，转换后的运算符程式将应用于计算数。要计算运算符，需要先将它存入 exp 寄存器中再跳转到 eval-dispatch。此时 env 寄存器中的环境正是计算运算符所需要的环境。不过我们需要将 env 储存在堆栈中，因为稍后我们还需要通过此环境计算运算数。同时，还需要将提取存储在 unev 中的运算数储存到堆栈中。然后设置 continue 为 ev-appl-did-operator 节点，使控制器在 eval-dispatch 运算完成后能够继续应用运算符程式。不过，在此之前需要先将 continue 的内容储存在堆栈中。

ev-application
  (save continue)
  (save env)
  (assign unev (op operand) (reg exp))
  (save unev)
  (assign exp (op operator) (reg exp))
  (assign continue (label ev-appl-did-operator))
  (goto (label eval-dispatch))

在运算符子表达式运算结束后，我们要继续计算其中的运算数，并将运算数的计算结果以列表形式组织，然后存储在 argl 中。首先需要从堆栈中取出尚未运算的运算数和环境。然后将 argl 初始化为空列表。然后将运算符计算产生的程式分配给 proc 寄存器。如果该程式应用没有计算数，则直接跳转 apply-dispatch，否则将 proc 存入堆栈中，然后开启参数运算的循环。

ev-appl-did-operator
  (restore unev)
  (restore env)
  (assign argl (op empty-arglist))
  (assign proc (reg val))
  (test (op no-operands?) (reg unev))
  (branch (label apply-dispatch))
  (save proc)

参数计算的每次循环都将计算 unev 列表中的一个运算数，并将计算结果收集到 argl 中。计算运算数时，需要将它存入 exp 寄存器中，然后跳转至 eval-dispatch 节点，接着设置 continue 中存储内容，以保证运算数计算完成后能够跳转回来。不过依然要将收集运算数计算结果的 argl、存储环境的 env 及持有尚未运算的运算数的 unev。比较特殊的情况发生在最后一个运算数的计算中，这种情况需要通过 ev-appl-last-arg 计算。

ev-appl-operand-loop
  (save argl)
  (assign exp (op first-operand) (reg unev))
  (test (op last-operand?) (reg unev))
  (branch (label ev-appl-last-arg))
  (save env)
  (save unev)
  (assign continue (label ev-appl-accumulate-arg))
  (goto (label eval-dispatch))

当运算数计算结束时，所有运算数的计算结果都将收集在 argl 寄存器中。然后计算完的运算数将从 unev 未计算的运算数中删除，然后继续计算其它运算数。

ev-appl-accumulate-arg
  (restore unev)
  (restore env)
  (restore argl)
  (assign argl (op adjoin-arg) (reg val) (reg argl))
  (assign unev (op rest-operands) (reg unev))
  (goto (label ev-appl-operand-loop))

最后一个运算数的求值过程与一般情况有些区别。在计算最后一个运算数时不需要在堆栈中存入环境或尚未计算的运算数。而且，在最后一个运算数计算完成后我们将跳转至 ev-appl-accum-last-arg 节点。此时我们要从堆栈中取出参数列表，并将运算数的计算结果汇入其中，然后从堆栈中取出运算符程式并执行该程式应用。

ev-appl-last-arg
  (assign continue (label ev-appl-accum-last-arg))
  (goto (label eval-dispatch))
ev-appl-accum-last-arg
  (restore argl)
  (assign argl (op adjoin-arg) (reg val) (reg argl))
  (restore proc)
  (goto (label apply-dispatch))

参数求值循环的细节决定了解释器计算运算数组合式的顺序。该顺序并不由元循环求值器决定，元循环求值器只是继承了 Scheme 底层实现的控制结构。因为 first-operand 是通过 car 实现，rest-operands 通过 cdr 实现，所以显示控制求值器计算组合式的运算数时是按从左至右的顺序。

程式应用

apply-dispatch 节点的功能与元循环求值器中的 apply 程式类似。在运行 apply-dispatch 指令序列时，proc 寄存器存储了将要应用的程式，argl 存储了用于程式应用的参数列表。存储于堆栈的 continue 的内容将决定程式计算完成后要继续跳转的节点。当程式应用计算完成时，控制器将跳转到 continue 指定的节点，程式应用计算的结果将存储于 val 中。根据元循环求值器的 apply 来看，此处有两种情况需要考虑。应用程式可能存在基础程式或复合程式两种情况。

apply-dispatch
  (test (op primitive-procedure?) (reg proc))
  (branch (label primitive-apply))
  (test (op compound-procedure?) (reg proc))
  (branch (label compound-apply))
  (goto (label unknown-procedure-type))

我们假设所有的基础程式都已经被实现，所以只需要向程式应用 argl 中的参数列表，并将计算结果存入 val 即可。为了实现基础程式的应用，需要提供一系列实现基础程式的控制器指令，然后在 primitive-apply 中根据 proc 的内容执行对应的指令序列。因为我们目前的研究重点是求值过程的结构而不是基础程式的实现细节，所以我们直接通过 apply-primitive-procedure 计算基础程式。我们只要向寄存器机器中注册 apply-primitive-procedure 程式即可。在基础程式计算完成后，我们将从堆栈恢复 continue 的内容并跳转。

primitive-apply
  (assign val (op apply-primitive-procedure)
              (reg proc)
              (reg argl))
  (restore continue)
  (goto (reg continue))

应用复合程式的过程与元循环求值器的方案一致。我们将构建一个框架，并在框架内绑定程式参数，然后使用该框架扩展负责程式的环境，然后在被扩展的环境中计算程式体的表达式序列。ev-sequence 负责程式体表达式序列的计算。

compound-apply
  (assign unev (op procedure-parameters) (reg proc))
  (assign env (op procedure-environment) (reg proc))
  (assign env (op extend-environment)
              (reg unev) (reg argl) (reg env))
  (assign unev (op procedure-body) (reg proc))
  (goto (label ev-sequenc))

compound-apply 只是为 env 替换了个新数值。与元循环求值器类似，新环境由负责程式的环境、参数列表及对应的参数值构成。

序列求值和尾递归

显示控制求值器的 ev-sequence 与元循环求值器的 eval-sequence 程式十分相似。它负责处理程式体或 begin 表达式中的表达式序列。

begin 表达式通过将待计算的表达式序列存入 unev 中进行运算，并将 continue 推入堆栈，然后跳转至 ev-sequence。

ev-begin
  (assign unev (op begin-actions) (reg exp))
  (save continue)
  (goto (label ev-sequence))

在处理程式体的表达式序列时需要从 compound-apply 节点跳转至 ev-sequence，此时的 continue 已经在 ev-application 运算时就已经被保存。

ev-sequence 和 ev-sequence-continue 会构建一个循环，该循环负责不断计算序列中的每个表达式。未运算的表达式序列一直储存在 unev 中。在计算每个表达式之前，需要检查表达式序列中是否还有表达式需要计算。如果还有表达式尚未计算，将余下的未计算表达式（存储于 unev 中）和计算所需的环境存入堆栈，然后调用 eval-dispatch 计算表达式。上述存入堆栈的两个寄存器内容将在该表达式计算完成后在 ev-sequence-continue 中恢复。

该序列中的最后一个表达式处理过程与一般情况有所区别，需要通过 ev-sequence-last-exp 指令序列处理。至此之后表达式序列中便没有未计算的表达式了，在继续进行 eval-dispatch 步骤前我们不再需要将 unev 和 env 存入堆栈。整个表达式序列的计算结果也就是最后一个表达式的计算结果，所以在最后一个表达式计算完成后，堆栈中除了跳转的节点之外不再存在其他数据。此时我们不再设置 continue 的值，而是直接跳转 eval-dispatch 然后从堆栈恢复 continue 的内容，继续进行计算，所以在进入 eval-dispatch 前需要恢复 continue 的内容，使 eval-dispatch 在表达式计算完成后能够继续进入指定的节点。

ev-sequence
  (assign exp (op first-exp) (reg unev))
  (test (op last-exp?) (reg unev))
  (branch (label ev-sequence-last-exp))
  (save unev)
  (save env)
  (assign continue (label ev-sequence-continue))
  (goto (label eval-dispatch))
ev-sequence-continue
  (restore env)
  (restore unev)
  (assign unev (op rest-exps) (reg unev))
  (goto (label ev-sequence))
ev-sequence-last-exp
  (restore continue)
  (goto (label eval-dispatch))

尾递归

在第 1 章时我们谈到过下列程式是一个迭代过程。虽然该程式从语法上来说是递归形式，但求值器在两次 sqrt-iter 调用间存储传递信息上没有逻辑必要性。如果求值器执行类似于 sqrt-iter 的程式时不需要为程式的递归调用增加存储空间，则这种求值器称为 尾递归（tail recursive） 求值器。在第 4 章元循环求值器的实现中并没有明确该求值器是否尾递归求值器，因为该求值器是继承的底层 Scheme 机制。但是，对于显示控制求值器，我们能够追踪整个求值过程，并在堆栈中查看整个程式调用过程的信息内容。

为了计算表达式序列的最后一个表达式，我们需要直接跳转 eval-dispatch 并且不能向堆栈中存入任何数据，所以我们现在实现的求值器必须是尾递归求值器。因此，即使计算的最后一个表达式是程式调用（例如 sqrt-iter 程式中最后一个表达式可能直接调用 sqrt-iter 程式本身），也不能因此导致堆栈中存入额外信息。

如果我们没有想到在这种情况下不向堆栈存入数据带来的好处，那么我们可能会将 eval-sequence 实现为序列中的所有表达式都按同样的方式计算，将一些寄存器内容存入堆栈，然后计算表达式，计算完成后返回并恢复寄存器的内容，一直重复该过程直到所有的表达式计算完成。

ev-sequence
  (test (op no-more-exps?) (reg unev))
  (branch (label ev-sequence-end))
  (assign exp (op first-exp) (reg unev))
  (save unev)
  (save env)
  (assign continue (label ev-sequence-continue))
  (goto (label eval-dispatch))
ev-sequence-continue
  (restore env)
  (restore unev)
  (assign unev (op rest-exps) (reg unev))
  (goto (label ev-sequence))
ev-sequence-end
  (restore continue)
  (goto (reg continue))

上述指令与之前表达式序列运算的指令的主要区别在于，表达式序列中的最后一个表达式也像序列中的其他表达式一样陷入寄存器内容存入堆栈和从堆栈中恢复的循环中。虽然解释器仍然会为表达式计算出正确的结果，但是这种实现变化对于尾递归来说却是致命的，因为在计算最后一个表达式时会向堆栈存入一些无用的寄存器内容。这些不必要的堆栈存储会在程式的内嵌调用中不断累积。于是，类似 sqrt-iter 的运算过程的空间消耗将与迭代次数成正比，不再是常量的空间消耗。这些区别极其重要。例如，在尾递归情况下，无限循环只需要通过程式调用机制就能表示。

(define (count n)
  (newline) (display n) (count (+ n 1)))

如果没有尾递归，类似的程式最终将导致堆栈溢出，而要表示一个正确的迭代便需要程式调用之外的其他控制机制参与。

条件表达式、赋值及定义

与元循环求值器类似，特殊形式需要按专门的方式计算。对于 if 表达式，必须优先计算谓词表达式，然后根据谓词计算结果决定执行肯定表达式还是否定表达式。

在计算谓词之前，需要将 if 表达式存入堆栈，以便随后从中提取肯定表达式和否定表达式。同时环境也需要存入堆栈，在随后计算肯定表达式或否定表达式时需要该环境，最后还需要将 continue 存入堆栈，稍后我们在执行完 if 表达式后要根据 continue 的内容跳转。

ev-if
  (save exp)
  (save env)
  (save continue)
  (assign continue (label ev-if-decide))
  (assign exp (op if-predicte) (reg exp))
  (goto (label eval-dispatch))

在谓词计算结束后，我们要检测谓词的运算结果，然后根据此结果决定稍后 eval-dispatch 执行的是肯定表达式还是否定表达式。同时需要恢复 env 和 continue 的值，保证接下来回到等待 if 执行完成的结点，以及保证接下来的表达式在正确的环境中运行。

ev-if-decide
  (restore continue)
  (restore env)
  (restore exp)
  (test (op true?) (reg val))
  (branch (label ev-if-consequent))
ev-if-alternative
  (assign exp (op if-alternative) (reg exp))
  (goto (label eval-dispatch))
ev-if-consequent
  (assign exp (op if-consequent) (reg exp))
  (goto (label eval-dispatch))

赋值与定义

赋值由 ev-assignment 负责计算，ev-assignment 首先会计算表达式部分的结果，然后将计算结果注册至环境中。我们假设 set-variable-value! 已经注册为机器中的一个操作方法。

ev-assignment
  (assign unev (op assignment-variable) (reg exp))
  (save unev)
  (assign exp (op assignment-value) (reg exp))
  (save env)
  (save continue)
  (assign continue (label ev-assignment-1))
  (goto (label eval-dispatch))
ev-assignment-1
  (restore continue)
  (restore env)
  (restore unev)
  (perform
   (op set-variable-value!) (reg unev) (reg val) (reg env))
  (assign val (const ok))
  (goto (reg continue))

定义的处理过程与赋值类似。

ev-difinition
  (assign unev (op definition-variable) (reg exp))
  (save unev)
  (assign exp (op definition-value) (reg exp))
  (save env)
  (save continue)
  (assign continue (label ev-definition-1))
  (goto (label eval-dispatch))
ev-definition-1
  (restore continue)
  (restore env)
  (restore unev)
  (perform
   (op definition-variable!) (reg unev) (reg val) (reg env))
  (assign val (cont ok))
  (goto (reg continue))

运行求值器

随着显示控制求值器的实现，我们来到了整个开发的结尾，从第 1 章开始，我们便不断在探索关于求值过程的精准模型。开始时我们以不够正规的替换模型描述求值过程，随后在第 3 章我们将其扩展为环境模型，在环境模型的解释下我们能够处理状态及状态变化。在第 4 章的元循环求值器中，我们使用 Scheme 制作了更加明晰的环境结构，并在表达式计算期间能够创建这些模型。现在，在对寄存器机器的研究中，我们将近距离观察求值器的存储管理、参数传递和控制机制。在每个阶段的学习中，我们不断抛出问题，并解答前一阶段明显不清晰的部分，以及对于求值过程更加精准的理解。要理解显示控制求值器的行为，我们只能通过模拟和监控性能的方式达成。

接下来我们要为求值器机器安装驱动循环。它与之前的 drvier-loop 程式扮演同样的角色。求值器会重复打印提示，然后读取表达式，接着通过 eval-dispatch 计算表达式，最后将结果打印在终端。下列指令负责显示控制求值器控制器的起始部分。

read-eval-print-loop
  (perform (op initialize-stack))
  (perform
   (op promt-for-input) (const ";;EC-Eval input:"))
  (assign exp (op read))
  (assign env (op get-global-environment))
  (assign continue (label print-result))
  (goto (label eval-dispatch))
print-result
  (perform (op announce-output) (const ";;EC-Eval value:"))
  (perform (op user-print) (reg val))
  (goto (label read-eval-print-loop))

当程式运算过程中出现错误时，我们需要打印错误信息并跳转回到驱动循环。

unknown-expression-type
  (assign val (const unknown-expression-type-error))
  (goto (label signal-error))
unknown-procedure-type
  (restore continue)
  (assign val (const unknown-procedure-type-error))
  (goto (label signal-error))
signal-error
  (perform (op user-print) (reg val))
  (goto (label read-eval-print-loop))

出于模拟的目的，我们在每次驱动循环开始时都会初始化堆栈，因为如果在计算过程中出错后没有清空堆栈可能会影响下一次计算。

如果我们将 5.4 章节的所有代码片段组装起来，便能创建一个求值器机器模型，这个机器模型能够通过 5.2 节的寄存器机器模拟器运行。

(define eceval
  (make-machine
   '(exp env val proc argl continue unev)
   eceval-operations
   '(read-eval-print-loop
     <entire machine controller as given above>)))

其次我们必须定义求值器中使用到的 Scheme 程式。这些程式与 4.1 章节在元循环求值器中使用类似。

(define eceval-operations
  (list (list 'self-evaluating? self-evaluating)
        <complete list of operations for eceval machine>))

最后，初始化全局环境并运行求值器。

(define the-global-environment (setup-environment))
(start eceval)
;;; EC-Eval input:
(define (append x y)
  (if (null? x) y (cons (car x) (append (cdr x) y))))
;;; EC-Eval value:
ok
;;; EC-Eval input:
(append '(a b c) '(d e f))
;;; EC-Eval value:
(a b c d e f)

诚然，通过这种方式计算表达式会比直接通过 Scheme 运算消耗更多时间，因为这其中包含了许多层级的模拟计算。从根本上来说，计算表达式的显示控制机器本身也是由 Scheme 程序模拟的，该机器最终也是由 Scheme 解释器运算。

监控求值器性能

模拟是指导求值器实现的有力工具。模拟不只是简单地研究各种寄存器机器的设计，同时还要监控的模拟求值器的性能。例如，在性能监控中一个重要的因素是求值器对堆栈的利用效率。通过在求值器寄存器机器中加入不同的监控器，我们便能够观察和分析计算不同表达式时堆栈的操作次数，加入监控器的方式与 5.2 章节加入 print-result 的节点的方式类似。

print-result
  (perform (op print-stack-statistics))
  (perform
   (op announce-output) (const ";;; EC-Eval value:"))
... ;same as before

求值器此时的交互如下。

;;; EC-Eval input:
(define (factorial n)
  (if (= n 1) 1 (* (factorial (- n 1)) n)))
(total-pushes = 3 maximum-depth = 3)
;;; EC-Eval value:
ok
;;; EC-Eval input:
(factorial 5)
(total-pushes = 144 maximum-depth = 28)
;;; EC-Eval value:
120

每次求值器的驱动循环都会重新初始化堆栈，所以此时打印的堆栈操作数据只是前一个表达式的运算过程分析。