Slide 1Upcoming scheduleTodayEquivalenceA definitionExampleAnother exampleSyntactic sugarStandard equivalencesStandard equivalencesStandard equivalencesOne moreWhat about performance?Different definitions for different jobsParametric polymorphismExampleInstantiationNon-exampleWhy not?CSE341: Programming LanguagesLecture 13Equivalence;Parametric PolymorphismDan GrossmanFall 2011Upcoming schedule•Today is Wednesday (duh )•Friday will be an introduction to Racket•Monday is our midterm, on material up through today–Biased toward later lectures because material builds–Section will focus on modules and do some review–My exams are difficult; possibly a bit harder than samples•Don’t panic; it’s fairer that way–You can bring one side of one sheet of paper•Will move into new concepts using Racket very quickly–Homework 4 due about a week after midterm and is much more than “getting started with Racket”Fall 2011 2CSE341: Programming LanguagesToday1. More careful look at what “two pieces of code are equivalent” means–Fundamental software-engineering idea–Made easier with (a) abstraction (b) fewer side effects2. Parametric polymorphism (a.k.a. generic types)–Before we stop using a statically typed language–See that while generics are very convenient in ML, even ML is more restrictive than it could be–(Will contrast with subtyping near end of course)Won’t learn any “new ways to code something up” todayFall 2011 3CSE341: Programming LanguagesEquivalenceMust reason about “are these equivalent” all the time–The more precisely you think about it the better•Code maintenance: Can I simplify this code?•Backward compatibility: Can I add new features without changing how any old features work?•Optimization: Can I make this code faster?•Abstraction: Can an external client tell I made this change?To focus discussion: When can we say two functions are equivalent, even without looking at all calls to them?–May not know all the calls (e.g., we are editing a library)Fall 2011 4CSE341: Programming LanguagesA definitionTwo functions are equivalent if they have the same “observable behavior” no matter how they are used anywhere in any programGiven equivalent arguments, they:–Produce equivalent results–Have the same (non-)termination behavior–Mutate (non-local) memory in the same way–Do the same input/output–Raise the same exceptionsNotice it is much easier to be equivalent if:•There are fewer possible arguments, e.g., with a type system and abstraction•We avoid side-effects: mutation, input/output, and exceptionsFall 2011 5CSE341: Programming LanguagesExampleSince looking up variables in ML has no side effects, these two functions are equivalent:But these next two are not equivalent in general: it depends on what is passed for f–They are if argument for f has no side-effects–Example: g ((fn i => print "hi" ; i), 7)–Great reason for “pure” functional programmingFall 2011 6CSE341: Programming Languagesfun f x = x + xval y = 2fun f x = y * xfun g (f,x) = (f x) + (f x)val y = 2fun g (f,x) = y * (f x)Another exampleThese are equivalent only if functions bound to g and h do not raise exceptions or have side effects (printing, updating state, etc.)–Again: pure functions make more things equivalent–Example: g divides by 0 and h mutates a top-level reference–Example: g writes to a reference that h reads fromFall 2011 7CSE341: Programming Languagesfun f x = let val y = g x val z = h x in (y,z) endfun f x = let val z = h x val y = g x in (y,z) endSyntactic sugarUsing or not using syntactic sugar is always equivalent–Else it’s not actually syntactic sugarExample:But be careful about evaluation orderFall 2011 8CSE341: Programming Languagesfun f x = if x then g x else falsefun f x = x andalso g x fun f x = if g x then x else falsefun f x = x andalso g xStandard equivalencesThree general equivalences that always work for functions–In any (?) decent language1. Consistently rename bound variables and usesBut notice you can’t use a variable name already used in the function body to refer to something elseFall 2011 9CSE341: Programming Languagesval y = 14fun f x = x+y+xval y = 14fun f z = z+y+zval y = 14fun f x = x+y+xval y = 14fun f y = y+y+yfun f x = let val y = 3 in x+y endfun f y = let val y = 3 in y+y endStandard equivalencesThree general equivalences that always work for functions–In (any?) decent language2. Use a helper function or don’tBut notice you need to be careful about environmentsFall 2011 10CSE341: Programming Languagesval y = 14fun f x = x+y+xfun g z = (f z)+zval y = 14fun g z = (z+y+z)+zval y = 14fun f x = x+y+xval y = 7fun g z = (f z)+zval y = 14val y = 7fun g z = (z+y+z)+zStandard equivalencesThree general equivalences that always work for functions–In (any?) decent language3. Unnecessary function wrappingBut notice that if you compute the function to call and that computation has side-effects, you have to be carefulFall 2011 11CSE341: Programming Languagesfun f x = x+xfun g y = f yfun f x = x+xval g = ffun f x = x+xfun h () = (print "hi"; f)fun g y = (h()) yfun f x = x+xfun h () = (print "hi"; f)val g = (h())One moreIf we ignore types, then ML let-bindings can be syntactic sugar for calling an anonymous function:–These both evaluate e1 to v1, then evaluate e2 in an environment extended to map x to v1–So exactly the same evaluation of expressions and resultBut in ML, there is a type-system difference:–x on the left can have a polymorphic type, but not on the right–Can always go from right to left–If x need not be polymorphic, can go from left to rightFall 2011 12CSE341: Programming Languageslet val x = e1in e2 end(fn x => e2) e1What about performance?According to our definition of equivalence, these two functions are equivalent, but we learned one is awful–(Actually we studied this before pattern-matching)Fall 2011 13CSE341: Programming Languagesfun max xs = case xs of [] => raise Empty | x::[] => x | x::xs => if x > max xs then x else max xsfun max xs = case xs of [] => raise Empty | x::[] => x | x::xs => let val y = max xs in if x > y then x else y endDifferent definitions for different jobs•CSE341: PL Equivalence: given same inputs, same outputs and effects–Good: Let’s us replace bad max with good max–Bad: Ignores performance in
View Full Document
Unlocking...