CSE 341, Spring 2008, Lecture 14 SummaryStandard 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 c an use set! to change what value anything in the environment has.Consider a more realistic example w ith 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 bo dy 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 addition), then pow will go into aninfinite loop.Though 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.1Delayed Evaluation:A key semantic issue for a language construct is when are its subexpressions evaluated. For e xample,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 whe rever 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 c ertainly 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 3 programming idioms; thunks are crucial in two of them and the third issimilar.Lazy Evaluation:Supp ose 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,” wecan use a programming idiom known by a few different (and perhaps technically slightly different) names(lazy-evaluation, call-by-need, promises). The idea is to use mutation (really) to remember the result fromfirst time we use the thunk so that we do not need to use the thunk again.One simple implementation in Scheme would be:(define (my-delay f)(cons #f f))(define (my-force th)(if (car th)(cdr th)(begin (set-car! th #t)(set-cdr! th ((cdr th)))(cdr th))))We can create a thunk f and pass it to my-delay. This returns a pair w here the first field indicates wehave not used the thunk yet. Then my-force, if it sees the thunk has not been used yet, uses it and then usesmutation to change the pair to hold the result of using the thunk. That way, any future calls to my-forcewith the same pair will not repeate the computation.Consider this silly example where want to multiply the result of two expressions e1 and e2 using arecursive algorithm (of course you would really just use * and this algorithm does not work if e1 producesa negative number):2(define (my-mult x y)(cond [(= x 0) 0][(= x 1) y][#t (+ y (my-mult (- x 1) y))]))Now calling (my-mult e1 e2) evaluates e1 and e2 once each and then does 0 or more additions. But whatif e1 evaluates to 0 and e2 takes a long to compute? Then evaluating e2 was wasteful. So we could thunkit:(define
View Full Document
Unlocking...