CSE 341, Winter 2008, Lecture 9 SummaryStandard Disclaimer: These comments may prove useful, but certainly are not a complete summary ofall the important stuff we did in class. They may make little sense if you missed class, but hopefully will helpyou organize and process what you have learned.We continue describing programming idioms enabled by function closures.Implementing an Abstract Data TypeThe key to an abstract data type is requiring clients to use it via a collection of functions rather thandirectly accessing its private s tate. Thanks to this abstraction, we can later change how the data typeis implemented without changing how it behaves for clients. In an object-oriented language, you mightimplement an abstract data type be defining a class with all private fields (inaccessible to clients) and somepublic methods (the interface with clients). We can do the same thing in ML with a record of closures;the variables that the closures use from the environment correspond to the private fields. Admittedly,this programming idiom can appear very fancy/clever/subtle, but it suggests (correctly) that functionalprogramming and object-oriented programming are more similar than they might first appear (a topic wewill revisit later in the course; there are important differences).As an example, consider an implementation of a set of integers that supports creating a new bigger setand seeing if an integer is in a set. Our sets are mutation-free in the sense that adding an integer to a setproduces a new, different set. In ML, we could define a type that describes this interface:datatype set = S of { add : int -> set, member : int -> bool }Roughly sp e aking, a set is a record with two fields, each of which holds a function. It would be simpler towrite:type set = { add : int -> set, member : int -> bool }but this does not work in ML because type bindings cannot be recursive. So we have to deal with themild inconvenience of having a constructor S around our record of functions defining a set. Notice we arenot using any new types or features; we simply have a type describing a record with fields named add andmember, each of which holds a function.Once we have an empty set, we can use its add field to create a one-element set, and then use that set’sadd field to create a two-element set and so on. So the only other thing our interface needs is a binding likethis:val empty_set = ... : setBefore implementing this interface, let’s see how a client might use it:fun use_a_set () =let val S s1 = empty_setval S s2 = (#add s1) 34val S s3 = (#add s2) 19inif (#member s3) 42then 99else if (#member s3) 19then 17else 0endAgain we are using no new features. #add s1 is reading a record field, which in this case produces a functionthat we can then call with 34. If we were in Java, we might write s1.add(34) to do something similar. Theval bindings use pattern-matching to “get rid of” the S constructors on values of type set.There are many ways we could define empty_set; they will all use the technique of using a closure to“remember” what elements a set has. He re is one way:1val empty_set =let fun exists(j,lst) = (* could use currying and/or fold to be fancier *)case lst of[] => false| hd::tl => j=hd orelse exists(j,tl)fun make_set lst = (* lst is a "private field" *)S { add = fn i => make_set (i::lst),member = fn i => exists (i,lst) }inmake_set []endThe helper function exists just sees if a list has an element; we could also just use List.exists in thestandard library. All the fanciness is in make_set and empty_set is just the record returned by make_set [].What make_set returns is a value of type set. It is essentially a record with two functions. The closuresproduced from fn i => make_set (i::lst) and fn i => exists (i,lst) are values that when called uselst — which is the “private field” we need to produce either a bool (for member) or a new set (for add).CallbacksAnother common idiom is to implement a library that detects when “events” occur and informs clientsthat have previously “registered” their interest in hearing about events. Clients c an register their interestby providing a “callback” — a function that gets called when the event occurs. Examples of events forwhich you might want this sort of library include things like users moving the mouse or pressing a key. Dataarriving from a network interface is another example.The purpose of these libraries is to allow multiple clients to register callbacks. The library implementerhas no idea what clients need to compute when an event occurs, and the clients may need “extra data” todo the computation. So the library implementor should not restrict what “extra data” each client uses. Aclosure is ideal for this because a function’s type t1 -> t2 doesn’t specify the types of any other variablesa closure uses, so we can put the “extra data” in the closure’s environment.If you have used “event listeners” in Java’s Swing library, then you have used this idiom in an object-oriented setting. In Java, you get “extra data” by defining a subclass with additional fields. This can takean awful lot of keystrokes for a simple listener, which is a (the?) main reason the Java language addedanonymous inner classes (which you do not need to know ab out for this course), which are closer to theconvenience of closures.To see an example in ML, we will finally introduce ML’s supp ort for mutation. Mutation is okay in somesettings. In this case, we really do want registering a callback to “change the state of the world” — whenan event occurs, there are now more callbacks to invoke. In ML, most things really cannot be mutated.Instead you must create a reference, which is a container whose contents can be changed. You create a newreference with the expression ref e (the initial contents are the result of evaluating e). You get a referencer’s current contents with !r (not to be confused with negation in Java or C), and you change r’s contentswith r := e. The type of a reference that contains values of type t is written t ref.Our example will use the idea that callbacks should be called when a key on the keyboard is pressed.We will pass the callbacks an int that enco des which key it was. Our interface just needs a way to registercallbacks. (In a real library, you might also want a way to unregister them.)val onKeyEvent : (int -> unit) -> unitClients will pass a int -> unit that, when called later with an int
View Full Document
Unlocking...