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.

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`.

ev-begin (assign unev (op begin-actions) (reg exp)) (save continue) (goto (label ev-sequence))The implicit sequences in procedure bodies are handled by jumping to

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`.

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 (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

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

(define (sqrt-iter guess x) (if (good-enough? guess x) guess (sqrt-iter (improve guess x) x)))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

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.^{}

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:^{}

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

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:

(define (count n) (newline) (display n) (count (+ n 1)))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.