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.