DOC PREVIEW
UW CSE 341 - Lecture Notes

This preview shows page 1-2-3-4 out of 11 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

'&$%CSE 341:Programming LanguagesHal PerkinsSpring 2011Lecture 24— Named Types; Polymorphism vs. Subtyping;Polymorphism + SubtypingHal Perkins CSE341 Spring 2011, Lecture 24 1'&$%Named TypesIn Java/C++/C#/..., types don’t look like{t10 m1(t11,...), ..., tn0 mn(tn1,...)}.Instead they look like C where C is a class or interface.But everything we learned about subtyping still applies!• Example: could have overriding method in subtype take asupertype of an argument(though Java/C++/C# do overloading instead).Yet the only subtyping is declared subtypes, plus transitivity(e.g., class C extends D implements I,J).• Having fewer subtypes is always sound; just allows fewer programsGiven types D, I, and J, ensure objects produced by class C’sconstructors can have subtypes (more methods, contra/co, etc.)Hal Perkins CSE341 Spring 2011, Lecture 24 2'&$%Named vs. UnnamedFor preventing “message not understood”, unnamed (“structural”)types worked fine.But many languages have named (“nominal”) types.Which is better is an old argument with points on both sides.Let’s consider whether subtyping should be:1. structural (“I have everything you need”), or2. nominal (“I said I was a subtype explicitly”)...Hal Perkins CSE341 Spring 2011, Lecture 24 3'&$%Some Fair PointsFor structural subtyping:• Allows more code reuse, while remaining sound.• Does not require refactoring or adding “implements clauses”later when you discover you could share some implementation.For nominal subtyping:• Reject more code, which catches bugs and avoids accidentalmethod-name clashes.• Confusion with classes saves keystrokes and “doing everythingtwice”?• Fewer subtypes makes type-checking and efficient code-generationeasier.Hal Perkins CSE341 Spring 2011, Lecture 24 4'&$%The Grand ConfusionFor convenience, many languages confuse classes and types:• C is a class and a type• If C extends D, then:– instances of the class C inherit from the class D– expressions of type C can be subsumed to have type DDo you usually want this confusion? Probably.Do you always want “subclass implies subtype”?• No: Consider distBetween for Point and 3DPoint.Do you always want “subtype implies subclass”?• No: Consider two classes with display methods and noinheritance relationship.Hal Perkins CSE341 Spring 2011, Lecture 24 5'&$%Untangling Classes and Types• Classes define object behavior; subclassing inherits behavior• Subtyping defines substitutability• Most languages require subclasses to be subtypesNow some other common features make more sense:• “Abstract” methods:– Expand the supertype without providing behavior to subclass– Superclass does not implement behavior, so no constructorsallowed (an additional static check; the class is abstract)– The static check is the only fundamental justification∗ Trivial to provide a method that raises an exception∗ In Ruby, just have a message-not-understood error• Interfaces (see previous lecture)Hal Perkins CSE341 Spring 2011, Lecture 24 6'&$%Static Typing and Code ReuseKey idea: Scheme and Ruby are different but not that different:• Scheme has arbitrarily nested lexical scope (so does Ruby vianested blocks within a method)• Ruby has subclassing and dynamic dispatch (but easy to code upwhat you need in Scheme)Java and ML are a bit more different:• ML has datatypes; Java has classes• The ML default is immutable• ML has 1st-class functions (but see Java’s inner classes)But the key difference is the type system: ML has parametricpolymorphism. Java has subtyping with parametric polymorphismadded on much later (combination greater than the sum of the parts)Hal Perkins CSE341 Spring 2011, Lecture 24 7'&$%What are “forall” types good for?Some good uses for parametric polymorphism:• Combining functions:(* ((’a->’b)*(’b->’c)) -> (’a->’c) *)fun 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 though):(* (’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) endHal Perkins CSE341 Spring 2011, Lecture 24 8'&$%Subtyping is not right hereIf you try to use subtyping for the previous examples:• arguments get “upcast” (to Object)• results get downcast (from Object)This is:• Inconvenient and error-prone• Avoiding the static checksIn general, when different values can be “any type” but “the same aseach other”, you want parametric polymorphism.Hal Perkins CSE341 Spring 2011, Lecture 24 9'&$%What is subtyping good for?• Passing in values with “extra” or “more useful” stuff//can pass a Pt3Dboolean isXPos(Pt p){ return p.x > 0; }• Passing private state like with closuresinterface J { int f(int); }class MaxEver implements J {private int m = 0;public int f(int i) { if(i > m) m = i; return m; }}Parametric polymorphism is not the right thing here (there aresophisticated workarounds)Hal Perkins CSE341 Spring 2011, Lecture 24 10'&$%Wanting bothCould one language support subtyping and parametric polymorphism?• Sure; Java and C# already do but they also let you “get aroundthe checks” :-(More interestingly, you may want both at once!A simple (?) example: Making a copy of a mutable list.Hal Perkins CSE341 Spring 2011, Lecture 24


View Full Document

UW CSE 341 - Lecture Notes

Documents in this Course
Macros

Macros

6 pages

Macros

Macros

6 pages

Macros

Macros

3 pages

Mutation

Mutation

10 pages

Macros

Macros

17 pages

Racket

Racket

25 pages

Scheme

Scheme

9 pages

Macros

Macros

6 pages

Load more
Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?