Generating Execution Procedures for Instructions
Instructions and Their Execution Functions
- SICP Comparison Edition"/>5.2.3
<span style="color:green">Generating Execution Procedures for Instructions</span>
<span style="color:blue">Instructions and Their Execution Functions</span>
- SICP Comparison EditionSICP — Scheme/JSStructure and Interpretation of Computer Programs — Comparison Edition
The assembler calls
make-execution-proceduremake_execution_function
to generate the execution
procedurefunction
for ana controller instruction.
Like the analyzeprocedurefunction
in the evaluator of section 4.1.7,
this dispatches on the type of instruction to generate the appropriate
execution
procedure.function.
Original
JavaScript
The details of these execution functions determine the
meaning of the individual instructions in the register-machine language.
For each type of instruction in the register-machine language,
there is a generator that builds an appropriate execution
procedure. The details of these procedures determine the
meaning of the individual instructions in the register-machine
language. We use data abstraction to isolate the detailed
syntax of register-machine expressions from the general
execution mechanism, as we did for evaluators in
section 4.1.2, by
using syntax procedures to extract and classify the parts of
an instruction.
The elements of the controller sequence
received by make_machine and passed
to assemble are strings (for
labels) and tagged lists (for instructions). The tag in an instruction
is a string that identifies the instruction type, such as
"go_to", and the remaining elements
of the list contains the arguments, such as the destination of the
go_to.
The dispatch in make_execution_function uses
function type(instruction) { return head(instruction); }
Original
JavaScript
The tagged lists are constructed when the
list expression that is the third
argument to make_machine is
evaluated. Each argument to that
list is either a string (which
evaluates to itself) or a call to a constructor for an instruction
tagged list. For example, assign("b", reg("t")) calls the constructor
assign with arguments
"b" and the result of calling the
constructor reg with the argument
"t". The constructors and their
arguments determine the syntax of the individual instructions in the
register-machine language. The instruction constructors and selectors
are shown below, along with the execution-function generators that use
the selectors.
Assign instructionsThe instruction assign
The
make-assignmake_assign_efprocedurefunctionhandles assignmakes execution functions for assign
instructions:
Make-assign
extracts the target register name (the second element of the instruction)
and the value expression (the rest of the list that forms the instruction)
from the assign instruction using the selectors
The function assign constructs
assign instructions.
The selectors assign_reg_name and
assign_value_exp extract the register name
and value expression from an assign instruction.
function assign(register_name, source) {
return list("assign", register_name, source);
}
function assign_reg_name(assign_instruction) {
return head(tail(assign_instruction));
}
function assign_value_exp(assign_instruction) {
return head(tail(tail(assign_instruction)));
}
The register name is looked up
The function make_assign_ef looks up the register name
with
get-registerget_register
to produce the target register object. The value expression is passed to
make-operation-expmake_operation_exp_ef
if the value is the result of an operation, and
it is passed
to
make-primitive-expmake_primitive_exp_ef
otherwise. These
proceduresfunctions
(shown below)
parseanalyze
the value expression and produce an execution
procedurefunction
for the value. This is a
procedurefunction
of no arguments, called
value-proc,value_fun,
which will be evaluated during the simulation to produce the actual
value to be assigned to the register. Notice that the work of looking
up the register name and
parsinganalyzing
the value expression is performed
just once, at assembly time, not every time the instruction is
simulated. This saving of work is the reason we use execution
procedures,functions,
and corresponds directly to the saving in work we obtained by separating
program analysis from execution in the evaluator of
section 4.1.7.
The result returned by
make-assignmake_assign_ef
is the execution
procedurefunction
for the assign instruction. When this
procedurefunction
is called (by the machine model's executeprocedure),function),
it sets the contents of the target register to the result obtained by
executing
value-proc.value_fun.
Then it advances the pc to the next instruction
by running the
procedurefunction
Original
JavaScript
(define (advance-pc pc)
(set-contents! pc (cdr (get-contents pc))))
function advance_pc(pc) {
set_contents(pc, tail(get_contents(pc)));
}
Advance-pc
The function
advance_pc
is the normal termination for all instructions except
branch and
goto.
go_to.
Test,
branch, and
goto
instructions
The instructions
test,
branch, and
go_to
Make-test
The function
make_test_ef
handles test instructions in a similar way.
It extracts the expression that specifies the condition to be tested and
generates an execution
procedurefunction
for it. At simulation time, the
procedurefunction
for the condition is called, the result is assigned to the
flag register, and the
pc is advanced:
The function
test constructs
test instructions. The selector
test_condition extracts the condition
from a test.
function test(condition) { return list("test", condition); }
function test_condition(test_instruction) {
return head(tail(test_instruction));
}
The execution
procedurefunction
for a branch instruction checks the contents of
the flag register and either sets the contents
of the pc to the branch destination (if the
branch is taken) or else just advances the pc
(if the branch is not taken). Notice that the indicated destination in a
branch instruction must be a label, and the
make-branchmake_branch_efprocedurefunction
enforces this. Notice also that the label is looked up at assembly time,
not each time the branch instruction is
simulated.
The function branch
constructs branch instructions. The
selector
branch_dest extracts
the destination from a branch.
function branch(label) { return list("branch", label); }
function branch_dest(branch_instruction) {
return head(tail(branch_instruction));
}
A
gotogo_to
instruction is similar to a branch, except that the destination may be
specified either as a label or as a register, and there is no condition to
check—the pc is always set to the
new destination.
The function go_to constructs
go_to instructions. The selector
go_to_dest extracts the destination from a
go_to instruction.
function go_to(label) { return list("go_to", label); }
function go_to_dest(go_to_instruction) {
return head(tail(go_to_instruction));
}
Other instructions
The stack instructions
save and restore
simply use the stack with the designated register and advance the
pc:
The functions save and
restore construct
save and restore instructions. The
selector
stack_inst_reg_name
extracts the register name from such instructions.
function save(reg) { return list("save", reg); }
function restore(reg) { return list("restore", reg); }
function stack_inst_reg_name(stack_instruction) {
return head(tail(stack_instruction));
}
The final instruction type, handled by
make-perform,make_perform_ef,
generates an execution
procedurefunction
for the action to be performed. At simulation time, the action
procedurefunction
is executed and the pc advanced.
The function perform
constructs perform instructions. The
selector
perform_action extracts
the action from a perform instruction.
function perform(action) { return list("perform", action); }
function perform_action(perform_instruction) {
return head(tail(perform_instruction));
}
Execution
proceduresfunctions
for subexpressions
The value of a
reg,
label, or
constconstant
expression may be needed for assignment to a register
(make-assign)(make_assign_ef, above)
or for input to an operation
(make-operation-exp,
(make_operation_exp_ef,
below). The following
procedurefunction
generates execution
proceduresfunctions
to produce values for these expressions during the simulation:
function make_primitive_exp_ef(exp, machine, labels) {
if (is_constant_exp(exp)) {
const c = constant_exp_value(exp);
return () => c;
} else if (is_label_exp(exp)) {
const insts = lookup_label(labels, label_exp_label(exp));
return () => insts;
} else if (is_register_exp(exp)) {
const r = get_register(machine, register_exp_reg(exp));
return () => get_contents(r);
} else {
error(exp, "unknown expression type -- assemble");
}
}
Original
JavaScript
The syntax of reg,
label, and const
expressions is determined by
(define (register-exp? exp) (tagged-list? exp 'reg))
(define (register-exp-reg exp) (cadr exp))
(define (constant-exp? exp) (tagged-list? exp 'const))
(define (constant-exp-value exp) (cadr exp))
(define (label-exp? exp) (tagged-list? exp 'label))
(define (label-exp-label exp) (cadr exp))
The syntax of reg,
label, and constant
expressions is determined by the following constructor functions, along with
corresponding predicates and selectors.
function reg(name) { return list("reg", name); }
function is_register_exp(exp) { return is_tagged_list(exp, "reg"); }
function register_exp_reg(exp) { return head(tail(exp)); }
function constant(value) { return list("constant", value); }
function is_constant_exp(exp) {
return is_tagged_list(exp, "constant");
}
function constant_exp_value(exp) { return head(tail(exp)); }
function label(name) { return list("label", name); }
function is_label_exp(exp) { return is_tagged_list(exp, "label"); }
function label_exp_label(exp) { return head(tail(exp)); }
Assign,
perform, and
test
instructions
The instructions
assign,
perform, and
test
may include the application of a machine operation (specified by an
op expression) to some operands (specified
by reg and
constconstant
expressions). The following
procedurefunction
produces an execution
procedurefunction
for an operation expression—a list containing the
operation and operand expressions from the instruction:
The syntax of operation expressions is determined by
(define (operation-exp? exp)
(and (pair? exp) (tagged-list? (car exp) 'op)))
(define (operation-exp-op operation-exp)
(cadr (car operation-exp)))
(define (operation-exp-operands operation-exp)
(cdr operation-exp))
The syntax of operation expressions is determined by
function op(name) { return list("op", name); }
function is_operation_exp(exp) {
return is_pair(exp) && is_tagged_list(head(exp), "op");
}
function operation_exp_op(op_exp) { return head(tail(head(op_exp))); }
function operation_exp_operands(op_exp) { return tail(op_exp); }
Observe that the treatment of operation expressions is very much like
the treatment of
procedurefunction
applications by the
analyze-applicationanalyze_applicationprocedurefunction
in the evaluator of section 4.1.7 in
that we generate an execution
procedurefunction
for each operand.
At simulation time, we call the operand
procedures
and apply the Scheme procedure
At simulation time, we call the operand
functions
and apply the JavaScript function
that simulates the operation to the resulting values.
Original
JavaScript
We make use of the function
apply_in_underlying_javascript, as we did
in apply_primitive_function in
section 4.1.4. This is needed to apply
op to all elements of the argument list
afuns
produced by the first map,
as if they were separate arguments to
op. Without this,
op would have been restricted to be a unary
function.
The simulation
procedurefunction
is found by looking up the operation name in the operation table for the
machine:
Original
JavaScript
(define (lookup-prim symbol operations)
(let ((val (assoc symbol operations)))
(if val
(cadr val)
(error "Unknown operation - - ASSEMBLE" symbol))))
function lookup_prim(symbol, operations) {
const val = assoc(symbol, operations);
return is_undefined(val)
? error(symbol, "unknown operation -- assemble")
: head(tail(val));
}
Exercise 5.9
The treatment of machine operations above permits them to operate
on labels as well as on constants and the contents of registers.
Modify the expression-processing
proceduresfunctions
to enforce the condition that operations can be used only with registers
and constants.
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
Original
JavaScript
Exercise 5.10
Design a new syntax for register-machine instructions and modify the
simulator to use your new syntax. Can you implement your new
syntax without changing any part of the simulator except the
syntax procedures in this section?constructor and selector functions in this section?
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
Exercise 5.11
When we introduced
save and
restore in
section 5.1.4, we didn't specify
what would happen if you tried to restore a register that was not the last
one saved, as in the sequence
Original
JavaScript
(save y)
(save x)
(restore y)
save(y);
save(x);
restore(y);
There are several reasonable possibilities for the meaning of
restore:
(restore y)restore(y)
puts into y the last value saved on the
stack, regardless of what register that value came from. This is the
way our simulator behaves. Show how to take advantage of this
behavior to eliminate one instruction from the Fibonacci machine of
section 5.1.4
(figure 5.15).
(restore y)restore(y)
puts into y the last value saved on the
stack, but only if that value was saved from
y; otherwise, it signals an error. Modify
the simulator to behave this way. You will have to change
save to put the register name on the stack
along with the value.
(restore y)restore(y)
puts into y the last value saved from
y regardless of what other registers were
saved after y and not restored. Modify the
simulator to behave this way. You will have to associate a separate
stack with each register. You should make the
initialize-stackinitialize_stack
operation initialize all the register stacks.
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
Exercise 5.12
The simulator can be used to help determine the data paths required
for implementing a machine with a given controller. Extend
the assembler to store the following information in the machine model:
a list of all instructions, with duplicates removed, sorted by
instruction type
(assign,
goto,go_to,
and so on);
a list (without duplicates) of the registers used to hold entry points
(these are the registers referenced by
gotogo_to
instructions);
a list (without duplicates) of the registers that are
saved
or restored;
for each register, a list (without duplicates) of the sources from
which it is assigned (for example, the sources for register
val in the factorial machine of
figure 5.13 are
(const 1)constant(1)
and
((op *) (reg n) (reg val))).
list(op("*"), reg("n"), reg("val"))).
Extend the message-passing interface to the machine to provide access to
this new information. To test your analyzer, define the Fibonacci machine
from figure 5.15 and examine the lists you
constructed.
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
Exercise 5.13
Modify the simulator so that it uses the controller sequence to determine
what registers the machine has rather than requiring a list of registers as
an argument to
make-machine.make_machine.
Instead of preallocating the registers in
make-machine,make_machine,
you can allocate them one at a time when they are first seen during assembly
of the instructions.
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.