CSE 341, Spring 2008, Lecture 4 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.Programming languages need ways to describe data so that we can write programs that operate on thatdata. We need base types such as int, string, bool, and unit. We also need ways to build compound typesfrom simpler types, such as tuples (pairs are 2-tuples, triples are 3-tuples, etc.), lists, and even functiontypes (->). This lecture is about record types, which are much like tuples, and datatype bindings, whichare probably unlike anything you have seen before. Conceptually, this lecture is about describing data interms of and (“each-of” types), or (“one-of” types), and self-reference (“recursive” types).Syntactically, an ML record is constructed via {f1=e1, ..., f2=en} where f1, ... fn are field names(sequences of letters) and e1, ..., en are expressions. Exactly like tuples, the evaluation rules are to evaluatethe expressions to values and a record with values in all fields is itself a value. The only difference fromtuples is that the order of the fields does not matter; we use field names instead of “position” to determinewhich field is which. Unlike in many languages, we do not need any sort of type declaration be fore we usea record; we can just use whatever field names we want. The type of a record describes what fields it hasand what types those fields have. Again, field order does not matter; in fact, the read-eval-print loop alwaysalphab e tizes field names before it prints a type. To extract a field foo from a record, we can use #foo ewhere e evaluates to a record.Tuples are, in fact, so much like records that they actually are records. When you write (7,"hi"),that is exactly the same as writing {1=7, 2="hi"}. The type int*string is just another way of writing{1:int, 2:string}. Now, using the tuple syntax is cleaner and better style, but it is still an elegantlanguage design to have it really just be another language feature (records). That way, the designer andimplementor of the language has less work to do; we can completely define how tuples behave by explaininghow they are really just a different syntax for particular records. This is our first example of the ideaof syntactic sugar, a piece of the language that is just a prettier way of writing something already in thelanguage. It is syntactic because it is just a different way of writing something, and it is sugar because itmakes the language sweeter.Let us now return to building c ompound types in terms of “each of”, “one of”, and “self reference”.Each-of types are often the simplest for people to understand. They are like records, or Java classes withonly fields. Given types t1, t2, t3, we make some new type t that “has” each of t1, t2, and t3. “One of”types are just as im portant; it is very common to have a type t that “has” either t1, t2, or t3. As we willdiscuss near the end of the course, in object-oriented languages like Java, one uses subclassing to implement“one of” types. Finally, self-reference is necessary to describe recursive data structures like lists and trees.We have actually seen examples of each kind of compound type in earlier lectures. int * bool is aneach-of type; e ach value of this type has an int and a bool. int option is a one-of type; each value ofthis type either has an int or it does not. int list is a compound type using all three notions: a valueof type int list has either no data (the empty list) or it has an int and another int list (notice theself-reference).In ML, you use a datatype binding to create a new one-of type that comes with constructors and patternsfor building and accessing values of the new type, respectively. A silly example of such a binding is:datatype mytype = TwoInts of int * int| Str of string| PizzaThis binding creates a new type mytype with 3 variants. A value of type mytype is created in one of 3 ways:(1) By using the constructor TwoInts on a pair of ints, (2) By using the c onstructor Str on a string, or (3)By using the constructor Pizza on nothing. In this sense, constructors are functions (if they take arguments)or constants (if they do not). In our example, the datatype binding adds to the environment/context: (1)TwoInts of type int * int -> mytype, (2) Str of type string -> mytype, and (3) Pizza of type mytype.As with any other function, an argument to a constructor can be any expression of the correct type.So constructors give us a way to make values of a datatype such as mytype, but we also need a way to usesuch values after we make them. Doing so requires two kinds of operations: (1) tests to see which variant1we have and (2) op e rations that extract the values that a particular variant has. We have already seen suchoperations for options and lists. The functions null and isSome are variant tests. The functions valOf, hd,and tl are the data extractors. Notice they raise exceptions if applied to a value of an unexpected variant.A datatype binding does not directly create variant tests and data extractors. Instead, ML uses pat-tern matching, an elegant and convenient feature that combines the variant test and data extraction. Bycombining them, the type-checker can check that you do not forget any cases or duplicate any cases.Pattern-matching is done with a case-expression. The syntax iscase e0 ofp1 => e1| ...| pn => enwhere e0, e1, ..., en are expressions and p1, ..., pn are patterns. We have not seen patterns before. Theylook a lot like expressions syntactically, but they are more restrictive and their semantics is very different.Here is a function using pattern matching and our previous datatype example:fun f2 x = (* f2 has type mytype -> int *)case x ofPizza => 3| TwoInts(i1,i2) => i1 + i2| Str s => 8The semantics of a case-expression is to evaluate the expression between the case and of to some valuev and then proceed through the patterns in order, finding the first one that matches. For now, a pattern-matches if the constructor in it is the same as the constructor for the value v. For example, if the value ifTwoInts(7,9), then the first pattern would not match and the second one would. We evaluate the expressionto the right of the matching pattern (on the other side of the =>) and that result is the result of the
View Full Document
Unlocking...