6.001 Recitation – May 05, 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)

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

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

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

B/ Tune this solution so it handles tail-recursion

C/ Could you find any further optimization?

2. Walk through EC-Eval

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

(inc 3)

Label Exp Env Val Proc Argl Unev Cont Stack

http://mitpress.mit.edu/sicp/code/

;;SECTION 5.4.1

eval-dispatch

(test (op self-evaluating?) (reg exp))

(branch (label ev-self-eval))

(test (op variable?) (reg exp))

(branch (label ev-variable))

(test (op quoted?) (reg exp))

(branch (label ev-quoted))

(test (op assignment?) (reg exp))

(branch (label ev-assignment))

(test (op definition?) (reg exp))

(branch (label ev-definition))

(test (op if?) (reg exp))

(branch (label ev-if))

(test (op lambda?) (reg exp))

(branch (label ev-lambda))

(test (op begin?) (reg exp))

(branch (label ev-begin))

(test (op application?) (reg exp))

(branch (label ev-application))

(goto (label unknown-expression-type))

ev-self-eval

(assign val (reg exp))

(goto (reg continue))

ev-variable

(assign val (op lookup-variable-value) (reg exp) (reg env))

(goto (reg continue))

ev-quoted

(assign val (op text-of-quotation) (reg exp))

(goto (reg continue))

ev-lambda

(assign unev (op lambda-parameters) (reg exp))

(assign exp (op lambda-body) (reg exp))

(assign val (op make-procedure)

(reg unev) (reg exp) (reg env))

(goto (reg continue))

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

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)

ev-appl-operand-loop

(save argl)

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

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

(branch (label ev-appl-last-arg))

(save env)

(save unev)

(assign continue (label ev-appl-accumulate-arg))

(goto (label eval-dispatch))

ev-appl-accumulate-arg

(restore unev)

(restore env)

(restore argl)

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

(assign unev (op rest-operands) (reg unev))

(goto (label ev-appl-operand-loop))

ev-appl-last-arg

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

(goto (label eval-dispatch))

ev-appl-accum-last-arg

(restore argl)

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

(restore proc)

(goto (label apply-dispatch))

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

primitive-apply

(assign val (op apply-primitive-procedure)

(reg proc)

(reg argl))

(restore continue)

(goto (reg continue))

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

;;;SECTION 5.4.2

ev-begin

(assign unev (op begin-actions) (reg exp))

(save continue)

(goto (label ev-sequence))

ev-sequence

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

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

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

(save unev)

(save env)

(assign continue (label ev-sequence-continue))

(goto (label eval-dispatch))

ev-sequence-continue

(restore env)

(restore unev)

(assign unev (op rest-exps) (reg unev))

(goto (label ev-sequence))

ev-sequence-last-exp

(restore continue)

(goto (label eval-dispatch))

;;;SECTION 5.4.3

ev-if

(save exp)

(save env)

(save continue)

(assign continue (label ev-if-decide))

(assign exp (op if-predicate) (reg exp))

(goto (label eval-dispatch))

ev-if-decide

(restore continue)

(restore env)

(restore exp)

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

(branch (label ev-if-consequent))

ev-if-alternative

(assign exp (op if-alternative) (reg exp))

(goto (label eval-dispatch))

ev-if-consequent

(assign exp (op if-consequent) (reg exp))

(goto (label eval-dispatch))

ev-assignment

(assign unev (op assignment-variable) (reg exp))

(save unev)

(assign exp (op assignment-value) (reg exp))

(save env)

(save continue)

(assign continue (label ev-assignment-1))

(goto (label eval-dispatch))

ev-assignment-1

(restore continue)

(restore env)

(restore unev)

(perform

(op set-variable-value!) (reg unev) (reg val) (reg env))

(assign val (const ok))

(goto (reg continue))

ev-definition

(assign unev (op definition-variable) (reg exp))

(save unev)

(assign exp (op definition-value) (reg exp))

(save env)

(save continue)

(assign continue (label ev-definition-1))

(goto (label eval-dispatch))

ev-definition-1

(restore continue)

(restore env)

(restore unev)

(perform

(op define-variable!) (reg unev) (reg val) (reg env))

(assign val (const ok))

(goto (reg continue))

)))