6 of 73

Building Types

We have studied several types already

Base types : bool int float string unit
Compound types : t1 * t2 t list t option

Today: how to design and define our own types

This way we can get exactly what we want 🤩
Easier to read and implement functions over well-designed data types
Type definitions in OCaml provide mechanisms for building values of those type : constructors
Will need a general mechanism for use (accessing their pieces) : pattern matching

7 of 73

Building Types

We have studied several types already

Base types : bool int float string unit
Compound types : t1 * t2 t list t option

Today: how to design and define our own types

This way we can get exactly what we want 🤩
Easier to read and implement functions over well-designed data types
Type definitions in OCaml provide mechanisms for building values of those type : constructors
Will need a general mechanism for use (accessing their pieces) : pattern matching

Show me your flowchart and conceal your tables, and I shall continue to be mystified. Show me your tables, and I won't usually need your flowchart; it'll be obvious.

-- Fred Brooks in The Mythical Man Month (1975)

8 of 73

Building Types

We have studied several types already

Base types : bool int float string unit
Compound types : t1 * t2 t list t option

Today: how to design and define our own types

This way we can get exactly what we want 🤩
Easier to read and implement functions over well-designed data types
Type definitions in OCaml provide mechanisms for building values of those type : constructors
Will need a general mechanism for use (accessing their pieces) : pattern matching

Show me your flowchart and conceal your tables, and I shall continue to be mystified. Show me your tables, and I won't usually need your flowchart; it'll be obvious.

-- Fred Brooks in The Mythical Man Month (1975)

Good programmers worry more about data structures and their relationships and less about code.

9 of 73

Anatomy of a Datatype in ANY Language

Languages generally provide three building blocks for defining types
Two ways to “combine” existing types t1, t2, …, tN into a new type t

“Each Of” : a value of type t contains values of each of t1, t2, …, tN
“One Of” : a value of type t contains values of one of t1, t2, …, tN

The ability for values a type t to contain smaller values of type t

“Self Reference” : a value of type t can contain other t values

10 of 73

Anatomy of a Datatype in ANY Language

Languages generally provide three building blocks for defining types
Two ways to “combine” existing types t1, t2, …, tN into a new type t

“Each Of” : a value of type t contains values of each of t1, t2, …, tN
“One Of” : a value of type t contains values of one of t1, t2, …, tN

The ability for values a type t to contain 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 😍

11 of 73

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

12 of 73

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!

13 of 73

Today: Records and Variants

Records : a new way to build each-of types

Record values are built roughly similar to tuples, except with named fields
Unlike tuples, can access any field (use any part) of a record by its name

Variants : a way to build our own one-of types

For example, we will be able to define a type whose values contain an int or a string
Variant values are built using constructors we define, like Some, None, ::, []
To use variant values we need a mechanism to test and unpack them: pattern matching

14 of 73

Records : Define

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

Where t1, …, tN are (already-defined) types
Where f1, …, fN are field names (same rules as for variable names)

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, you can shadow earlier type and field name definitions ⚠️

Must define a record type before you can build or use

15 of 73

Records : Define

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

Where t1, …, tN are (already-defined) types
Where f1, …, fN are field names (same rules as for variable names)

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, you can shadow earlier type and field name definitions ⚠️

Must define a record type before you can build or use

There are ≈ 11 name spaces in OCaml 😳

16 of 73

Records : Build

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

Where e1, …, eN are expressions

Type Checking

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

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 }

17 of 73

Records : Build

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

Where e1, …, eN are expressions

Type Checking

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

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 }

Elements separated by semicolons “ ; ” ⚠️

Get very weird error messages otherwise ⚠️

18 of 73

Records : Build

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

Where e1, …, eN are expressions

Type Checking

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

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.

Elements separated by semicolons “ ; ” ⚠️

Get very weird error messages otherwise ⚠️

19 of 73

Records : Use

Syntax: e.f

Where is e is an expression

Type Checking

If has e has type t and
If t is a record type 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

20 of 73

Records : Use

Syntax: e.f

Where is e is an expression

Type Checking

If has e has type t and
If t is a record type 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

We can access any part of a record!

21 of 73

Record Example

type lava_lamp =

{ height : float

; color_liquid : string

; color_lava : string }

let my_lamp =

