6.001 Recitation – April 30, 2003

RI: Konrad Tollmar

• Subroutines / Stacks

• Recursion

label-name

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

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

(assign <register-name> (op <operation-name>) <input1> <input2>)

(perform (op <operation-name>) <input1> <input2>...)

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

(branch (label <label-name>))

(goto (label <label-name>))

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

(goto (reg <register-name>))

(save <register-name>)

(restore <register-name>)

1. 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

2. Use a stack

Write a subroutine F(x) and use that to implement a register machine that compute F(a)/F(b).

Hint: instead of multiply the code in the first exercise use of a subroutine and save the needed data in a stack.

; Contract: input in x, output in y,

; writes t

f-of-x

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

(goto (reg continue))

3. A recursive register machine

Write the register machine corresponding to the recursive procedure to compute B^N:

4. A recursive register machine

Write the register machine corresponding to the recursive procedure to compute Sx

(define (add-from-one-to-recursive x)

(if (= x 1)

1

(+ (add-from-one-to-recursive (- x 1)) x)))

5. Iterative Sum…

Write the register machine corresponding to the iterative procedure to compute Sx

(define (add-from-one-to-iterative x)

(define (helper x ans)

(if (= x 1)

ans

(helper (- x 1) (+ x ans))))

(helper x 1))

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