5.4  显式控制求值器

在章节 5.1 中，我们看到了如何将简单的 Scheme 程序变换为寄存器机器的描述。现在我们将对更复杂的程序进行这种变换，即章节 4.1.1-4.1.4 的元循环求值器，它展示了如何用过程 eval 和 apply 来描述 Scheme 解释器的行为。本节中开发的显式控制求值器展示了如何用寄存器和堆栈上的操作来描述求值过程中使用的基本过程调用和参数传递机制。此外，显式控制求值器可以作为一个 Scheme 解释器的实现，它使用的语言非常类似于常规计算机的原生机语言。该求值器可以由章节 5.2 的寄存器机器模拟器执行。或者，它也可以作为构建 Scheme 求值器机器语言实现的基础，甚至可以作为用于求值 Scheme 表达式的专用机器。图 5.16 展示了这样一种硬件实现：一个作为 Scheme 求值器的硅芯片。芯片设计者从类似于本节描述的求值器的寄存器机器的数据通路和控制器规格出发，使用设计自动化程序构建了集成电路布局。¹⁹

Registers and operations

在设计显式控制求值器时，我们必须指定寄存器机器中要使用的操作。我们使用诸如 quoted? 和 make-procedure 之类的过程，以抽象语法的方式描述了元循环求值器。在实现寄存器机器时，我们可以将这些过程展开为基本表结构内存操作的序列，并在寄存器机器上实现这些操作。然而，这会使我们的求值器非常冗长，用细节掩盖了基本结构。为了表述清晰，我们将把章节 4.1.2 中给出的语法过程和章节 4.1.3 与 4.1.4 中给出的表示环境和运行时数据的过程，作为寄存器机器的基本操作包含进来。为了完全指定一个可以用低级机器语言编程或用硬件实现的求值器，我们需要使用章节 5.3 中描述的表结构实现，将这些操作替换为更基本的操作。

图 5.16:  一个 Scheme 求值器的硅芯片实现。

我们的 Scheme 求值器寄存器机器包含一个堆栈和七个寄存器：exp、env、val、continue、proc、argl 和 unev。Exp 用于保存待求值的表达式，env 包含求值执行所在的环境。求值结束时，val 包含在指定环境中求值表达式得到的值。continue 寄存器用于实现递归，如章节 5.1.4 中所述。（求值器需要递归地调用自身，因为求值一个表达式需要求值其子表达式。）寄存器 proc、argl 和 unev 用于求值组合式。

我们不会提供数据通路图来展示求值器的寄存器和操作是如何连接的，也不会给出机器操作的完整列表。这些都隐含在求值器的控制器中，控制器将在后面详细给出。

5.4.1  The Core of the Explicit-Control Evaluator

求值器的核心元素是从 eval-dispatch 开始的指令序列。这对应于章节 4.1.1 中描述的元循环求值器的 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))

Evaluating simple expressions

数字和字符串（它们是自求值的）、变量、引号和 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 操作。

Evaluating procedure applications

过程应用由包含运算符和操作数的组合式指定。运算符是一个子表达式，其值是一个过程；操作数是子表达式，其值是将要应用于过程的参数。元循环 eval 通过递归调用自身来求值组合式的每个元素，然后将结果传递给执行实际过程应用的 apply。显式控制求值器也做同样的事情；这些递归调用通过 goto 指令实现，同时使用堆栈保存那些将在递归调用返回后恢复的寄存器。在每次调用之前，我们都会仔细确定哪些寄存器必须被保存（因为它们的值稍后会被用到）。²¹

我们通过求值运算符来开始一个应用的过程求值，以产生一个过程，该过程随后将被应用于求值后的操作数。为了求值运算符，我们将其移动到 exp 寄存器并转到 eval-dispatch。env 寄存器中的环境已经是求值运算符所需的正确环境。然而，我们保存 env，因为稍后需要它来求值操作数。我们还将操作数提取到 unev 中并将其保存在堆栈上。我们设置 continue，使得 eval-dispatch 在运算符求值完成后在 ev-appl-did-operator 处恢复执行。但是，首先我们保存 continue 的旧值，它告诉控制器在应用之后应该从哪里继续。

ev-application
  (save continue)
  (save env)
  (assign unev (op operands) (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)                  ; the operands
  (restore env)
  (assign argl (op empty-arglist))
  (assign proc (reg val))         ; the operator
  (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))

