'&$%CSE 341:Programming LanguagesDan GrossmanSpring 2004Lecture 25— Static Overloading; Subtype vs. ParametricPolymorphism; Bounded QuantificationDan Grossman CSE341 Spring 2004, Lecture 25 1'&$%Static OverloadingMany OO languages allow methods in the same class to have the same“name” but different argument types. E.g.:void show(Window w) ...void show(DancingBear db) ...float distTo(Point p) ...float distTo(3DPoint p) ...This complicates slightly the semantics of message send. As before,we:• Use the class (“run-time type”) of the receiver to pick a method.• Call the method with the receiver bound to self.But now there are multiple methods with the same name, so we:• Use the (compile-time) types of the arguments to pick the “bestmatch”.Dan Grossman CSE341 Spring 2004, Lecture 25 2'&$%A lower-level viewHere’s an equivalent way to think about it:• A method’s name includes the types of its “formal” arguments(e.g., show$Window)• A message send is rewritten with the types of its “actual”arguments after typechecking (e.g., show(e) becaomesshow$Window(e) if e has type Window.This seems like an “ugly” view, but:• It’s exactly how static overloading is implemented.• It suggests static overloading is not very “interesting”, justconvenient.But... It interacts poorly with contravariant subtyping on methodargument-types, which (I believe) is why Java and C++ use invariantsubtyping there.Dan Grossman CSE341 Spring 2004, Lecture 25 3'&$%Static Overloading vs. Multimethod sA very simple difference: Multimethods choose the method atrun-time using the class of the actuals.Example: e.distTo((Point)(new 3DPoint(3.0,4.0,2.0)))The same “no best match” errors arise, but with overloading they ariseat compile-time (and can be resolved with explicit subsumption).Dan Grossman CSE341 Spring 2004, Lecture 25 4'&$%Static Typing and Code ReuseKey idea: Scheme and Smalltalk are different but not that different:• Scheme has arbitrarily nested lexical scope (so does Smalltalk, butonly within a method)• Smalltalk has subclassing and dynamic dispatch (but easy to codeup what you need in Scheme)Java and ML are a bit more different:• ML has datatypes; Java has classes• The ML default is immutable• Java does not have first-class functions (but does have anonymousinner classes)But the key difference is the type system: Java has subtyping; ML hasparametric polymorphism (e.g., (’a * (’a -> ’b)) -> ’b).Dan Grossman CSE341 Spring 2004, Lecture 25 5'&$%What are “forall” types good for?Some good uses for forall types:• Combining functions:(* ((’a->’b)*(’b->’c)) -> (’a->’c) *)let compose (f,g) x = g (f x)• Operating on generic container types:isempty : (’a list) -> boolmap : ((’a list) * (’a -> ’b)) -> ’b list• Passing private data (unnecessary with closures):(* (’a * ((’a * string) -> int)) -> int *)let f (env, g) =let val s1 = getString(37)val s2 = getString(49)in g(env,s1) + g(env,s2) endDan Grossman CSE341 Spring 2004, Lecture 25 6'&$%More on private data(* (’a * ((’a * string) -> int)) -> int *)let f (env, g) =let val s1 = getString(37)val s2 = getString(49)in g(env,s1) + g(env,s2) endThe last point is important in safe, lower-level languages (related tomy research), but is unnecessary in ML or Java:• In ML, just use (string->int) -> int and have the caller “passthe ’a” via a closure (a free variable in the function passed in.– This works because the types of free variables do not appear ina function type• In Java, just “pass the ’a” as a field in the object thatimplements the interface.– This works because subtyping lets us “forget” we have fields.Dan Grossman CSE341 Spring 2004, Lecture 25 7'&$%What is subtyping good for?• Passing in values with “extra” or “more useful” stuffbool isXPos(Pt p) { p.x > 0; } // works fine for a Pt3DBut in ML, we end up encoding coercive subtyping using regular MLfunctions that build new values:type pt = { x : real, y : real}type pt3D = { x : real, y : real, z : real }fun isXPos (p:pt) = (#x p) > 0.0val p3:pt3D = { x=4.0, y=3.0, z=5.0}fun pt (p:pt3D) = { x=(#x p), y=(#y p)}val _ = isXPos ((pt) p3)Dan Grossman CSE341 Spring 2004, Lecture 25 8'&$%What else is subtyping good for?In addition to adding “public” fields, we can use it for private state:interface I { int f(int); }class MaxEver implements I {int m = 0;int f(int i) {if(i > m)i = m;return m;}}In ML, we encode private state using closures.Dan Grossman CSE341 Spring 2004, Lecture 25 9'&$%Wanting bothCould one language support subtype polymorphism and parametricpolymorphism?• Sure; and the next generation of OO languages will• C++ templates are sort of like parametric polymorphism, but theyduplicate code, so they’re a bit like macrosMore interestingly, you may want both at once!Pt withXZero(Pt p) { return new P(0,p.y); }How could we make a version that worked for subtype s too?Dan Grossman CSE341 Spring 2004, Lecture 25 10'&$%Bounded QuantificationHere’s an excellent start:interface I { Pt copy(Pt p); }Pt withXZero(Pt p, I i) {Pt ans = i.copy(p); ans.x = 0; return ans;}But consider using it for a Pt3D:• copy method will have to downcast argument.• user of withXZero will have to downcast result.Enter bounded quantification:interface I<’a> { ’a copy(’a p); }’a withXZero(’a p, I<’a> i) where ’a <: Pt {’a ans = i.copy(p); ans.x = 0; return ans;}Dan Grossman CSE341 Spring 2004, Lecture 25 11'&$%How did that work?• No downcasts.• Without the bound, ans.x would not typecheck.• At call-sites of withXZero, just check the instantiation for ’a is asubtype of PtIn general, in a language with subtyping (t1<:t2) and parametricpolymorphism, a useful generalization of forall ’a. t is forall’a<:t1 . t2. This allows fewer instantiations for ’a.Advanced point: When is forall ’a<:t1. t2 a subtype of forall’a<:t3. t4.• Sound answer: contravariant bounds; covariant body.• But that answer makes the subtyping question (for any two types,is one a subtype of the other) undecidable! (1992 result)• A common restriction in practice is invariant bounds.Dan Grossman CSE341 Spring 2004, Lecture 25
View Full Document
Unlocking...