next up previous contents
Next: The Assembler Up: A Register-Machine Simulator Previous: A Register-Machine Simulator

   
The Machine Model

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 [*]) 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))

Registers

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

The stack

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 basic machine

The make-new-machine procedure, shown in figure [*], 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).


 \begin{figure}<pre>
(define (make-new-machine)
(let ((pc (make-register 'pc))
...
...e-new-machine} procedure, which implements
the basic machine model.}\end{figure}

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.

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 [*]:

(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 [*] and [*]) 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))


next up previous contents
Next: The Assembler Up: A Register-Machine Simulator Previous: A Register-Machine Simulator
Ryan Bender
2000-04-17