recitation 24: register machines (6.004, part 1 of 2)
------------------------------------------------------------------------
register machine
- a finite set of registers
- a fixed set of operators
- a controller (set of instructions)
- and a stack (next time)
data path diagrams (the components for a particular register machine)
- registers [boxes] - each store one value
- tests [circles] - answer stored in a special condition register
- constants [triangles]
- operators [trapezoids] - primitive operations on one or more arguments
- data flow paths - connect the components together
- assignment buttons [circle with X] - placed just before a register,
when pressed the data on the path is stored into the register
sequencer
- keeps track of the program counter (where we are in the controller code)
controller: sequence of commands & labels
- types of commands (so far)
(assign (reg ))
(assign (const ))
(assign (op ) ... )
(test (op ) ... )
(branch (label ))
(goto (label ))
- our commands look like scheme expressions, but that's just
so we can build a register machine simulator.
* what's a primitive operation?
* how many registers do we have? & what are the names?
------------------------------------------------------------------------
let's build a sqrt register machine
(define (sqrt x)
(define (good-enough? ...) ...)
(define (improve guess) (average guess (/ x guess)))
(define (sqrt-iter guess)
(if (good-enough? guess)
guess
(sqrt-iter (improve guess))))
(sqrt-iter 1))
* radio shack is out of square root chips, so we need to implement it
ourselves. luckily they did have chips for average and
good-enough?. draw the data paths for a square root machine.
* convert the diagrams into a register machine:
(controller
)
------------------------------------------------------------------------
* what function, y = f(x), does this compute?
(controller
(assign y (const 5))
(assign t (op *) (reg x) (const 7))
(assign y (op +) (reg t) (reg y))
(assign t (op *) (reg x) (reg x))
(assign t (op *) (reg t) (const 3))
(assign y (op +) (reg t) (reg y))
)
* change the controller to compute
y = g(k) = f(1) + f(2) + f(3) + .. + f(k)
where k is an additional input register
------------------------------------------------------------------------
* write the register machine code to compute list-ref. assume the
inputs are in register lst and k, and the output should be stored in
register result.
(define (list-ref lst k)
(if (= k 0)
(car lst)
(list-ref (- k 1) (cdr lst))))
(controller
)
------------------------------------------------------------------------
* write an iterative procedure in scheme to do exponentiation by
successive addition. draw the data paths and write a controller to
implement this as a register machine.