Structure and Interpretation of Computer Programs (95 page)

Make-new-machine
returns a
dispatch
procedure that implements message-passing
access to the internal state. Notice that starting the machine is
accomplished by setting
pc
to the beginning of the instruction
sequence and calling
execute
.

For convenience, we provide an alternate procedural interface to a
machine's
start
operation,
as well as procedures to set and examine register contents,
as specified at the beginning of section 
5.2
:

(define (start machine)
  (machine 'start))
(define (get-register-contents machine register-name)
  (get-contents (get-register machine register-name)))
(define (set-register-contents! machine register-name value)
  (set-contents! (get-register machine register-name) value)
  'done)

These procedures (and many procedures in sections 
5.2.2
and
5.2.3
) use the following to look up the register with a
given name in a given machine:

(define (get-register machine reg-name)
  ((machine 'get-register) reg-name))

The assembler transforms the sequence of controller expressions for a
machine into a corresponding list of machine instructions, each with
its execution procedure. Overall, the assembler is much like the
evaluators we studied in chapter 4 – there is an input language (in
this case, the register-machine language) and we must perform an
appropriate action for each type of expression in the language.

The technique of producing an execution procedure for each instruction
is just what we used in section 
4.1.7
to speed
up the evaluator by separating analysis from runtime execution. As we
saw in chapter 4, much useful analysis of Scheme expressions could be
performed without knowing the actual values of variables. Here,
analogously, much useful analysis of register-machine-language
expressions can be performed without knowing the actual contents of
machine registers. For example, we can replace references to
registers by pointers to the register objects, and we can
replace references to labels by pointers to the place in the
instruction sequence that the label designates.

Before it can generate the instruction execution procedures, 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. As it scans the text, it constructs both a list of
instructions and a table that associates each label with a pointer
into that list. Then the assembler augments the instruction list by
inserting the execution procedure for each instruction.

The
assemble
procedure is the main entry to the assembler.
It takes the controller text and the machine model as arguments and
returns the instruction sequence to be stored in the model.
Assemble
calls
extract-labels
to build the initial instruction list
and label table from the supplied controller text. The second argument
to
extract-labels
is a procedure to be called to process these results:
This procedure uses
update-insts!
to generate the instruction execution
procedures and insert them into the instruction list,
and returns the modified list.

(define (assemble controller-text machine)
  (extract-labels controller-text
    (lambda (insts labels)
      (update-insts! insts labels machine)
      insts)))

Extract-labels
takes as arguments a list
text
(the sequence of controller
instruction expressions) and a
receive
procedure.
Receive
will be called with two values: (1) a list
insts
of instruction
data structures, each containing an instruction from
text
; and
(2) a table called
labels
, which associates each label from
text
with the position in the list
insts
that the label designates.

(define (extract-labels text receive)
  (if (null? text)
      (receive '() '())
      (extract-labels (cdr text)
       (lambda (insts labels)
         (let ((next-inst (car text)))
           (if (symbol? next-inst)
               (receive insts
                        (cons (make-label-entry next-inst
                                                insts)
                              labels))
               (receive (cons (make-instruction next-inst)
                              insts)
                        labels)))))))

Extract-labels
works by sequentially scanning the elements of
the
text
and accumulating the
insts
and the
labels
.
If an element is a symbol (and thus a label) an appropriate entry is
added to the
labels
table. Otherwise the element is accumulated
onto the
insts
list.
⁴

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

(define (update-insts! insts labels machine)
  (let ((pc (get-register machine 'pc))
        (flag (get-register machine 'flag))
        (stack (machine 'stack))
        (ops (machine 'operations)))
    (for-each
     (lambda (inst)
       (set-instruction-execution-proc! 
        inst
        (make-execution-procedure
         (instruction-text inst) labels machine
         pc flag stack ops)))
     insts)))

The machine instruction data structure simply pairs the
instruction text with the corresponding execution procedure.
The execution procedure is not yet available when
extract-labels
constructs the instruction, and is inserted later by
update-insts!
.

(define (make-instruction text)
  (cons text '()))
(define (instruction-text inst)
  (car inst))
(define (instruction-execution-proc inst)
  (cdr inst))
(define (set-instruction-execution-proc! inst proc)
  (set-cdr! inst proc))

The instruction text is not used by our simulator, but it is handy to keep
around for debugging (see exercise 
5.16
).

Elements of the label table are pairs:

(define (make-label-entry label-name insts)
  (cons label-name insts))

Entries will be looked up in the table with

(define (lookup-label labels label-name)
  (let ((val (assoc label-name labels)))
    (if val
        (cdr val)
        (error "Undefined label -- ASSEMBLE" label-name))))

Exercise 5.8.
  The following register-machine code is ambiguous, because the label
here
is defined more than once:

start
  (goto (label here))
here
  (assign a (const 3))
  (goto (label there))
here
  (assign a (const 4))
  (goto (label there))
there

With the simulator as written, what will the contents of register
a
be when control reaches
there
? Modify the
extract-labels
procedure so that the assembler will signal an error if the same label
name is used to indicate two different locations.

The assembler calls
make-execution-procedure
to
generate the execution procedure for an instruction.
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.

(define (make-execution-procedure inst labels machine
                                  pc flag stack ops)
  (cond ((eq? (car inst) 'assign)
         (make-assign inst machine labels ops pc))
        ((eq? (car inst) 'test)
         (make-test inst machine labels ops flag pc))
        ((eq? (car inst) 'branch)
         (make-branch inst machine labels flag pc))
        ((eq? (car inst) 'goto)
         (make-goto inst machine labels pc))
        ((eq? (car inst) 'save)
         (make-save inst machine stack pc))
        ((eq? (car inst) 'restore)
         (make-restore inst machine stack pc))
        ((eq? (car inst) 'perform)
         (make-perform inst machine labels ops pc))
        (else (error "Unknown instruction type -- ASSEMBLE"
                     inst))))

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 both the syntax and 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
make-assign
procedure handles
assign
instructions:

(define (make-assign inst machine labels operations pc)
  (let ((target
         (get-register machine (assign-reg-name inst)))
        (value-exp (assign-value-exp inst)))
    (let ((value-proc
           (if (operation-exp? value-exp)
               (make-operation-exp
                value-exp machine labels operations)
               (make-primitive-exp
                (car value-exp) machine labels))))
      (lambda ()                
; execution procedure for 
assign
        (set-contents! target (value-proc))
        (advance-pc pc)))))

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

(define (assign-reg-name assign-instruction)
  (cadr assign-instruction))
(define (assign-value-exp assign-instruction)
  (cddr assign-instruction))

The register name is looked up with
get-register
to produce the
target register object. The value expression is passed to
make-operation-exp
if the value is the result of an operation, and to
make-primitive-exp
otherwise. These procedures (shown below)
parse the value expression and produce an execution procedure for the
value. This is a procedure of no arguments, called
value-proc
,
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 parsing 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, 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
is the execution
procedure for the
assign
instruction. When this procedure is
called (by the machine model's
execute
procedure),
it sets the contents of the target register to the result
obtained by executing
value-proc
. Then it advances
the
pc
to the next instruction by running the procedure

(define (advance-pc pc)
  (set-contents! pc (cdr (get-contents pc))))

Advance-pc
is the normal termination for all instructions except
branch
and
goto
.

Make-test
handles
test
instructions in a similar way. It
extracts the expression that specifies the condition to be tested and
generates an execution procedure for it. At simulation time, the
procedure for the condition is called, the result is assigned to the
flag
register, and the
pc
is advanced:

(define (make-test inst machine labels operations flag pc)
  (let ((condition (test-condition inst)))
    (if (operation-exp? condition)
        (let ((condition-proc
               (make-operation-exp
                condition machine labels operations)))
          (lambda ()
            (set-contents! flag (condition-proc))
            (advance-pc pc)))
        (error "Bad TEST instruction -- ASSEMBLE" inst))))
(define (test-condition test-instruction)
  (cdr test-instruction))

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

(define (make-branch inst machine labels flag pc)
  (let ((dest (branch-dest inst)))
    (if (label-exp? dest)
        (let ((insts
               (lookup-label labels (label-exp-label dest))))
          (lambda ()
            (if (get-contents flag)
                (set-contents! pc insts)
                (advance-pc pc))))
        (error "Bad BRANCH instruction -- ASSEMBLE" inst))))
(define (branch-dest branch-instruction)
  (cadr branch-instruction))

A
goto
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.