最后一个参数的处理方式有所不同。在转到 eval-dispatch 之前，无需保存环境或未求值操作数列表，因为最后一个操作数求值完成后不再需要它们。因此，我们从求值返回到一个特殊的入口点 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))

参数求值循环的细节决定了解释器求值组合式操作数的顺序（例如，从左到右或从右到左——见练习 3.8）。这个顺序并非由元循环求值器确定，它继承了其所基于的 Scheme 语言的控制结构。²⁴ 由于 first-operand 选择器（在 ev-appl-operand-loop 中用于从 unev 中提取连续的操作数）实现为 car，而 rest-operands 选择器实现为 cdr，所以显式控制求值器将按从左到右的顺序求值组合式的操作数。

Procedure application

入口点 apply-dispatch 对应于元循环求值器的 apply 过程。当到达 apply-dispatch 时，proc 寄存器包含要应用的过程，argl 包含要求值的已求值参数列表。continue 的保存值（最初传递给 eval-dispatch 并在 ev-application 处保存）位于堆栈上，它告诉在过程应用完成后将结果返回到哪里。当应用完成时，控制器转移到保存的 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 操作，它将 proc 中的过程应用于 argl 中的参数。为了使用章节 5.2 的模拟器来模拟求值器，我们使用过程 apply-primitive-procedure，它调用底层的 Scheme 系统来执行应用，就像我们在章节 4.1.4 中对元循环求值器所做的那样。计算出基本应用的值后，我们恢复 continue 并转到指定的入口点。

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

要应用一个复合过程，我们按照与元循环求值器相同的方式进行。我们构造一个将过程参数绑定到参数的框架，使用这个框架来扩展过程携带的环境，并在这个扩展环境中求值组成过程体的表达式序列。Ev-sequence 在下面的章节 5.4.2 中描述，负责处理序列的求值。

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-sequence))

Compound-apply 是解释器中唯一给 env 寄存器赋予新值的地方。与元循环求值器一样，新环境由过程携带的环境、参数列表以及相应的要绑定的变量列表构造而成。

5.4.2  Sequence Evaluation and Tail Recursion

显式控制求值器中 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 中）和求值这些表达式所需的环境（保存在 env 中），并调用 eval-dispatch 来求值表达式。这两个保存的寄存器在从本次求值返回时（在 ev-sequence-continue 处）被恢复。

序列中的最后一个表达式在入口点 ev-sequence-last-exp 处以不同方式处理。由于这个表达式之后没有更多表达式要求值，我们无需在转到 eval-dispatch 之前保存 unev 或 env。整个序列的值就是最后一个表达式的值，因此在对最后一个表达式求值后，除了在堆栈上当前保存的入口点（由 ev-application 或 ev-begin 保存）继续执行之外，没有其他事情可做。我们不是在设置 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))

Tail recursion

在第 1 章中，我们说过，像下面这样一个过程所描述的计算过程

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x)
                 x)))

是一个迭代计算过程。尽管该过程在语法上是递归的（以其自身来定义），但从逻辑上讲，求值器在从一个 sqrt-iter 调用传递到下一个时，并不需要保存信息。²⁵ 一个能够在执行诸如 sqrt-iter 这样的过程时，不因过程持续调用自身而需要增加存储空间的求值器，称为尾递归求值器。第 4 章中元循环求值器的实现并未指定该求值器是否是尾递归的，因为该求值器从底层的 Scheme 继承了其保存状态的机制。然而，使用显式控制求值器，我们可以追踪求值过程，观察过程调用何时会在堆栈上引起信息的净累积。

我们的求值器是尾递归的，因为为了求值一个序列的最后一个表达式，我们直接转移到 eval-dispatch，而不在堆栈上保存任何信息。因此，求值一个序列中的最后一个表达式——即使它是一个过程调用（就像在 sqrt-iter 中，作为过程体中最后一个表达式的 if 表达式归约为对 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)))

没有尾递归，这样的过程最终会耗尽堆栈空间，而表达真正的迭代将需要某种过程调用之外的控制机制。

5.4.3  Conditionals, Assignments, and Definitions

与元循环求值器一样，特殊形式通过选择性地求值表达式的片段来处理。对于 if 表达式，我们须求值谓词，并基于谓词的值决定是求值后继还是替代。

在求值谓词之前，我们保存 if 表达式本身，以便稍后提取后继或替代。我们还保存环境（稍后求值后继或替代时需要它），并保存 continue（稍后返回求值等待 if 值的表达式时需要它）。

