CS61A Notes – Week 8: EnvironmentsThe Attack of the EnvironmentalistsThe biggest blow side effects deal us is that we can no longer use the substitution model of evaluation that we’ve fallen so hopelessly in love with. Consider this:> (define (foo x) (set! x 3) x) > (foo 10)If we use the substitution model, then when we do (foo 10), we will replace all occurrences of x inside foo with 10. Note that this means (foo 10) will then return 10, not 3! Obviously, we can no longer afford to be so obtuse, as values of the variables can now change at any point in time. Thus, we need to use what is called the “environment model” of evaluation. Briefly, we keep an “environment” of bindings from variable to value, and every time we encounter a variable, we look up its value in the current environment. Note that we only lookup the value when we see the variable, and so we’ll lookup the value of x only after we’ve already set x to be 3. Drawing these environment diagrams is one of the most hated aspects of CS61A, but remember this: this is what the Scheme interpreter does, and since you’re much smarter than the interpreter, if the interpreter can do it, you can do it.An environment frame is a box that contains bindings from variables to values. An environment frame can “extend” another frame; that is, this frame can see all bindings of the frame it extends. We represent this by drawing an arrow from an environment frame to the frame it is extending. The global environment is the only environment that extends nothing. Here’s how to go about it:1. Start with a box labeled global environment. This box starts out with bindings for all the primitives like +, cons, map, etc.2. Set the current frame to be the global environment. The current frame is just the environment that you're in at the moment, and of course, you start in the global environment.3. Evaluate your expressions, one by one. I'd recommend converting all sugar-coated procedure definitions to their raw forms: (define (square x) (* x x)) => (define square (lambda (x) (* x x)))Evaluation rules:• constant (numbers, strings, etc), they are self-evaluating so don’t do any work.• variable, try to find a binding for it in the current frame. Failing that, follow what environment the current frame points to, and try to find the binding there, and so on, until you reach the global environment. If it’s still not in the global environment, then you can’t find it; it’s an error! (Recall that the global environment contains all the bindings for primitives like cons, +, etc.)• define expression, first evaluate the value to bind to according to these evaluation rules, then add an entry into the current frame for the variable pointing to that value.• lambda expression, draw two bubbles next to each other (usually just in the space around the boxes). The first bubble should point to the text of the lambda – the argument list and the body – and the second bubble should point to the current frame. The frame this circle points to is called the “procedure environment”.• let expression, convert to a lambda and invoke this lambda on its arguments (the values to bind the new variables to).• set! expression, evaluate the value to set! to. Then, for the given variable, find its closest binding from the current frame, and overwrite the old value with the new value.• any other special forms, just evaluate what you’re supposed to in the current frame.• procedure call, check if the procedure is a:o primitive procedure, these work by magic, so just apply the procedure intuitively in your head.o compound procedure, evaluate all the arguments first. Then, create a new box, and make this box point to the “procedure environment” box of the procedure. Note that you often do not point to the current frame! Set this new box as the new current frame, and add all the parameters into the box, and have them point to the argument values you evaluated. Evaluate the body of the procedure in the current frame. Once done, go back to the frame from which you made the procedure call.QUESTIONS: Draw environment diagrams for the following:IN CLASS:SU2010: # 3, 41. (define x 3)(let ((x 3) (y x))(set! X (+ y x)) x)Eric, Kevin, Phill, Hamilton, and Stephanie – CS61A Summer 2011– notes courtesy of Justin Chen12. (define (foo x)(let ((y x) (z 3))(+ y z)))(foo 3)3. (define (foo x)(let ((y x) (z 3))(let ((t (+ y z)))(+ t y z))))EXTRA PRACTICE:1. (define answer 0)(define (square f x) (let ((answer 0)) (f x) answer))(square (lambda (n) (set! answer (* n n))) 3)2. (define (hmm n) (lambda (x) (+ x y n)))(define (uhh y) (define hmm-y (hmm y)) (hmm-y 2))(uhh 42)Eric, Kevin, Phill, Hamilton, and Stephanie – CS61A Summer 2011– notes courtesy of Justin Chen23. (define a 3)((lambda (a) ((lambda (a) (a)) (lambda () (set! a ‘myxomatosis))) a) (* a a))4. (define a ‘scatterbrain)((lambda (a b) (b) a)a (let ((b ‘cuttooth)) (lambda () (set! a b))))a6. (define (f + -) (+ ((lambda (-) (- 3 5)) -) 10))(f - +)7. (define (slow-op-maker op) (let ((old-result #f)) (lambda (x) (let ((return old-result)) (set! old-result (op x)) return))))(define slow-sqr (slow-op-maker square))(slow-sqr 3)(slow-sqr 5)(define slow-cube (slow-op-maker cube))(slow-cube 3)(slow-cube 5)Eric, Kevin, Phill, Hamilton, and Stephanie – CS61A Summer 2011– notes courtesy of Justin Chen38. (define (slow-op-maker op) (let ((old-result #f)) (lambda (op) (lambda (x) (let ((return old-result)) (set! old-result (op x)) return))))(define slow-sqr (slow-op-maker square))(slow-sqr 3)(slow-sqr 5)(define slow-cube (slow-op-maker cube))(slow-cube 3)Imperative PerilsFor those of you used to programming in C or Java or almost any other languages, the idea of “assignment” – assigning a value to a symbol – should be a dusty old hat. Certainly, there’s nothing exotic about it. But why have we been so cautious about introducing this concept to you – 9 weeks into the semester! – when, if you take an introductory CS class in any other language, you would see assignment on the first day? And why do I write such long and convoluted sentences?Before that, note that we have now stepped out of pure “functional programming”, and now we have functional programming with side effects. Here, nice properties of functional programming disappear; more specifically, the order in which expressions are evaluated
View Full Document
Unlocking...