{ height = 13.5 +. 1.0

; color_liquid = "bl" ^ "ue"

; color_lava = "" ^ "green" ^ "" }

let a = my_lamp.height

let b = my_lamp.color_liquid

let c = my_lamp.color_lava

22 of 73

Record Example

type lava_lamp =

{ height : float

; color_liquid : string

; color_lava : string }

let my_lamp =

{ height = 13.5 +. 1.0

; color_liquid = "bl" ^ "ue"

; color_lava = "" ^ "green" ^ "" }

let a = my_lamp.height

let b = my_lamp.color_liquid

let c = my_lamp.color_lava

type lava_lamp = {

height : float;

color_liquid : string;

color_lava : string;

}

val my_lamp : lava_lamp = {

height = 14.5;

color_liquid = "blue";

color_lava = "green"

}

val a : float = 14.5

val b : string = "blue"

val c : string = "green"

23 of 73

Record Example

type lava_lamp =

{ height : float

; color_liquid : string

; color_lava : string }

let my_lamp =

{ height = 13.5 +. 1.0

; color_liquid = "bl" ^ "ue"

; color_lava = "" ^ "green" ^ "" }

let a = my_lamp.height

let b = my_lamp.color_liquid

let c = my_lamp.color_lava

type lava_lamp = {

height : float;

color_liquid : string;

color_lava : string;

}

val my_lamp : lava_lamp = {

height = 14.5;

color_liquid = "blue";

color_lava = "green"

}

val a : float = 14.5

val b : string = "blue"

val c : string = "green"

Style: keep field names unique for each record type

Can get really confusing error message otherwise ⚠️

24 of 73

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 usually use records when multiple fields have the same type

Common language design question

By position (tuples) or by name (records) ?

Functions sort of do both: position for caller but name for callee

25 of 73

Today: Records and Variants

Records : a new way to build each-of types ✅

Record values are built roughly similar to tuples, except with named fields
Unlike tuples, can access any field (use any part) of a record by its name

Variants : a way to build our own one-of types

For example, we will be able to define a type whose values contain an int or a string
Variant values are built using constructors we define, like Some, None, ::, []
To use variant values we need a mechanism to test and unpack them: pattern matching

26 of 73

Variant Examples : Enumerations (SI Units)

type si_unit =

| Second | Meter | Kilogram | Ampere

| Kelvin | Mole | Candela

let string_of_si_unit (u: si_unit) : string =

match u with

| Second -> "second"

| Meter -> "meter"

| Kilogram -> "kilogram"

| Ampere -> "ampere"

| Kelvin -> "kelvin"

| Mole -> "mole"

| Candela -> "candela"

let s = string_of_si_unit Ampere

27 of 73

Variant Examples : Enumerations (SI Units)

type si_unit =

| Second | Meter | Kilogram | Ampere

| Kelvin | Mole | Candela

let string_of_si_unit (u: si_unit) : string =

match u with

| Second -> "second"

| Meter -> "meter"

| Kilogram -> "kilogram"

| Ampere -> "ampere"

| Kelvin -> "kelvin"

| Mole -> "mole"

| Candela -> "candela"

let s = string_of_si_unit Ampere

type si_unit =

Second | Meter | Kilogram | Ampere |

Kelvin | Mole | Candela

val string_of_si_unit :

si_unit -> string = <fun>

val s : string = "ampere"

28 of 73

Variant Examples : Enumerations (SI Units)

type si_unit =

| Second | Meter | Kilogram | Ampere

| Kelvin | Mole | Candela

let string_of_si_unit (u: si_unit) : string =

match u with

| Second -> "second"

| Meter -> "meter"

| Kilogram -> "kilogram"

| Ampere -> "ampere"

| Kelvin -> "kelvin"

| Mole -> "mole"

| Candela -> "candela"

let s = string_of_si_unit Ampere

type si_unit =

Second | Meter | Kilogram | Ampere |

Kelvin | Mole | Candela

val string_of_si_unit :

si_unit -> string = <fun>

val s : string = "ampere"

First pipe (“|”) is optional

Use with pattern match

Build with constructor

29 of 73

Variant Examples : Enumerations (SI Prefixes)

type si_prefix =

| Giga | Mega | Kilo

| Milli | Micro | Nano

let scale (p : si_prefix) : float =

match p with

| Giga -> 1e9

| Mega -> 1e6