ev-if
  (save exp)                    ; save expression for later
  (save env)
  (save continue)
  (assign continue (label ev-if-decide))
  (assign exp (op if-predicate) (reg exp))
  (goto (label eval-dispatch))  ; evaluate the predicate

当我们从谓词求值返回时，我们测试其为真还是假，并根据结果在转到 eval-dispatch 之前将后继或替代放入 exp。注意，在这里恢复 env 和 continue 使得 eval-dispatch 拥有正确的环境，并在正确的位置继续执行以接收 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))

Assignments and definitions

赋值由 ev-assignment 处理，从 eval-dispatch 到达时，赋值表达式在 exp 中。ev-assignment 处的代码首先求值表达式的值部分，然后将新值安装到环境中。Set-variable-value! 假定可作为机器操作使用。

ev-assignment
  (assign unev (op assignment-variable) (reg exp))
  (save unev)                   ; save variable for later
  (assign exp (op assignment-value) (reg exp))
  (save env)
  (save continue)
  (assign continue (label ev-assignment-1))
  (goto (label eval-dispatch))  ; evaluate the assignment value
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-definition
  (assign unev (op definition-variable) (reg exp))
  (save unev)                   ; save variable for later
  (assign exp (op definition-value) (reg exp))
  (save env)
  (save continue)
  (assign continue (label ev-definition-1))
  (goto (label eval-dispatch))  ; evaluate the definition value
ev-definition-1
  (restore continue)
  (restore env)
  (restore unev)
  (perform
   (op define-variable!) (reg unev) (reg val) (reg env))
  (assign val (const ok))
  (goto (reg continue))

练习 5.23.  扩展求值器以处理派生表达式，如 cond、let 等（章节 4.1.2）。你可以``作弊''并假设像 cond->if 这样的语法变换器可作为机器操作使用。²⁸

练习 5.24.  将 cond 实现为一个新的基本特殊形式，而不将其归约为 if。你需要构造一个循环，测试连续 cond 子句的谓词，直到找到一个为真的谓词，然后使用 ev-sequence 求值该子句的动作。

练习 5.25.  修改求值器，使其基于章节 4.2 的惰性求值器，使用正则序求值。

5.4.4  Running the Evaluator

随着显式控制求值器的实现，我们走到了自第 1 章开始的一次开发的终点，在这个开发过程中，我们逐步探索了越来越精确的求值过程模型。我们从相对非形式化的代换模型开始，然后在第 3 章将其扩展到环境模型，这使我们能够处理状态和变化。在第 4 章的元循环求值器中，我们使用 Scheme 本身作为一种语言，更明确地揭示表达式求值过程中构造的环境结构。现在，通过寄存器机器，我们仔细审视了求值器在存储管理、参数传递和控制方面的机制。在每个新的描述层次上，我们都必须提出并解决在之前不够精确的求值处理中未显现的问题和歧义。为了理解显式控制求值器的行为，我们可以模拟它并监控其性能。

我们将在求值器机器中安装一个驱动循环。这扮演了章节 4.1.4 中 driver-loop 过程的角色。求值器将重复打印提示符，读取表达式，通过转到 eval-dispatch 来求值表达式，然后打印结果。以下指令构成显式控制求值器控制器序列的开头：²⁹

read-eval-print-loop
  (perform (op initialize-stack))
  (perform
   (op prompt-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))

当我们在过程中遇到错误时（例如在 apply-dispatch 处指出的``未知过程类型错误''），我们打印一条错误消息并返回到驱动循环。³⁰

unknown-expression-type
  (assign val (const unknown-expression-type-error))
  (goto (label signal-error))
