DOC PREVIEW
UW CSE 341 - Lecture Notes

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

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

Unformatted text preview:

'&$%CSE 341:Programming LanguagesHal PerkinsSpring 2011Lecture 3— Lack of Mutation, let bindings, optionsHal Perkins CSE341 Spring 2011, Lecture 3 1'&$%List Review• Build lists: [], ::, and shorthand [e1,e2,...,en]• Use lists: null, hd, tl• Types: Each list has elements of the same type. Examples:int list(int*int) list((int*int) list) list• So what are the typing rules for [], ::, null, hd, and tl?• Functions that build or use lists are usually recursive– And/or use other recursive functions– Elegant algorithms by “thinking high-level” (e.g., append)Hal Perkins CSE341 Spring 2011, Lecture 3 2'&$%SharingRecall append([2,4],[5,3,0]) evaluates to [2,4,5,3,0].Similarly, tl [9,7,4,2] evaluates to [7,4,2].Do the results share, i.e., alias the arguments?Example: val x=[2,4]; val y=[5,3,0]; val z=append(x,y)Hal Perkins CSE341 Spring 2011, Lecture 3 3'&$%Sharing, good or bad?Java programmer’s view:• A never-ending obsession with what is shared. This obsession isnecessary because everything is mutable.• Sharing is wrong if you don’t want a mutation of “one list” to“affect the other” and right if you do.• So sometimes make copies just to avoid sharing in case someother code might do a mutation.Hal Perkins CSE341 Spring 2011, Lecture 3 4'&$%Sharing, good or bad?ML programmer’s view:• It is actually impossible to tell if there is sharing or not!• So stop worrying and just write append; all lists [2,4,5,3,0]behave the same no matter what they do or do not share with.• Amount of sharing is just a “space optimization”– Usually good to share.– tl shares, which makes it very fast (O(1)).Hal Perkins CSE341 Spring 2011, Lecture 3 5'&$%Let bindingsMotivation: Functions without local variables can be poor style and/orreally inefficient.Syntax: let b1 b2 ... bn in e end where each bi is a binding.Typing rules: Type-check each bi and e in context including previousbindings. Type of whole expression is type of e.Evaluation rules: Evaluate each bi and e in environment includingprevious bindings. Value of whole expression is result of evaluating e.Elegant design worth repeating:• Let-expressions can appear anywhere an expression can.• Let-expressions can have any kind of binding.– Local functions can refer to any bindings in scope.– Better style than passing around unchanging arguments.Hal Perkins CSE341 Spring 2011, Lecture 3 6'&$%More than styleExercise: hand-evaluate bad_max and good_max for lists, [3,2,1],[1,2], and [1,2,3].Moral: Repeating expensive (recursive) computations is not just badstyle; it is the wrong algorithm performance-wise.Hal Perkins CSE341 Spring 2011, Lecture 3 7'&$%Options“Options are like lists that can have at most one element.”• Create a t option with NONE or SOME e where e has type t.• Use a t option with isSome and valOfWhy not just use lists? An interesting style trade-off:• Options better express purpose, enforce invariants on callers,maybe faster.• But cannot use functions for lists already written.Hal Perkins CSE341 Spring 2011, Lecture 3 8'&$%Summary and general patternMajor progress: recursive functions, pairs, lists, let-expressions, optionsEach has a syntax, typing rules, evaluation rules.Functions, pairs, lists, and options are very different, but we candescribe them in the same way:• How do you create values?– function definition; pair expressions; [] and ::; NONE and SOME• How do you use values?– function application; #1 and #2; null, hd, and tl; isSomeand valOfSoon: much better ways to use pairs and lists (pattern-matching)Hal Perkins CSE341 Spring 2011, Lecture 3


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?