recitation 26: eval as a register machine (explicit control evaluator) ------------------------------------------------------------------------------- big picture -- this semester we've learned how to: * program a specific task in a high-level language (scheme) * implement an evaluator for arbitrary expressions in scheme * program a specific task in a low-level register machine code * implement an evaluator for arbitrary expressions in register machine code pieces missing? * how do we actually implement the register machine with circuits? [6.004] * how do we implement cons cells (& other data structures) [tuesday] * aren't we cheating by using complex ops? (self-evaluating?, definition?, make-procedure, lookup-variable-value, extend-environment, set-variable-value!, etc.) ------------------------------------------------------------------------------- * in general, a call to eval-dispatch should look like this: <save registers whose values are needed later> (assign exp <expression to evaluate>) (assign env <environment in which to evaluate expression>) (assign continue <label>) (goto eval-dispatch) <label> <restore any saved registers> <use the expression value stored in val> but often exp, env &/or continue already have the proper value. * eval-sequence and apply use a different convention/contract for storing the return point (continue). this is just a performance optimization to minimize use of the stack (tail recursion). ------------------------------------------------------------------------------- assume the scheme expressions below are evaluated in sequence by eval-dispatch. determine what label is in the continue register when eval-dispatch is called to evaluate the subexpressions. assume that the continue register contains the label "halt" when each top-level expression is evaluated. (if(+ 3 2) (#f3 2)) * what's the value in the continue register when*is evaluated? ev-if-decide * what's the value in the continue register when#fis evaluated? ev-appl-did-operator (+*(- 2)) * what's the value in the continue register when(* x x)is evaluated? ev-appl-accumulate-arg (define fact (lambda (n) (if (= n 1)(* x x)(* n (fact (- n 1)))))) (fact1) * what's the value in the continue register when the if consequent2is evaluated? ev-appl-accum-last-arg * what's the value in the continue register when1is evaluated? ev-appl-accum-last-arg (define ifact (lambda (n product) (if (= n 1)2(ifact (- n 1) (* n product))))) (ifact 2product) * what's the value in the continue register when the if consequent1is evaluated? halt * what's the value in the continue register whenproductis evaluated? ev-appl-accum-last-arg ------------------------------------------------------------------------------- let's add the special form and to the explicit control evaluator. for simplicity, we'll only worry about ANDs of two sub-expressions. assume that we have primitive ops and-first-exp and and-second-exp. first we add a clause to eval-dispatch: eval-dispatch ... (test (op and?) (reg exp)) (branch (label ev-and)) ... * fill in the blanks below: ev-and 1 (assign unev (op and-second-exp) (reg exp)) 2 (assign exp (op and-first-exp) (reg exp)) 3 (save continue) 4 (save env) 5 (save unev) 6 (assign continue eval-after-first) 7 (goto (label eval-dispatch)) eval-after-first 8 (restore unev) 9 (restore env) 10 (test (op true?) (reg val)) 11 (branch (label eval-second-arg)) 12 (assign val #f) 13 (restore continue) 14 (goto (reg continue)) eval-second-arg 15 (assign exp (reg unev)) 16 (assign continue after-second) 17 (goto (label eval-dispatch)) after-second 18 (restore continue) 19 (goto (reg continue)) * hand evaluate the expression (and #t (and #f #t)) * does this ev-and routine handle tail recursion? compare the behavior of regular scheme and our explicit control evaluator when evaluating the expressions below. (define (list? x) (or (null? x) (and (pair? x) (list? (cdr x))))) (define z (list 1)) (set-cdr! z z) (list? z) * how could we change the code above so that it handles tail-recursion? hint: remove lines 16 through 19 and add two lines in their place. new 16: (restore continue) new 17: (goto (label eval-dispatch)) * can we get rid of the new line 16 by moving another line somewhere? yes, move 13 after 9 * could we remove line 12 without changing the value returned by the code? why or why not? yes (assuming everything except #f is "true?") * how can we get rid of line 15 by changing another line? change line 8 to (restore exp) AFTER OPTIMIZATIONS: ev-and 1 (assign unev (op and-second-exp) (reg exp)) 2 (assign exp (op and-first-exp) (reg exp)) 3 (save continue) 4 (save env) 5 (save unev) 6 (assign continue eval-after-first) 7 (goto (label eval-dispatch)) eval-after-first 8 (restore exp) 9 (restore env) 10 (restore continue) 11 (test (op true?) (reg val)) 12 (branch (label eval-second-arg)) 13 (goto (reg continue)) eval-second-arg 14 (goto (label eval-dispatch)) -------------------------------------------------------------------------------1