DOC PREVIEW
UW CSE 341 - Parametric Polymorphism

This preview shows page 1-2-3-4-5-6 out of 17 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 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 17 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 17 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 17 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 17 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 17 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

'&$%CSE 341:Programming LanguagesDan GrossmanSpring 2008Lecture 12— Parametric Polymorphism; EquivalenceDan Grossman CSE341 Spring 2008, Lecture 12 1'&$%TodayTwo more “conceptual” topics• Higher density of more abstract concepts as course progresses• Think about the theory and how languages “fit together”, not justhow do I “code som ething up”1. Parametric polymorphism• Also: Type constructors (e .g., ML’s list and option)2. Equivalence• When are two functions or other expressions “the same”Dan Grossman CSE341 Spring 2008, Lecture 12 2'&$%Parametric PolymorphismFancy phrase for “forall types” or sometimes “generics.” In ML sincemid-80s and now in Java, C#, VB, etc.• (C++ templates are more like macros (later)).In ML, there’s an implicit “for all” at the beginning of any type with’a, ’b, etc. Example:(’a * ’b) -> (’b * ’a)really means:forall ’a, ’b . ((’a * ’b) -> (’b * ’a))(though forall is just for lecture purposes; it is not in ML)We can instantiate the type variables to get a less general type. Forexample, with string for ’a and int->int for ’b we get:(string * (int -> int)) -> ((int->int) * string)Dan Grossman CSE341 Spring 2008, Lecture 12 3'&$%All the typesIn principle, we could have a very flexible way of building types:• Base types like int, string, real, ...• Compound types like t1 * t2 and t1 -> t2 where t1 and t2are any type• Polymorphic types like forall ’a. t where ’a can appear in t.Would let you have types like(forall ’a. ’a -> (’a*’a)) -> ((int*int) * (bool*bool))Every language has limits; in ML there is no type like this.The forall is always implicit and “all the way to the outside left”, forexample this different type:(’a -> (’a * ’a)) -> ((int * int) * (bool * bool))Dan Grossman CSE341 Spring 2008, Lecture 12 4'&$%ExampleThis code is fine, but ML disallows it to make type inference easier.(* function f does _not_ type-check *)fun f pairmaker = (pairmaker 7, pairmaker true)val x = f (fn y => (y,y))Dan Grossman CSE341 Spring 2008, Lecture 12 5'&$%Versus Subtypi ngCompare:fun swap (x,y) = (y,x) (* (’a * ’b) -> (’b * ’a) *)with:class Pair {Object x;Object y;Pair(Object _x, Object _y) { x=_x; y=_y; }static Pair swap(Pair pr) {return new Pair(pr.y, pr.x);}}ML wins in two ways (for this example):• Caller instantiates types, so doesn’t need to cast fields of result• Callee cannot return a pair of any two objects.That’s why Java added generics...Dan Grossman CSE341 Spring 2008, Lecture 12 6'&$%Java Genericsclass Pair<T1,T2> {T1 x;T2 y;Pair(T1 _x, T2 _y) { x=_x; y=_y; }static <T1,T2> Pair<T2,T1> swap(Pair<T1,T2> pr) {return new Pair<T2,T1>(pr.y,pr.x);}}This really is a step forward despite the clutter, i.e., it isfun swap (x,y) = (y,x)with explicit types and other verbiage.Dan Grossman CSE341 Spring 2008, Lecture 12 7'&$%ContainersParametric polymorphism is also ideal for functions over containers(lists, sets, hashtables, etc.) where elements have the same type.Example: ML listsval :: : (’a * (’a list)) -> ’a list (* infix is syntax *)val map : ((’a -> ’b) * (’a list)) -> ’b listval sum : int list -> intval fold : (’a * ’b -> ’b) -> (’a list) -> ’blist is not a type ; if t is a type, then t list is a type.Dan Grossman CSE341 Spring 2008, Lecture 12 8'&$%User-defined type constructorsLanguage-design: If something is useful for a built-in feature, it isuseful for progerammer-defined stuff too.So: Let programmers declare type constructors.Examples:datatype ’a non_mt_list = One of ’a| More of ’a * (’a non_mt_list)datatype (’a,’b) mytree =Leaf of ’a| Node of ’b * (’a,’b) mytree * (’a,’b) mytreeExample construction of values:Node("hi",Leaf 17,Leaf 4) (* (string,int) mytree *)Node(14,Leaf "hi",Leaf "mom") (* (int,string) mytree *)(* Node("hi",Leaf 17,Leaf true) *) (* doesn’t type-check *)Dan Grossman CSE341 Spring 2008, Lecture 12 9'&$%What about lists?Now everything about lists is syntactic sugar!• Constuctors use funny (infix) syntax• [1,2,3] syntax is built-inBut otherwise it is basically:datatype ’a list = [] | :: of ’a * (’a list)Dan Grossman CSE341 Spring 2008, Lecture 12 10'&$%One last thing – not on the testPolymorphism and mutation can be a dangerous combination.val x = ref [] (* ’a list ref *)val _ = x := ["hi"] (* instantiate ’a with string *)val _ = (hd(!x)) + 7 (* instantiate ’a with int -- bad!! *)To prevent this, ML has “the value restriction”: bindings can only getpolymorphic types if they are initialized with values.Alas, that means this does not work even though it should be fine:val pr_list = List.map (fn x => (x,x))But these all work:val pr_list : int list -> (int*int) list =List.map (fn x => (x,x))val pr_list = fun lst => List.map (fn x => (x,x)) lstfun pr_list lst = List.map (fn x => (x,x)) lstDan Grossman CSE341 Spring 2008, Lecture 12 11'&$%Equivalence“Equivalence” is a fundamental programming concept• Code maintenance (simplify code)• Backward-compatibility (add new optional features)• Program optimization (make faster without breaking it)• Abstraction and strong interfaces (previous lecture)But what does it mean for an expre ssion (or program) e1 to be“equivalent” to expression e2?Dan Grossman CSE341 Spring 2008, Lecture 12 12'&$%Toward a de finition“Equivalence” really depends on what is observable.• Two different sorting algorithms generally “are equivalent”.• But if one takes a second and the other takes a century?In programming languages, we generally ignore internal differences likerunning time, private data structures used, etc.• Otherwise too few things would be “equivalent” — we want tojustify replacing code with “better (or at least as good) butequivalent”Dan Grossman CSE341 Spring 2008, Lecture 12 13'&$%A definitionTwo functions are equivalent if they have the same observablebehavior no matter how they are used anywhere in any program.Given the same argument/environment:• they produce the same result.• they have the same (non)termination behavior.• they mutate the same memory the same way.• they do the same input/output.• they raise the same exceptions.Discouraging/forbidding 3, 4, and 5, helps ensure equivalence.• For example, if you “stay functional” then (f x) + (f x) canbe replaced by (f x)*2 without consulting what f is bound to.• (Side)-effects are often worth discouraging in any language.Dan


View Full Document

UW CSE 341 - Parametric Polymorphism

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 Parametric Polymorphism
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 Parametric Polymorphism 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 Parametric Polymorphism 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?