CSE341 Programming Languages Lecture 10 References Polymorphic Datatypes the Value Restriction Type Inference Ben Wood filling in for Dan Grossman Fall 2011 Callbacks A 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 Fall 2011 CSE341 Programming Languages 2 Mutable state While 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 calls For 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 Fall 2011 CSE341 Programming Languages 3 References example val x ref 42 val y ref 42 val z x val x 43 val 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 field Fall 2011 CSE341 Programming Languages 4 Example call back library Library 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 unit Fall 2011 CSE341 Programming Languages 5 Library implementation val 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 end Fall 2011 CSE341 Programming Languages 6 Clients Can 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 state Examples val timesPressed ref 0 val onKeyEvent fn timesPressed timesPressed 1 fun printIfPressed i onKeyEvent fn j if i j then print pressed Int toString i else Fall 2011 CSE341 Programming Languages 7 More about types Polymorphic datatypes type constructors Why do we need the Value Restriction Type inference behind the curtain Fall 2011 CSE341 Programming Languages 8 Polymorphic Datatypes datatype int list EmptyList Cons of int int list datatype 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 tree val t1 Node hi Leaf 4 Leaf 8 int string tree val t2 Node hi Leaf true Leaf 8 does not typecheck Fall 2011 CSE341 Programming Languages 9 Polymorphic Datatypes datatype a list of a a list if this were valid syntax datatype a option NONE SOME of a list tree etc are not types they are type constructors int list string real tree etc are types Pattern matching works on all datatypes Fall 2011 CSE341 Programming Languages 10 The 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 still must change your code but you 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 system Fall 2011 CSE341 Programming Languages 11 Purpose of the Value Restriction val 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 Fall 2011 CSE341 Programming Languages 12 Downside of the Value Restriction val 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 Fall 2011 CSE341 Programming Languages 13 Type inference sum fun sum xs case xs of 0 x xs x sum xs sum t1 t2 xs t1 t1 t2 t3 t4 t3 t1 x t3 xs t4 Fall 2011 CSE341 Programming Languages t5 list int t5 t5 list int t4 14 Type inference sum fun sum xs case xs of 0 x xs x sum xs sum t1 int t2 xs t1 x t3 int xs t4 t1 Fall 2011 t1 t2 int t3 t4 t1 t3 t1 CSE341 Programming Languages t5 int list int t5 t5 list int t4 15 Type inference sum fun sum xs case xs of 0 x xs x sum xs sum int list int xs int list x int xs t4 int list Fall 2011 t1 t2 int t3 t1 t4 t3 t1 CSE341 Programming Languages t5 int list int t5 t5 list int t4 16 Type inference length fun length xs case xs of 0 xs 1 length xs length t1 t2 xs t1 xs t3 Fall 2011 t1 t2 t3 t1 CSE341 Programming Languages t4 list int t4 list t3 17 Type inference length fun length xs case xs of 0 xs 1 length xs length t1 int t2 xs t1 xs t1 t3 Fall 2011 CSE341 Programming Languages t1 t2 t3 t1 t1 t4 list int t4 list t3 18 Type inference length fun length xs case xs of 0 xs 1 length xs length a t4 list int xs t4 list int xs t4 list t1 t2 t3 t1 t1 t4 list int t4 list t3 length works no matter what a is Fall 2011 CSE341 Programming Languages 19 Type inference compose fun compose f g fn x f g x compose f g x Fall 2011 t1 t2 t3 t1 t2 t4 t3 t2 t1 t5 CSE341 Programming Languages t4 t5 t4 t6 t6 t7 t7 20 Type inference compose fun …
View Full Document
Unlocking...