SICP 9a
Register Machines

Table of Contents

Copyright notice: the two diagrams on this page are sourced from Unofficial Texinfo Format, licensed under the Creative Commons Attribution-ShareAlike 4.0 International License.

1 Agenda

So far, we have covered how to organise big programs. Now, we will see how those mechanisms work; we shall take simple LISP programs, and build the corresponding machines. The next lecture will show how an evaluator can be turned into hardware.

2 Euclid's algorithm

Let's see how the following iterative algorithm can be expressed as a machine. 

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

Every single-processor computer comprises of two major parts: data paths and a controller.

2.1 Data paths

Registers store numbers.

Sorry, your browser does not support SVG.

2.2 Controller

Every machine has a state. The machine state is the state of the controller.

Sorry, your browser does not support SVG.

2.3 In writing

Diagrams take up a lot of space (and can take a long time to draw on a computer!), so we will describe the machine in a language. 

(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))

2.4 Reading

Computers also require input from the outside occasionally. read implements this functionality. 

(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)))

2.5 Remainder

We have assumed remainder is a basic operation, but it is actually a whole machine in of itself. 

(define (remainder n d)
  (if (< n d)
      n
      (remainder (- n d) d)))

In a practical computer, the proper way to implement remainder would be using binary notation and shift.

3 Factorial

So far we have seen how an iterative process can be turned into a machine. How about a recursive process? 

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

With recursive processes, we have the problem that the machine contains itself inside of it, leading to a potentially infinitely large machine. We have to create the illusion of infinity somewhere in the machine.

Organisation of Register Machine 

stack <—> data paths <—> finite-state controller

  • Controller: finite and very simple.
  • Data paths: registers and operators.
  • Stack: not infinite, just very large (memory).

To create the illusion of infinity, we store the information in the stack required after the inner machine runs to resume the operation of the outer machine. Since they're nested in a recursive manner, the stack will only be accessed in a last-in first-out (LIFO) manner. So only a small part of the stack memory needs to be accessible.

Controller 

     (assign continue done)
loop (branch (= (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

4 Fibonacci

Let's see how the stack holds up with a doubly recursive algorithm. 

(define (fib n)
  (if (< n 2)
      n
      (+ (fib (- n 1))
         (fib (- n 2)))))

Controller 

    (assign continue f-bdone)
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 needed, since no call before save
    (assign n (- (fetch n) 2))
    (save continue) ; since continue not used, can also be removed
    (assign continue after-fib-n-2)
    (save val)
    (goto fib-loop)
after-fib-n-2
    (assign n (fetch val))  ; fib(n-2)
    (restore val)
    (assign val
            (+ (fetch val) (fetch n)))
    (goto (fetch continue))
immediate-ans
    (assign val (fetch n))
    (goto (fetch continue))
fib-done

When using the stack, use discipline. Only save things which are needed later.

Note: there's a fantastic cough at 57:17.

Christian Christiansen