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.

Explicitbegin 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 ev-sequence from compound-apply, at which point continue is already on the stack, having been saved at 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.

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

A function application is specified by a combination containing a function expression and argument expressions. The function expression is a subexpression whose value is a function, and the argument expressions are subexpressions whose values are the arguments to which the function should be applied. The metacircular evaluate handles applications by calling itself recursively to evaluate each element of the combination, and then passing the results to apply, which performs the actual function application. The explicit-control evaluator does the same thing; these recursive calls are implemented by go_to instructions, together with use of the stack to save registers that will be restored after the recursive call returns. Before each call we will be careful to identify which registers must be saved (because their values will be needed later).[1]

As in the metacircular evaluator, operator combinations are transformed into applications of primitive functions corresponding to the operators. This takes place at ev_operator_combination, which performs this transformation in place in comp and falls through to ev_application.[2]

We begin the evaluation of an application by evaluating the function expression to produce a function, which will later be applied to the evaluated argument expressions. To evaluate the function expression, we move it to the comp register and go to eval_dispatch. The environment in the env register is already the correct one in which to evaluate the function expression. However, we save env because we will need it later to evaluate the argument expressions. We also extract the argument expressions into unev and save this on the stack. We set up continue so that eval_dispatch will resume at ev_appl_did_function_expression after the function expression has been evaluated. First, however, we save the old value of continue, which tells the controller where to continue after the application. "ev_operator_combination", assign("comp", list(op("operator_combination_to_application"), reg("comp"), reg("env"))), "ev_application", save("continue"), save("env"), assign("unev", list(op("arg_expressions"), reg("comp"))), save("unev"), assign("comp", list(op("function_expression"), reg("comp"))), assign("continue", label("ev_appl_did_function_expression")), go_to(label("eval_dispatch")),

Upon returning from evaluating the function expression, we proceed to evaluate the argument expressions of the application and to accumulate the resulting arguments in a list, held in argl. (This is like the evaluation of a sequence of statements, except that we collect the values.) First we restore the unevaluated argument expressions and the environment. We initialize argl to an empty list. Then we assign to the fun register the function that was produced by evaluating the function expression. If there are no argument expressions, we go directly to apply_dispatch. Otherwise we save fun on the stack and start the argument-evaluation loop:[3] "ev_appl_did_function_expression", restore("unev"), // the argument expressions restore("env"), assign("argl", list(op("empty_arglist"))), assign("fun", reg("val")), // the function test(list(op("is_null"), reg("unev"))), branch(label("apply_dispatch")), save("fun"),

Each cycle of the argument-evaluation loop evaluates an argument expression from the list in unev and accumulates the result into argl. To evaluate an argument expression, we place it in the comp register and go to eval_dispatch, after setting continue so that execution will resume with the argument-accumulation phase. But first we save the arguments accumulated so far (held in argl), the environment (held in env), and the remaining argument expressions to be evaluated (held in unev). A special case is made for the evaluation of the last argument expression, which is handled at ev_appl_last_arg. "ev_appl_argument_expression_loop", save("argl"), assign("comp", list(op("head"), reg("unev"))), test(list(op("is_last_argument_expression"), reg("unev"))), branch(label("ev_appl_last_arg")), save("env"), save("unev"), assign("continue", label("ev_appl_accumulate_arg")), go_to(label("eval_dispatch")),

When an argument expression has been evaluated, the value is accumulated into the list held in argl. The argument expression is then removed from the list of unevaluated argument expressions in unev, and the argument-evaluation loop continues. "ev_appl_accumulate_arg", restore("unev"), restore("env"), restore("argl"), assign("argl", list(op("adjoin_arg"), reg("val"), reg("argl"))), assign("unev", list(op("tail"), reg("unev"))), go_to(label("ev_appl_argument_expression_loop")),

