New version page

UW CSE 341 - Mutual Recursion, Equivalence, and Syntactic Sugar

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
Upgrade to remove ads

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

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

Upgrade to remove ads
Unformatted text preview:

CSE 341:Programming LanguagesAutumn 2005Lecture 10 — Mutual Recursion, Equivalence, and Syntactic SugarCSE 341 Autumn 2005, Lecture 10 1Mutual RecursionYou’ve already seen how multiple functions can recursively call eachother in HW 2.ML uses the keyword and to provide different scope 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.Syntax gotcha: Easy to forget that you write and fi xi = ei, notand fun fi xi = ei.CSE 341 Autumn 2005, Lecture 10 2Mutual Recursion Idioms1. Encode a state machine (see product_sign example)• Sometimes easier to understand than explicit state values.2. Process mutually recursive types, as in HW 2CSE 341 Autumn 2005, Lecture 10 3Equivalence“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?CSE 341 Autumn 2005, Lecture 10 4Equivalence I: where?Context (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).CSE 341 Autumn 2005, Lecture 10 5Equivalence II: how?“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, ...)CSE 341 Autumn 2005, Lecture 10 6Accounting for “Effects”Consider whether fn x => e1 and fn x => e2 are totallycontextually equivalent.Is this enough? For all environments, e1 terminates and evaluates to vunder the environments if and only if e2 terminates and evaluates to vunder the environment.Functions produce values; may also produce (side-) effects. Considerboth!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.).CSE 341 Autumn 2005, Lecture 10 7Syntactic Sugar“Syntactic sugar causes cancer of the semicolon.”– Alan PerlisWhen 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)CSE 341 Autumn 2005, Lecture 10 8More 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-check (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.CSE 341 Autumn 2005, Lecture 10 9Equivalences 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 equivalent to fn y => e2 where e2 is e1 with every xreplaced by y?CSE 341 Autumn 2005, Lecture 10 10Systematic 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, and no freex occurs within the scope of a binding for y (capture; e.g.:fn x => let y = 2 in x + y end; see also next slide.)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?CSE 341 Autumn 2005, Lecture 10 11Argument 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?)CSE 341 Autumn 2005, Lecture 10 12Unnecessary Function WrappingA 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 lstCSE 341 Autumn 2005, Lecture 10 13SummaryWe breezed through some core programming-language facts anddesign goals:• Definition of equivalence depends on observable behavior• Syntactic sugar “makes a big language smaller” by definingconstructs in terms of equivalence• Notion of free and bound variables crucial to understandingfunction equivalence.• Three common forms of function equivalence:– Systematic Renaming– Argument Substitution– Unnecessary Function WrappingCSE 341 Autumn 2005, Lecture 10


View Full Document
Download Mutual Recursion, Equivalence, and Syntactic Sugar
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 Mutual Recursion, Equivalence, and Syntactic Sugar 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 Mutual Recursion, Equivalence, and Syntactic Sugar 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?