6.001 Recitation – April 25, 2003

RI: Konrad Tollmar

• Register machines:

- Datapaths

- Sequencer

- Instruction code

(Slides 20020501b – 20020503)

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

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

for solving square roots.

(you can assume good-enough and improve are primitive boxes / ops)

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

(controller

(assign g (const 1))

loop

(test (op good-enough?) (reg g) (reg x))

(branch (label done))

(assign t (op /) (reg g) (reg x))

(assign g (op average) (reg t) (reg g))

(goto (label loop))

)

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

)

F(x) = 3x² + 7x + 5

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

(controller

(assign sum (const 0))

loop

(test (op =) (reg k) (const 0))

(branch (label done))

(assign x (reg k))

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

(assign k (op -) (reg k) (const 1))

(assign sum (op +) (reg sum) (reg y))

(goto (label loop))

)

3. Some more register machines

1.label-name

2.(assign <register-name> (reg <register-name>))

3.(assign <register-name> (const <constant-value>))

4.(assign <register-name> (op <operation-name>)
<input-1> ... <input-n>)

5.(test (op <operation-name>) <input1> <input2>...)

6.(branch (label <label-name>))

7.(goto (label <label-name>))

8.(perform (op <operation-name>) <input1> ... <input-n>)

9.(assign <register-name> (label <label-name>))

10.(goto (reg <register-name>))

11.(save <register-name>)

12.(restore <register-name>)

Implement for each procedure a register machine.

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

greater - input in a,b; result in val

(controller

(test (op >) (reg a) (reg b))

(branch (label l1))

(assign val (reg b))

(goto (label l2))

l1

(assign val (reg a))

l2)

abs - input in a; result in val

(controller

(test (op >) (reg a) (const 0))

(branch (label l1))

(assign val (op *) (reg a) (const -1))

(goto (label l2))

l1

(assign val (reg a))

l2)

factorial - input in n; result in prod

(controller

(assign prod (const 1))

loop

(test (op =) (reg n) (const 1))

(branch (label done))

(assign prod (op *) (reg n) (reg prod))

(assign n (op -) (reg n) (const 1))

(goto (label loop))

done)

length - input in lst; result in count

(controller

(assign count (const 0))

loop

(test (op null?) (reg lst))

(branch (label done))

(assign count (op +) (reg count) (const 1))

(assign lst (op cdr) (reg lst))

(goto (label loop))

done)

reverse - input in lst; result in result

(define (rec-reverse lst)

(if (null? lst)

nil

(append (rec-reverse (cdr lst)) (list (car lst))))

(define (itr-reverse lst)

(define (ihelp rest rev)

(if (null? rest)

rev

(ihelp (cdr rest) (cons (car rest) rev))))

(ihelp lst nil))

(controller

(assign result (const empty-list))

loop

(test (op null?) (reg lst))

(branch (label done))

(assign temp (op car) (reg lst))

(assign result (op cons) (reg temp) (reg result))

(assign lst (op cdr) (reg lst))

(goto (label loop))

done)