CSE341 Programming Languages Lecture 15 Mutation Pairs Thunks Laziness Streams Memoization Dan Grossman Fall 2011 Today Primary focus Powerful programming idioms related to Delaying evaluation using functions Remembering previous results using mutation Lazy evaluation Streams Memoization But first need to discuss Mutation in Racket The truth about cons cells they re just pairs mcons cells mutable pairs Fall 2011 CSE341 Programming Languages 2 Set Unlike ML Racket really has assignment statements But used only when really appropriate set x e 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 begin e1 e2 en Fall 2011 CSE341 Programming Languages 3 Example Example uses set at top level mutating local variables is similar define define define set b define define b 3 f lambda x 1 x b c b 4 7 5 z f 4 9 w c 7 Not 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 produced Fall 2011 CSE341 Programming Languages 4 Top 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 define b 3 define f let b b lambda x 1 x b Could use a different name for local copy but do not need to Fall 2011 CSE341 Programming Languages 5 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 define f let b b lambda x 1 x b 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 used Fall 2011 CSE341 Programming Languages 6 No such madness In 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 them In Scheme you really could do set cons Naturally nobody defended against this in practice so it would just break the program Showed you this for the concept of copying to defend against mutation Fall 2011 CSE341 Programming Languages 7 The truth about cons cons just makes a pair By convention and standard library lists are nested pairs that eventually end with null define define define define define define pr cons 1 cons t hi 1 t hi hi cdr cdr pr no list pr yes pair pr lst cons 1 cons t cons hi null hi2 car cdr cdr pr Passing an improper list to functions like length is a run time error So why allow improper lists Pairs are useful Without static types why distinguish e1 e2 and e1 e2 Fall 2011 CSE341 Programming Languages 8 cons cells are immutable What 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 created This does not mutate the contents define define set x define x cons 14 null y x cons 42 null fourteen car y Like Java s x new Cons 42 null not x car 42 Fall 2011 CSE341 Programming Languages 9 mcons cells are mutable Since 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 cell Fall 2011 CSE341 Programming Languages 10 Delayed evaluation For 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 not It matters calling fact wrong never terminates 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 Fall 2011 CSE341 Programming Languages 11 Thunks delay We know how to delay evaluation put expression in a function Thanks to closures can use all the same variables later A zero argument function used to delay evaluation is called a thunk As a verb thunk the expression This works though silly to wrap if like this define my if x y z if x y z define fact n my if n 0 lambda 1 lambda n fact n 1 Fall 2011 CSE341 Programming Languages 12 Avoiding expensive computations Thunks let you skip expensive computations if they aren t needed Great if take the true branch define f th if 0 th But a net loss if you end up using the thunk more than once define f th if 0 th if 0 th if 0 th In general might now how many more times result is needed Fall 2011 CSE341 Programming Languages 13 Best of both worlds Assuming our expensive computation has no side effects ideally we would Not compute it until needed Remember the answer so future uses complete immediately Called lazy evaluation Languages where most constructs including function calls work this way are lazy languages Haskell Racket predefines support for promises but we can make our own Thunks and mutable pairs are enough Fall 2011 CSE341 Programming Languages 14 Delay and force 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 module Fall 2011 CSE341 Programming Languages 15 Using promises define f p if 0 my force p if 0 my force p if 0 my force p f my delay lambda e Fall 2011 CSE341 Programming Languages 16 Streams A stream is an infinite sequence of values So can t make a stream by making all the values Key idea Use a thunk to delay creating most of the sequence Just a programming idiom A powerful concept for division of labor Stream producer knows how create any number of values Stream consumer decides how many values to ask for Some examples of streams you might not be familiar with User actions mouse clicks etc UNIX pipes cmd1 cmd2 has cmd2 pull data from cmd1 Output values from a sequential feedback circuit Fall 2011 CSE341 Programming Languages 17 Using streams Coding up a stream in your program is easy We will do functional streams using pairs and thunks Let a stream be a thunk that when called returns a pair next answer next thunk So given a stream st the client can get any number …
View Full Document
Unlocking...