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.