Chapter 5: Computing with Register Machines

My aim is to show that the heavenly machines is not a kind of divine, living being, but a kind of clockwork (and he who believes that a clock has soul attributes the maker’s glory to the work), insofar as nearly all the manifold motions are caused by a most simple and material force, just as all motions of the clock are caused by a single weight.
–Johannes Kepler (letter to Herwart von Honhenburg, 1605)

We began this book by studying processes and by describing processes in therms of procedures written in Lisp. To explain the meanings of these procedures, we used a succession of models of evaluation: the substitution model of Chapter 1, the environment model of Chapter 3, and the metacircular evaluator, in particular, dispelled much of the mystery of how Lisp-like languages are interpreted. But that evaluator fails to elucidate the mechanisms of control in a Lisp system because it inherits the control structure of the underlying Lisp system.
In this chapter we will describe process in terms of the step-by-step operation of a traditional computer. A typical register machine instruction applies a primitive operation to the contents of some registers and assigns that result to another register. We will approach our task from the perspective of a hardware architect rather than that of a machine-language computer programmer. We will providing an explicit model for the mechanisms of control in evaluator.

5.1 Designing Register Machines

To design a register machine, we must design its data paths (registers and operations) and the controller that sequences these operations.


Each way to assign a value to a register is indicated by an arrow with an X behind the head, pointing from the source of data to the register. We can think of the X as a button that, when pushed, allows the value at the source to “flow” into the designated register.

In order for data paths to actually compute GCDs, the buttons must be pushed in the correct sequences. We will describe this sequence in terms of controller diagram.

5.1.1 A Language for Describing Register Machines

We will crated a language that presents, in textual form, all the information given by the data-path and controller diagrams.

The above language is difficult to read because we must constantly refer back to the definitions of the button names and the operation names.
We will replace the arbitrary button and operation names by the definitions of their behavior, which means that we will omit the data-path description.

It is more verbose for large machines and obscures the actual data-path structure of the machine, however, we will use this register-machine language throughout this chapter, because we will be more concerned with understanding controllers that with understanding the elements and connections in data paths.

5.1.2 Abstraction in Machine Design

We will often define a machine to include “primitive” operations that are actually very complex.

5.1.3 Subroutines

We used the continue register to hold the label of the entry point in the controller sequence at which execution should continue when the subroutines is finished. (We can assign to a register a label in the controller sequence in such a way that this value can be fetched from the register and used to continue execution at the designated entry pointl)
However, if we call the subroutine again, the continue register will be overwritten.

5.1.4 Using a Stack to Implement Recursion

We will use a stack to handle the problem of nested subroutines calls in a way that save the contents of any registers that will be needed after the subproblem is solved so that these can be restored to continue the suspended computation.


5.1.5 Instruction Summary

5.2 A Register-Machine Simulator

In this section we construct a simulator for machines described in register-machine language.
The simulator is a Scheme program with four interface procedures. the first uses a description of a register with four interface procedures to construct a model of the machine (a data structure whose parts correspond to the parts of the machine to be simulated), and the other three allow us to simulate the machine by manipulating the model:

  • (make-machine <register-names> <operations> <controller>) constructs and returns a model of machine with the give registers, operations, and controller.
  • (set-register-contents! <machine-model> <register-name> <value>) stores a value in a simulated register in the given machine.
  • (get-register-contents <machine-model> <register-name>) returns the contents of a simulated register in the given machine.
  • (start <machine-model>) simulates the execution of the given machine, starting from the beginning of the controller sequence and stopping when it reaches the end of the sequence.

5.2.1 The Machine Model

To build the model, make-machine begins with calling the procedure make-new-machine to constructs a container for some registers and a stack, together with an execution mechanism that process the controller instructions one by one.
make-machine then extends this basic model to include the registers, operations, and controller of the particular machine being defined.
First it allocates a register in the new machine for each of the supplied register names and installs the designated operations in the machine.
Then it uses an assembler to transform the controller list into instructions for the new machine and installs these as the machine’s instruction.
make-machine returns as its value the modified machine model.

We will represent a register as a procedure with local state.

The Stack
We can also represent a stack as a procedure with local state.

The basic machine
The make-new-machine procedure constructs an object whose local state consists of a stack, an initially empty instruction sequence, a list of operations that initially contains an operation to initialize the stack, and a register table that initially contains two registers, named flag and pc.
The flag register is used to control branching in the simulated machine.
The pc register determines the sequencing of instructions as the machine runs. Each machine instruction is a data structure that includes a procedure of no arguments, called the instruction execution procedure, such that calling this procedure simulates executing the instruction.

5.2.2 The Assembler

Overall, the assembler is much like the evaluators which perform an appropriate action for each type of expression in the input language (in this case, the register-machine language).
The technique of producing an execution procedure for each instruction is just what we use in Section 4.1.7 to speed up the evaluator by separating analysis from runtime execution.
To begins, the assembler must know what all the labels refer to, so it begins by scanning the controller text to separate the labels from the instructions.
extract=labels takes as arguments a list text and a receive procedure.
receive will be called with two values:
(1) a list insts of instruction data structures
(2) a table labels, which associates each label from text with the position in the list insts that the label designates.

update-insts! modifies the instruction list, which initially contains only the text of the instructions, to include the corresponding execution procedures.

Elements of the label table are pairs:

5.2.3 Generating Execution Procedures for Instructions

Like the analyze procedure in the evaluator of Section 4.1.7, this dispatches on the type of instruction to generate the appropriate execution procedure.

assign instructions

The make-assign procedure handles assign instructions:

The register name is looked up with get-register to produce the target register object.
The work of looking up and parsing is performed just once, at assembly time, not every time the instruction is simulated. This saving of work is the reason we use execution procedure, and corresponds directly the saving in work we obtained by separating program analysis from execution in the evaluator of Section 4.1.7.

advance-pc will advance the pc to the next instruction:

test, branch, and goto instructions

make-test handles test instructions in a similar way:

make-branch 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).
The destination in a branch instruction must be a label which is looked up at assembly time.

A goto instruction is similar to a branch, except that the destination may be specified either as a label or as a register, and the pc will is always set to the new destination.

Other instructions
The stack instructions save and restore simply use the stack with the designated register and advance the pc:

make-perform generates an execution procedure for the action to be performed.

Execution procedures for subexpression
The value of a reg, label, or const expression will produced by make-primitive-exp:

assign, perform, and test instructions may include the application of a machine operation (specified by an op expression) to some operands.

The simulation procedure is found by looking up the operation name in the operation table for the machine:

5.2.4 Monitoring Machine Performance

Exercise 5.19
Add a breakpoint feature in the simulator to help debugging.

5.3 Storage Allocation and Garbage Collection

5.4 The Explicit-Control Evaluator

5.5 Compilation

Leave a Reply