Structure and Interpretation of Computer Programs (96 page)

(define (make-goto inst machine labels pc)
  (let ((dest (goto-dest inst)))
    (cond ((label-exp? dest)
           (let ((insts
                  (lookup-label labels
                                (label-exp-label dest))))
             (lambda () (set-contents! pc insts))))
          ((register-exp? dest)
           (let ((reg
                  (get-register machine
                                (register-exp-reg dest))))
             (lambda ()
               (set-contents! pc (get-contents reg)))))
          (else (error "Bad GOTO instruction -- ASSEMBLE"
                       inst)))))
(define (goto-dest goto-instruction)
  (cadr goto-instruction))

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

(define (make-save inst machine stack pc)
  (let ((reg (get-register machine
                           (stack-inst-reg-name inst))))
    (lambda ()
      (push stack (get-contents reg))
      (advance-pc pc))))
(define (make-restore inst machine stack pc)
  (let ((reg (get-register machine
                           (stack-inst-reg-name inst))))
    (lambda ()
      (set-contents! reg (pop stack))    
      (advance-pc pc))))
(define (stack-inst-reg-name stack-instruction)
  (cadr stack-instruction))

The final instruction type, handled by
make-perform
, generates
an execution procedure for the action to be performed. At simulation
time, the action procedure is executed and the
pc
advanced.

(define (make-perform inst machine labels operations pc)
  (let ((action (perform-action inst)))
    (if (operation-exp? action)
        (let ((action-proc
               (make-operation-exp
                action machine labels operations)))
          (lambda ()
            (action-proc)
            (advance-pc pc)))
        (error "Bad PERFORM instruction -- ASSEMBLE" inst))))
(define (perform-action inst) (cdr inst))

The value of a
reg
,
label
, or
const
expression
may be needed for assignment to a register (
make-assign
) or for input to
an operation (
make-operation-exp
, below). The following procedure
generates execution procedures to produce values for these expressions
during the simulation:

(define (make-primitive-exp exp machine labels)
  (cond ((constant-exp? exp)
         (let ((c (constant-exp-value exp)))
           (lambda () c)))
        ((label-exp? exp)
         (let ((insts
                (lookup-label labels
                              (label-exp-label exp))))
           (lambda () insts)))
        ((register-exp? exp)
         (let ((r (get-register machine
                                (register-exp-reg exp))))
           (lambda () (get-contents r))))
        (else
         (error "Unknown expression type -- ASSEMBLE" exp))))

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

Assign
,
perform
, and
test
instructions
may include the application of a machine operation (specified by
an
op
expression) to some operands (specified by
reg
and
const
expressions).
The following procedure produces an execution procedure
for an “operation expression” – a list containing the operation and
operand expressions from the instruction:

(define (make-operation-exp exp machine labels operations)
  (let ((op (lookup-prim (operation-exp-op exp) operations))
        (aprocs
         (map (lambda (e)
                (make-primitive-exp e machine labels))
              (operation-exp-operands exp))))
    (lambda ()
      (apply op (map (lambda (p) (p)) aprocs)))))

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

Observe that the treatment of operation expressions is very much like
the treatment of procedure applications by the
analyze-application
procedure in the evaluator of
section 
4.1.7
in that we generate an execution
procedure for each operand. At simulation time, we call the
operand procedures and apply the Scheme procedure that simulates
the operation to the resulting values.
The simulation procedure is found by looking up the operation name in
the operation table for the machine:

(define (lookup-prim symbol operations)
  (let ((val (assoc symbol operations)))
    (if val
        (cadr val)
        (error "Unknown operation -- ASSEMBLE" symbol))))

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 procedures to enforce the condition
that operations can be used only with registers and constants.

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?

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

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

There are several reasonable possibilities for the meaning of
restore
:

a.  
(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.12
).