| Kilo -> 1e3

| Milli -> 1e-3

| Micro -> 1e-6

| Nano -> 1e-9

let s = scale Giga

type si_prefix =

Giga | Mega | Kilo |

Milli | Micro | Nano

val scale :

si_prefix -> float = <fun>

val s : float = 1000000000.

30 of 73

Variant Examples : Shapes From Points

type pt = float * float

type shape =

| Circle of pt * float

| Rectangle of pt * pt

| Triangle of pt * pt * pt

let area (s : shape) : float = match s with

| Circle (center, radius) ->

Float.pi *. radius *. radius

| Rectangle ((x1, y1), (x2, y2)) ->

Float.abs ((x2 -. x1) *. (y2 -. y1))

| Triangle ((x1, y1), (x2, y2), (x3, y3)) ->

let a = x1 *. (y2 -. y3) in

let b = x2 *. (y3 -. y1) in

let c = x3 *. (y1 -. y2) in

Float.abs ((a +. b +. c) /. 2.0)

type pt = float * float

type shape =

Circle of pt * float

| Rectangle of pt * pt

| Triangle of pt * pt * pt

val area : shape -> float = <fun>

val a : float = 4.5

let a = area (Triangle ( (0.0, 0.0)

, (0.0, 3.0)

, (3.0, 0.0)))

31 of 73

Variant Examples : Shapes From Points

type pt = float * float

type shape =

| Circle of pt * float

| Rectangle of pt * pt

| Triangle of pt * pt * pt

let area (s : shape) : float = match s with

| Circle (center, radius) ->

Float.pi *. radius *. radius

| Rectangle ((x1, y1), (x2, y2)) ->

Float.abs ((x2 -. x1) *. (y2 -. y1))

| Triangle ((x1, y1), (x2, y2), (x3, y3)) ->

let a = x1 *. (y2 -. y3) in

let b = x2 *. (y3 -. y1) in

let c = x3 *. (y1 -. y2) in

Float.abs ((a +. b +. c) /. 2.0)

type pt = float * float

type shape =

Circle of pt * float

| Rectangle of pt * pt

| Triangle of pt * pt * pt

val area : shape -> float = <fun>

val a : float = 4.5

let a = area (Triangle ( (0.0, 0.0)

, (0.0, 3.0)

, (3.0, 0.0)))

Constructors just “tag” their arguments

32 of 73

Variants : Define

Syntax: type t = C1 of t1 | … | CN of tN

Where t1, …, tN are types (self reference: t can appear in these type arguments!)
Where C1, …, CN are constructors (name must start with capital letter)

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

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

Must define a variant type before you can build or use

33 of 73

Variants : Define

Syntax: type t = C1 of t1 | … | CN of tN

Where t1, …, tN are types (self reference: t can appear in these type arguments!)
Where C1, …, CN are constructors (name must start with capital letter)

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

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

Must define a variant type before you can build or use

Constructor parameters are optional.

34 of 73

Variants : Define

Syntax: type t = C1 of t1 | … | CN of tN

Where t1, …, tN are types (self reference: t can appear in these type arguments!)
Where C1, …, CN are constructors (name must start with capital letter)

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

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

Must define a variant type before you can build or use

Constructor parameters are optional.

Constructors that don’t take any arguments are just values of their type.

35 of 73

Variants : Build

Syntax: C e

Where C is a constructor and e is an expression

Type Checking

If t is a variant type defined as type t = C1 of t1 | … | C of tC | … | CN of tN
If has e has type tC
Then C e has type t
Else, report error and fail

Evaluation

If e evaluates to value v
Then C e evaluates to C v

36 of 73

Variants : Build

Syntax: C e

Where C is a constructor and e is an expression

Type Checking

If t is a variant type defined as type t = C1 of t1 | … | C of tC | … | CN of tN
If has e has type tC
Then C e has type t
Else, report error and fail

Evaluation

If e evaluates to value v
Then C e evaluates to C v

Values “tagged with a constructor” are values!

37 of 73

Variants : Build

Syntax: C e

Where C is a constructor and e is an expression

Type Checking

If t is a variant type defined as type t = C1 of t1 | … | C of tC | … | CN of tN
If has e has type tC
Then C e has type t
Else, report error and fail

Evaluation

If e evaluates to value v
Then C e evaluates to C v

