6.001 Recitation – May 05, 2003

6.001 Recitation – May 02, 2003

RI: Konrad Tollmar

• RRM

• Explicit control evaluator

1. A recursive register machine

Write the register machine for

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

(if (= x 1)

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

(assign continue (label finish))

rec

;; test and branch for base case

;; recursively call loop with x=x-1

after-rec

;; compute x+ans

goto (reg continue)) ;; return

base-case

;; set answer

(goto (reg continue)) ;; return

finish

(assign continue (label finish))

loop

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

(branch (label base-case))

(save continue)

(save x)

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

(assign continue (label after-loop))

(goto (label loop))

after-loop

(restore x)

(restore continue)

(assign ans (op +) (reg x) (reg ans))

(goto (reg continue))

base-case

(assign ans (const 0))

(goto (reg continue))

finish

2. Iterative Sum…

Write the register machine corresponding to this iterative procedure to compute S x :

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

(define (helper x ans)

(if (= x 1)

ans

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

(helper x 1))

Unoptimized version

...

(assign continue (label finish))

(assign ans (const 0))

loop

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

(branch (label base-case))

(save continue)

(save x)

(assign ans (op +) (reg x) (reg ans))

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

(assign continue (label after-loop))

(goto (label loop))

after-loop

(restore x)

(restore continue)

(goto (reg continue))

base-case

(goto (reg continue))

finish

Optimized version

(assign ans (const 0))

loop

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

(branch (label done-loop))

(assign ans (op +) (reg x) (reg ans))

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

(goto (label loop))

done-loop

2. Extend the Explicit Control Evaluator

Add And to the Explicit Control Evaluator.

A/ Covert this psedo-code to machine-code:

1. ev-and

2. store in unev and exp the conjunts

3. save needed data on stack

4. evaluate the first-conjunct

5. eval-after-first

6. restore needed data

7. test the first- conjunct

8. break if false

9. evaluate the second-conjunct

10. eval-after-second

11. break procedure

Assume that we have:

(op second-conjunct)

(op first-conjunct)

ev-and

(assign unev (op second-conjunct) (reg exp) )

(assign exp (op first-conjunct) (reg exp) )

(save continue)

(save env)

(save unev)

(assign continue eval-after-first)

(goto (label eval-dispatch) )

eval-after-first

(restore unev )

(restore env )

(restore continue )

(test (op true?) (reg val))

(branch (label eval-second-arg))

(assign val #f)

(goto (reg continue))

eval-second-arg

(save continue)

(assign exp (reg unev) )

(assign continue after-second)

(goto (label eval-dispatch) )

eval-after-second

(restore continue)

(goto (reg continue))

B/ Tune this solution so it handles tail-recursion

ev-and

(assign unev (op second-conjunct) (reg exp) )

(assign exp (op first-conjunct) (reg exp) )

(save continue)

(save env)

(save unev)

(assign continue eval-after-first)

(goto (label eval-dispatch) )

eval-after-first

(restore unev )

(restore env )

(test (op true?) (reg val))

(branch (label eval-second-arg))

(assign val #f)

(restore continue )

(goto (reg continue))

eval-second-arg

(restore continue)

(assign exp (reg unev) )

(goto (label eval-dispatch))

C/ Could you find any further optimization?

4. Walk through EC-Eval

(define (inc x) (+ x 1))

(inc 3)

Label Exp Env Val Proc Argl Unev Cont Stack

Eval (inc 3) GE REP

Eval inc GE (3) didop REP GE (3)

ev-application

(save continue)

(save env)

(assign unev (op operands) (reg exp))

(save unev)

(assign exp (op operator) (reg exp))

(assign continue (label ev-appl-did-operator))

(goto (label eval-dispatch))

Didop inc GE [proc] (3) didop REP GE (3)

ev-appl-did-operator

(restore unev)

(restore env)

(assign argl (op empty-arglist))

(assign proc (reg val))

(test (op no-operands?) (reg unev))

(branch (label apply-dispatch))

(save proc)

Oploop inc GE [proc] [proc] () (3) didop REP [proc]

ev-appl-operand-loop

(save argl)

(assign exp (op first-operand) (reg unev))

(test (op last-operand?) (reg unev))

Lastarg 3 GE [proc] [proc] () (3) didop REP [proc] ()

ev-appl-last-arg

(assign continue (label ev-appl-accum-last-arg))

(goto (label eval-dispatch))

Eval 3 GE [proc] [proc] () (3) a-l-a REP [proc] ()

Val <- 3

A-l-a 3 GE 3 [proc] () (3) a-l-a REP [proc] ()

ev-appl-accum-last-arg

(restore argl)

(assign argl (op adjoin-arg) (reg val) (reg argl))

(restore proc)

(goto (label apply-dispatch))

Capply 3 GE 3 [proc] (3) (3) a-l-a REP

apply-dispatch

(test (op primitive-procedure?) (reg proc))

(branch (label primitive-apply))

(test (op compound-procedure?) (reg proc))

(branch (label compound-apply))

(goto (label unknown-procedure-type))

compound-apply

(assign unev (op procedure-parameters) (reg proc))

(assign env (op procedure-environment) (reg proc))

(assign env (op extend-environment)

(reg unev) (reg argl) (reg env))

(assign unev (op procedure-body) (reg proc))

(goto (label ev-sequence))

Seq 3 E1 3 [proc] (3) ((+..)) a-l-a REP

ev-sequence

(assign exp (op first-exp) (reg unev))

(test (op last-exp?) (reg unev))

(branch (label ev-sequence-last-exp))

Seqlst (+ ..) E1 3 [proc] (3) ((+..)) a-l-a REP

ev-sequence-last-exp

(restore continue)

(goto (label eval-dispatch))

Eval (+ ..) E1 3 [proc] (3) ((+..)) REP

… and again ev-application, save continue

Papply .. E1 4 [+] (3 1) .. REP

primitive-apply

(assign val (op apply-primitive-procedure)

(reg proc)

(reg argl))

(restore continue)

(goto (reg continue))