5.4.2 Sequence Evaluation and Tail Recursion

The portion of the explicit-control evaluator at ev-sequence is

analogous to the metacircular evaluator’s eval-sequence procedure. It

handles sequences of expressions in procedure bodies or in explicit

begin expressions.

显式控制求值器中位于 ev-sequence 处的部分，类似于元循环求值器的 eval-sequence 过程。它负责处理过程体中的表达式序列，以及显式 begin 表达式中的表达式序列。

Explicit begin expressions are evaluated by placing the sequence of

expressions to be evaluated in unev, saving continue on the

stack, and jumping to ev-sequence.

显式 begin 表达式的求值方式为：将待求值的表达式序列置入 unev，将 continue 压栈保存，然后跳转至 ev-sequence。

The implicit sequences in procedure bodies are handled by jumping to

ev-sequence from compound-apply, at which point continue

is already on the stack, having been saved at ev-application.

过程体中的隐式序列由 compound-apply 跳转至 ev-sequence 来处理，此时 continue 已在 ev-application 处被保存到栈上。

The entries at ev-sequence and ev-sequence-continue form a loop

that successively evaluates each expression in a sequence. The list of

unevaluated expressions is kept in unev. Before evaluating each

expression, we check to see if there are additional expressions to be evaluated

in the sequence. If so, we save the rest of the unevaluated expressions (held

in unev) and the environment in which these must be evaluated (held in

env) and call eval-dispatch to evaluate the expression. The two

saved registers are restored upon the return from this evaluation, at

ev-sequence-continue.

ev-sequence 和 ev-sequence-continue 处的代码共同构成一个循环，依次对序列中的每个表达式求值。尚未求值的表达式表保存在 unev 中。在对每个表达式求值之前，我们检查序列中是否还有其他表达式待求值。若有，则将 unev 中剩余的未求值表达式以及对应的求值环境（保存在 env 中）压栈保存，然后调用 eval-dispatch 对当前表达式求值。从该次求值返回后，在 ev-sequence-continue 处恢复两个已保存的寄存器。

The final expression in the sequence is handled differently, at the entry point

ev-sequence-last-exp. Since there are no more expressions to be

evaluated after this one, we need not save unev or env before

going to eval-dispatch. The value of the whole sequence is the value of

the last expression, so after the evaluation of the last expression there is

nothing left to do except continue at the entry point currently held on the

stack (which was saved by ev-application or ev-begin.) Rather

than setting up continue to arrange for eval-dispatch to return

here and then restoring continue from the stack and continuing at that

entry point, we restore continue from the stack before going to

eval-dispatch, so that eval-dispatch will continue at that entry

point after evaluating the expression.

序列中最后一个表达式的处理方式有所不同，在入口点 ev-sequence-last-exp 处执行。由于该表达式求值完成后再无其他表达式需要求值，因此跳转至 eval-dispatch 之前无需保存 unev 或 env。整个序列的值即为最后一个表达式的值，因此对最后一个表达式求值完毕后，只需继续执行当前栈顶所保存的入口点（该入口点由 ev-application 或 ev-begin 保存）即可。与其设置 continue 使 eval-dispatch 在此处返回、再从栈中恢复 continue 并跳转，不如在跳转至 eval-dispatch 之前就直接从栈中恢复 continue，从而使 eval-dispatch 在对表达式求值完成后直接继续执行该入口点。

Subheading: Tail recursion

In Chapter 1 we said that the process described by a procedure such as

小节标题：尾递归

在第 1 章中，我们曾指出，如下过程所描述的计算过程

is an iterative process. Even though the procedure is syntactically recursive

(defined in terms of itself), it is not logically necessary for an evaluator to

save information in passing from one call to sqrt-iter to the

next. An evaluator that can execute a procedure such as

sqrt-iter without requiring increasing storage as the procedure

continues to call itself is called a

tail-recursive evaluator. The

metacircular implementation of the evaluator in Chapter 4 does not

specify whether the evaluator is tail-recursive, because that evaluator

inherits its mechanism for saving state from the underlying Scheme. With the

explicit-control evaluator, however, we can trace through the evaluation

process to see when procedure calls cause a net accumulation of information on

the stack.

是一个迭代型计算过程。尽管该过程在语法上是递归的（以自身来定义），但求值器在从一次 sqrt-iter 调用转至下一次调用时，在逻辑上并不需要保存任何信息。能够执行像 sqrt-iter 这样的过程、且在过程持续自我调用的过程中不需要不断增大存储空间的求值器，称为尾递归求值器 (tail-recursive evaluator)。第 4 章中元循环实现的求值器并未规定求值器是否具有尾递归性，因为该求值器保存状态的机制继承自底层的 Scheme 实现。然而，借助显式控制求值器，我们可以追踪求值的计算过程，从而观察到过程调用在何时会导致栈上信息的净累积。

Our evaluator is tail-recursive, because in order to evaluate the final

expression of a sequence we transfer directly to eval-dispatch without

saving any information on the stack. Hence, evaluating the final expression in

a sequence—even if it is a procedure call (as in sqrt-iter, where the

if expression, which is the last expression in the procedure body,

reduces to a call to sqrt-iter)—will not cause any information to be

accumulated on the stack.

我们的求值器具有尾递归性，原因在于：为了对序列中的最后一个表达式求值，我们直接跳转至 eval-dispatch，而不在栈上保存任何信息。因此，对序列最后一个表达式的求值——即便它是一次过程调用（如 sqrt-iter 中，过程体最后一个表达式 if 表达式最终归结为对 sqrt-iter 的调用）——也不会在栈上累积任何信息。

If we did not think to take advantage of the fact that it was unnecessary to

save information in this case, we might have implemented eval-sequence

by treating all the expressions in a sequence in the same way—saving the

registers, evaluating the expression, returning to restore the registers, and

repeating this until all the expressions have been evaluated:

如果我们不曾意识到在这种情况下无需保存信息，或许就会以统一方式实现 eval-sequence——对序列中的所有表达式都执行同样的操作：保存寄存器、对表达式求值、返回并恢复寄存器，如此反复直到所有表达式求值完毕：

This may seem like a minor change to our previous code for evaluation of a

sequence: The only difference is that we go through the save-restore cycle for

the last expression in a sequence as well as for the others. The interpreter

will still give the same value for any expression. But this change is fatal to

the tail-recursive implementation, because we must now return after evaluating

the final expression in a sequence in order to undo the (useless) register

saves. These extra saves will accumulate during a nest of procedure calls.

Consequently, processes such as sqrt-iter will require space

proportional to the number of iterations rather than requiring constant space.

This difference can be significant. For example, with tail recursion, an

infinite loop can be expressed using only the procedure-call mechanism:

这看起来似乎只是对之前序列求值代码的微小改动：唯一的区别在于，对序列最后一个表达式也像其他表达式一样执行了保存-恢复周期。解释器对任何表达式给出的值仍然相同。然而，这一改动对尾递归实现而言却是致命的，因为现在对序列最后一个表达式求值后必须返回，以撤销那些（徒劳无益的）寄存器保存操作。这些额外的保存操作会在过程调用的层层嵌套中不断累积。结果，像 sqrt-iter 这样的计算过程所需的空间将正比于迭代次数，而非常数空间。这一差异可能相当显著。举例来说，有了尾递归，一个无限循环只需过程调用机制即可表达：

Without tail recursion, such a procedure would eventually run out of stack

space, and expressing a true iteration would require some control mechanism

other than procedure call.

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