unknown-procedure-type
  (restore continue)    ; clean up stack (from apply-dispatch)
  (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.1-5.4.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 中用于元循环求值器的过程相同，再加上在章节 5.4 的脚注中定义的一些额外过程。

(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 程序本身又由 Scheme 解释器求值。

Monitoring the performance of the evaluator

模拟可以成为指导求值器实现的强大工具。模拟不仅使探索寄存器机器设计的变体变得容易，还可以监控被模拟求值器的性能。例如，性能的一个重要因素是如何高效地使用堆栈。我们可以通过使用收集堆栈使用统计信息的模拟器版本（章节 5.2.4）来定义求值器寄存器机器，并在求值器的 print-result 入口点添加一条指令来打印统计信息，从而观察求值各种表达式所需的堆栈操作次数：

print-result
  (perform (op print-stack-statistics)); added instruction
  (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

注意，求值器的驱动循环在每次交互开始时重新初始化堆栈，这样打印的统计信息将只涉及用于求值前一个表达式的堆栈操作。

练习 5.26.  使用受监控的堆栈来探索求值器的尾递归性质（章节 5.4.2）。启动求值器并定义章节 1.2.1 中的迭代 factorial 过程：

(define (factorial n)
  (define (iter product counter)
    (if (> counter n)
        product
        (iter (* counter product)
              (+ counter 1))))
  (iter 1 1))

用一些较小的 n 值运行该过程。记录计算每个值的 n! 所需的最大堆栈深度和推入次数。

a. 你会发现求值 n! 所需的最大深度与 n 无关。这个深度是多少？

b. 根据你的数据，给出一个以 n 表示的公式，用于计算求值任意 n > 1 的 n! 时所用 push 操作的总数。注意，所用的操作次数是 n 的线性函数，因此由两个常数确定。

练习 5.27.  为了与练习 5.26 比较，探索以下递归计算阶乘的过程的行为：

(define (factorial n)
  (if (= n 1)
      1
      (* (factorial (- n 1)) n)))

通过使用受监控的堆栈运行该过程，确定作为 n 函数的、在求值 n > 1 的 n! 时使用的最大堆栈深度和 push 操作总数。（同样，这些函数将是线性的。）用关于 n 的适当表达式填写下表，总结你的实验：

	最大深度	Push 次数
递归
factorial
迭代
factorial

最大深度是求值器在执行计算时所使用空间量的度量，而 push 次数与所需时间密切相关。

练习 5.28.  按照章节 5.4.2 中的描述修改求值器的定义，改变 eval-sequence，使求值器不再是尾递归的。重新运行练习 5.26 和 5.27 中的实验，说明 factorial 过程的两个版本现在都需要与其输入线性增长的空间。

练习 5.29.  监控树形递归 Fibonacci 计算中的堆栈操作：

(define (fib n)
  (if (< n 2)
      n
      (+ (fib (- n 1)) (fib (- n 2)))))

a. 给出一个以 n 表示的公式，用于计算 n > 2 时求值 Fib(n) 所需的最大堆栈深度。提示：在章节 1.2.2 中，我们认为该过程使用的空间随 n 线性增长。

b. 给出一个公式，用于计算 n > 2 时求值 Fib(n) 所使用的 push 操作总数。你会发现 push 次数（与所用时间密切相关）随 n 指数增长。提示：设 S(n) 为计算 Fib(n) 所用的 push 次数。你应该能论证存在一个公式，将 S(n) 表示为 S(n - 1)、S(n - 2) 和某个与 n 无关的固定``开销''常数 k 的函数。给出这个公式，并说明 k 的值。然后证明 S(n) 可以表示为 a Fib(n + 1) + b，并给出 a 和 b 的值。

练习 5.30.  我们的求值器目前只捕获和报告两种错误——未知表达式类型和未知过程类型。其他错误会使我们退出求值器的读取-求值-打印循环。当我们使用寄存器机器模拟器运行求值器时，这些错误由底层的 Scheme 系统捕获。这类似于当用户程序出错时计算机崩溃。³² 构建一个真正的错误处理系统是一个庞大的工程，但理解其中涉及的问题是非常值得的。

a. 求值过程中发生的错误，例如尝试访问未绑定的变量，可以通过修改查找操作来捕获，使其返回一个特殊的条件码，该条件码不能是任何用户变量的可能值。求值器可以测试这个条件码，然后执行必要的操作转到 signal-error。找出求值器中所有需要进行此类修改的地方并修复它们。这是大量的工作。

b. 更糟糕的是处理由基本过程应用引发的错误，例如尝试除以零或尝试提取符号的 car。在一个专业编写的高质量系统中，每个基本应用在作为基本过程的一部分时都会检查安全性。例如，每次对 car 的调用都可以首先检查参数是否为序对。如果参数不是序对，应用将向求值器返回一个特殊的条件码，求值器随后报告失败。我们可以通过让每个基本过程检查适用性并在失败时返回适当的特殊条件码，在寄存器机器模拟器中安排这一点。然后求值器中的 primitive-apply 代码可以检查条件码，并在必要时转到 signal-error。构建这个结构并使其工作。这是一个大项目。