Slide 1TodaySet!ExampleTop-levelBut wait…No such madnessThe truth about conscons cells are immutablemcons cells are mutableDelayed evaluationThunks delayAvoiding expensive computationsBest of both worldsDelay and forceUsing promisesStreamsUsing streamsExample using streamsMaking streamsMemoizationHow to do memoization: see exampleCSE341: Programming LanguagesLecture 15Mutation, Pairs, Thunks, Laziness, Streams, MemoizationDan GrossmanFall 2011TodayPrimary focus: Powerful programming idioms related to:–Delaying evaluation (using functions)–Remembering previous results (using mutation)Lazy evaluation, Streams, MemoizationBut first need to discuss:–Mutation in Racket–The truth about cons cells (they’re just pairs)–mcons cells (mutable pairs)Fall 2011 2CSE341: Programming LanguagesSet!•Unlike ML, Racket really has assignment statements–But used only-when-really-appropriate!•For the x in the current environment, subsequent lookups of x get the result of evaluating expression e–Any code using this x will be affected–Like Java’s x = e•Once you have side-effects, sequences are useful:Fall 2011 3CSE341: Programming Languages(set! x e)(begin e1 e2 … en)ExampleExample uses set! at top-level; mutating local variables is similarNot much new here:–Environment for closure determined when function is defined, but body is evaluated when function is called–Once an expression produces a value, it is irrelevant how the value was producedFall 2011 4CSE341: Programming Languages(define b 3) (define f (lambda (x) (* 1 (+ x b)))) (define c (+ b 4)) ; 7(set! b 5)(define z (f 4)) ; 9(define w c) ; 7Top-level•Mutating top-level definitions is particularly problematic–What if any code could do set! on anything?–How could we defend against this?•A general principle: If something you need not to change might change, make a local copy of it. Example: Could use a different name for local copy but do not need toFall 2011 5CSE341: Programming Languages(define b 3) (define f (let ([b b]) (lambda (x) (* 1 (+ x b)))))But wait…•Simple elegant language design:–Primitives like + and * are just predefined variables bound to functions–But maybe that means they are mutable–Example continued:–Even that won’t work if f uses other functions that use things that might get mutated – all functions would need to copy everything mutable they usedFall 2011 6CSE341: Programming Languages(define f (let ([b b] [+ +] [* +]) (lambda (x) (* 1 (+ x b)))))No such madnessIn Racket, you do not have to program like this–Each file is a module–If a module does not use set! on a top-level variable, then Racket makes it constant and forbids set! outside the module–Primitives like +, *, and cons are in a module that does not mutate themIn Scheme, you really could do (set! + cons)–Naturally, nobody defended against this in practice so it would just break the programShowed you this for the concept of copying to defend against mutationFall 2011 7CSE341: Programming LanguagesThe truth about conscons just makes a pair–By convention and standard library, lists are nested pairs that eventually end with nullPassing an improper list to functions like length is a run-time errorSo why allow improper lists?–Pairs are useful–Without static types, why distinguish (e1,e2) and e1::e2Fall 2011 8CSE341: Programming Languages(define pr (cons 1 (cons #t "hi"))) ; '(1 #t . "hi")(define hi (cdr (cdr pr)))(define no (list? pr))(define yes (pair? pr))(define lst (cons 1 (cons #t (cons "hi" null))))(define hi2 (car (cdr (cdr pr))))cons cells are immutableWhat if you wanted to mutate the contents of a cons cell?–In Racket you can’t (major change from Scheme)–This is good•List-aliasing irrelevant•Implementation can make a fast list? since listness is determined when cons cell is createdThis does not mutate the contents:–Like Java’s x = new Cons(42,null), not x.car = 42Fall 2011 9CSE341: Programming Languages(define x (cons 14 null))(define y x)(set! x (cons 42 null))(define fourteen (car y))mcons cells are mutableSince mutable pairs are sometimes useful (will use them later in lecture), Racket provides them too:–mcons–mcar–mcdr–mpair?–set-mcar!–set-mcdr!Run-time error to use mcar on a cons cell or car on a mcons cellFall 2011 10CSE341: Programming LanguagesDelayed evaluationFor each language construct, the semantics specifies when subexpressions get evaluated. In ML, Racket, Java, C:–Function arguments are eager (call-by-value)–Conditional branches are notIt matters: calling fact-wrong never terminates:Fall 2011 11CSE341: Programming Languages(define (my-if-bad x y z) (if x y z))(define (fact-wrong n) (my-if-bad (= n 0) 1 (* n (fact-wrong (- n 1)))))Thunks delayWe know how to delay evaluation: put expression in a function!–Thanks to closures, can use all the same variables laterA zero-argument function used to delay evaluation is called a thunk–As a verb: thunk the expressionThis works (though silly to wrap if like this):Fall 2011 12CSE341: Programming Languages(define (my-if x y z) (if x (y) (z)))(define (fact n) (my-if (= n 0) (lambda() 1) (lambda() (* n (fact (- n 1))))))Avoiding expensive computationsThunks let you skip expensive computations if they aren’t neededGreat if take the true-branch:But a net-loss if you end up using the thunk more than once:In general, might now how many (more) times result is neededFall 2011 13CSE341: Programming Languages(define (f th) (if (…) 0 (… (th) …)))(define (f th) (… (if (…) 0 (… (th) …)) (if (…) 0 (… (th) …)) … (if (…) 0 (… (th) …))))Best of both worldsAssuming our expensive computation has no side effects, ideally we would:–Not compute it until needed–Remember the answer so future uses complete immediatelyCalled lazy evaluationLanguages where most constructs, including function calls, work this way are lazy languages–HaskellRacket predefines support for promises, but we can make our own–Thunks and mutable pairs are enoughFall 2011 14CSE341: Programming LanguagesDelay and forceFall 2011 15CSE341: Programming Languages(define (my-delay th) (mcons #f th))(define (my-force p)(if (mcar p) (mcdr p) (begin (set-mcar! p #t) (set-mcdr! p ((mcdr p))) (mcdr p))))An ADT represented by a mutable pair•#f in car means cdr is unevaluated thunk•Ideally hide representation in a moduleUsing promisesFall
View Full Document
Unlocking...