CSE341: Programming Languages Lecture 4 Records (“each of”), Datatypes (“one of”), Case Expressions Dan Grossman Fall 2011Review • Done: functions, tuples, lists, local bindings, options • Done: syntax vs. semantics, environments, mutation-free • Today: Focus on compound types – New feature: records • New concept: syntactic sugar (tuples are records) – New features: datatypes, constructors, case expressions Fall 2011 2 CSE341: Programming LanguagesHow to build bigger types • Already know: – Have various base types like int bool unit char – Ways to build (nested) compound types: tuples, lists, options • Today: more ways to build compound types • First: 3 most important type building blocks in any language – “Each of”: A t value contains values of each of t1 t2 … tn – “One of”: A t value contains values of one of t1 t2 … tn – “Self reference”: A t value can refer to other t values Remarkable: A lot of data can be described with just these building blocks Note: These are not the common names for these concepts Fall 2011 3 CSE341: Programming LanguagesExamples • Tuples build each-of types – int * bool contains an int and a bool • Options build one-of types – int option contains an int or it contains no data • Lists use all three building blocks – int list contains an int and another int list or it contains no data • And of course we can nest compound types – ((int * int) option) * (int list list)) option Fall 2011 4 CSE341: Programming LanguagesRest of today • Another way to build each-of types in ML – Records: have named fields – Connection to tuples and idea of syntactic sugar • A way to build and use our own one-of types in ML – For example, a type that contains and int or a string – Will lead to pattern-matching (more next lecture), one of ML’s coolest and strangest-to-Java-programmers features – How OOP does one-of types discussed later in course Fall 2011 5 CSE341: Programming LanguagesRecords Record values have fields (any name) holding values Record types have fields (and name) holding types The order of fields in a record value or type never matters – REPL alphabetizes fields just for consistency Building records: Accessing components: (Evaluation rules and type-checking as expected) Fall 2011 6 CSE341: Programming Languages {f1 = v1, …, fn = vn} {f1 : t1, …, fn : tn} {f1 = e1, …, fn = en} #myfieldname eExample Evaluates to And has type If some expression such as a variable x has this type, then get fields with: Note we didn’t have to declare any record types – The same program could also make a {id=true,ego=false} of type {id:bool,ego:bool} Fall 2011 7 CSE341: Programming Languages {name = “Amelia”, id = 41123 - 12} {id = 41111, name = “Amelia”} {id : int, name : string} #id x #name xBy name vs. by position • Little difference between (4,7,9) and {f=4,g=7,h=9} – Tuples a little shorter – Records a little easier to remember “what is where” – Generally a matter of taste, but for many (6? 8? 12?) fields, a record is usually a better choice • A common decision for a construct’s syntax is whether to refer to things by position (as in tuples) or by some (field) name (as with records) – A common hybrid is like with Java method arguments (and ML functions as used so far): • Caller uses position • Callee uses variables • Could totally do it differently; some languages have Fall 2011 8 CSE341: Programming LanguagesThe truth about tuples Last week we gave tuples syntax, type-checking rules, and evaluation rules But we could have done this instead: – Tuple syntax is just a different way to write certain records – (e1,…,en) is another way of writing {1=e1,…,n=en} – t1*…*tn is another way of writing {1:t1,…,n:tn} – In other words, records with field names 1, 2, … In fact, this is how ML actually defines tuples – Other than special syntax in programs and printing, they don’t exist – You really can write {1=4,2=7,3=9}, but it’s bad style Fall 2011 9 CSE341: Programming LanguagesSyntactic sugar “Tuples are just syntactic sugar for records with fields named 1, 2, … n” • Syntactic: Can describe the semantics entirely by the corresponding record syntax • Sugar: They make the language sweeter Will see many more examples of syntactic sugar – They simplify understanding the language – They simplify implementing the language Why? Because there are fewer semantics to worry about even though we have the syntactic convenience of tuples Fall 2011 10 CSE341: Programming LanguagesDatatype bindings A “strange” (?) and totally awesome (!) way to make one-of types: – A datatype binding Fall 2011 11 CSE341: Programming Languages datatype mytype = TwoInts of int * int | Str of string | Pizza • Adds a new type mytype to the environment • Adds constructors to the environment: TwoInts, Str, and Pizza • A constructor is (among other things), a function that makes values of the new type (or is a value of the new type): – TwoInts : int * int -> mytype – Str : string -> mytype – Pizza : mytypeThe values we make • Any value of type mytype is made from one of the constructors • The value contains: − A “tag” for “which constructor” (e.g., TwoInts) − The corresponding data (e.g., (7,9)) − Examples: − TwoInts(3+4,5+4) evaluates to TwoInts(7,9) − Str(if true then “hi” else “bye”) evaluates to Str(“hi”) − Pizza is a value Fall 2011 12 CSE341: Programming Languages datatype mytype = TwoInts of int * int | Str of string | PizzaUsing them So we know how to build datatype values; need to access them There are two aspects to accessing a datatype value 1. Check what variant it is (what constructor made it) 2. Extract the data (if that variant has any) Notice how our other one-of types used functions for this: • null and iSome check variants • hd, tl, and valOf extract data (raise exception on wrong variant) ML could have done the same for datatype bindings – For example, functions like “isStr” and “getStrData” – Instead it did something better Fall 2011 13 CSE341: Programming LanguagesCase ML combines the two aspects of accessing a one-of value with a case expression and pattern-matching – Pattern-matching much more general/powerful (lecture 5)
View Full Document