5.2.3 Instructions and Their Execution Functions

The assembler calls make_execution_function to generate the execution function for a controller instruction. Like the analyze function in the evaluator of section 4.1.7, this dispatches on the type of instruction to generate the appropriate execution function. The details of these execution functions determine the meaning of the individual instructions in the register-machine language.

function make_execution_function(inst, labels, machine, 
                                 pc, flag, stack, ops) {
    const inst_type = type(inst);
    return inst_type === "assign"
           ? make_assign_ef(inst, machine, labels, ops, pc)
           : inst_type === "test"
           ? make_test_ef(inst, machine, labels, ops, flag, pc)
           : inst_type === "branch"
           ? make_branch_ef(inst, machine, labels, flag, pc)
           : inst_type === "go_to"
           ? make_go_to_ef(inst, machine, labels, pc)
           : inst_type === "save"
           ? make_save_ef(inst, machine, stack, pc)
           : inst_type === "restore"
           ? make_restore_ef(inst, machine, stack, pc)
           : inst_type === "perform"
           ? make_perform_ef(inst, machine, labels, ops, pc)
           : error(inst, "unknown instruction type -- assemble");
}

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

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.

The instruction assign

The make_assign_ef function makes execution functions for assign instructions:

function make_assign_ef(inst, machine, labels, operations, pc) {
    const target = get_register(machine, assign_reg_name(inst));
    const value_exp = assign_value_exp(inst);
    const value_fun =
        is_operation_exp(value_exp)
        ? make_operation_exp_ef(value_exp, machine, labels, operations)
        : make_primitive_exp_ef(value_exp, machine, labels);
    return () => {
               set_contents(target, value_fun());
               advance_pc(pc); 
           };
}

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 function make_assign_ef looks up the register name with get_register to produce the target register object. The value expression is passed to make_operation_exp_ef if the value is the result of an operation, and it is passed to make_primitive_exp_ef otherwise. These functions (shown below) analyze the value expression and produce an execution function for the value. This is a function of no arguments, called 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 analyzing 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 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_assign_ef is the execution function for the assign instruction. When this function is called (by the machine model's execute function), it sets the contents of the target register to the result obtained by executing value_fun. Then it advances the pc to the next instruction by running the function

function advance_pc(pc) {
    set_contents(pc, tail(get_contents(pc))); 
}

The function advance_pc is the normal termination for all instructions except branch and go_to.

The instructions test, branch, and go_to

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 function for it. At simulation time, the function for the condition is called, the result is assigned to the flag register, and the pc is advanced:

function make_test_ef(inst, machine, labels, operations, flag, pc) {
    const condition = test_condition(inst);
    if (is_operation_exp(condition)) {
        const condition_fun = make_operation_exp_ef(
                                  condition, machine, 
                                  labels, operations);
        return () => {
                   set_contents(flag, condition_fun());
                   advance_pc(pc); 
               };
    } else {
        error(inst, "bad test instruction -- assemble");
    }
}

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 function 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_branch_ef function enforces this. Notice also that the label is looked up at assembly time, not each time the branch instruction is simulated.

function make_branch_ef(inst, machine, labels, flag, pc) {
    const dest = branch_dest(inst);
    if (is_label_exp(dest)) {
        const insts = lookup_label(labels, label_exp_label(dest));
        return () => {
                   if (get_contents(flag)) {
                       set_contents(pc, insts);
                   } else {
                       advance_pc(pc);
                   }
               };
    } else {
        error(inst, "bad branch instruction -- assemble");
    }
}

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

function make_go_to_ef(inst, machine, labels, pc) {
    const dest = go_to_dest(inst);
    if (is_label_exp(dest)) {
        const insts = lookup_label(labels, label_exp_label(dest));
        return () => set_contents(pc, insts);
    } else if (is_register_exp(dest)) {
        const reg = get_register(machine, register_exp_reg(dest));
        return () => set_contents(pc, get_contents(reg));
    } else {
        error(inst, "bad go_to instruction -- assemble");
    }
}

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:

function make_save_ef(inst, machine, stack, pc) {
    const reg = get_register(machine, stack_inst_reg_name(inst));
    return () => {
               push(stack, get_contents(reg));
               advance_pc(pc);
           };
}
function make_restore_ef(inst, machine, stack, pc) {
    const reg = get_register(machine, stack_inst_reg_name(inst));
    return () => {
               set_contents(reg, pop(stack));
               advance_pc(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_ef, generates an execution function for the action to be performed. At simulation time, the action function is executed and the pc advanced.

function make_perform_ef(inst, machine, labels, operations, pc) {
    const action = perform_action(inst);
    if (is_operation_exp(action)) {
        const action_fun = make_operation_exp_ef(action, machine,
                                                 labels, operations);
        return () => { 
                   action_fun(); 
                   advance_pc(pc); 
               };
    } else {
        error(inst, "bad perform instruction -- assemble");
    }
}

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 functions for subexpressions

The value of a reg, label, or constant expression may be needed for assignment to a register (make_assign_ef, above) or for input to an operation (make_operation_exp_ef, below). The following function generates execution functions 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");
    }
}

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

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 constant expressions). The following function produces an execution function for an operation expression—a list containing the operation and operand expressions from the instruction:

function make_operation_exp_ef(exp, machine, labels, operations) {
    const op = lookup_prim(operation_exp_op(exp), operations);
    const afuns = map(e => make_primitive_exp_ef(e, machine, labels),
                      operation_exp_operands(exp));
    return () => apply_in_underlying_javascript(
                     op, map(f => f(), afuns));
}

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 function applications by the analyze_application function in the evaluator of section 4.1.7 in that we generate an execution function for each operand. At simulation time, we call the operand functions and apply the JavaScript function that simulates the operation to the resulting values. 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 function is found by looking up the operation name in the operation table for the machine:

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

Exercise 5.10 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

save(y);
save(x);
restore(y);

There are several reasonable possibilities for the meaning of restore:

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) 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) 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_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.11 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, go_to, and so on);
a list (without duplicates) of the registers used to hold entry points (these are the registers referenced by go_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 constant(1) and 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.12 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. Instead of preallocating the registers in 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.