Values “tagged with a constructor” are values!

Constructors are NOT functions!

They don’t have a function body or other code
They don’t evaluate, just “tag some data”

Instead, each constructor of a variant type t is more like

a “tag” that can make some kind of data also belong to t.

38 of 73

Variants : Build (Constructor with No Arguments)

Syntax: C

Where C is a constructor

Type Checking

If t is a variant type defined as type t = C1 of t1 | … | C | … | CN of tN
Then C has type t
Else, report error and fail

Evaluation

C is a value (nothing to do!)

39 of 73

Variants : Build (Constructor with No Arguments)

Syntax: C

Where C is a constructor

Type Checking

If t is a variant type defined as type t = C1 of t1 | … | C | … | CN of tN
Then C has type t
Else, report error and fail

Evaluation

C is a value (nothing to do!)

Again, this only for constructors with no arguments!

40 of 73

Variants : Use

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

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

41 of 73

Variants : Use

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

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

A pattern is one of (syntax)

x : a variable
(p1, …, pN) : a tuple of patterns pi
C p : a constructor C applied to a pattern p

42 of 73

Variants : Use

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

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

A pattern is one of (syntax)

x : a variable
(p1, …, pN) : a tuple of patterns pi
C p : a constructor C applied to a pattern p

Patterns are NOT expressions!

(though they kinda look like expressions)

43 of 73

Variants : Use

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

Type Checking

If t0 is a variant type defined as type t0 = C1 of t1 | … | CN of tN
If e has type t0 and each pattern Pi matches values of type t0
If in each case Pi -> ei, expression ei has type t
Then match e with P1 -> e1 | … | PN -> eN has type t
Else, report error and fail

44 of 73

Variants : Use

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

Type Checking

If t0 is a variant type defined as type t0 = C1 of t1 | … | CN of tN
If e has type t0 and each pattern Pi matches values of type t0
If in each case Pi -> ei, expression ei has type t
Then match e with P1 -> e1 | … | PN -> eN has type t
Else, report error and fail

Like conditionals, all branches must have the same type t!

45 of 73

Variants : Use

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

Type Checking

If t0 is a variant type defined as type t0 = C1 of t1 | … | CN of tN
If e has type t0 and each pattern Pi matches values of type t0
If in each case Pi -> ei, expression ei has type t
Then match e with P1 -> e1 | … | PN -> eN has type t
Else, report error and fail

Need to define:

How patterns match
How cases type check

46 of 73

Variants : Use

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

Type Checking

If t0 is a variant type defined as type t0 = C1 of t1 | … | CN of tN
If e has type t0 and each pattern Pi matches values of type t0
If in each case Pi -> ei, expression ei has type t
Then match e with P1 -> e1 | … | PN -> eN has type t
Else, report error and fail

Need to define:

How patterns match
How cases type check

Notice pattern (😂): we keep breaking language features down into smaller pieces that are easier to precisely define!

47 of 73

Variants : Use

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

Type Checking

If t0 is a variant type defined as type t0 = C1 of t1 | … | CN of tN
If e has type t0 and each pattern Pi matches values of type t0
If in each case Pi -> ei, expression e has type t
Then match e with P1 -> e1 | … | PN -> eN has type t
Else, report error and fail

Need to define:

How patterns match
How cases type check

Rules for matching pattern p against value v of type tV:

If p is a variable xP

Then p matches v (variable patterns always match any value)

Bind xP ↦ tV in the static environment
Bind xP ↦ v in the dynamic environment

If p is a tuple pattern (p1, …, pN)

Then p matches v if v = (v1, …, vN) AND all pi match vi

Introduce bindings from recursively matching all pi against vi

If p is a constructor applied to another pattern C pP

Then p matches v if v = C vV AND pP matches vV

Introduce bindings from recursively matching pP against vV

48 of 73

Variants : Use

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

Type Checking

If t0 is a variant type defined as type t0 = C1 of t1 | … | CN of tN
If e has type t0 and each pattern Pi matches values of type t0
If in each case Pi -> ei, expression e has type t
Then match e with P1 -> e1 | … | PN -> eN has type t
Else, report error and fail

Need to define:

How patterns match
How cases type check

Rules for matching pattern p against value v of type tV:

If p is a variable xP

Then p matches v (variable patterns always match any value)

