DOC PREVIEW
UW CSE 341 - Lecture Notes

This preview shows page 1-2-3 out of 8 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 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 8 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 8 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

'&$%CSE 341:Programming LanguagesDan GrossmanSpring 2004Lecture 14— Delayed Evaluation, Memoization, Thunks, StreamsDan Grossman CSE341 Spring 2004, Lecture 14 1'&$%Today• Scheme top-level: forward references and evil mutation• Delaying evaluation: Function bodies evaluated only at application• Key idioms of delaying evaluation– Thunks– Laziness– Memoization– Streams• In general, evaluation rules defined by language semantics– Some languages have “lazy” function application!Dan Grossman CSE341 Spring 2004, Lecture 14 2'&$%Top-level definitionsScheme top-level allows forward references and mutation of bindings• What should a name clash do? (In fact, it’s mutation.)• How can you program defensively?– General point: Make a local copy!• How does “primitives are functions” make this harder?• What do Schemers do in practice?– Don’t mutate top-level bindings– Use a module system for names pace managementDan Grossman CSE341 Spring 2004, Lecture 14 3'&$%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-terminationDan Grossman CSE341 Spring 2004, Lecture 14 4'&$%Best of both worlds?The “lazy” (call-by-need) rule: Evaluate the argument, the first timeit’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 effec ts– Typically used in (sub)languages without effects• Nonetheless, a key idiom with syntactic support in Scheme– And related to memoizationDan Grossman CSE341 Spring 2004, Lecture 14 5'&$%ThunksA “thunk” is just a function taking no arguments, which works greatfor delaying evaluation.My small “thunk” library implements lazy evaluation (would be betterto use abstraction; mutation is an implementation detail)If thunks are lightweight enough syntactically, why not make if eager?(Smalltalk does this!)Dan Grossman CSE341 Spring 2004, 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 expone ntial explosion.An association list is not t he fastest data structure for large memotables, but works fine for 341.Question: Why does assoc return the pair?Dan Grossman CSE341 Spring 2004, Lecture 14 7'&$%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 describe what comes next.Note: Deep connection to sequential feedback circuitsNote: Connection to UNIX pipesDan Grossman CSE341 Spring 2004, Lecture 14


View Full Document

UW CSE 341 - Lecture Notes

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 Lecture Notes
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 Lecture Notes 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 Lecture Notes 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?