sicpsgjd/5/1/jord/lecture.org

• Lecture 9A: Register Machines

Lecture 9A: Register Machines

we have a lot of ideas about big programs but there are still mysteries about how things work

we are going to take some very simple lisp programs and translate them to hardware

our "very simple program":

  (define (gcd a b)
    (if (= b 0)
	a
	(gcd b (remainder a b))))

this algo has well defined state vars, a and b, that contain the essence of the algorithm

we have two registers, a and b. we need a way to

• store b in a

• compute remainder (primitive)

• test equality with zero

• have a temp register

• be able to store temp in b

now we need a controller

there was a time, like with the DEC PDP-6, where this was the literal implementation

gjs in a jovial mood XD

(define-machine gcd
  (registers a b t)
  (controller
  loop (branch (zero? (fetch b)) done)
       (assign t (remainder (fetch a) (fetch b)))
       (assign a (fetch b))
       (assign b (fetch t))
       (goto loop)
  done))

gjs remembers using ibm 7090 computers

–> break

we can now build machines that can handle iterative processes. what about machines that can process recursive processes?

  (define (fact n)
    (if (= n 1)
	1
	(* n (fact (- n 1)))))

we can only make the illusion of infinity and "illusion's all that matters"

we can develop a stack to keep track of subsequent recursive computated values

(assign continue done)
loop (branch (= 1 (fetch n)) base)
(save continue)
(save n)
(assign n (-1+ (fetch n)))
(assign continue after)
(goto loop)
after (restore n)
(restore continue)
(assign val (* (fetch n) (fetch val)))
(goto (fetch continue))
base (assign val (fetch n))
(goto (fetch continue))
done

"bang!" -gjs

"memory is el cheapo and people are expensive" -gjs

–> break

gonna look at a more complicated algo, doubly recursive fibonacci

  (define (fib n)
    (if (< n 2)
	n
	(+ (fib (- n 1))
	   (fib (- n 2)))))

(assign continue fib-done)
fib-loop ; n contains arg, continue is recipient
(branch (< (fetch n) 2) immediate-ans)
(save continue)
(assign continue after-fib-n-1)
(save n)
(assign n (- (fetch n) 1))
(goto fib-loop)
after-fib-n-1
(restore n)
;; (restore continue) ;; not necessary
(assign n (- (fetch n) 2))
;; (save continue) ;; not necessary
(assign continue after-fib-n-2)
(save val)
(goto fib-loop)
after-fib-n-2
(assign n (fetch val)) ;; fib(n-2)
(restore val) ;; restores and saves always match
(restore continue)
(assign val (+ (fetch val) (fetch n)))
(goto (fetch continue))
immediate-ans
(assign val (fetch n))
(goto (fetch continue))
fib-done.