Bind xP ↦ tV in the static environment
Bind xP ↦ v in the dynamic environment

If p is a tuple pattern (p1, …, pN)

Then p matches v if v = (v1, …, vN) AND all pi match vi

Introduce bindings from recursively matching all pi against vi

If p is a constructor applied to another pattern C pP

Then p matches v if v = C vV AND pP matches vV

Introduce bindings from recursively matching pP against vV

Match for compound patterns

is defined recursively !

49 of 73

Variants : Use

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

Type Checking

If t0 is a variant type defined as type t0 = C1 of t1 | … | CN of tN
If e has type t0 and each pattern Pi matches values of type t0
If in each case Pi -> ei, expression e has type t
Then match e with P1 -> e1 | … | PN -> eN has type t
Else, report error and fail

Need to define:

How patterns match
How cases type check

Rules for matching pattern p against value v of type tV:

If p is a variable xP

Then p matches v (variable patterns always match any value)

Bind xP ↦ tV in the static environment
Bind xP ↦ v in the dynamic environment

If p is a tuple pattern (p1, …, pN)

Then p matches v if v = (v1, …, vN) AND all pi match vi

Introduce bindings from recursively matching all pi against vi

If p is a constructor applied to another pattern C pP

Then p matches v if v = C vV AND pP matches vV

Introduce bindings from recursively matching pP against vV

Must have same length,

and all sub-patterns must match!

50 of 73

Variants : Use

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

Type Checking

If t0 is a variant type defined as type t0 = C1 of t1 | … | CN of tN
If e has type t0 and each pattern Pi matches values of type t0
If in each case Pi -> ei, expression e has type t
Then match e with P1 -> e1 | … | PN -> eN has type t
Else, report error and fail

Need to define:

How patterns match
How cases type check

Rules for matching pattern p against value v of type tV:

If p is a variable xP

Then p matches v (variable patterns always match any value)

Bind xP ↦ tV in the static environment
Bind xP ↦ v in the dynamic environment

If p is a tuple pattern (p1, …, pN)

Then p matches v if v = (v1, …, vN) AND all pi match vi

Introduce bindings from recursively matching all pi against vi

If p is a constructor applied to another pattern C pP

Then p matches v if v = C vV AND pP matches vV

Introduce bindings from recursively matching pP against vV

Must be same constructor C !

51 of 73

Variants : Use

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

Type Checking

If t0 is a variant type defined as type t0 = C1 of t1 | … | CN of tN
If e has type t0 and each pattern Pi matches values of type t0
If in each case Pi -> ei, expression e has type t
Then match e with P1 -> e1 | … | PN -> eN has type t
Else, report error and fail

Need to define:

How patterns match
How cases type check

Rules for matching pattern p against value v of type tV:

If p is a variable xP

Then p matches v (variable patterns always match any value)

Bind xP ↦ tV in the static environment
Bind xP ↦ v in the dynamic environment

If p is a tuple pattern (p1, …, pN)

Then p matches v if v = (v1, …, vN) AND all pi match vi

Introduce bindings from recursively matching all pi against vi

If p is a constructor applied to another pattern C pP

Then p matches v if v = C vV AND pP matches vV

Introduce bindings from recursively matching pP against vV

Patterns can only be one of a few things:

Variable
Tuple of patterns
Constructor + pattern

For any pattern and value of any type:

These are (basically) all the rules!

52 of 73

Variants : Use

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

Type Checking

If t0 is a variant type defined as type t0 = C1 of t1 | … | CN of tN
If e has type t0 and each pattern Pi matches values of type t0
If in each case Pi -> ei, expression e has type t
Then match e with P1 -> e1 | … | PN -> eN has type t
Else, report error and fail

Need to define:

How patterns match
How cases type check

Rules for matching pattern p against value v of type tV:

If p is a variable xP

Then p matches v (variable patterns always match any value)

Bind xP ↦ tV in the static environment
Bind xP ↦ v in the dynamic environment

If p is a tuple pattern (p1, …, pN)

Then p matches v if v = (v1, …, vN) AND all pi match vi

Introduce bindings from recursively matching all pi against vi

If p is a constructor applied to another pattern C pP

Then p matches v if v = C vV AND pP matches vV

Introduce bindings from recursively matching pP against vV

Patterns can only be one of a few things:

