5-2-simulator.html

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html>
<head>
<meta charset="UTF-8">

<link rel="stylesheet" type="text/css" href="web-worker-interpreter/deps/codemirror/lib/codemirror.css" />
<link rel="stylesheet" type="text/css" href="css/isicp.css" />
<link rel="stylesheet" type="text/css" href="css/footnotes.css" />
<link rel="stylesheet" type="text/css" href="css/theme.css" />

<script src="js/helper.js"></script>
<script src="js/jquery.min.js"></script>
<script src="web-worker-interpreter/deps/codemirror/lib/codemirror.js"></script>
<script src="web-worker-interpreter/deps/codemirror/mode/scheme/scheme.js"></script>
<script src="web-worker-interpreter/coding.js"> </script>
<script>
  set_interpreter_path("web-worker-interpreter/");
  set_language("scheme");
</script>
<script src="js/footnotes.js"></script>

<script type="text/x-mathjax-config">
MathJax.Hub.Config({
  tex2jax: {inlineMath: [['$','$']]}
});
</script>
<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>


<title> iSICP 2.4 - Multiple Representations for Abstract Data </title>
<script type="text/javascript">

  var _gaq = _gaq || [];
  _gaq.push(['_setAccount', 'UA-36868476-1']);
  _gaq.push(['_trackPageview']);

  (function() {
    var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true;
    ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js';
    var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s);
  })();

</script>
</head>
<body>

<div id="sidebox">
  <div class="tab"></div>
  <div class="content">
    
    <p> 
    
    <a href="index.html" class="navlink"> <img src='images/home.svg' width=32 height=32> </a>
    <span id="toc-link" class="navlink"> <img src='images/list.svg' width=32 height=32> </span>
    <span id="currently-editing-link" class="navlink"> <img src='images/file-edit.svg' width=32 height=32> </span>
    
    <script src="http://cdn.jotfor.ms/static/feedback2.js?3.2.310" type="text/javascript">
    new JotformFeedback({
    formId:'40222623177447',
    base:'http://jotform.me/',
    windowTitle:'Notify Me',
    background:'#FFA500',
    fontColor:'#FFFFFF',
    type:false,
    height:500,
    width:700
    });
    </script>
    <a class="lightbox-40222623177447" style="cursor:pointer;color:blue;text-decoration:underline;"><img src='images/envelope.svg' width=32 height=32></a>

    <p>
    
    <div id="currently-editing"> </div>


    <script>
    
    function hideAll() {
      $("#currently-editing").hide();
      $("#toc").hide();
    }
    
    $("#currently-editing-link").click(function() {
      hideAll();
      $("#currently-editing").show();
    });
    
    $("#toc-link").click(function() {
      hideAll();
      $("#toc").show();
    });
    
    </script>
    
    <div id="toc"> </div>
    
    <p style='font-size:12px'> (Click on the left edge of this green box to hide it!)
    
    <script>
    hideAll();
    $("#toc").show();
    </script>
  
  </div>
</div>

<script> 
$('#sidebox .tab').toggle(function(){
    $('#sidebox').animate({'right':'0%'});
}, function(){
    $('#sidebox').animate({'right':'-30%'});
});

$(document).ready(createTOC);

</script>

<div id="main">

<h2> A Register-Machine Simulator </h2> 

<p> 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:

<div class="exercise">

<div id="">
(make-machine <register-names> <operations> <controller>)
</div>
<script>
prompt();
</script>

<p> constructs and returns a model of the machine with the given registers, operations, and controller.

<div id="">
(set-register-contents! <machine-model> <register-name> <value>)
</div>
<script>
prompt();
</script>

<p> stores a value in a simulated register in the given machine.

<div id="">
(get-register-contents <machine-model> <register-name>)
</div>
<script>
prompt();
</script>

<p> returns the contents of a simulated register in the given machine.

<div id="">
(start <machine-model>)
</div>
<script>
prompt();
</script>

<p> 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.
</div>

<p> As an example of how these procedures are used, we can define <tt>gcd-machine</tt> to be a model of the GCD machine of section 5-1-1 as follows:

<div id="">
(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)))
</div>
<script>
prompt();
</script>

<p> The first argument to <tt>make-machine</tt> 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.

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

