DOC PREVIEW
UW CSE 341 - Lecture Notes

This preview shows page 1-2-3-4-5 out of 15 pages.

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

Unformatted text preview:

'&$%CSE 341:Programming LanguagesWinter 2005Lecture 10— Mutual Recursion, Equivalence and Syntactic SugarCSE341 Winter 2005, Lecture 10 1'&$%Mutual RecursionWe haven’t yet seen how multiple functions can recursively call eachother? (Why can’t we do this with what we have?)ML uses the keyword and to provide different sc ope rules. Example:fun even i = if i=0 then true else odd (i-1)and odd i = if i=0 then false else even (i-1)Roughly extends the binding form for functions from fun f1 x1 = e1to fun f1 x1 = e1 and f2 x2 = e2 and ... and fn xn = en.Actually, you can have val bindings too, but bindings being definedare in scope only inside function bodies. (Why?)Syntax gotcha: Easy to forget that you write and fi xi = ei, notand fun fi xi = ei.CSE341 Winter 2005, Lecture 10 2'&$%Mutual Recursion Idioms1. Encode a state machine (see product_sign example)• Sometimes easier to understand than explicit state values.2. Process mutually recursive types, e xample:datatype webtext = Empty| Link of webpage * string * webtext| Word of string * webtextand webpage = Found of string * webtext| Unfound of stringA function “crawl for word” is inherently mutually recursive. (Youcould make a datatype for “webtext or webpage”, but that’s ugly.)Problem: the Web has cycles, which (sigh) is a common need formutation in ML.Unproblem: When crawling, we don’t want cycles (use Unfound ifwe have seen the page before).CSE341 Winter 2005, Lecture 10 3'&$%Where are We• We have covered enough basics to focus more on concepts now• Before Scheme: Equivalence, parametric polymorphism, typeinference, modules/abstract-types• Homework 3 out tomorrow (today?), due Feb. 3 (do not wait)• Midterm exam Monday Feb. 7 (more info later)CSE341 Winter 2005, Lecture 10 4'&$%Equivalence“Equivalence” is a fundamental programming concept• Code maintenance / backward-compatibility• Program verification• Program optimization• Abstraction and strong interfacesBut what does it mean for an expression (or program) e1 to be“equivalent” to expression e2?CSE341 Winter 2005, Lecture 10 5'&$%First equivalence notionContext (i.e., “where equivalent”)• Given where e1 occurs in a program e, replacing e1 with e2makes a program e0equivalent to e• At any point in any program, replacing e1 with e2 makes anequivalent program.The latter (contextual equivalence) is much more interesting.For the former, the body of an unused function body is equivalent toeverything (that typechecks).CSE341 Winter 2005, Lecture 10 6'&$%Second equivalence notion“how equivalent”• “partial”: e and e0are equivalent if they input and output thesame data (any limits on input?)• “total”: partial plus e and e0have the same termination behavior• efficiency: e and e0are totally equivalent and one never takesmore than (for example) c times longer than the other (or usesmuch more space or ...)• syntactic notions: e and e0differ only in whitespace andcomments (for example)Key notion: what is observable? (memory, clock, REP-loop,file-system, ...)CSE341 Winter 2005, Lecture 10 7'&$%Accounting for “Effects”Consider whether fn x => e1 and fn x => e2 are totallycontextually equivalent.Is this enough? For all e nvironments, e1 terminates and evaluates to vunder the environments if and only if e2 terminates and evaluates to vunder the environment.We must also consider any effects the function may have.Purely functional languages have fewer/none, but ML is not purelyfunctional.In real languages, contextual equivalence usually requires many things.Nonetheless, “equivalence” usually means total contextual equivalencefor practical purposes (optimization, reasoning about correctness, etc.).CSE341 Winter 2005, Lecture 10 8'&$%Syntactic SugarWhen all expressions using one construct are totally equivalent toanother more primitive construct, we say the former is “syntacticsugar”.• Makes language definition easier• Makes language implementation easierExamples:• e1 andalso e2 (define as a conditional)• if e1 then e2 else e3 (define as a case)• fun f x y = e (define with an anonymous function)CSE341 Winter 2005, Lecture 10 9'&$%More sugar#1 e is just let val (x,...) = e in x endIf we ignore types, then we have even more sugar:let val p = e1 in e2 end is just (fn p => e2) e1.In fact, if we let every program type-c heck (or just use one bigdatatype), then a language with just functions and functionapplication is as powerful as ML or Java (in the Turing Tarpit sense).This language is called “lambda calculus” – we’ll learn a bit moreabout it later.CSE341 Winter 2005, Lecture 10 10'&$%Equivalences for FunctionsWhile sugar defines one construct in terms of another, there are alsoimportant notions of meaning-preserving changes involving functionsand bound variables.They’re so important that a goal of language design is that a languagesupports them.But the correct definitions are subtle.First example: systematic renamingIs fn x => e1 is equivalent to fn y => e2 where e2 is e1 with everyx replaced by y?CSE341 Winter 2005, Lecture 10 11'&$%Systematic renaming requires careIs fn x => e1 is equivalent to fn y => e2 where e2 is e1 with everyx replaced by y?What if e1 is y?What if e1 is fn x => x?Need caveats: fn x => e1 is equivalent to fn y => e2 where e2 ise1 with every free x replaced by y and y is not free in e1.Note: We can provide a very precise recursive (meta-)definition of freevariables in an expression.Next: Is (fn x => e1) e2 equivalent to e3 where e3 is e1 with everyx replaced by e2?CSE341 Winter 2005, Lecture 10 12'&$%Argument SubstitutionIs (fn x => e1) e2 equivalent to e3 where e3 is e1 with every xreplaced by e2?• Every free x (of course).• A free variable in e2 must not be bound at an occurrence of x.(Called “capture”.)– Always satisfiable by renaming bound variables.• Evaluating e2 must have no effects (printing, exceptions,infinite-loop, etc.)– Closely tied to the rule that arguments are evaluated to valuesbefore function application. (Not true for all languages)– In ML, many expressions have no such effects (x, #foo x, ...);much fewer in Java.• Efficiency? Could be faster or slower. (Why?)CSE341 Winter 2005, Lecture 10 13'&$%Unnecessary Function Wrappin gA common source of bad style for beginnersIs e1 equivalent to fn x => e1 x?Sure, provided:• e1 is effect-free• x does not occur free in e1Example:List.map (fn x => SOME x) lstList.map SOME lstCSE341 Winter 2005, Lecture


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?