DOC PREVIEW
UW CSE 341 - Delayed Evaluation, Memoization, Thunks, Streams

This preview shows page 1-2 out of 7 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

'&$%CSE 341:Programming LanguagesWinter 2006Lecture 14— Delayed Evaluation, Memoization, Thunks, StreamsCSE341 Winter 2006, Lecture 14 1'&$%Today• Delaying evaluation: Function bodies evaluated only at application• Key idioms of delaying evaluation– Conditionals– Streams– Laziness– Memoization• In general, evaluation rules defined by language semantics– Some languages have “lazy” function application!CSE341 Winter 2006, Lecture 14 2'&$%Delayed EvaluationFor each language construct, there are rules governing whensubexpressions get evaluated. In ML, Scheme, and Java:• function arguments are “eager” (call-by-value)• conditional branches are notWe could define a language in which function arguments were notevaluated before call, but instead at each use of argument in body.(call-by-name)• Sometimes faster: (lambda (x) 3)• Sometimes slower: (lambda (x) (+ x x))• Equivalent if function argument has no effects/non-terminationCSE341 Winter 2006, Lecture 14 3'&$%ThunksA “thunk” is just a function taking no arguments, which works greatfor delaying evaluation.• Instead of passing a value directly, pass a thunk (function) whichyields the value when it is calledIf thunks are lightweight enough syntactically, w hy not make if eager?(Smalltalk does this!)CSE341 Winter 2006, Lecture 14 4'&$%Streams• A stream is an “infinite” list — you can ask for the rest of it asmany times as you like and youll never get null.• The universe is finite, so a stream must really be an object thatacts like an infinite list.• The idea: use a function to desc ribe what comes next.Note: Deep connec tion to se quential feedback circuitsNote: Connection to UNIX pipesCSE341 Winter 2006, Lecture 14 5'&$%Best of both worlds?The “lazy” (call-by-need) rule: Evaluate the argument the first tim eit’s used. Save answer for subsequent uses.• Asymptotically it’s the best• But behind-the-scenes bookkeeping can be costly• And it’s hard to reason about with effects– Typically used in (sub)languages without effects• Nonetheless, a key idiom with syntactic support in Scheme– And related to memoizationCSE341 Winter 2006, Lecture 14 6'&$%MemoizationA “cache” of previous results is equivalent if results cannot change.• Could be slower: cache too big or computation too cheap• Could be faster: just a lookup– On homework: An example where it’s a lot faster bypreventing an exponential explosion.An association list is not the fastest data structure for large memotables, but works fine for 341.Question: W hy does assoc return the pair?CSE341 Winter 2006, Lecture 14


View Full Document

UW CSE 341 - Delayed Evaluation, Memoization, Thunks, Streams

Documents in this Course
Macros

Macros

6 pages

Macros

Macros

6 pages

Macros

Macros

3 pages

Mutation

Mutation

10 pages

Macros

Macros

17 pages

Racket

Racket

25 pages

Scheme

Scheme

9 pages

Macros

Macros

6 pages

Load more
Download Delayed Evaluation, Memoization, Thunks, Streams
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Delayed Evaluation, Memoization, Thunks, Streams and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Delayed Evaluation, Memoization, Thunks, Streams 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?