Weeks 13/14 Discussion/Lab Notes

Administrivia

• Quiz 4 next Wednesday (5-3). It may cover anything we've covered in the course so far.

Discussion Outline

• the analyzing evaluator
• separation of analysis from execution
• why did all the drawings of the MCE machine have separate inputs for program and data?
• we should only need go through that big cond once
• how does it work?
• analyze parses expressions before you run them and stores results in underlying Scheme procedures
• will we get an improvement in running time in terms of Theta?
• eval-sequence (exercise 4.23 in hw13)
• when do we see benefits of analysis?
• when we run analyzed code multiple times
• is there any benefit from:
     A-Eval> ((lambda (x) (* x x)) 5)
     A-Eval> ((lambda (x) (* x x)) 7)
• compare that to:
     A-Eval> (define (square x) (* x x))
     A-Eval> (square 5)
     A-Eval> (square 7)
• could we use memoization to improve this?
• yes, but the analyzing evaluator is mysterious enough as it is =(
• the lazy evaluator
• what's delayed?
• only arguments to compound procedures are delayed
• how?
• in mc-eval, we can delay arguments instead of evaluating them
• (textbook actually does this in mc-apply to distinguish primitive procedures from compound)
• when do we need to force arguments?
• two main cases:
• when we pass arguments to primitive procedures
• when we return a value to the user
• a couple of other cases
• eval-if
• forcing operators in mc-eval
• why do we need to force the operators in mc-eval? (exercise 4.28 from hw13)
• why do we need to store the environment with thunks?
• why memoization?
• what's memoized?
     Lazy> (define count 0)
     Lazy> (define (incr) (set! count (+ count 1)) count)
     Lazy> (incr) ==> <??>
     Lazy> (incr) ==> <??>
• lazy lists
• do we need to do anything special under-the-hood to implement them?
• the non-deterministic evaluator (the amb evaluator)
• non-determinism
• new syntax:
• amb <-- special form to amb evaluator
• (amb) <-- failure case
• try-again <-- not a procedure! only valid at the the driver-loop prompt
• require <-- ordinary procedure
• example:
• (list (amb 1 2 3) (amb 4 5))
• decision trees
• depth-first-search and backtracking
• why doesn't this work?
     (define (an-integer-starting-from n)
       (amb n (an-integer-starting-from (+ n 1)) ))
     (define (an-integer-between low high)
       (let ((n (an-integer-starting-from low) ))
         (require (<= n high))
         n))
• continuations
• know Java? think about try/catch blocks
• comparison to streams

What You're Responsible for Knowing

You should have a thorough understanding of how the basic metacircular evaluator is implemented and how it works. You should also understand what changes are necessary to make the metacircular evaluator use dynamic scope.

From Project 4, you should also know the details about how the Logo interpreter works. Make sure you understand the differences between logo-eval, eval-line, and eval-prefix.

You should have a fair understanding of how the lazy evaluator works. It's not too different from the basic MCE, and the changes are pretty straightforward.

For the rest, especially the analyzing and non-deterministic evaluators, you generally don't need to concern yourself much with the implementation details. However, you should know how to use them, and you should understand their big ideas!