'&$%CSE 341:Programming LanguagesDan GrossmanSpring 2004Lecture 10— Equivalence and Syntactic SugarDan Grossman CSE341 Spring 2004, Lecture 10 1'&$%Where are We• We have covered enough basics to focus more on concepts now• You can complete homework 3• Next Monday will be “Scheme basics”• This week: Equivalence, modules/abstract-types, parametricpolymorphism• Exam Wednesday April 28...Dan Grossman CSE341 Spring 2004, Lecture 10 2'&$%Exam• My tests are usually difficult• You may have 1 side of 1 8.5x11in piece of paper– Just a “comfort page”• Read code, write a little code, write a sentence or two of English– Whereas homework was “write code”– And you can’t “try 50 things you don’t understand”• Heavily biased toward weeks 3 and 4!– We’ve been building on earlier material.Dan Grossman CSE341 Spring 2004, Lecture 10 3'&$%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?Dan Grossman CSE341 Spring 2004, Lecture 10 4'&$%First equivalence notionContext• 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).Dan Grossman CSE341 Spring 2004, Lecture 10 5'&$%Second equivalence notion• “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, ...)Dan Grossman CSE341 Spring 2004, Lecture 10 6'&$%Accounting for “Effects”Consider whether fn x => e1 and fn x => e2 are totallycontextually equivalent.Is this enough? For all environments E such that e1 and e2typecheck, e1 terminates and evaluates to v if and only if e2terminates and evaluates to v.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” to me usually means total contextualequivalence.Dan Grossman CSE341 Spring 2004, Lecture 10 7'&$%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)Dan Grossman CSE341 Spring 2004, Lecture 10 8'&$%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-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.Dan Grossman CSE341 Spring 2004, Lecture 10 9'&$%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?Dan Grossman CSE341 Spring 2004, Lecture 10 10'&$%Systematic renaming requires careWhat 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?Dan Grossman CSE341 Spring 2004, Lecture 10 11'&$%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?)Dan Grossman CSE341 Spring 2004, Lecture 10 12'&$%Unnecessary 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 lstDan Grossman CSE341 Spring 2004, Lecture 10 13'&$%SummaryWe breezed through some core programming-language facts anddesign goals:• Definition of equivalence depends on observable behavior• Systematic renaming means context cannot depend on variablenames• Notion of free and bound variables crucial to understandingfunction equivalence.• Syntactic sugar “makes a big language smaller” by definingconstructs in terms of equivalenceDan Grossman CSE341 Spring 2004, Lecture 10
View Full Document
Unlocking...