Evaluating procedure applications

A procedure application is specified by a combination containing an operator and operands. The operator is a subexpression whose value is a procedure, and the operands are subexpressions whose values are the arguments to which the procedure should be applied. The metacircular eval handles applications by calling itself recursively to evaluate each element of the combination, and then passing the results to apply, which performs the actual procedure application. The explicit-control evaluator does the same thing; these recursive calls are implemented by goto 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).[2]

We begin the evaluation of an application by evaluating the operator to produce a procedure, which will later be applied to the evaluated operands. To evaluate the operator, we move it to the exp register and go to eval-dispatch. The environment in the env register is already the correct one in which to evaluate the operator. However, we save env because we will need it later to evaluate the operands. We also extract the operands into unev and save this on the stack. We set up continue so that eval-dispatch will resume at ev-appl-did-operator after the operator has been evaluated. First, however, we save the old value of continue, which tells the controller where to continue after the application. 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))

Upon returning from evaluating the operator subexpression, we proceed to evaluate the operands of the combination and to accumulate the resulting arguments in a list, held in argl. First we restore the unevaluated operands and the environment. We initialize argl to an empty list. Then we assign to the proc register the procedure that was produced by evaluating the operator. If there are no operands, we go directly to apply-dispatch. Otherwise we save proc on the stack and start the argument-evaluation loop:[3] 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)

Each cycle of the argument-evaluation loop evaluates an operand from the list in unev and accumulates the result into argl. To evaluate an operand, we place it in the exp 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 operands to be evaluated (held in unev). A special case is made for the evaluation of the last operand which is handled at 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))

When an operand has been evaluated, the value is accumulated into the list held in argl. The operand is then removed from the list of unevaluated operands in unev, and the argument-evaluation loop continues. 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))

Evaluation of the last argument is handled differently. There is no need to save the environment or the list of unevaluated operands before going to eval-dispatch, since they will not be required after the last operand 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 procedure, and goes off to perform the application.[4] 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))

The details of the argument-evaluation loop determine the order in which the interpreter evaluates the operands 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 Scheme in which it is implemented.[5] Because the first-operand selector (used in ev-appl-operand-loop to extract successive operands from unev) is implemented as car and the rest-operands selector is implemented as cdr, the explicit-control evaluator will evaluate the operands of a combination in left-to-right order.

Procedure application

The entry point apply-dispatch corresponds to the apply procedure of the metacircular evaluator. By the time we get to apply-dispatch, the proc register contains the procedure 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 procedure 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 procedure to be applied is a primitive or it is a compound procedure. 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))

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 proc. 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-procedure operation that applies the procedure in proc to the arguments in argl. For the purpose of simulating the evaluator with the simulator of section 5.2 we use the procedure apply-primitive-procedure, which calls on the underlying Scheme system to perform the application, just as we did for the metacircular evaluator in section 4.1.4. After computing the value of the primitive application, we restore continue and go to the designated entry point. primitive-apply (assign val (op apply-primitive-procedure) (reg proc) (reg argl)) (restore continue) (goto (reg continue))

To apply a compound procedure, we proceed just as with the metacircular evaluator. We construct a frame that binds the procedure's parameters to the arguments, use this frame to extend the environment carried by the procedure, and evaluate in this extended environment the sequence of expressions that forms the body of the procedure. Ev-sequence, described below in section 5.4.2, handles the evaluation of the 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-sequence))

Compound-apply is the only place in the interpreter where the env register is ever assigned a new value. Just as in the metacircular evaluator, the new environment is constructed from the environment carried by the procedure, together with the argument list and the corresponding list of variables to be bound.

Conditionals

As with the metacircular evaluator, syntactic forms are handled by selectively evaluating fragments of the component. For a conditional, we must evaluate the predicate and decide, based on the value of predicate, whether to evaluate the consequent or the alternative.

Before evaluating the predicate, we save the conditional itself, which is in comp, so that we can later extract the consequent or alternative. To evaluate the predicate 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 predicate. However, we save env because we will need it later to evaluate the consequent or the alternative. We set up continue so that evaluation will resume at ev_conditional_decide after the predicate has been evaluated. First, however, we save the old value of continue, which we will need later in order to return to the evaluation of the statement that is waiting for the value of the conditional. "ev_conditional", save("comp"), // save conditional for later save("env"), save("continue"), assign("continue", label("ev_conditional_decide")), assign("comp", list(op("conditional_predicate"), reg("comp"))), go_to(label("eval_dispatch")), // evaluate the predicate

When we resume at ev_conditional_decide after evaluating the predicate, we test whether it was true or false and, depending on the result, place either the consequent or the alternative in comp before going to eval_dispatch.[6] Notice that restoring env and continue here sets up eval_dispatch to have the correct environment and to continue at the right place to receive the value of the conditional. "ev_conditional_decide", restore("continue"), restore("env"), restore("comp"), test(list(op("is_falsy"), reg("val"))), branch(label("ev_conditional_alternative")), "ev_conditional_consequent", assign("comp", list(op("conditional_consequent"), reg("comp"))), go_to(label("eval_dispatch")), "ev_conditional_alternative", assign("comp", list(op("conditional_alternative"), reg("comp"))), go_to(label("eval_dispatch")),

Sequence Evaluation

The portion of the explicit-control evaluator beginning at ev_sequence, which handles sequences of statements, is analogous to the metacircular evaluator's eval_sequence function.

The entries at ev_sequence_next and ev_sequence_continue form a loop that successively evaluates each statement in a sequence. The list of unevaluated statements is kept in unev. At ev_sequence we place the sequence of statements to be evaluated in unev. If the sequence is empty, we set val to undefined and jump to continue via ev_sequence_empty. Otherwise we start the sequence-evaluation loop, first saving the value of continue on the stack, because the continue register will be used for local flow of control in the loop, and the original value is needed for continuing after the statement sequence. Before evaluating each statement, we check to see if there are additional statements to be evaluated in the sequence. If so, we save the rest of the unevaluated statements (held in unev) and the environment in which these must be evaluated (held in env) and call eval_dispatch to evaluate the statement, which has been placed in comp. The two saved registers are restored after this evaluation, at ev_sequence_continue.

The final statement in the sequence is handled differently, at the entry point ev_sequence_last_statement. Since there are no more statements 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 statement, so after the evaluation of the last statement there is nothing left to do except continue at the entry point that was saved at ev_sequence. 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 statement.

Unlike eval_sequence in the metacircular evaluator, ev_sequence does not need to check whether a return statement was evaluated so as to terminate the sequence evaluation. The explicit control in this evaluator allows a return statement to jump directly to the continuation of the current function application without resuming the sequence evaluation. Thus sequence evaluation does not need to be concerned with returns, or even be aware of the existence of return statements in the language. Because a return statement jumps out of the sequence-evaluation code, the restores of saved registers at ev_sequence_continue won't be executed. We will see later how the return statement removes these values from the stack.