New version page

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

Documents in this Course

5 pages

17 pages

17 pages

17 pages

6 pages

3 pages

2 pages

9 pages

29 pages

6 pages

5 pages

14 pages

6 pages

6 pages

33 pages

3 pages

7 pages

5 pages

25 pages

11 pages

7 pages

5 pages

14 pages

5 pages

11 pages

14 pages

4 pages

3 pages

4 pages

4 pages

4 pages

3 pages

7 pages

2 pages

22 pages

6 pages

3 pages

15 pages

7 pages

15 pages

13 pages

13 pages

7 pages

19 pages

12 pages

16 pages

3 pages

2 pages

12 pages

3 pages

20 pages

2 pages

12 pages

15 pages

14 pages

4 pages

2 pages

8 pages

9 pages

7 pages

27 pages

6 pages

3 pages

10 pages

5 pages

7 pages

6 pages

6 pages

13 pages

7 pages

8 pages

18 pages

4 pages

11 pages

17 pages

3 pages

7 pages

17 pages

17 pages

5 pages

17 pages

3 pages

3 pages

3 pages

3 pages

107 pages

14 pages

12 pages

11 pages

20 pages

4 pages

6 pages

7 pages

29 pages

6 pages

8 pages

10 pages

21 pages

6 pages

10 pages

2 pages

19 pages

6 pages

5 pages

22 pages

8 pages

4 pages

20 pages

19 pages

17 pages

8 pages

6 pages

5 pages

16 pages

3 pages

4 pages

7 pages

7 pages

7 pages

2 pages

8 pages

3 pages

7 pages

7 pages

20 pages

8 pages

25 pages

3 pages

6 pages

7 pages

5 pages

4 pages

11 pages

6 pages

3 pages

20 pages

9 pages

9 pages

11 pages

2 pages

7 pages

14 pages

19 pages

9 pages

10 pages

4 pages

9 pages

7 pages

15 pages

6 pages

9 pages

17 pages

11 pages

16 pages

6 pages

19 pages

2 pages

14 pages

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

View Full Document
Do you want full access? Go Premium and unlock all 14 pages.
Do you want full access? Go Premium and unlock all 14 pages.
Do you want full access? Go Premium and unlock all 14 pages.
Do you want full access? Go Premium and unlock all 14 pages.
Do you want full access? Go Premium and unlock all 14 pages.

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