Evaluation of the last argument expression is handled differently, as is the last statement in a sequence. There is no need to save the environment or the list of unevaluated argument expressions before going to eval_dispatch, since they will not be required after the last argument expression is evaluated. Thus, we return from the evaluation to a special entry point ev_appl_accum_last_arg, which restores the argument list, accumulates the new argument, restores the saved function, and goes off to perform the application.[4] "ev_appl_last_arg", assign("continue", label("ev_appl_accum_last_arg")), go_to(label("eval_dispatch")), "ev_appl_accum_last_arg", restore("argl"), assign("argl", list(op("adjoin_arg"), reg("val"), reg("argl"))), restore("fun"), go_to(label("apply_dispatch")),

The details of the argument-evaluation loop determine the order in which the interpreter evaluates the argument expressions of a combination (e.g., left to right or right to left—see exercise 3.8). This order is not determined by the metacircular evaluator, which inherits its control structure from the underlying JavaScript in which it is implemented.[5] Because we use head in ev_appl_argument_expression_loop to extract successive argument expressions from unev and tail at ev_appl_accumulate_arg to extract the rest of the argument expressions, the explicit-control evaluator will evaluate the argument expressions of a combination in left-to-right order, as required by the ECMAScript specification.

Function Application

The entry point apply_dispatch corresponds to the apply function of the metacircular evaluator. By the time we get to apply_dispatch, the fun register contains the function to apply and argl contains the list of evaluated arguments to which it must be applied. The saved value of continue (originally passed to eval_dispatch and saved at ev_application), which tells where to return with the result of the function application, is on the stack. When the application is complete, the controller transfers to the entry point specified by the saved continue, with the result of the application in val. As with the metacircular apply, there are two cases to consider. Either the function to be applied is a primitive or it is a compound function. "apply_dispatch", test(list(op("is_primitive_function"), reg("fun"))), branch(label("primitive_apply")), test(list(op("is_compound_function"), reg("fun"))), branch(label("compound_apply")), go_to(label("unknown_function_type")),

We assume that each primitive is implemented so as to obtain its arguments from argl and place its result in val. To specify how the machine handles primitives, we would have to provide a sequence of controller instructions to implement each primitive and arrange for primitive_apply to dispatch to the instructions for the primitive identified by the contents of fun. Since we are interested in the structure of the evaluation process rather than the details of the primitives, we will instead just use an apply_primitive_function operation that applies the function in fun to the arguments in argl. For the purpose of simulating the evaluator with the simulator of section 5.2 we use the function apply_primitive_function, which calls on the underlying JavaScript system to perform the application, just as we did for the metacircular evaluator in section 4.1.1. After computing the value of the primitive application, we restore continue and go to the designated entry point. "primitive_apply", assign("val", list(op("apply_primitive_function"), reg("fun"), reg("argl"))), restore("continue"), go_to(reg("continue")),

The sequence of instructions labeled compound_apply specifies the application of compound functions. To apply a compound function, we proceed in a way similar to what we did in the metacircular evaluator. We construct a frame that binds the function's parameters to the arguments, use this frame to extend the environment carried by the function, and evaluate in this extended environment the body of the function.

At this point the compound function is in register fun and its arguments are in argl. We extract the function's parameters into unev and its environment into env. We then replace the environment in env with the environment constructed by extending it with bindings of the parameters to the given arguments. We then extract the body of the function into comp. The natural next step would be to restore the saved continue and proceed to eval_dispatch to evaluate the body and go to the restored continuation with the result in val, as is done for the last statement of a sequence. But there is a complication!

The complication has two aspects. One is that at any point in the evaluation of the body, a return statement may require the function to return the value of the return expression as the value of the body. But a return statement may be nested arbitrarily deeply in the body; so the stack at the moment the return statement is encountered is not necessarily the stack that is needed for a return from the function. One way to make it possible to adjust the stack for the return is to put a \emph{marker} on the stack that can be found by the return code. This is implemented by the push_marker_to_stack instruction. The return code can then use the revert_stack_to_marker instruction to restore the stack to the place indicated by the marker before evaluating the return expression.[6]