b.  
(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.

c.  
(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.

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
  , and so on);
  
• a list (without duplicates) of the registers used to hold entry
  points (these are the registers referenced by
  goto
  instructions);
  
• a list (without duplicates) of the registers that are
  save
  d
  or
  restore
  d;
  
• 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.11
  are
  (const 1)
  and
  ((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.12
and examine the lists you constructed.

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
. Instead of
pre-allocating the registers in
make-machine
, you can allocate
them one at a time when they are first seen during assembly of the
instructions.

Simulation is useful not only for verifying the correctness of a
proposed machine design but also for measuring the machine's
performance. For example, we can install in our simulation program a
“meter” that measures the number of stack operations used in a
computation. To do this, we modify our simulated stack to keep track
of the number of times registers are saved on the stack and the
maximum depth reached by the stack, and add a message to the stack's
interface that prints the statistics, as shown below.
We also add an operation to the basic machine model to print the
stack statistics, by initializing
the-ops
in
make-new-machine
to

(list (list 'initialize-stack
            (lambda () (stack 'initialize)))
      (list 'print-stack-statistics
            (lambda () (stack 'print-statistics))))

Here is the new version of
make-stack
:

(define (make-stack)
  (let ((s '())
        (number-pushes 0)
        (max-depth 0)
        (current-depth 0))
    (define (push x)
      (set! s (cons x s))
      (set! number-pushes (+ 1 number-pushes))
      (set! current-depth (+ 1 current-depth))
      (set! max-depth (max current-depth max-depth)))
    (define (pop)
      (if (null? s)
          (error "Empty stack -- POP")
          (let ((top (car s)))
            (set! s (cdr s))
            (set! current-depth (- current-depth 1))
            top)))    
    (define (initialize)
      (set! s '())
      (set! number-pushes 0)
      (set! max-depth 0)
      (set! current-depth 0)
      'done)
    (define (print-statistics)
      (newline)
      (display (list 'total-pushes  '= number-pushes
                     'maximum-depth '= max-depth)))
    (define (dispatch message)
      (cond ((eq? message 'push) push)
            ((eq? message 'pop) (pop))
            ((eq? message 'initialize) (initialize))
            ((eq? message 'print-statistics)
             (print-statistics))
            (else
             (error "Unknown request -- STACK" message))))
    dispatch))

Exercises 
5.15
through 
5.19
describe other useful monitoring and debugging features that can be
added to the register-machine simulator.

Exercise 5.14.
  
Measure the number of pushes and the maximum stack depth required to
compute
n
! for various small values of
n
using the factorial
machine shown in figure 
5.11
. From your data
determine formulas in terms of
n
for the total number of push
operations and the maximum stack depth used in computing
n
! for any
n
> 1. Note that each of these is a linear function of
n
and is
thus determined by two constants. In order to get the statistics
printed, you will have to augment the factorial machine with instructions to
initialize the stack and print the statistics.
You may want to also modify the
machine so that it repeatedly reads a value for
n
, computes the
factorial, and prints the result (as we did for the GCD machine in
figure 
5.4
), so that you will not have to repeatedly
invoke
get-register-contents
,
set-register-contents!
, and
start
.

Exercise 5.15.
  Add
instruction counting
to the register machine simulation.
That is, have the machine model keep track of the number of
instructions executed. Extend the machine model's interface to accept
a new message that prints the value of the instruction count and
resets the count to zero.

Exercise 5.16.
  Augment the simulator to provide for
instruction tracing
.
That is, before each instruction is executed, the simulator should print
the text of the instruction. Make the machine model accept
trace-on
and
trace-off
messages to turn tracing on and off.

Exercise 5.17.
  Extend the instruction tracing of
exercise 
5.16
so that before
printing an instruction, the simulator prints any labels that
immediately precede that instruction in the controller sequence. Be
careful to do this in a way that does not interfere with instruction
counting (exercise 
5.15
).
You will have to make the simulator retain the necessary label information.

Exercise 5.18.
  
Modify the
make-register
procedure of
section 
5.2.1
so that registers can be traced.
Registers should accept messages that turn tracing on and off. When a
register is traced, assigning a value to the register should print the
name of the register, the old contents of the register, and the new
contents being assigned. Extend the interface to the machine model
to permit you to turn tracing on and off for designated machine registers.