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 <register-name> (reg <register-name>))
    (assign <register-name> (const <constant-value>))
    (assign <register-name> (op <operation-name>) <input1> ... <inputn>)
    (test (op <operation-name>) <input1> ... <inputn>)
    (branch (label <label-name>))
    (goto (label <label-name>))
  - 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.