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 #f       
      (+ 3 2)
      (* 3 2))

     * what's the value in the continue register when #f is evaluated?  
          ev-if-decide
     * what's the value in the continue register when * is evaluated?
          ev-appl-did-operator

  (+ (* x x) (- 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)
          1                     
          (* n (fact (- n 1))))))
  (fact 2)  

     * what's the value in the continue register when the if consequent 
          1 is evaluated?   ev-appl-accum-last-arg
     * what's the value in the continue register when 2 is evaluated?
          ev-appl-accum-last-arg

  (define ifact
    (lambda (n product)
      (if (= n 1)
	  product           
	  (ifact (- n 1) (* n product)))))
  (ifact 2 1)       

     * what's the value in the continue register when the if consequent
          product is evaluated?   halt
     * what's the value in the continue register when 1 is 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))

-------------------------------------------------------------------------------