Lecture 05

​

Records, Variants,

Match Expressions

Programming Languages

UW CSE 341 - Spring 2021

What is a Programming Language?

• Syntax: How to write programs down (spelling and grammar)
• Semantics: What programs mean (type checking and evaluation)
• Idioms: Typical ways to use language features for common needs
• Libraries: What is “standard” and easily available
• Tools / Ecosystem: What support do you get?
• REPL, IDE, debugger, message board, governance, etc.

What is a Programming Language?

• Syntax: How to write programs down (spelling and grammar)
• Semantics: What programs mean (type checking and evaluation)
• Idioms: Typical ways to express common computations
• Libraries: What is “standard” and easily available
• Tools / Ecosystem: What support do you get?
• REPL, IDE, debugger, message board, governance, etc.

We will mostly focus on semantics and idioms

• Carefully thinking about these makes us better programmers in any language
• Other parts of a PL are important and interesting
• Especially when doing “real work”
• … but not my expertise 🤓

​

Building Types

• Already know many ways to build types
• Base types : bool int float string ...
• Type constructors : t1 * t2 t1 -> t2 t list t option
• Today: Define our own new types in ML
• Especially enumerations and trees
• Type structure often more important to program design than algorithms!
• But first: More generally way to think about types in any language

Anatomy of types in ANY Language

Languages generally provide three kinds of building blocks to define types

• Two ways to “combine” existing types t1, t2, ..., tN in a new type t
• “Each Of” : a value of type t contains values of each of t1, ..., tN
• “One Of” : a value of type t contains values of one of t1, ..., tN
• A way for values of type t to contain other (smaller) values of type t
• “Self Reference” : a value of type t can contain other t values

The ability to nest and mix-and-match makes these building blocks even more powerful!

😍 Composition 😍

Example Types From Building Blocks

• Tuples are each of : an int * bool contains an int and a bool
• Options are one of : an int option contains an int or no data
• Lists throw in self reference to use all three building blocks:
• An int list contains (an int and another int list) or no data
• Nesting lets us build all kinds of interesting types
• ((int * bool) option * (string list list)) option list

Example Types From Building Blocks

• Tuples are each of : an int * bool contains an int and a bool
• Options are one of : an int option contains an int or no data
• Lists throw in self reference to use all three building blocks:
• An int list either contains (an int and another int list) or no data
• Nesting lets us build all kinds of interesting types
• ((int * bool) option * (string list list)) option list

Types provide a compact language for expressing the “shape” of data!

Today: Records and Variants

• Records: a new way to build each-of types, a little different than tuples
• Named types
• Named fields
• Variants: a new way to build our own one-of types
• Named types
• E.g., can define a type whose values hold an int or a string
• To build variant values, type definitions include constructors like Some, None, ::, []
• Do not think Java constructors
• To use variant values, match expressions test and unpack them

Records : Define

Syntax: type t = { f1 : t1; … ; fN : tN }

• t1, …, tN are (already-defined) types
• f1, …, fN are field names (same “spelling” rules as variables)

Adds new (record) type t and fields f1, …, fN

• Types are in their own name space -- types don’t conflict with variables/functions, fields
• Field names are in their own name space -- fields don’t conflict with variables/functions, types
• However, can shadow earlier type and field name definitions ⚠️

Must define a record type before you can build or use

• That’s just OCaml’s rule (not fundamental)

Example

As usual, see the accompanying code

​

​

Records : Build

Syntax: { f1 = e1; … ; fN = eN }

• e1, …, eN are expressions
• f1, …, fN are field names

Type Checking

• If t is defined as type t = { f1 : t1; … ; fN : tN } and
• e1 has type t1 and … and eN has type tN
• Then { f1 = e1; … ; fN = eN } has type t
• Else, report error and fail

Elements separated by semicolons “ ; ” ⚠️

Get very weird error messages otherwise ⚠️

Records : Build

Syntax: { f1 = e1; … ; fN = eN }

• e1, …, eN are expressions
• f1, …, fN are field names

Evaluation

• If e1 evaluates to value v1 and … and eN evaluates to value vN
• Then { f1 : e1; … ; fN : eN } evaluates to { f1 = v1; … ; fN = vN }

​

Records of values are values.

Records : Use

Syntax: e.f

• Where is e is an expression and f is a field name

Type Checking

• If has e has type t and
• If t is defined as type t = {f1:t1; … ; f:tF; … ; fN:tN}
• Then e.f has type tF
• Else, report error and fail

Evaluation

• If e evaluates to { f1=v1; … ; f=vF; … ; fN=vN }
• Then e.f evaluates to vF

​

Tuples vs. Records

• Semantically, not much difference. Compare:
• (1, true, "three") versus {a=1; b=true; c="three"}
• Tuples a little shorter, records easier to remember “what is where” (self-documenting)
• Avoid large tuples and consider records when multiple fields have the same type
• Common language design question: By position (tuples) or by name (records)
• Functions do some of each: position for caller but name for callee

Today: Records and Variants

• Records: a new way to build each-of types, a little different than tuples
• Named types
• Named fields
• Variants: a new way to build our own one-of types
• Named types
• E.g., can define a type whose values hold an int or a string
• To build variant values, type definitions include constructors like Some, None, ::, []
• Do not think Java constructors
• To use variant values, match expressions test and unpack them

✅

Variants are not like records!

One-of types are not each-of types!

Enumerations

