notes.org 2.0 KB
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
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))))
the controller is a sequence of instructions with labels that define entry points in the sequence
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
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
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
(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)