CSE341: Programming Languages Lecture 13 Equivalence; Parametric Polymorphism Dan Grossman Fall 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 2 CSE341: Programming LanguagesToday 1. More careful look at what “two pieces of code are equivalent” means – Fundamental software-engineering idea – Made easier with (a) abstraction (b) fewer side effects 2. 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” today Fall 2011 3 CSE341: Programming LanguagesEquivalence Must 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 4 CSE341: Programming LanguagesA definition Two functions are equivalent if they have the same “observable behavior” no matter how they are used anywhere in any program Given 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 exceptions Notice 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 exceptions Fall 2011 5 CSE341: Programming LanguagesExample Since 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 programming Fall 2011 6 CSE341: Programming Languages fun f x = x + x val y = 2 fun f x = y * x fun g (f,x) = (f x) + (f x) val y = 2 fun g (f,x) = y * (f x)Another example These 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 from Fall 2011 7 CSE341: Programming Languages fun f x = let val y = g x val z = h x in (y,z) end fun f x = let val z = h x val y = g x in (y,z) endSyntactic sugar Using or not using syntactic sugar is always equivalent – Else it’s not actually syntactic sugar Example: But be careful about evaluation order Fall 2011 8 CSE341: Programming Languages fun f x = if x then g x else false fun f x = x andalso g x fun f x = if g x then x else false fun f x = x andalso g xStandard equivalences Three general equivalences that always work for functions – In any (?) decent language 1. Consistently rename bound variables and uses But notice you can’t use a variable name already used in the function body to refer to something else Fall 2011 9 CSE341: Programming Languages val y = 14 fun f x = x+y+x val y = 14 fun f z = z+y+z val y = 14 fun f x = x+y+x val y = 14 fun f y = y+y+y fun f x = let val y = 3 in x+y end fun f y = let val y = 3 in y+y endStandard equivalences Three general equivalences that always work for functions – In (any?) decent language 2. Use a helper function or don’t But notice you need to be careful about environments Fall 2011 10 CSE341: Programming Languages val y = 14 fun f x = x+y+x fun g z = (f z)+z val y = 14 fun g z = (z+y+z)+z val y = 14 fun f x = x+y+x val y = 7 fun g z = (f z)+z val y = 14 val y = 7 fun g z = (z+y+z)+zStandard equivalences Three general equivalences that always work for functions – In (any?) decent language 3. Unnecessary function wrapping But notice that if you compute the function to call and that computation has side-effects, you have to be careful Fall 2011 11 CSE341: Programming Languages fun f x = x+x fun g y = f y fun f x = x+x val g = f fun f x = x+x fun h () = (print "hi"; f) fun g y = (h()) y fun f x = x+x fun h () = (print "hi"; f) val g = (h())One more If 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 result But 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 right Fall 2011 12 CSE341: Programming Languages let val x = e1 in 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 13 CSE341: Programming Languages fun max xs = case xs of [] => raise Empty | x::[] => x | x::xs => if x > max xs then x else max xs fun 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
View Full Document
Unlocking...