SICP 5.1 Computing with Register Machines: Designing Register Machines
2024-12-24 Tue (Updated on 2025-01-09 Thu; 2025-01-30 Thu)
- The book began talking about ``processes''. [Question as an ex philosophy student: can we say that processes are to procedures what semantic content is to linguistic expressions? If the answer is yes, we might want to avoid saying that procedures describe processes…]
- We have described processes in terms of procedures written in Lisp.
- The ``meaning'' of those procedures, Authors say, has been explained
by using ``models of evaluations'':
- the substitution model (chapter 1);
- the environment model (chapter 3);
- the metacircular evaluator (chapter 4).
- [Q: doesn't the metacircular evaluator implement an environment model of evaluation?]
- Much mystery has been cleared away, but important questions have
been left unanswered.
- In particular, the mechanisms of control have not been explained.
- How are values returned by the evaluation of subexpressions to the expressions that use them?
- Why some recursive procedures generate iterative process (that is, processes whose growth complexity in space is constant) and some recursive procedures generate recursive processes?
- In particular, the mechanisms of control have not been explained.
- The reason such important questions remain unanswered is that the metacircular evaluator is itself a Lisp program so it inherits the control structure of the underlying Lisp system.
- To elucidate the control structure of the Lisp evaluator we shall descend at a more primitive level.
- Chapter 5 describes processes in terms of the operations of a traditional computer, a.k.a. register machine.
- A register machine ``sequentially executes instructions that manipulate the contents of a fixed set of storage elements called registers'' (491).
- ``[W]e will examine some procedures and design a register machine for each of them. Thus, we will approach our task from the perspective of a hardware architect rather than that of a machine-language computer programmer'' (492).
- To design a register machine, me must design
- its data paths;
- its controller.
- Only one register can be assigned a new value at each step.
- Authors present a way to represents data paths and controllers with diagrams.
- As an example, they draw the data paths and controller of a
GCDmachine. - Authors present a way to describe machines in a textual form and presents a specification of the GCD machine.
- Authors introduce the notion of subroutine. [What's the def? It wasn't that clear.]
- Authors show that we can use a register to hold a label.
- Authors show how to use a stack to implement recursion.
- Example:
factorial; Example:
fib(double recursion). Here is the controller for thefibmachine with some comments:(controller ;; We are going to to compute `(fib n)`. ;; ;; When we are done computing it, we have finished. ;; ;; The `continue` register stores the address of the instruction we ;; have to execute when we are done doing something. ;; ;; When we are done with computing `(fib n)`, we have nothing left to ;; do. So we set `continue` to `fib-done`. (assign continue (label 'fib-done)) ;; Then we initiate the computation of `(fib n)`. We will come back ;; to this piece of code when, if ever, `n` will have lower values ;; than the initial one; so we use a label. fib-loop ;; We test whether `(< n 2)`. (test (op <) (reg n) (const 2)) (branch (label immediate-answer)) ;; Either we have the answer for `(fib n)` or we don't. If we do, ;; then we jump to the `immediate-answer` label with the instruction ;; above. If don't, then we need to recur. When we recur, we first ;; compute `(fib (- n 1))`, and then we compute `(fib (- n 2))`, and ;; finally we add the two results. ;; ;; Since we have to postpone the computation of `(fib n)`, let's save ;; the current values of `n` and `continue` onto the stack, so we can ;; come back to them when we need to do so. Once those values are ;; saved in the stack, we can update `n` and `continue`. We are going ;; to compute `(fib (- n 1))` so we set `n` to `n-1`. Once we are ;; done with that, we will be done computing the `(fib (- n 1))` so ;; we set the the value of the `continue` register to the ;; `after-fib-n-1` label. (save continue) (assign continue (label after-fib-n-1)) (assign n (op -) (reg n) (const 1)) (save n) ;; Now we can start the computation of `(fib (- n 1))` so we loop ;; back to the portion of code which starts the compuation of a fib. (goto (label fib-loop)) after-fib-n-1 ;; If we are here, then it means we have just put the value of a ;; `(fib (- n 1))` in the `val` register. ;; ;; Given the so, we still have to compute the value of the relevant ;; `(fib (- n 2))`, before we can compute the value of the relevant ;; (fib n) --- which, as we have already said, is the sum of `(fib (- ;; n 1))` and `(fib (- n 2))`. (restore n) (restore continue) (save continue) (assign continue (label after-fib-n-2)) ;; We want to save the result of `(fib (- n 1))`, which we have ;; stored in val, since val will be used to store the result of `(fib ;; (- n 2))` (save val) (goto (label fib-loop)) after-fib-n-2 ;; If we are here, then it means we have just put the value of a ;; `(fib (- n 2))` in the `val` register. ;; ;; Remember, moreover, that the value of `(fib (- n 1))` is stored at ;; the top of the stack. We want to restore the value of `(fib (- n ;; 1))`, but we don't want to overwrite and lose the value currently ;; stored in the `val` register, so we move the value stored in the ;; the `val` register into the `n` register. (assign n (reg val)) (restore val) ;; we restore `continue` so we know what to do once we have computed ;; `(fib n)`. (restore continue) ;; the value of `(fib (- n 1))` is in the `val` register and the ;; value of `(fib (- n 1))` is in the `n` register. We can now add ;; them up to get the value of `(fib n)` (assign val (op +) (reg val) (reg n)) (goto (reg continue)) immediate-answer ;; If we are here, then it means that we are computing `(fib n)` ;; where `(< n 2). The result of that is `n`. We put the result into ;; the `val` register. (assign val (reg n)) ;; now that the result is in the `val` register, we need to know what ;; to do. In order to know what to do, we need to know what result is ;; have computed. There are three possibilities: 1) we are done; 2) ;; we have computed the value of a `(fib (- n 1))` recursion; 3) we ;; have computed the value of a `(fib (- n 2))` recursion. The ;; `continue` register is expected to hold the relevant label to let ;; us know what value we have just finished computing. (goto (reg continue)) fib-done) ;; we are done
- Example:
Exercise 5.1
Exercise:
Design a register machine to compute factorials using the iterative algorithm specified by the following procedure. Draw data-path and controller diagrams for this machine.
(define (factorial n) (define (iter product counter) (if (> counter n) product (iter (* counter product) (+ counter 1)))) (iter 1 1))
Answer:
Data paths Controller
/\--------------------------------+
/ \ | start
+---/ 1 \ (x) 1->n |
| / \ ----- | |
| ---------- --------->( > ) | V
| \ / ----- | +-----------+
| 1->c (x) / ^ | | 1->c |
| \ / | | | |
| V / | V +-----------+
| +----------+ +-+---------+ +------------+ |
| | counter | | n | | product | |
| | | | | | | V
| +----------+ +-----------+ +------------+ +-----------+
| | \ ^ / ^ | 1->n |
| | \ +------------------------+ / | | |
| | \ | / | +-----------+
| | \ | / | |
| | \ +---------+----------- | |
| | \ | | | V
| | V V | | /\
| | \-------------------/ | | / \
| | \ / | (x) *->p / \ yes
| | \ * / | | +----> / > \----------> done
| | \ / | | | \ /
| | \ / | | | \ /
| | -----+----- | | | \ /
| | | | | | \/
| +------------+ | | | | |
| | -----------------+---------------------+ | |
+---------------+ | | | |no
| | | | |
V V | | |
\-------------------/ | | V
\ / | | +-----------+
\ + / | | | *->p |
\ / (x) +->c | | |
\ / | | +-----------+
-----+----- | | |
| | | |
| | | V
+----------------+ | +-----------+
| | +->c |
| | |
| +----+------+
| |
| |
+---------+
The result is stored in the product register.
Exercise 5.2
Exercise:
Use the register-machine language to describe the iterative factorial machine of Exercise 5.1
Answer:
(controller (assign counter (const 1)) (assign n (const 1)) test-counter-n (test (op >) (reg counter) (reg n)) (branch (label factorial-done)) (assign product (op *) (reg counter) (reg product)) (assign counter (op +) (reg counter) (const 1)) (goto (label test-counter-n)) factorial-done)
Exercise 5.3
Exercise:
Design a machine to compute square roots using Newton's method, as described in section 1.1.7.
(define (sqrt x) (define (good-enough? guess) (< (abs (- (square guess) x)) 0.001)) (define (improve guess) (average guess (/ x guess))) (define (sqrt-iter guess) (if (good-enough? guess) guess (sqrt-iter (improve guess)))) (sqrt-iter 1.0))Begin by assuming that
good-enough?andimproveoperations are available as primitives. Then show how to expand these in terms of arithmetic operations. Describe each version of thesqrtmachine design by drawing a data-path diagram and writing a controller definition in the register-machine language.
Answer:
First version of sqrt machine:
Data paths:
/\
/ \ -----------------------
/ \ \ /
/ \ \ read /
/ 1.0 \ \ /
/ \ \ /
/ \ ----+---------/
------+------- |
| g<-1 |
+----(x)-----+ +----------
| |
V v
+--------------+ +------+-----+
| | | |
| guess | | x |
| | | |
+----------+---+ +------------+
| | ^
| | | g<-i
| | +-----------(x)--------+
V | |
------- +--------------+ |
-/ \- V |
/ \ --------------+---------
|good-enough| \ /
\ / \ improve /
-\ /- \ /
------- \--------------/
Controller:
(controller (assign guess (const 1.0)) (assign x (op read)) test-ge (test (op good-enough) (reg guess)) (branch (label sqr-done)) (assign guess (op improve) (reg guess)) (goto (label test-ge)) sqr-done)
Second version of the sqrt machine (without the good-enough and
the improve abstractions):
Data paths:
/\
/ \
/ \
/ \
/ 1.0 \
/ \
-----+------
|
|
|
+-----------------------------+
|
|
|
V
---------------------------- |---------------------------|
| | | |
| | | |
| guess | | x |
| | | |
| | | |
---------------------------- | |
| ^ | -----------------------------
| | | | |
| | +------------------------------------+ | |
| | | | |
| | | +--------------------------+ |
| | | | |
| | | | |
| | V V |
| | ------------------------ |
V | \ / |
|----------------------------- | \ / / |
| | | \ / |
| |<-+-----------------------------+ \ / +-----------+ |
-------------------| tmp | | | -------------- | | |
| | |--+---------------------+ | | | | V |
| | | | | +------------+ +--------+ ------------------------ |
| |----------------------------- | | \ / |
| ^ | ^ ^ | | | | \ average / |
| +---------+ | | | | | | +-----------------------------------------> \ / |
| | +--------+ | | | | | ---------------- |
| | | +---------+ | | | | | |
| | | | | | | +-------------------------------------------------------------------------+ |
| | | | +---------+ | +----------------------------------------+ |
| | | | | V | +-------------------------------------------+
| | | | | ------------------------------- V V
| | | | | \ / -------------------------------
| | | | | \ / \ /
| | | | | \ square / \ /
| | | | | \ / \ - /
| | | | | \ / \ /
| | | | | -------------------- \ /
| | | | | | -------------------
| | | | | | |
| | | | | | |
| | | | +------------+ |
| | | | |
| | | | |
| | | +------------------------------------------------------------------+
| | |
| | |
| | +---------------------------------+
| | |
| | |
| | V
| | --------------------------
| | | |
| | | |
| | | abs |
| | | |
| | | |
| | --------------------------
| | |
| | |
| +---------------------------------------+
|
|
| /\
| ------- / \
| -/ \- / \
| / \ / \
|-------------------------> | < | <-----------------/ \
\ / / 0.001 \
-\ /- / \
------- --------------
Controller:
(controller (assign guess (const 1.0)) test-ge (assign tmp (reg guess)) (assign tmp (op square) (reg tmp)) (assign tmp (op -) (reg tmp) (reg x)) (assing tmp (op abs) (reg tmp)) (test (op <) (reg tmp) (const 0.001)) (branch (label sqrt-done)) (assign tmp (op /) (reg x) (reg guess)) (assign guess (op average) (reg guess) (reg tmp)) sqrt-done)
Exercise 5.4
Exercise:
Specify register machines that implement each of the following procedures. For each machine, write a controller instruction sequence and draw a diagram showing the data paths.
a. Recursive exponentiation:
(define (expt b n) (if (= n 0) 1 (* b (expt b (- n 1)))))b. Iterative exponentiation:
(define (expt b n) (define (expt-iter counter product) (if (= counter 0) product (expt-iter (- counter 1) (* b product)))) (expt-iter n 1))
Answer:
Recursive exponentiation:
;; - example: (expt 2 3); initial values: ;; - register b is set to 2 ;; - register n is set to 3 (controller (assign continue (label fact-done)) expt-loop (test (op =) (reg n) (const 0)) (branch (label base-case)) (save continue) (save n) ;; no need to save b since it always holds the same val (assign n (op -) (reg n) (const 1)) (assign continue (label after-expt)) (goto (label expt-loop)) after-expt (restore n) (restore continue) (assign val (op *) (reg b) (reg val)) (goto continue) base-case (assign val (const 1)) (goto (reg continue)) expt-done)
Iterative exponentiation:
;; - example: (expt 2 3); initial values: ;; - register b is set to 2 ;; - register counter is set to 3 ;; - register product is set to 1 (controller expt-loop (test (op =) (reg counter) (const 0)) (branch expt-done) (assign counter (op -) (reg counter) (const 1)) (assign product (op *) (reg b) (reg product)) (goto expt-loop) expt-done)
Exercise 5.5
Exercise:
Hand-simulate the factorial and Fibonacci machines, using some nontrivial input (requiring execution of at least one recursive call). Show the contents of the stack at each significant point in the execution.
Answer:
Relevant contents of the stack when computing the
factorialof5(the stack grows backwards):[] [5|fact-done] [4|after-fact|5|fact-done] [3|after-fact|4|after-fact|5|fact-done] [2|after-fact|3|after-fact|4|after-fact|5|fact-done] [3|after-fact|4|after-fact|5|fact-done] [4|after-fact|5|fact-done] [5|fact-done] []Relevant contents of the stack when computing the
fibof2:[] (starting point) [2|fib-done] (when setting up the computation of fib(n-1)) [] (before setting up the computation of fib(n-2)) [1|fib-done] (setting up the computation of fib(n-2)) [] (before computing fib(n-1) + fib(n-2))
Exercise 5.6
Exercise:
Ben Bitdiddle observes that the Fibonacci machine's controller sequence has an extra `save' and an extra `restore', which can be removed to make a faster machine. Where are these instructions?
Answer:
Those two instructions are the (restore continue) and (save
continue) in after-fib-n-2. Here I create a fib-machine without
those two instructions and show that it works nonetheless:
;; racket repl in emacs provided by racket-mode.el
repl.rkt> (define fib-machine
(make-machine
'(continue n val)
(list (list '+ +) (list '< <) (list '- -))
'(
(assign continue (label fib-done))
fib-loop
(test (op <) (reg n) (const 2))
(branch (label immediate-answer))
(save continue)
(assign continue (label afterfib-n-1))
(save n)
(assign n (op -) (reg n) (const 1))
(goto (label fib-loop))
afterfib-n-1
(restore n)
;; (restore continue) <----------------------------------
(assign n (op -) (reg n) (const 2))
;; (save continue) <----------------------------------
(assign continue (label afterfib-n-2))
(save val)
(goto (label fib-loop))
afterfib-n-2
(assign n (reg val))
(restore val)
(restore continue)
(assign val
(op +) (reg val) (reg n))
(goto (reg continue))
immediate-answer
(assign val (reg n))
(goto (reg continue))
fib-done)))
repl.rkt> (set-register-contents! fib-machine 'n 4)
'done
repl.rkt> (start fib-machine)
'done
repl.rkt> (get-register-contents fib-machine 'val)
3
repl.rkt> (set-register-contents! fib-machine 'n 5)
'done
repl.rkt> (start fib-machine)
'done
repl.rkt> (get-register-contents fib-machine 'val)
5
repl.rkt> (set-register-contents! fib-machine 'n 6)
'done
repl.rkt> (start fib-machine)
'done
repl.rkt> (get-register-contents fib-machine 'val)
8
repl.rkt>