Slide 1Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37CSE341: Programming LanguagesLecture 10References, Polymorphic Datatypes, the Value Restriction, Type InferenceBen Wood, filling in for Dan GrossmanFall 201113Fall 2011 CSE341: Programming LanguagesCallbacksA common idiom: Library takes functions to apply later, when an event occurs – examples:–When a key is pressed, mouse moves, data arrives–When the program enters some state (e.g., turns in a game)A library may accept multiple callbacks–Different callbacks may need different private data with different types–Fortunately, a function’s type does not include the types of bindings in its environment–(In OOP, objects and private fields are used similarly, e.g., Java Swing’s event-listeners)1314Fall 2011 CSE341: Programming LanguagesMutable stateWhile it’s not absolutely necessary, mutable state is reasonably appropriate here–We really do want the “callbacks registered” and “events that have been delivered” to change due to function callsFor the reasons we have discussed, ML variables really are immutable, but there are mutable references (use sparingly)–New types: t ref where t is a type–New expressions:•ref e to create a reference with initial contents e•e1 := e2 to update contents •!e to retrieve contents (not negation)1415Fall 2011 CSE341: Programming LanguagesReferences exampleval x = ref 42 val y = ref 42 val z = xval _ = x := 43val w = (!y) + (!z) (* 85 *)(* x + 1 does not type-check)•A variable bound to a reference (e.g., x) is still immutable: it will always refer to the same reference•But the contents of the reference may change via :=•And there may be aliases to the reference, which matter a lot•Reference are first-class values•Like a one-field mutable object, so := and ! don’t specify the field16Fall 2011 CSE341: Programming LanguagesExample call-back libraryLibrary maintains mutable state for “what callbacks are there” and provides a function for accepting new ones–A real library would support removing them, etc.–In example, callbacks have type int->unit (executed for side-effect)So the entire public library interface would be the function for registering new callbacks:val onKeyEvent : (int -> unit) -> unit17Fall 2011 CSE341: Programming LanguagesLibrary implementationval cbs : (int -> unit) list ref = ref [] fun onKeyEvent f = cbs := f :: (!cbs) fun onEvent i = let fun loop fs = case fs of [] => () | f::fs’ => (f i; loop fs’) in loop (!cbs) end18Fall 2011 CSE341: Programming LanguagesClientsCan only register an int -> unit, so if any other data is needed, must be in closure’s environment–And if need to “remember” something, need mutable stateExamples:val timesPressed = ref 0val _ = onKeyEvent (fn _ => timesPressed := (!timesPressed) + 1)fun printIfPressed i = onKeyEvent (fn j => if i=j then print ("pressed " ^ Int.toString i) else ())20Fall 2011 CSE341: Programming LanguagesMore about types•Polymorphic datatypes, type constructors•Why do we need the Value Restriction?•Type inference: behind the curtain2021Fall 2011 CSE341: Programming LanguagesPolymorphic Datatypesdatatype int_list = EmptyList | Cons of int * int_listdatatype ‘a non_mt_list = One of ‘a | More of ‘a * (‘a non_mt_list)datatype (‘a,‘b) tree = Leaf of ‘a | Node of ‘b * (‘a,‘b) tree * (‘a,‘b) treeval t1 = Node(“hi”,Leaf 4,Leaf 8)(* (int,string) tree *)val t2 = Node(“hi”,Leaf true,Leaf 8)(* does not typecheck *)22Fall 2011 CSE341: Programming LanguagesPolymorphic Datatypes•list, tree, etc. are not types; they are type constructors•int list, (string,real) tree, etc. are types. •Pattern-matching works on all datatypes.22datatype ‘a list = [] | :: of ‘a * (‘a list) (* if this were valid syntax *)datatype ‘a option = NONE | SOME of ‘a23Fall 2011 CSE341: Programming LanguagesThe Value Restriction Appears If you use partial application to create a polymorphic function, it may not work due to the value restriction–Warning about “type vars not generalized”•And won’t let you call the function–This should surprise you; you did nothing wrong but you still must change your code–See the written lecture summary about how to work around this wart (and ignore the issue until it arises)–The wart is there for good reasons, related to mutation and not breaking the type system2324Fall 2011 CSE341: Programming LanguagesPurpose of the Value Restrictionval xs = ref [](* xs : ‘a list ref *)val _ = xs := [“hi”](* instantiate ‘a with string *)val y = 1 + (hd (!xs))(* BAD: instantiate ‘a with int *)•A binding is only allowed to be polymorphic if the right-hand side is:–a variable; or–a value (including function definitions, constructors, etc.)•ref [] is not a value, so we can only give it non-polymorphic types such as int list ref or string list ref, but not ‘a list ref.25Fall 2011 CSE341: Programming LanguagesDownside of the Value Restrictionval pr_list = List.map (fn x => (x,x)) (* X *)val pr_list : int list -> (int*int) list =List.map (fn x => (x,x)) val pr_list =fn lst => List.map (fn x => (x,x)) lst fun pr_list lst = List.map (fn x => (x,x)) lst•The SML type checker does not know if the ‘a list type uses references internally, so it has to be conservative and assume it could.•In practice, this means we need to be more explicit about partial application of polymorphic functions.26Fall 2011 CSE341: Programming LanguagesType inference: sumfun sum xs = case xs of [] => 0 | x::xs’ => x + (sum xs’)sum : t1 -> t2 xs : t1 t1 = t5 list x : t3xs’ : t4 t2 = int t3 = t5 t3 = int t4 = t5 list t1 = t427Fall 2011 CSE341: Programming LanguagesType inference: sumfun sum xs = case xs of [] => 0 | x::xs’ => x + (sum xs’)sum : t1 -> t2 xs : t1 t1 = t5 list x : t3xs’ : t4 t2 = int t3 = t5 t3 = int t4 = t5 list t1 = t4t1 t1intintintint28Fall 2011 CSE341: Programming LanguagesType inference: sumfun sum xs = case xs of [] => 0 | x::xs’ => x + (sum xs’)sum : int list -> int xs : int list t1 = t5 list x : intxs’ : t4 t2 = int t3 = t5 t3 = int t4 = t5 list t1 = t4int list t1intint29Fall 2011 CSE341: Programming LanguagesType inference: lengthfun length xs = case xs of [] => 0 | _::xs’ => 1 +
View Full Document
Unlocking...