Structure and Interpretation of Computer Programs (94 page)

A controller instruction in our register-machine language
has one of the following forms, where each
<
input
_i
> is either
(reg <
register-name
>)
or
(const <
constant-value
>)
.

These instructions were introduced in
section 
5.1.1
:

(assign <
register-name
> (reg <
register-name
>))
(assign <
register-name
> (const <
constant-value
>))
(assign <
register-name
> (op <
operation-name
>) <
input
₁
> 
...
<
input
_n
>)
(perform (op <
operation-name
>) <
input
₁
> 
...
<
input
_n
>)
(test (op <
operation-name
>) <
input
₁
> 
...
<
input
_n
>)
(branch (label <
label-name
>))
(goto (label <
label-name
>))

The use of registers to hold labels was introduced in
section 
5.1.3
:

(assign <
register-name
> (label <
label-name
>))
(goto (reg <
register-name
>))

Instructions to use the stack were introduced in
section 
5.1.4
:

(save <
register-name
>)
(restore <
register-name
>)

The only kind of <
constant-value
> we have seen so far is a number,
but later we will use strings, symbols, and lists.
For example,
(const "abc")
is the string
"abc"
,
(const abc)
is the symbol
abc
,
(const (a b c))
is the list
(a b c)
,
and
(const ())
is the empty list.

In order to gain a good understanding of the design of register
machines, we must test the machines we design to see if they perform
as expected. One way to test a design is to hand-simulate the
operation of the controller, as in exercise 
5.5
. But this is
extremely tedious for all but the simplest machines. In this section
we construct a simulator for machines described in the
register-machine language. The simulator is a Scheme program with
four interface procedures. The first uses a description of a register
machine 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 the machine with the given
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.

As an example of how these procedures are used, we can define
gcd-machine
to be a model of the GCD machine
of section 
5.1.1
as follows:

(define gcd-machine
  (make-machine
   '(a b t)
   (list (list 'rem remainder) (list '= =))
   '(test-b
       (test (op =) (reg b) (const 0))
       (branch (label gcd-done))
       (assign t (op rem) (reg a) (reg b))
       (assign a (reg b))
       (assign b (reg t))
       (goto (label test-b))
     gcd-done)))

The first argument to
make-machine
is a list of register names.
The next argument is a table (a list of two-element lists) that pairs
each operation name with a Scheme procedure that implements the operation
(that is, produces the same output value given the same input values).
The last argument specifies the controller as a list of labels and
machine instructions, as in section 
5.1
.

To compute GCDs with this machine, we set the
input registers, start the machine, and examine the result when the
simulation terminates:

(set-register-contents! gcd-machine 'a 206)
done
(set-register-contents! gcd-machine 'b 40)
done
(start gcd-machine)
done
(get-register-contents gcd-machine 'a)
2

This computation will run much more slowly than a
gcd
procedure
written in Scheme, because we will simulate low-level machine
instructions, such as
assign
, by much more complex operations.

Exercise 5.7.
  Use the simulator to test the machines you designed in
exercise 
5.4
.

The machine model generated by
make-machine
is represented as a
procedure with local state using the message-passing techniques
developed in chapter 3. To build this model,
make-machine
begins by calling the procedure
make-new-machine
to construct
the parts of the machine model that are common to all register
machines. This basic machine model constructed by
make-new-machine
is essentially a container for some registers and a
stack, together with an execution mechanism that processes the controller
instructions one by one.

Make-machine
then extends this basic model (by sending it
messages) 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
(described below in section 
5.2.2
) to
transform the controller list into instructions for the new machine
and installs these as the machine's instruction sequence.
Make-machine
returns as its value the modified machine model.

(define (make-machine register-names ops controller-text)
  (let ((machine (make-new-machine)))
    (for-each (lambda (register-name)
                ((machine 'allocate-register) register-name))
              register-names)
    ((machine 'install-operations) ops)    
    ((machine 'install-instruction-sequence)
     (assemble controller-text machine))
    machine))

We will represent a register as a procedure with local state, as in
chapter 3. The procedure
make-register
creates a register that
holds a value that can be accessed or changed:

(define (make-register name)
  (let ((contents '*unassigned*))
    (define (dispatch message)
      (cond ((eq? message 'get) contents)
            ((eq? message 'set)
             (lambda (value) (set! contents value)))
            (else
             (error "Unknown request -- REGISTER" message))))
    dispatch))

The following procedures are used to access registers:

(define (get-contents register)
  (register 'get))
(define (set-contents! register value)
  ((register 'set) value))

We can also represent a stack as a procedure with local state. The
procedure
make-stack
creates a stack whose local state consists
of a list of the items on the stack. A stack accepts requests to
push
an item onto the stack, to
pop
the top item off the stack
and return it, and to
initialize
the stack to empty.

(define (make-stack)
  (let ((s '()))
    (define (push x)
      (set! s (cons x s)))
    (define (pop)
      (if (null? s)
          (error "Empty stack -- POP")
          (let ((top (car s)))
            (set! s (cdr s))
            top)))
    (define (initialize)
      (set! s '())
      'done)
    (define (dispatch message)
      (cond ((eq? message 'push) push)
            ((eq? message 'pop) (pop))
            ((eq? message 'initialize) (initialize))
            (else (error "Unknown request -- STACK"
                         message))))
    dispatch))

The following procedures are used to access stacks:

(define (pop stack)
  (stack 'pop))
(define (push stack value)
  ((stack 'push) value))

The
make-new-machine
procedure, shown in
figure 
5.13
, 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
(for “program counter”).
The internal procedure
allocate-register
adds new entries to the
register table, and the internal procedure
lookup-register
looks
up registers in the table.

The
flag
register is used to control branching in the simulated
machine.
Test
instructions set the contents of
flag
to
the result of the test (true or false).
Branch
instructions
decide whether or not to branch by examining the contents of
flag
.

The
pc
register determines the sequencing of instructions as
the machine runs. This sequencing is implemented by the internal
procedure
execute
.
In the simulation model, 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. As the simulation runs,
pc
points to
the place in the instruction sequence beginning with the next
instruction to be executed.
Execute
gets that instruction,
executes it by calling the instruction execution procedure, and
repeats this cycle until there are no more instructions to execute
(i.e., until
pc
points to the end of the instruction sequence).

As part of its operation, each instruction execution procedure
modifies
pc
to indicate the next instruction to be executed.
Branch
and
goto
instructions change
pc
to point to
the new destination. All other instructions simply advance
pc
,
making it point to the next instruction in the sequence. Observe that
each call to
execute
calls
execute
again, but this does
not produce an infinite loop because running the instruction execution
procedure changes the contents of
pc
.