CSE 341, Spring 2011, Lecture 14 SummaryLast update: 4/28/11 to reflect change to DrRacket from DrScheme. HPStandard Disclaimer: These comments may prove useful, but certainly are not a complete summary of allthe important stuff we did in class. They may make little sense if you missed class, but hopefully will helpyou organize and process what you have learned.Scheme top-level (again):In ML, a top-level fun binding’s environment included only itself and earlier bindings. This leads to astraightforward semantics, but it can be inconvenient (having to organize your functions in a certain order)or limiting (which is why we had different syntax for mutual recursion). In Scheme, earlier functions canrefer to later bindings, but this comes at the cost of more complicated rules, especially since Scheme allowsany binding to be mutated (with set!). You may assume what essentially all Scheme programmers do —that top-level bindings are not mutated. Nonetheless, it is worth investigating how mutation of top-leveldefinitions affects program correctness because it motivates an important programming idiom that comesup throughout computer science (particularly in operating systems and security): If data/code might changeand you need to assume it doesn’t, make a local copy.This code fails because when we evaluate the y on the first line there is no x in the environment:(define x y)(define y 1)However, this code defines f1 as a zero-argument function that returns 1 when called. That is becauseall top-level definitions are included in a function’s environment, even top-level definitions added after thefunction is defined.(define f1 (lambda () y))(define y 1)However, we cannot really say f1 always returns 1, since if there is another top-level definition of y, itwill have the effect of mutation.(define y 7) ; now (f1) evaluates to 7Similarly, any code can use set! to change what value anything in the environment has.Consider a more realistic example with a simple curried exponentiation function and a cube functionthat uses partial application:(define (pow y)(lambda (x)(if (= y 0)1(* x ((pow (- y 1)) x)))))(define cube (pow 3))For the corresponding ML code, we know any call to cube will “do the right thing”, but in Scheme thatassumes that nothing is mutated/redefined to break pow. If we later do (define pow 6) then the recursivecall in pow’s body will not be recursive at all — it will fail because pow is no longer bound to a function.If we later do (define (pow y) (lambda (x) 2)) we will produce the wrong answer. And if we later do(define - +) (after all, - is just a binding so we can redefine it to be addition1), then pow will go into aninfinite loop.1This is true in standard Schme, but not in Racket, where many items in the top-level environment are treated as “constants”that cannot be redefined. See below for a short discussion.1Though you should not bother in Scheme, the general solution to avoiding code breaking due to mutationthat is beyond your control is to make “private” copies of what must not change. For example, we coulddefine a version of pow in which there was a local environment that bound all the helper functions we needed(including =, *, and -). That will work because top-level redefinitions will not change the local environmentwe created.Delayed Evaluation:A key semantic issue for a language construct is when are its subexpressions evaluated. For example,in Scheme (and similarly in Java and ML), given (e1 e2 ... en) we evaluate the function arguments e2,..., en once before we execute the function body and given a function (lambda (...) ...) we do notevaluate the body until it is called. We can contrast this rule (“evaluate arguments in advance”) with how(if e1 e2 e3) works: we do not evaluate both e2 and e3. This is why:(define (my-if-bad x y z) (if x y z))is a function that cannot be used wherever you use an if-expression; the rules for evaluating subexpressionsare fundamentally different.However, we can use the fact that function bodies are not evaluated until the function gets called tomake a more useful version of an “if function”:(define (my-if x y z) (if x (y) (z)))Now wherever we would write (if e1 e2 e3) we could instead write (my-if e1 (lambda () e2) (lambda () e3)).The body of my-if either calls the zero-argument function bound to y or the zero-argument function boundto z.Though there is certainly no reason to wrap Scheme’s “if” in this way, the general idiom of using azero-argument function to delay evaluation (do not evaluate e2 now, do it later when/if the zero-argumentfunction is called) is very powerful. As convenient terminology/jargon, when we use a zero-argument functionto delay evaluation we call the function a thunk. You can even say, “thunk the argument” to mean “use(lambda () e) instead of e”.The rest of lecture considers three programming idioms; thunks are crucial in two of them and the thirdis similar.An aside: Scheme, immutability, and RacketAs hinted in a footnote above, Scheme and Racket have different ideas about what should be immutable.In regular Scheme anything in the global environment can be modified, including previously defined itemsas well as names like +, -, cons, and so forth. Pairs and lists created by cons, list, and related functionsare also mutable. Any pair can be altered by applying functions set-car! or set-cdr! to it.Racket takes a different approach, defining most (all?) of the symbols in the standard environmentto be constants that cannot be rebound or modified, although programmer-defined global bindings remainmutable. Pairs and lists created by the standard functions are also immutable, and set-car! and set-cdr!do not exist. Racket introduces a new data type for mutable pairs and lists, with associated functions mcons,mcar, mcdr, set-mcar!, and so forth. We will use these newer functions as needed so that our examples willwork with Racket, however they are not part of standard Scheme.Lazy Eval uation:Suppose we have a very large computation that we know how to perform but we do not know if we needto perform it. The rest of the application knows where it needs this computation and there may be a fewdifferent places. If we thunk, then we may repeat the large computation many times. But if we do not thunk,then we will perform the large computation even if we do not need to. To get the “best of both worlds,” we2can use a programming idiom known by a few different (and perhaps
View Full Document
Unlocking...