<div id="">
(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
</div>
<script>
prompt();
</script>

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

<div class="exercise">
<p> <b>Exercise 5.7:</b> Use the simulator to test the machines you designed in Exercise 5-4.
</div>

<h3> The Machine Model </h3> 

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

<p> <tt>Make-machine</tt> 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 <tt>assembler</tt> (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. <tt>Make-machine</tt> returns as its value the modified machine model.

<div id="">
(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))
</div>
<script>
prompt();
</script>

<h4> Registers </h4> 

<p> We will represent a register as a procedure with local state, as in Chapter 3. The procedure <tt>make-register</tt> creates a register that holds a value that can be accessed or changed:

<div id="">
(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))
</div>
<script>
prompt();
</script>

<p> The following procedures are used to access registers:

<div id="">
(define (get-contents register)
  (register 'get))

(define (set-contents! register value)
  ((register 'set) value))
</div>
<script>
prompt();
</script>

<h4> The stack </h4> 

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

<div id="">
(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))
</div>
<script>
prompt();
</script>

<p> The following procedures are used to access stacks:

<div id="">
(define (pop stack)
  (stack 'pop))

(define (push stack value)
  ((stack 'push) value))
</div>
<script>
prompt();
</script>

<h4> The basic machine </h4> 

<p> The <tt>make-new-machine</tt> 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 <tt>register table</tt> that initially contains two registers, named <tt>flag</tt> and <tt>pc</tt> (for ``program counter''). The internal procedure <tt>allocate-register</tt> adds new entries to the register table, and the internal procedure <tt>lookup-register</tt> looks up registers in the table.

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

<p> The <tt>pc</tt> register determines the sequencing of instructions as the machine runs. This sequencing is implemented by the internal procedure <tt>execute</tt>. In the simulation model, each machine instruction is a data structure that includes a procedure of no arguments, called the <tt>instruction execution procedure</tt> , such that calling this procedure simulates executing the instruction. As the simulation runs, <tt>pc</tt> points to the place in the instruction sequence beginning with the next instruction to be executed. <tt>Execute</tt> 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 <tt>pc</tt> points to the end of the instruction sequence).

<div class="exercise">
<p> <b>Figure 5.13:</b> The <tt>make-new-machine</tt> procedure, which implements the basic machine model.

@smalllisp
(define (make-new-machine)
  (let ((pc (make-register 'pc))
        (flag (make-register 'flag))
        (stack (make-stack))
        (the-instruction-sequence '()))
    (let ((the-ops
           (list (list 'initialize-stack
                       (lambda () (stack 'initialize)))))
          (register-table
           (list (list 'pc pc) (list 'flag flag))))
      (define (allocate-register name)
        (if (assoc name register-table)
            (error "Multiply defined register: " name)
            (set! register-table
                  (cons (list name (make-register name))
                        register-table)))
        'register-allocated)
      (define (lookup-register name)
        (let ((val (assoc name register-table)))
          (if val
              (cadr val)
              (error "Unknown register:" name))))
      (define (execute)
        (let ((insts (get-contents pc)))
          (if (null? insts)
              'done
              (begin
                ((instruction-execution-proc (car insts)))
                (execute)))))
      (define (dispatch message)
        (cond ((eq? message 'start)
               (set-contents! pc the-instruction-sequence)
               (execute))
              ((eq? message 'install-instruction-sequence)
               (lambda (seq) (set! the-instruction-sequence seq)))
              ((eq? message 'allocate-register) allocate-register)
              ((eq? message 'get-register) lookup-register)
              ((eq? message 'install-operations)
               (lambda (ops) (set! the-ops (append the-ops ops))))
              ((eq? message 'stack) stack)
              ((eq? message 'operations) the-ops)
              (else (error "Unknown request -- MACHINE" message))))
      dispatch)))
@end smalllisp
</div>

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

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

<p> For convenience, we provide an alternate procedural interface to a machine's <tt>start</tt> operation, as well as procedures to set and examine register contents, as specified at the beginning of section 5-2:

<div id="">
(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)
</div>
<script>
prompt();
</script>

<p> 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:

<div id="">
(define (get-register machine reg-name)
  ((machine 'get-register) reg-name))
</div>
<script>
prompt();
</script>

<h3> The Assembler </h3> 

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

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

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

<p> The <tt>assemble</tt> 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. <tt>Assemble</tt> calls <tt>extract-labels</tt> to build the initial instruction list and label table from the supplied controller text. The second argument to <tt>extract-labels</tt> is a procedure to be called to process these results: This procedure uses <tt>update-insts!</tt> to generate the instruction execution procedures and insert them into the instruction list, and returns the modified list.

<div id="">
(define (assemble controller-text machine)
  (extract-labels controller-text
    (lambda (insts labels)
      (update-insts! insts labels machine)
      insts)))
</div>
<script>
prompt();
</script>

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

<div id="">
(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)))))))
</div>
<script>
prompt();
</script>

<p> <tt>Extract-labels</tt> works by sequentially scanning the elements of the <tt>text</tt> and accumulating the <tt>insts</tt> and the <tt>labels</tt>. If an element is a symbol (and thus a label) an appropriate entry is added to the <tt>labels</tt> table. Otherwise the element is accumulated onto the <tt>insts</tt> list.@footnote{Using the <tt>receive</tt> procedure here is a way to get <tt>extract-labels</tt> to effectively return two values---<tt>labels</tt> and <tt>insts</tt>---without explicitly making a compound data structure to hold them. An alternative implementation, which returns an explicit pair of values, is

<div id="">
(define (extract-labels text)
  (if (null? text)
      (cons '() '())
      (let ((result (extract-labels (cdr text))))
        (let ((insts (car result)) (labels (cdr result)))
          (let ((next-inst (car text)))
            (if (symbol? next-inst)
                (cons insts
                      (cons (make-label-entry next-inst insts) labels))
                (cons (cons (make-instruction next-inst) insts)
                      labels)))))))
</div>
<script>
prompt();
</script>

<p> which would be called by <tt>assemble</tt> as follows:

<div id="">
(define (assemble controller-text machine)
  (let ((result (extract-labels controller-text)))
    (let ((insts (car result)) (labels (cdr result)))
      (update-insts! insts labels machine)
      insts)))
</div>
<script>
prompt();
</script>

<p> You can consider our use of <tt>receive</tt> as demonstrating an elegant way to return multiple values, or simply an excuse to show off a programming trick. An argument like <tt>receive</tt> that is the next procedure to be invoked is called a ``continuation.''  Recall that we also used continuations to implement the backtracking control structure in the <tt>amb</tt> evaluator in section 4-3-3.}

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

<div id="">
(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)))
</div>
<script>
prompt();
</script>

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

<div id="">
(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))
</div>
<script>
prompt();
</script>

<p> The instruction text is not used by our simulator, but it is handy to keep around for debugging (see Exercise 5-16).

<p> Elements of the label table are pairs:

<div id="">
(define (make-label-entry label-name insts)
  (cons label-name insts))
</div>
<script>
prompt();
</script>

<p> Entries will be looked up in the table with

<div id="">
(define (lookup-label labels label-name)
  (let ((val (assoc label-name labels)))
    (if val
        (cdr val)
        (error "Undefined label -- ASSEMBLE" label-name))))
</div>
<script>
prompt();
</script>

<div class="exercise">
<p> <b>Exercise 5.8:</b> The following register-machine code is ambiguous, because the label <tt>here</tt> is defined more than once:

<div id="">
start
  (goto (label here))
here
  (assign a (const 3))
  (goto (label there))
here
  (assign a (const 4))
  (goto (label there))
there
</div>
<script>
prompt();
</script>

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

<h3> Generating Execution Procedures for Instructions </h3> 

<p> The assembler calls <tt>make-execution-procedure</tt> to generate the execution procedure for an instruction. Like the <tt>analyze</tt> procedure in the evaluator of section 4-1-7, this dispatches on the type of instruction to generate the appropriate execution procedure.

<div id="">
(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))))
</div>
<script>
prompt();
</script>

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

<h4> <tt>Assign</tt> instructions </h4> 

<p> The <tt>make-assign</tt> procedure handles <tt>assign</tt> instructions:

<div id="">
(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 <tt>assign</tt>
        (set-contents! target (value-proc))
        (advance-pc pc)))))
</div>
<script>
prompt();
</script>

<p> <tt>Make-assign</tt> 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 <tt>assign</tt> instruction using the selectors

<div id="">
(define (assign-reg-name assign-instruction)
  (cadr assign-instruction))

(define (assign-value-exp assign-instruction)
  (cddr assign-instruction))
</div>
<script>
prompt();
</script>

<p> The register name is looked up with <tt>get-register</tt> to produce the target register object. The value expression is passed to <tt>make-operation-exp</tt> if the value is the result of an operation, and to <tt>make-primitive-exp</tt> 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 <tt>value-proc</tt>, 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.

<p> The result returned by <tt>make-assign</tt> is the execution procedure for the <tt>assign</tt> instruction. When this procedure is called (by the machine model's <tt>execute</tt> procedure), it sets the contents of the target register to the result obtained by executing <tt>value-proc</tt>. Then it advances the <tt>pc</tt> to the next instruction by running the procedure

<div id="">
(define (advance-pc pc)
  (set-contents! pc (cdr (get-contents pc))))
</div>
<script>
prompt();
</script>

<p> <tt>Advance-pc</tt> is the normal termination for all instructions except <tt>branch</tt> and <tt>goto</tt>.

<h4> <tt>Test</tt>, <tt>branch</tt>, and <tt>goto</tt> instructions </h4> 

<p> <tt>Make-test</tt> handles <tt>test</tt> 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 <tt>flag</tt> register, and the <tt>pc</tt> is advanced:

<div id="">
(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))
</div>
<script>
prompt();
</script>

<p> The execution procedure for a <tt>branch</tt> instruction checks the contents of the <tt>flag</tt> register and either sets the contents of the <tt>pc</tt> to the branch destination (if the branch is taken) or else just advances the <tt>pc</tt> (if the branch is not taken). Notice that the indicated destination in a <tt>branch</tt> instruction must be a label, and the <tt>make-branch</tt> procedure enforces this. Notice also that the label is looked up at assembly time, not each time the <tt>branch</tt> instruction is simulated.

<div id="">
(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))
</div>
<script>
prompt();
</script>

<p> A <tt>goto</tt> 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 <tt>pc</tt> is always set to the new destination.

<div id="">
(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))
</div>
<script>
prompt();
</script>

<h4> Other instructions </h4> 

<p> The stack instructions <tt>save</tt> and <tt>restore</tt> simply use the stack with the designated register and advance the <tt>pc</tt>:

<div id="">
(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))
</div>
<script>
prompt();
</script>

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

<div id="">
(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))
</div>
<script>
prompt();
</script>

<h4> Execution procedures for subexpressions </h4> 

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

<div id="">
(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))))
</div>
<script>
prompt();
</script>

<p> The syntax of <tt>reg</tt>, <tt>label</tt>, and <tt>const</tt> expressions is determined by

<div id="">
(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))
</div>
<script>
prompt();
</script>

<p> <tt>Assign</tt>, <tt>perform</tt>, and <tt>test</tt> instructions may include the application of a machine operation (specified by an <tt>op</tt> expression) to some operands (specified by <tt>reg</tt> and <tt>const</tt> expressions). The following procedure produces an execution procedure for an ``operation expression''---a list containing the operation and operand expressions from the instruction:

<div id="">
(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)))))
</div>
<script>
prompt();
</script>

<p> The syntax of operation expressions is determined by

<div id="">
(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))
</div>
<script>
prompt();
</script>

<p> Observe that the treatment of operation expressions is very much like the treatment of procedure applications by the <tt>analyze-application</tt> 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:

<div id="">
(define (lookup-prim symbol operations)
  (let ((val (assoc symbol operations)))
    (if val
        (cadr val)
        (error "Unknown operation -- ASSEMBLE" symbol))))
</div>
<script>
prompt();
</script>

<div class="exercise">
<p> <b>Exercise 5.9:</b> 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.
</div>

<div class="exercise">
<p> <b>Exercise 5.10:</b> 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?
</div>

<div class="exercise">
<p> <b>Exercise 5.11:</b> When we introduced <tt>save</tt> and <tt>restore</tt> 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

<div id="">
(save y)
(save x)
(restore y)
</div>
<script>
prompt();
</script>

<p> There are several reasonable possibilities for the meaning of <tt>restore</tt>:

<ul>
<li>
<tt>(restore y)</tt> puts into <tt>y</tt> 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).
</li>

<li>
<tt>(restore y)</tt> puts into <tt>y</tt> the last value saved on the stack, but only if that value was saved from <tt>y</tt>; otherwise, it signals an error. Modify the simulator to behave this way. You will have to change <tt>save</tt> to put the register name on the stack along with the value.
</li>

<li>
<tt>(restore y)</tt> puts into <tt>y</tt> the last value saved from <tt>y</tt> regardless of what other registers were saved after <tt>y</tt> 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 <tt>initialize-stack</tt> operation initialize all the register stacks.
</li>
</ul>
</div>

<div class="exercise">
<p> <b>Exercise 5.12:</b> 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:

<ul>
<li>
a list of all instructions, with duplicates removed, sorted by instruction type (<tt>assign</tt>, <tt>goto</tt>, and so on);
</li>

<li>
a list (without duplicates) of the registers used to hold entry points (these are the registers referenced by <tt>goto</tt> instructions);
</li>

<li>
a list (without duplicates) of the registers that are <tt>save</tt>d or <tt>restore</tt>d;
</li>

<li>
for each register, a list (without duplicates) of the sources from which it is assigned (for example, the sources for register <tt>val</tt> in the factorial machine of Figure 5-11 are <tt>(const 1)</tt> and <tt>((op *) (reg n) (reg val))</tt>).
</li>
</ul>

<p> 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.
</div>

<div class="exercise">
<p> <b>Exercise 5.13:</b> 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 <tt>make-machine</tt>. Instead of pre-allocating the registers in <tt>make-machine</tt>, you can allocate them one at a time when they are first seen during assembly of the instructions.
</div>

<h3> Monitoring Machine Performance </h3> 

<p> 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 <tt>the-ops</tt> in <tt>make-new-machine</tt> to

<div id="">
(list (list 'initialize-stack
            (lambda () (stack 'initialize)))
      (list 'print-stack-statistics
            (lambda () (stack 'print-statistics))))
</div>
<script>
prompt();
</script>

<p> Here is the new version of <tt>make-stack</tt>:

<div id="">
(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))
</div>
<script>
prompt();
</script>

<p> Exercise 5-15 through Exercise 5-19 describe other useful monitoring and debugging features that can be added to the register-machine simulator.

<div class="exercise">
<p> <b>Exercise 5.14:</b> 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 <tt>get-register-contents</tt>, <tt>set-register-contents!</tt>, and <tt>start</tt>.
</div>

<div class="exercise">
<p> <b>Exercise 5.15:</b> Add <tt>instruction counting</tt> 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.
</div>

<div class="exercise">
<p> <b>Exercise 5.16:</b> Augment the simulator to provide for <tt>instruction tracing</tt> . That is, before each instruction is executed, the simulator should print the text of the instruction. Make the machine model accept <tt>trace-on</tt> and <tt>trace-off</tt> messages to turn tracing on and off.
</div>

<div class="exercise">
<p> <b>Exercise 5.17:</b> 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.
</div>

<div class="exercise">
<p> <b>Exercise 5.18:</b> Modify the <tt>make-register</tt> 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.
</div>

<div class="exercise">
<p> <b>Exercise 5.19:</b> Alyssa P. Hacker wants a <tt>breakpoint</tt> feature in the simulator to help her debug her machine designs. You have been hired to install this feature for her. She wants to be able to specify a place in the controller sequence where the simulator will stop and allow her to examine the state of the machine. You are to implement a procedure

<div id="">
(set-breakpoint <machine> <label> <n>)
</div>
<script>
prompt();
</script>

<p> that sets a breakpoint just before the nth instruction after the given label. For example,

<div id="">
(set-breakpoint gcd-machine 'test-b 4)
</div>
<script>
prompt();
</script>

<p> installs a breakpoint in <tt>gcd-machine</tt> just before the assignment to register <tt>a</tt>. When the simulator reaches the breakpoint it should print the label and the offset of the breakpoint and stop executing instructions. Alyssa can then use <tt>get-register-contents</tt> and <tt>set-register-contents!</tt> to manipulate the state of the simulated machine. She should then be able to continue execution by saying

<div id="">
(proceed-machine <machine>)
</div>
<script>
prompt();
</script>

<p> She should also be able to remove a specific breakpoint by means of

<div id="">
(cancel-breakpoint <machine> <label> <n>)
</div>
<script>
prompt();
</script>

<p> or to remove all breakpoints by means of

<div id="">
(cancel-all-breakpoints <machine>)
</div>
<script>
prompt();
</script>
</div>

<br>
<br>

<hr>

<div id="footnotes">
<h3 id='Notes'> Notes </h3>
 </div>

<hr>

<p> <a rel="license" href="http://creativecommons.org/licenses/by-sa/3.0/deed.en_US" target="_blank"><img alt="Creative Commons License" style="border-width:0" src="http://i.creativecommons.org/l/by-sa/3.0/88x31.png" /></a><br /> Based on Structure and Interpretation of Computer Programs, a work at <a xmlns:dct="http://purl.org/dc/terms/" href="http://mitpress.mit.edu/sicp/" rel="dct:source" target="_blank">http://mitpress.mit.edu/sicp/</a>.

</div>

<a href="https://github.com/zodiac/isicp" target="_blank"><img style="position: absolute; top: 0; right: 0; border: 0;" src="https://s3.amazonaws.com/github/ribbons/forkme_right_green_007200.png" alt="Fork me on GitHub"></a>

</body>
</html>