• Can use variant types to enumerate a fixed set of values for some new type
• The simplest use of variant types, which are much more powerful
• We start with this simplest use-case and build up quickly
• We name a new type and the values of that type are the constructors

​

​

type si_unit =

| Second | Meter | Kilogram | Ampere

| Kelvin | Mole | Candela

​

​

Variant definition syntax/semantics

• Syntax details:
• First | optional
• Constructors must start with capital
• Semantics: Adds to environment the type name and the constructors

type si_unit =

| Second | Meter | Kilogram | Ampere

| Kelvin | Mole | Candela

​

​

Build

• These 7 constructors are now values (and therefore expressions)
• 7 different ways to build a value of the new type si_unit
• There are no other values of the type si_unit
• E.g., [Second; Meter; Second] has type si_unit list

​

type si_unit =

| Second | Meter | Kilogram | Ampere

| Kelvin | Mole | Candela

​

​

Bool

• One of the simplest enumerations is our old friend the booleans
• Could almost be defined type bool = true | false
• Only issue is capitalization rule (the language violated their own rule)
• We can write type mybool = True | False

​

Anyway, we can now define enumerations and build values of them, so need a way to use values of them

Use variant types with match expressions

• match expression with one branch for each constructor
• Like a multi-way if, with one branch for each constructor
• Guides type-checking: all branches must have same type and every constructor must have a branch
• Guides evaluation rules: evaluate exactly one branch

let string_of_si_unit u =

match u with

| Second -> "second"

| Meter -> "meter"

| Kilogram -> "kilogram"

| Ampere -> "ampere"

| Kelvin -> "kelvin"

| Mole -> "mole"

| Candela -> "candela"

​

let s =

string_of_si_unit Ampere

Back to bool

• In fact, can use match expressions instead of conditional expressions
• Yes, this works in ML
• No, not good style
• Demonstrates that one feature (conditional expressions) can be explained entirely in terms of another more powerful feature (match expressions)
• The first (?) of many examples of “syntactic sugar”

match e1 with

| true -> e2

| false -> e3

​

if e1 then e2 else e3

​

Beyond enumerations

As promised, ML variant types are much more powerful

• Each constructor can carry data [or not]
• Type definition indicates the type of data each constructor carries
• Self-reference allowed in type definition
• Can carry “another of the same thing”
• See code for three examples
• A silly example to learn the syntax and semantics
• An example for different kinds of shapes
• An example that uses self-reference to define arithmetic-expression trees

Variants: Define

Syntax: type t = | C1 [of t1] | … | CN [of t1]

• t1, …, tN are types (and can include t inside them)
• C1, …, CN are constructors
• Remember [...] is metasyntax for optional

Adds new (variant) type t and constructors C1, …, CN

• Types are in their own name space
• Constructors are in their own name space
• However, can shadow earlier type and constructor definitions ⚠️

Must define a variant type before you can build or use

​

type silly =

| A of int * bool * string list

| Foo of string

| Pizza

​

Variants: Build

Syntax: C e

​

Type-checking:

• If C is in the environment due to type t = … | C of tC | …
• And e has type tC (must provide correct arguments to C)
• Then C e has type t
• Else does not type-check

​

Evaluation: Evaluate e to a value v and C v is a value

• “Tags the data v with a C”, producing a value of type t

​

type silly =

| A of int * bool * string list

| Foo of string

| Pizza

​

Match expressions, the big picture

A powerful and concise expression form that combines three things:

1. A multiway conditional that branches based on which variant of a one-of type you have
2. Extract the underlying data that was “tagged” with a constructor
3. Bind the extracted data to local variables that can then be used in the chosen conditional branch

This is elegant (once you get used to it) and avoids errors like forgetting cases or trying to extract the “wrong” data for the tag you have

Variants: Use

[will generalize this soon!]

Syntax:

match e with P1 -> e1 | … | PN -> eN

• Where e, e1, …, eN are expressions
• Where P1, …, PN are patterns

For now, each pattern should be one of these:

• C if C is a constructor that carries no data
• C (x1,x2,…,xn) if C is a constructor that carries an n-tuple of data
• C x otherwise

where x1, …, xn and x are variables

type silly =

| A of int * bool * string list

| Foo of string

| Pizza

​

Patterns

Patterns are not expressions, even though they kind of look like them

They are used for matching and to bind local variables when they match

Evaluation rules (again, will generalize soon)

match e with P1 -> e1 | … | PN -> eN

1. Evaluate e to some C v or just C
2. Find the pattern Pi made with constructor C.
3. Create local bindings
• C matching C creates no bindings
• C v matching C x creates x bound to v
• C(v1,...,vn) matching C(x1,...,xn) creates x1 bound to v1, ... , xn bound to vn
4. Evaluate the corresponding ei using these local bindings to produce an overall result

Type-checking

Lots going on, toward two goals:

1. All the types to work out so the evaluation rules won’t “run into problems”
2. Require one pattern for each constructor
• Don’t forget any
• Don’t repeat any

Type-checking

match e with P1 -> e1 | … | PN -> eN

1. Typecheck e to some type t where type t = | C1 [of t1] | … | CN [of t1]
2. For each constructor C1 ,…, CN
1. Require exactly one pattern uses Ci
2. Require the pattern has “the right number of variables”
3. Require the corresponding ei type-checks in an environment where the variable(s) in the pattern have the type(s) indicating in the variant type definition
3. All ei need to have the same type and that is the overall type