(jordyn sicp)

Chapter 5: Computing with Register Machines

we have so far studied processes in lisp with successive models:

substitution (ch 1)
environment (ch 2)
metacircular evaluator (ch 4)

but still we don't know how it works deep down, at the machine level

a computer is really a register machine
that sequentially executes instructions
on some storage elements i.e. registers

a register machine applies a primitive operation to the contents of
some registers and assigns the result to another register

we will approach this study from the perspective of a hardware architect

5.1 Designing Register Machines

we need two elements to design a register machine:

data paths: registers and operations
a controller: to sequence the operations

algorithm analysis (1.2.5's euclid algo):

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

5.1.1 a language for describing register machines

the controller is a sequence of instructions with labels that
define entry points in the sequence

5.1.2 abstraction in machine design

we are assuming a lot here, hiding a lot of complexity in
primitives. this is good though bc it allows us to think about design
in other parts of the system

5.1.3 subroutines

we'd like to share components rather than duplicating them. we can do
this by sharing registers. a better way is to have the 'continue'
register hold the label of the entrypoint so that computation can
continue after processing

5.1.4 using a stack to implement recursion

the register machine so far can compute any iterative
procedure. consider the following algorithm (from 1.2.1)

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

we have to solve for recursive execution

5.1.5 instruction summary

(assign r (reg r))
(assign r (const r))
(assign r (op p) x ... )
(perform (op p) x ... )
(test (op p) x ...)
(branch (label n))
(goto (label n))

(assign r (label n))
(goto (reg r))

(save r)
(restore r)