Variable
Tuple of patterns
Constructor + pattern

For any pattern and value of any type:

These are (basically) all the rules!

Some extensions that “work as expected”:

The _ (“don’t care”) pattern matches anything

But doesn’t introduce any bindings

A pattern can also be a value v

Matches precisely the value v
Doesn’t introduce any bindings

Values don’t contain any variables!

There are also record patterns

{ f1 = p1; …; fN = pN }

53 of 73

Variants : Use

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

Type Checking

If t0 is a variant type defined as type t0 = C1 of t1 | … | CN of tN
If e has type t0 and each pattern Pi matches values of type t0
If in each case Pi -> ei, expression ei has type t
Then match e with P1 -> e1 | … | PN -> eN has type t
Else, report error and fail

Need to define:

How patterns match ✅
How cases type check

54 of 73

Variants : Use

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

Type Checking

If t0 is a variant type defined as type t0 = C1 of t1 | … | CN of tN
If e has type t0 and each pattern Pi matches values of type t0
If in each case Pi -> ei, expression ei has type t
Then match e with P1 -> e1 | … | PN -> eN has type t
Else, report error and fail

Need to define:

How patterns match ✅
How cases type check

Rules for type checking case P -> e :

If e has type t in the static environment extended by matching P
Then in the case P -> e, the expression e has type t

55 of 73

Variants : Use

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

Type Checking

If t0 is a variant type defined as type t0 = C1 of t1 | … | CN of tN
If e has type t0 and each pattern Pi matches values of type t0
If in each case Pi -> ei, expression ei has type t
Then match e with P1 -> e1 | … | PN -> eN has type t
Else, report error and fail

Need to define:

How patterns match ✅
How cases type check

Rules for type checking case P -> e :

If e has type t in the static environment extended by matching P
Then in the case P -> e, the expression e has type t

In case P -> e, the scope of bindings added by matching is only for the expression e.

56 of 73

Variants : Use

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

Type Checking

If t0 is a variant type defined as type t0 = C1 of t1 | … | CN of tN
If e has type t0 and each pattern Pi matches values of type t0
If in each case Pi -> ei, expression ei has type t
Then match e with P1 -> e1 | … | PN -> eN has type t
Else, report error and fail

Need to define:

How patterns match ✅
How cases type check ✅

57 of 73

Variants : Use

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

Type Checking

If t0 is a variant type defined as type t0 = C1 of t1 | … | CN of tN
If e has type t0 and each pattern Pi matches values of type t0
If in each case Pi -> ei, expression ei has type t
Then match e with P1 -> e1 | … | PN -> eN has type t
Else, report error and fail

Need to define:

How patterns match ✅
How cases type check ✅

And it gets better! OCaml will also check that:

All possible values of e‘s type can be matched

So no missing cases!

No patterns are redundant / unreachable

So no dead / unreachable code!

Based on coarse type-level analysis at least

58 of 73

Variants : Use

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

Evaluation

If e evaluates to value v and Pi is the first pattern that matches value v and
In the dynamic environment extended by v matching Pi, ei evaluates to value vi
Then match e with P1 -> e1 | … | PN -> eN evaluates to value vi

59 of 73

Variants : Use

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

Evaluation

If e evaluates to value v and Pi is the first pattern that matches value v and
In the dynamic environment extended by v matching Pi, ei evaluates to value vi
Then match e with P1 -> e1 | … | PN -> eN evaluates to value vi

Try patterns in order till one matches

60 of 73

Variants : Use

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

Evaluation

If e evaluates to value v and Pi is the first pattern that matches value v and
In the dynamic environment extended by v matching Pi, ei evaluates to value vi
Then match e with P1 -> e1 | … | PN -> eN evaluates to value vi

Try patterns in order till one matches

Semantics pretty easy once we carefully defined what it means to match a pattern 😎

61 of 73

Variants : Polymorphism

Variant type definitions can also be parameterized by type variables

Needed for things like option, list, etc.

Easy extension from earlier definitions:

type [(‘a, ‘b, ...)] t = C1 of t1 | … | CN of tN
The ti can now include / use types ‘a, ‘b, ...

62 of 73

Variant Examples : Our Own “Option” Type

type 'a maybe =

| Nothing

| Just of 'a

