6.001 Recitation – April 25, 2003

RI: Konrad Tollmar

• Register machines:

- Datapaths

- Sequencer

- Instruction code

Register Machine Code Language

register (reg name)

const (const val)

assign (assign reg (const val)) / (assign reg (op x) (reg y) (reg z))

op (op x) x: {+ - * / > < = null? car cdr cons }

goto (goto (label name))

test (test (op x)

branch (branch (label name)

label name

1. A register machine for sqrt

Recall scheme code for sqrt() via Newton’s method:

(define (sqrt x)

(sqrt-iter 2.0 x))

(define (sqrt-iter guess x)

(if (good-enough? guess x)

guess

(sqrt-iter (improve guess x) x)))

A/ Draw datapaths and a control diagram (sequencer flowchart) that implement Newton’s method

for solving square roots. (you can now assume good-enough, improve and average are primitive boxes / ops)

B/ Implement the datapaths and a control diagram in register machine code.

C/ Implement the complete datapath as:

(define (good-enough? guess x)

(< (abs (- (square guess) x)) 0.00001))

(define (improve guess x)

(average guess (/ x guess)))

(define (average x y)

(/ (+ x y) 2.0))

2. A register machine for f(x)

What does the following register machine compute?

(controller

(assign y (const 5))

(assign t (op *) (reg x) (const 7))

(assign y (op +) (reg t) (reg y))

(assign t (op *) (reg x) (reg x))

(assign t (op *) (reg t) (const 3))

(assign y (op +) (reg t) (reg y))

)

Implement the register machine code that compute S f(x) for k = 1 .. N

3. Some more register machines

Implement for each procedure a register machine.

(you can assume the ops: > * - = null? car cdr cons).

greater - input in a,b; result in val

abs - input in a; result in val

factorial - input in n; result in prod

length - input in lst; result in count

reverse - input in lst; result in result

4. The register machine simulator

;; SICP section 5.2, page 513

(load "regsim.scm")

(define gcd-machine

(make-machine '(a b t)

(list (list 'rem remainder) (list '= =))

'(test-b (test (op =) (reg b) (const 0))

(branch (label gcd-done))

(assign t (op rem) (reg a) (reg b))

(assign a (reg b)) (assign b (reg t))

(goto (label test-b)) gcd-done)))

(set-register-contents! gcd-machine 'a 206)

(set-register-contents! gcd-machine 'b 40)

(start gcd-machine)

(get-register-contents gcd-machine 'a)