CSE 341:Programming LanguagesAutumn 2005Lecture 4 — Mutation; “one-of” types; user-defined typesCSE 341 Autumn 2005, Lecture 4 1Where are we• Done features: functions, tuples, lists, options, local bindings• Done concepts: syntax vs. semantics, environments• Today features: record types, datatypes, type synonyms,pattern-matching• Today concepts: Mutation-free, “one-of” types,constructors/destructors, case-coverageCSE 341 Autumn 2005, Lecture 4 2You want to chan ge something?There is no way to mutate (assign to) a binding, pair component, orlist element.How could the lack of a feature make programming easier?In this case:• Amount of sharing is indistinguishable– Aliasing irrelevant to correctness!• Bindings are invariant across function application– Mutation breaks compositional reasoning, a (the?) intellectualtool of engineeringCSE 341 Autumn 2005, Lecture 4 3Base types and compound typesLanguages typically provide a small number of “built-in” types andways to build compound types out of simpler ones:• Base types examples: int, bool• Type builder examples: tuples, lists, recordsBase types clutter a language definition; better to make them librarieswhen possible.• ML does this to a remarkable extent (e.g., we will soon defineaway bool and conditionals)Good to let programmers bind types to type names, just like we bindvalues to variables.CSE 341 Autumn 2005, Lecture 4 4Compound- type flavorsConceptually, just a few ways to build compound types:1. “Each-of”: A t contains a t1 and a t22. “One-of”: A t contains a t1 or a t23. “Self-reference”: The definition of t may refer to tExamples:• int * bool• int option• int listRemarkable: A lot of data can be described this way.Convenient to think of as trees.(optional) jargon: Product types, sum types, recursive typesCSE 341 Autumn 2005, Lecture 4 5User-defined typesThere are many reasons to define your own types:1. Using a tuple with 12 fields is incomprehensible2. Writing down large types is unpleasant; we have computers forthat3. Large programs can use abstract types to be robust to change• A couple weeks ahead4. So the language doesn’t have to “bake in” lists and options and. . .CSE 341 Autumn 2005, Lecture 4 6DatatypeOne-of types are less similar across languages• We’ll discuss OO’s approach to one-of in a few weeksIn ML, we use make a new type with a datatype binding, e.g.:datatype mytype = TwoInts of int*int| Str of string| PizzaSemantics: Extend the environment with three constructors (in part,functions/constants that produce values of type mytype)So we have a way to build them... what’s missing?CSE 341 Autumn 2005, Lecture 4 7The old wayFor lists, we had a way to:• Test which variant a value was• Extract the values from value-carrying variants– Makes no sense if you have the wrong variantWhat would this look like for mytype?CSE 341 Autumn 2005, Lecture 4 8The new wayRather than add variant-tests and variant-destructors (non-standardjargon and nothing to do with C++ destructors), ML has a caseexpression that uses pattern-matching.In its simplest form, case has one pattern for each constructor in adataype and binds one variable for each value carried. Example:case e ofTwoInts(i1,i2) => e1| Str s => e2| Pizza => e3What are the typing rules?What are the evaluation rules?CSE 341 Autumn 2005, Lecture 4 9Type-checking caseIn addition to binding local variables and requiring branches to havethe same type, the typing rules for case prevent some run-time errors:• Exhaustiveness: No test can “fail” (a warning)• Redundancy: No test can be “impossible” (an error)So far, case gives us what we need to use datatypes:• A (combined) way to test variants and extract values• Powerful enough to define our own tests and destructorsIn fact, pattern-matching is far more general and elegant:• Can use it for datatypes already in the top-level environment• Can use it for any type (later)• Can have deep patterns (later)CSE 341 Autumn 2005, Lecture 4
View Full Document
Unlocking...