The other aspect of the complication is that if the evaluation of the body terminates without executing a return statement, the value of the body must be undefined. To handle this, we set up the continue register to point to the entry point return_undefined before going off to eval_dispatch to evaluate the body. If a return statement is not encountered during evaluation of the body, evaluation of the body will continue at return_undefined. "compound_apply", assign("unev", list(op("function_parameters"), reg("fun"))), assign("env", list(op("function_environment"), reg("fun"))), assign("env", list(op("extend_environment"), reg("unev"), reg("argl"), reg("env"))), assign("comp", list(op("function_body"), reg("fun"))), push_marker_to_stack(), assign("continue", label("return_undefined")), go_to(label("eval_dispatch")),

The only places in the interpreter where the env register is assigned a new value are compound_apply and ev_block (section 5.4.3). Just as in the metacircular evaluator, the new environment for evaluation of a function body is constructed from the environment carried by the function, together with the argument list and the corresponding list of names to be bound.

When a return statement is evaluated at ev_return, we use the revert_stack_to_marker instruction to restore the stack to its state at the beginning of the function call by removing all values from the stack down to and including the marker. As a consequence, restore("continue") will restore the continuation of the function call, which was saved at ev_application. We then proceed to evaluate the return expression, whose result will be placed in val and thus be the value returned from the function when we continue after the evaluation of the return expression. "ev_return", revert_stack_to_marker(), restore("continue"), assign("comp", list(op("return_expression"), reg("comp"))), go_to(label("eval_dispatch")),

If no return statement is encountered during evaluation of the function body, evaluation continues at return_undefined, the continuation that was set up at compound_apply. To return undefined from the function, we put undefined into val and go to the entry point that was put onto the stack at ev_application. Before we can restore that continuation from the stack, however, we must remove the marker that was saved at compound_apply. "return_undefined", revert_stack_to_marker(), restore("continue"), assign("val", constant(undefined)), go_to(reg("continue")),

The metacircular implementation of the evaluator in chapter 4 isn't tail-recursive. It implements a return statement as a constructor of a return value object containing the value to be returned and inspects the result of a function call to see whether it is such an object. If the evaluation of a function body produces a return value object, the return value of the function is the contents of that object; otherwise, the return value is undefined. Both the construction of the return value object and the eventual inspection of the result of the function call are deferred operations, which lead to an accumulation of information on the stack.

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:[8] 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))

Our explicit-control evaluator is tail-recursive, because it does not need to wrap up return values for inspection and thus avoids the buildup of stack from deferred operations. At ev_return, in order to evaluate the expression that computes the return value of a function, we transfer directly to eval_dispatch with nothing more on the stack than right before the function call. We accomplish this by undoing any saves to the stack by the function (which are useless because we are returning) using revert_stack_to_marker. Then, rather than arranging for eval_dispatch to come back 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. Finally, we transfer to eval_dispatch without saving any information on the stack. Thus, when we proceed to evaluate a return expression, the stack is the same as just before the call to the function whose return value we are about to compute. Hence, evaluating a return expression—even if it is a function call (as in sqrt_iter, where the conditional expression reduces to a call to sqrt_iter)—will not cause any information to accumulate on the stack.[9]

If we did not think to take advantage of the fact that it is unnecessary to hold on to the useless information on the stack while evaluating a return expression, we might have taken the straightforward approach of evaluating the return expression, coming back to restore the stack, and finally continuing at the entry point that is waiting for the result of the function call: "ev_return", // alternative implementation: not tail-recursive assign("comp", list(op("return_expression"), reg("comp"))), assign("continue", label("ev_restore_stack")), go_to(label("eval_dispatch")), "ev_restore_stack", revert_stack_to_marker(), // undo saves in current function restore("continue"), // undo save at $\texttt{ev\char`_application}$ go_to(reg("continue")),

Note that our JavaScript implementation requires the use of return in order to be tail-recursive. Because the undoing of the register saves takes place at ev_return, removing return from the count function above will cause it to eventually run out of stack space. This explains the use of return in the infinite driver loops in chapter 4.