In this lecture Sussman covers register machines, and we walk through the operation of a couple of very simple programs. We look at an embedded register machine language.
Note dump:
Register Machines
Rather than looking at large programs we're looking at the mechanisms that allow programs to work.
A program is a description of a machine.
Start with a very simple program. Euclics algorithm for GCD:
(DEFINE (GCD A B)
(IF (= B 0)
A
(GCD B (REMAINDER A B))))
Recursive definition, iterative process.
Data pads and controller are the two main parts of computer.
Data pads are like a calculator, pushing the buttons manipulates registers.
Controller pushes the buttons according to the instructions it get.
Registers store numbers
When designing a computer, should put in the mechanisms to solve the problem you are faced with.
If you are trying to solve common problem, put in a universal interpretter for a language.
a[ ]x---b[ ]--->(B=0?)
| | x
/REMAINDER/ |
| |
t[ ]----|
a and b are fed into a process REMAINDER. There is a check for b==0 that "lights a light bulb) if true. Remainder is dropped into a temporary register so that b can be moved to a before the remainder is dropped into b.
Now we are drawing a flow chart.
(DEFINE-MACHINE GCD
(REGISTERS A B T)
(CONTROLLER
MAIN (ASSIGN A (READ))
(ASSIGN B (READ))
LOOP (BRANCH (ZERO? (FETCH B)) DONE)
(ASSIGN T (REMAINDER (FETCH A) (FETCH B)))
(ASSIGN A (FETCH B))
(ASSIGN B (FETCH T))
(GOTO LOOP)
DONE (PERFORM (PRINT (FETCH A)))
(GOTO MAIN)))
(DEFINE (REMAINDER N D)
(IF (< N D)
N
(REMAINDER (- N D) D)))
Now that we've seen an iterative process, we want to look at a recursive process
(DEFINE (FACT N)
(IF (= N 1)
1
(* N (FACT (- N 1)))))
This creates a situation where we have an infinitely large machine. Infinite hardware doesn't exist so we have to create the illusion of an infinite machine.
Organization of register machine
Finite-state controller <---> Data Paths
|
|
Stack...
(stack continues forever)
...
Stack is FILO (first in-last out) memory.
For factorial, have have the following controller:
(ASSIGN CONTINUE DONE)
LOOP
(BRANCH (= 1 (FETCH N)) BASE)
(SAVE CONTINUE)
(SAVE N)
(ASSIGN N (-1+ (FETCH N)))
(ASSIGN CONTINUE AFT)
(GOTO LOOP)
AFT
(RESTORE N)
(RESTORE CONTINUE)
(ASSIGN VAL (* (FETCH N) (FETCH VAL)))
(GOTO (FETCH CONTINUE))
BASE
(ASSIGN VAL (FETCH N))
(GOTO (FETCH CONTINUE))
DONE
Walk through applying this algorithm to calculating 3!
Get a question about running out of stack space, and the obvious answer is that "the magic doesn't work any more".
Looking at a design for double 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-ANSWER)
(SAVE CONTINUE) <- we need continue so the program knows where to go
(ASSIGN CONTINUE AFTER-FIB-N-1)
(SAVE N)
(ASSIGN N (- (FETCH N) 1))
(GOTO FIB-LOOP)
AFTER-FIB-N-1
(RESTORE N)
(RESTORE CONTINUE) <- we won't need this in a bit (subject to peephole optimization
(ASSIGN N (- (FETCH N) 2))
(SAVE CONTINUE) <- we don't need this either
(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 are always matched
(RESTORE CONTINUE) ;continuation of fib(n)
(ASSIGN VAL (+ (FETCH VAL) (FETCH N)))
(GOTO (FETCH CONTINUE))
IMMIDIATE-ANSWER
(ASSIGN VAL (FETCH N))
(GOTO (FETCH CONTINUE))
FIB-DONE
Note: This register language is NOT LISP per se, it is an embedded language with similar syntax.
We can have systems with other operations (CAR, CDR, CONS, vectors)
At this level of detail, we can conceptualize them as primitive operations
in the data path.
We can look at something like CONS and if we open it up, it will just be a machine with a controller, some registers, and a stack (some infinite thing as Sussman puts it) which we'll call memory...
No comments:
Post a Comment