let is_nothing (m : 'a maybe) : bool =

match m with

| Nothing -> true

| Just _ -> false

let maybe_get (m : 'a maybe) : 'a =

match m with

| Nothing -> failwith "maybe_get: Nothing"

| Just a -> a

type 'a maybe =

Nothing | Just of 'a

val is_nothing :

'a maybe -> bool = <fun>

val maybe_get :

'a maybe -> 'a = <fun>

63 of 73

Variant Examples : Our Own “List” Type

type 'a llist =

| Nil

| Cons of 'a * 'a llist

let rec llength (ll : 'a llist) : int =

match ll with

| Nil -> 0

| Cons (x, xs) -> 1 + llength xs

let rec append (ll1 : 'a llist) (ll2 : 'a llist) : 'a llist =

match ll1 with

| Nil -> ll2

| Cons (x, xs) -> Cons (x, append xs ll2)

type 'a llist =

Nil | Cons of 'a * 'a llist

val llength :

'a llist -> int = <fun>

val append :

'a llist -> 'a llist -> 'a llist = <fun>

64 of 73

Variant Examples : Parameterizing Multiple Types

type ('a, 'b) either = Left of 'a | Right of 'b

let mk_left (a : 'a) : ('a, 'b) either = Left a

let mk_right (b : 'b) : ('a, 'b) either = Right b

let rec split_lr (ll : ('a, 'b) either list) : 'a list * 'b list =

match ll with

| [] -> ([], [])

| x :: xs ->

let (ls, rs) = split_lr xs in

match x with

| Left a -> (a :: ls, rs)

| Right b -> (ls, b :: rs)

type ('a, 'b) either =

Left of 'a | Right of 'b

val mk_left :

'a -> ('a, 'b) either = <fun>

val mk_right :

'b -> ('a, 'b) either = <fun>

val split_lr :

('a, 'b) either list -> 'a list * 'b list = <fun>

65 of 73

Whew…

(take a breath)

66 of 73

So What?

Variants let us define our own “one of” types (list lists, options, trees, etc.)
Pattern matching lets us simultaneously

Test to see which constructor a value was built with
Bind variables to the parts of that value and use them in a case of the match

We cannot forget to check a case in the match or have redundant cases!
Single, concise, elegant mechanism works for using any compound data

67 of 73

Today: Records and Variants

Records : a new way to build each-of types ✅

Record values are built roughly similar to tuples, except with named fields
Unlike tuples, can access any field (use any part) of a record by its name

Variants : a way to build our own one-of types ✅

For example, we will be able to define a type whose values contain an int or a string
Variant values are built using constructors we define, like Some, None, ::, []
To use variant values we need a mechanism to test and unpack them: pattern matching

68 of 73

Today: Records and Variants

Records : a new way to build each-of types ✅

Record values are built roughly similar to tuples, except with named fields
Unlike tuples, can access any field (use any part) of a record by its name

Variants : a way to build our own one-of types ✅

For example, we will be able to define a type whose values contain an int or a string
Variant values are built using constructors we define, like Some, None, ::, []
To use variant values we need a mechanism to test and unpack them: pattern matching

Later in the quarter, we’ll see one-of types in OOP

A key difference between FP and non-FP

69 of 73

Programming

Languages

70 of 73

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.

71 of 73

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

… but not my expertise 🤓

Goal: become “semanticists”

72 of 73

Syntactic Sugar

One way we will simplify designing and analyzing PL features: syntactic sugar

Essentially “defining some language feature in terms of other features”

Example: e1 && e2

Could give syntax, type checking, and evaluation rules
OR could just say that e1 && e2 “desugars” (expands) to if e1 then e2 else false

“Syntactic”: semantics explained by transforming some syntax into other syntax
“Sugar”: makes the language sweeter ?! 🤷

73 of 73

Syntactic Sugar

One way we will simplify designing and analyzing PL features: syntactic sugar

Essentially “defining some language feature in terms of other features”

Example: e1 && e2

Could give syntax, type checking, and evaluation rules
OR could just say that e1 && e2 “desugars” (expands) to if e1 then e2 else false

“Syntactic”: semantics explained by transforming some syntax into other syntax
“Sugar”: makes the language sweeter ?! 🤷

Syntactic sugar helps us keep the “core language” small and orthogonal (thus making it easier to understand and implement) while still providing convenient “features” that really just desugar into the core language.