The machine model generated by make-machine make_machine is represented as a procedure function with local state using the message-passing techniques developed in chapter 3. To build this model, make-machine make_machine begins by calling the procedure function make-new-machine 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 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 The function 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 The function make_machine returns as its value the modified machine model.
| Original | Python |
| (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)) | def make_machine(register_names, ops, controller): 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, machine)) return machine |
We will represent a register as a procedure function with local state, as in chapter 3. The procedure function make-register make_register creates a register that holds a value that can be accessed or changed:
| Original | Python |
| (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)) | def make_register(name): contents = "*unassigned*" def dispatch(message): def set_value(value): nonlocal contents contents = value return (contents if message == "get" else set_value if message == "set" else error("unknown request -- make_register", message)) return dispatch |
| Original | Python |
| (define (get-contents register) (register 'get)) (define (set-contents! register value) ((register 'set) value)) | def get_contents(register): return register("get") def set_contents(register, value): return register("set")(value) |
We can also represent a stack as a procedure function with local state. The procedure function make-stack 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.
| Original | Python |
| (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)) | def make_stack(): stack = None def push(x): nonlocal stack stack = pair(x, stack) return "done" def pop(): nonlocal stack if is_null(stack): error("empty stack -- pop") else: top = head(stack) stack = tail(stack) return top def initialize(): nonlocal stack stack = None return "done" def dispatch(message): return (push if message == "push" else pop() if message == "pop" else initialize() if message == "initialize" else error("unknown request -- stack", message)) return dispatch |
| Original | Python |
| (define (pop stack) (stack 'pop)) (define (push stack value) ((stack 'push) value)) | def pop(stack): return stack("pop") def push(stack, value): return stack("push")(value) |
The
make-new-machine
make_new_machine
procedure,
function,
shown in figure 5.16, 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
function
allocate-register
allocate_register
adds new entries to the register table, and the internal
procedure
function
lookup-register
lookup_register
looks up registers in the table.
| Original | Python | |
| (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))) |
Figure 5.16
The
make_new_machine
function implements the basic machine model.
|
The flag register is used to control branching in the simulated machine. Test Our test instructions set the contents of flag to the result of the test (true or false). Branch Our 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 function execute. In the simulation model, each machine instruction is a data structure that includes a procedure function of no arguments, called the instruction execution procedure, instruction execution function, such that calling this procedure function 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 The function execute gets that instruction, executes it by calling the instruction execution procedure, function, 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 function modifies pc to indicate the next instruction to be executed. Branch and goto instructions The instructions branch and go_to 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 function changes the contents of pc.
Make-new-machine The function make_new_machine returns a dispatch dispatch procedure function 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 functions to set and examine register contents, as specified at the beginning of section 5.2:
| Original | Python |
| (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) | def start(machine): return machine("start") def get_register_contents(machine, register_name): return get_contents(get_register(machine, register_name)) def set_register_contents(machine, register_name, value): set_contents(get_register(machine, register_name), value) return "done" |
| Original | Python |
| (define (get-register machine reg-name) ((machine 'get-register) reg-name)) | def get_register(machine, reg_name): return machine("get_register")(reg_name) |