Lecture 04

​

Lists, Lets, Options

Programming Languages

UW CSE 341 - Winter 2021

Updates (2020-01-11)

• Homework 1 posted!
• Due 5pm on Friday
• Make sure to start early
• Will need some stuff from lecture today
• Pipe up on the course discussion board with any questions!

Updates (2020-01-13)

• Homework 1 due Friday!
• You should have a draft in progress by now :)
• Pipe up on the course discussion board with any questions!
• New 341 components: Class-based Quizzes
• 🔬⚗️🔭🥼🧪🧬 EXCITING NEW EXPERIMENT 🧬🔬⚗️🔭🥼🧪

Syntax + Semantics

• Syntax: how programs are written down
• Roughly “spelling and grammar”
• Semantics: what programs mean
• Type checking : compile time (aka “static”) semantics
• Evaluation : run time (aka “dynamic”) semantics
• Both syntax and semantics matter
• 341’s view ≈ “Semantics give the essence of a PL. Syntax is more about taste.”

OCaml Carefully So Far

• A program is just a sequence of bindings
• Typecheck each binding in order
• Using static environment from previous bindings
• Evaluate each binding in order
• Using dynamic environment from previous bindings
• So far variable bindings and functions bindings
• Today will see how to put variable bindings inside expressions too!

Data

Compound Data Types

• Ways to build data with multiple parts
• Plan
• Tuples : fixed number of “pieces” with possibly different types ✅
• Lists : any number of “pieces” all with the same type
• Later
• More general ways to create compound data (trees, maps, graphs, etc.)

General Design Principle

• Whenever we design a new type t we need two things:
• A way to build (“introduce”, “construct”) values of type t
• A way to use (“eliminate”, “destruct”) values of type t

Pairs (2-tuples) : Build

Syntax: (e1, e2)

• Where e1 and e2 are expressions

Type Checking

• If has e1 has type t1 and e2 has type t2
• Then (e1, e2) has type t1 * t2
• Else, report error and fail

Evaluation

• If e1 evaluates to value v1 and e2 evaluates to value v2
• Then (e1, e2) evaluates to (v1, v2)

​

Pairs (2-tuples) : Use

Syntax: fst e and snd e

• Where e is an expression

Type Checking

• If has e has type t1 * t2, then
• fst e has type t1
• snd e has type t2

Evaluation

• If e evaluates to a pair of values (v1, v2), then
• fst e evaluates to v1
• snd e evaluates to v2

Nested Pairs

• Pairs (and tuples in general) can be nested
• Nesting is NOT a new feature!
• Simply a consequence of the syntax and semantics rules we set up 🧩

(1, (2, 3)) : int * (int * int)

• Compositionality is a hallmark of good design (often from orthogonality)
• (Also: Homework 1 makes extensive use of nested pairs 😉)

Nested Pairs

• Pairs (and tuples in general) can be nested
• Nesting is NOT a new feature!
• Simply a consequence of the syntax and semantics rules we set up 🧩

(1, (2, 3)) : int * (int * int)

• Compositionality is a hallmark of good design (often from orthogonality)
• (Also: Homework 1 makes extensive use of nested pairs 😉)

NOT a triple (3-tuple)!

​

Instead “pair of int and (pair of int and int)”

Nested Pairs

• Pairs (and tuples in general) can be nested
• Nesting is NOT a new feature!
• Simply a consequence of the syntax and semantics rules we set up 🧩

(1, (2, 3)) : int * (int * int)

• Compositionality is a hallmark of good design (often from orthogonality)
• (Also: Homework 1 makes extensive use of nested pairs 😉)

NOT a triple (3-tuple)!

​

Instead “pair of int and (pair of int and int)”

Parentheses matter in tuple types:

int * (int * int)

is NOT the same as

int * int * int

Lists : Build

Syntax: [e1; …; eN]

• Where e1, …, eN are expressions

Type Checking

• If has e1 has type t and … and eN has type t
• Then [e1; …; eN] has type t list
• Else, report error and fail

Evaluation

• If e1 evaluates to value v1 and … and eN evaluates to value vN
• Then [e1; …; eN] evaluates to [v1; …; vN]

​

Lists : Build

Syntax: [e1; …; eN]

• Where e1, …, eN are expressions

Type Checking

• If has e1 has type t and … and eN has type t
• Then [e1; …; eN] has type t list
• Else, report error and fail

Evaluation

• If e1 evaluates to value v1 and … and eN evaluates to value vN
• Then [e1; …; eN] evaluates to [v1; …; vN]

​

Elements separated by semicolons “ ; ” ⚠️

Get very weird error messages otherwise ⚠️

Lists : Build

Syntax: [e1; …; eN]

• Where e1, …, eN are expressions

Type Checking

• If has e1 has type t and … and eN has type t
• Then [e1; …; eN] has type t list
• Else, report error and fail

Evaluation

• If e1 evaluates to value v1 and … and eN evaluates to value vN
• Then [e1; …; eN] evaluates to [v1; …; vN]

​

Lists of values are values.

Elements separated by semicolons “ ; ” ⚠️

Get very weird error messages otherwise ⚠️

Lists : Build

Syntax: [e1; …; eN]

• Where e1, …, eN are expressions

Type Checking

• If has e1 has type t and … and eN has type t
• Then [e1; …; eN] has type t list
• Else, report error and fail

Evaluation

• If e1 evaluates to value v1 and … and eN evaluates to value vN
• Then [e1; …; eN] evaluates to [v1; …; vN]

​

New kind of type!

t list

Another type constructor (list) for making the type of lists whose elements have type t.

Lists : Build

Syntax: [e1; …; eN]

• Where e1, …, eN are expressions

Type Checking

• If has e1 has type t and … and eN has type t
• Then [e1; …; eN] has type t list
• Else, report error and fail

Evaluation

• If e1 evaluates to value v1 and … and eN evaluates to value vN
• Then [e1; …; eN] evaluates to [v1; …; vN]

​

New kind of type!

t list

Another type constructor (list) for making the type of lists whose elements have type t.

Examples:

bool list int list

(int * (int * int)) list

int list list

Lists : Build

Syntax: [e1; …; eN]

• Where e1, …, eN are expressions

Type Checking

• If has e1 has type t and … and eN has type t
• Then [e1; …; eN] has type t list
• Else, report error and fail

Evaluation

• If e1 evaluates to value v1 and … and eN evaluates to value vN
• Then [e1; …; eN] evaluates to [v1; …; vN]

​

N can be zero!

[] is the empty list for any type.

New kind of type!

t list

Another type constructor (list) for making the type of lists whose elements have type t.

Examples:

bool list int list

(int * (int * int)) list

int list list

Lists : Build

Syntax: [e1; …; eN]

• Where e1, …, eN are expressions

Type Checking

• If has e1 has type t and … and eN has type t
• Then [e1; …; eN] has type t list
• Else, report error and fail

Evaluation

• If e1 evaluates to value v1 and … and eN evaluates to value vN
• Then [e1; …; eN] evaluates to [v1; …; vN]

​

N can be zero!

[] is the empty list for any type.

New kind of type!

t list

Another type constructor (list) for making the type of lists whose elements have type t.

Type written as (syntax) : ‘a list

Pronounced : “tick a” or “alpha”

​

Type variables (‘a, ‘b, ‘c, …) support polymorphism.

Examples:

bool list int list

(int * (int * int)) list

int list list

List Types

• At the type level, list is a type constructor
• Defines a type based on other types
• For any type t, the type t list describes lists whose elements all have type t
• All (zero) elements of the empty list [] have ANY type
• OCaml uses a type variable to describe the type of []
• Written ‘a list (or equivalently ‘b list, ‘c list, …)
• Type variables support polymorphism and will let us specify constraints between types

Lists : Build with “cons” (::)

Syntax: e1 :: e2

• Where e1 and e2 are expressions

Type Checking

• If has e1 has type t and e2 has type t list
• Then e1 :: e2 has type t list
• Else, report error and fail

Evaluation

• If e1 evaluates to value v1 and e2 evaluates to value [v2; …; vN]
• Then e1 :: e2 evaluates to [v1; v2;…; vN]

​

Lists : Build with “cons” (::)

Syntax: e1 :: e2

• Where e1 and e2 are expressions

Type Checking

• If has e1 has type t and e2 has type t list
• Then e1 :: e2 has type t list
• Else, report error and fail

Evaluation

• If e1 evaluates to value v1 and e2 evaluates to value [v2; …; vN]
• Then e1 :: e2 evaluates to [v1; v2;…; vN]

​

Adds an element to the front of the list!

Lists : Use

• We’ll start by just using functions to:
• Test if a list is empty with e = []
• Get the first element of a non-empty list with List.hd
• Get the rest of a non-empty list (everything after first element) with List.tl
• List.hd and List.tl will throw an exception if given an empty list
• Later, will use pattern matching to do this more safely and elegantly

Lists : Use -- Test for empty

Syntax: e = []

• Where e is an expression

Type Checking

• If has e has type t list
• Then e = [] has type bool
• Else, report error and fail

Evaluation

• If e evaluates to value [], then e = [] evaluates to value true
• Otherwise, e = [] evaluates to value false

​

Lists : Use -- Get the first element

Syntax: List.hd e

• Where e is an expression

Type Checking

• If has e has type t list
• Then List.hd e has type t
• Else, report error and fail

Evaluation

• If e evaluates to value [v1; v2; …; vN]
• Then List.hd e evaluates to value v1
• Otherwise, e evaluated to [] so List.tl e will raise an exception

Lists : Use -- Get the rest (everything after first)

Syntax: List.tl e

• Where e is an expression

Type Checking

• If has e has type t list
• Then List.tl e has type t list
• Else, report error and fail

Evaluation

• If e evaluates to value [v1; v2; …; vN]
• Then List.tl e evaluates to value [v2; …; vN]
• Otherwise, e evaluated to [] so List.tl e will raise an exception

Recursion again!

• Functions over lists are usually recursive
• Only way to “get to all the elements”
• Design recipe: answer two questions
• What should the answer be for an empty list?
• Often thinking about the return type provides a good hint (base case)
• What should the answer be for a non-empty list?
• Typically this will be in terms of the answer for the tail (recursion)

Recursion again!

• Functions over lists are usually recursive
• Only way to “get to all the elements”
• Design recipe: answer two questions
• What should the answer be for an empty list?
• Often thinking about the return type provides a good hint (base case)
• What should the answer be for a non-empty list?
• Typically this will be in terms of the answer for the tail (recursion)

Really, only two ways to build a list:

1. Empty list ( [ ] )
• “start a list”
2. Cons ( v :: vs )
• “make a list one element bigger”

Recursion again!

• Functions over lists are usually recursive
• Only way to “get to all the elements”
• Design recipe: answer two questions
• What should the answer be for an empty list?
• Often thinking about the return type provides a good hint (base case)
• What should the answer be for a non-empty list?
• Typically this will be in terms of the answer for the tail (recursion)

Really, only two ways to build a list:

• Empty list ( [ ] )
• “start a list”
• Cons ( v :: vs )
• “make a list one element bigger”

“The types write the code.”

Lists of Pairs

• Processing lists of pairs is a common pattern
• Requires no new features!
• “Just” compose what we’ve already learned.
• Again, compositionality is a hallmark of good design (often from orthogonality)

Local Bindings

OCaml So Far

• Types
• int bool unit t1 -> t2 t1 * t2 t list
• Expressions
• x e1 + e2 if e1 then e2 else e3 (e1, e2) e1 :: e2
• Bindings
• let x = e let f (x1 : t1) … (xN : tN) : t = e

OCaml So Far

• Types
• int bool unit t1 -> t2 t1 * t2 t list
• Expressions
• x e1 + e2 if e1 then e2 else e3 (e1, e2) e1 :: e2
• Bindings
• let x = e let f (x1 : t1) … (xN : tN) : t = e

can nest

OCaml So Far

• Types
• int bool unit t1 -> t2 t1 * t2 t list
• Expressions
• x e1 + e2 if e1 then e2 else e3 (e1, e2) e1 :: e2
• Bindings
• let x = e let f (x1 : t1) … (xN : tN) : t = e

can nest

can nest

OCaml So Far

• Types
• int bool unit t1 -> t2 t1 * t2 t list
• Expressions
• x e1 + e2 if e1 then e2 else e3 (e1, e2) e1 :: e2
• Bindings
• let x = e let f (x1 : t1) … (xN : tN) : t = e

can nest

can nest

???

Local Bindings aka Let Expressions

• Expressions can have their own local (private) variable and function bindings
• For style and convenience -- lets (😂) us name intermediate results
• For consistency -- everything else can nest
• For efficiency -- avoid unnecessary recomputation
• For safety and maintenance -- hide implementation details from clients

Let Expressions : Local Variable Binding

Syntax: let x = e1 in e2

• Where e1 and e2 are expressions

Let Expressions : Local Variable Binding

Syntax: let x = e1 in e2

Type Checking

• If e1 has type t1 in current static environment AND
• If e2 has type t2 in static environment extended with x ↦ t1
• Then let x = e1 in e2 has type t2
• Else, report error and fail

Let Expressions : Local Variable Binding

Syntax: let x = e1 in e2

Evaluation

• If e1 evaluates to value v1 in current dynamic environment AND
• If e2 evaluates to value v2 in dynamic environment extended with x ↦ v1
• Then let x = e1 in e2 evaluates to value v2

Let Expressions are “Just Expressions”!

• A let expression can go anywhere an expression can go

​

Let Expressions are “Just Expressions”!

• A let expression can go anywhere an expression can go
• Expressions can have their own local (private) variable and function bindings
• For style and convenience -- lets (😂) us name intermediate results
• For consistency -- everything else can nest
• For efficiency -- avoid unnecessary recomputation
• For safety and maintenance -- hide implementation details from clients

​

Let Expressions are “Just Expressions”!

• A let expression can go anywhere an expression can go

​

let two_pow_16 =

2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 *

2 * 2 * 2 * 2 * 2 * 2 * 2 * 2

​

Let Expressions are “Just Expressions”!

• A let expression can go anywhere an expression can go

​

let two_pow_16 =

2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 *

2 * 2 * 2 * 2 * 2 * 2 * 2 * 2

​

15 multiplications 😒

Lots of copy / paste 🤮

Let Expressions are “Just Expressions”!

• A let expression can go anywhere an expression can go

​

let two_pow_16 =

2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 *

2 * 2 * 2 * 2 * 2 * 2 * 2 * 2

​

let two_pow_16 =

let two_pow_08 =

2 * 2 * 2 * 2 * 2 * 2 * 2 * 2

in

two_pow_08 * two_pow_08

15 multiplications 😒

Lots of copy / paste 🤮

Let Expressions are “Just Expressions”!

• A let expression can go anywhere an expression can go

​

let two_pow_16 =

2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 *

2 * 2 * 2 * 2 * 2 * 2 * 2 * 2

​

let two_pow_16 =

let two_pow_08 =

2 * 2 * 2 * 2 * 2 * 2 * 2 * 2

in

two_pow_08 * two_pow_08

15 multiplications 😒

Lots of copy / paste 🤮

Still 8 multiplications 😏

Still lots of copy / paste 🤢

Let Expressions are “Just Expressions”!

• A let expression can go anywhere an expression can go

​

let two_pow_16 =

let tp2 = 2 * 2 in

let tp4 = tp2 * tp2 in

let tp8 = tp4 * tp4 in

tp8 * tp8

let two_pow_16 =

2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 *

2 * 2 * 2 * 2 * 2 * 2 * 2 * 2

​

Let Expressions are “Just Expressions”!

• A let expression can go anywhere an expression can go

​

let two_pow_16 =

let tp2 = 2 * 2 in

let tp4 = tp2 * tp2 in

let tp8 = tp4 * tp4 in

tp8 * tp8

let two_pow_16 =

2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 *

2 * 2 * 2 * 2 * 2 * 2 * 2 * 2

​

4 multiplications 🙂

Not much copy / paste 🙂

Let Expressions are “Just Expressions”!

• A let expression can go anywhere an expression can go
• But use good judgement, we’re not trying to win the IOCC or anything
• For example, these are terrible but show let expressions really are just expressions

let silly_00 =

let x = 1 in

let y = 2 in

(let x = 3 in x + y) +

(let y = 4 in x + y)

let silly_01 (z : int) : int =

let x = if 0 < z then 2021 else z in

let y = x + z + 98195 in

if x > y then

x * 2

else

y * y

Let Expressions are “Just Expressions”!

• A let expression can go anywhere an expression can go
• But use good judgement, we’re not trying to win the IOCC or anything
• For example, these are terrible but show let expressions really are just expressions

let silly_00 =

let x = 1 in

let y = 2 in

(let x = 3 in x + y) +

(let y = 4 in x + y)

let silly_01 (z : int) : int =

let x = if 0 < z then 2021 else z in

let y = x + z + 98195 in

if x > y then

x * 2

else

y * y

shadows outer bindings

(but only locally)

Local Bindings: What’s New Here?

• Scope
• More control over which parts of a program can access a binding
• For let expressions: just the body of the let !
• Nothing else is really new
• let expressions just work pretty much like top-level let bindings

Let Expressions : Local Function Binding

Syntax: let [rec] f (x1 : t1) … (xN : tN) : t = e1 in e2

• Where e1 and e2 are expressions

Let Expressions : Local Function Binding

Syntax: let [rec] f (x1 : t1) … (xN : tN) : t = e1 in e2

Type Checking

• Type check f “as usual” (see rules for type checking function bindings)
• If e2 has type tR in static environment extended with f ↦ t1 -> … -> tN -> t
• Then let [rec] f (x1 : t1) … (xN : tN) : t = e1 in e2 has type tR
• Else, report error and fail

Let Expressions : Local Function Binding

Syntax: let [rec] f (x1 : t1) … (xN : tN) : t = e1 in e2

Evaluation

• Functions are values, so no need to do anything for f, it’s already a value
• If e2 evaluates to value v2 in dynamic environment extended with f ↦ <the function f>
• Then let [rec] f (x1 : t1) … (xN : tN) : t = e1 in e2 evaluates to value v2

Let Expression Examples

​

• Not great style:

let nats_upto (hi : int) : int list =

let rec range (lo : int) (hi : int) : int list =

if lo < hi then

lo :: range (lo + 1) hi

else

[]

in

range 0 hi

Let Expression Examples

​

• Not great style:

let nats_upto (hi : int) : int list =

let rec range (lo : int) (hi : int) : int list =

if lo < hi then

lo :: range (lo + 1) hi

else

[]

in

range 0 hi

local function

Let Expression Examples

​

• Not great style:

let nats_upto (hi : int) : int list =

let rec range (lo : int) (hi : int) : int list =

if lo < hi then

lo :: range (lo + 1) hi

else

[]

in

range 0 hi

local function

But range is hidden…

No one else can use it!

Let Expression Examples

​

• Not great style:

let nats_upto (hi : int) : int list =

let rec range (lo : int) (hi : int) : int list =

if lo < hi then

lo :: range (lo + 1) hi

else

[]

in

range 0 hi

local function

But range is hidden…

No one else can use it!

Also, does this helper function really need the hi parameter?

Let Expression Examples

​

• Better style:

let nats_upto (hi : int) : int list =

let rec loop (lo : int) : int list =

if lo < hi then

lo :: loop (lo + 1)

else

[]

in

loop 0

Let Expression Examples

​

• Better style:

let nats_upto (hi : int) : int list =

let rec loop (lo : int) : int list =

if lo < hi then

lo :: loop (lo + 1)

else

[]

in

loop 0

nats_upto 10;;

- : int list = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9]

Let Expression Examples

​

• Better style:

let nats_upto (hi : int) : int list =

let rec loop (lo : int) : int list =

if lo < hi then

lo :: loop (lo + 1)

else

[]

in

loop 0

• Functions can use bindings from the environment where they are defined.
• Including “outer” environments
• Including parameters to outer function
• Unnecessary parameters are bad style

Let Expression Examples

​

• Function to list a “hailstone sequence” (from Collatz conjecture)

let hailstone_seq (n : int) : int list =

let rec loop (i : int) : int list =

if i = 1 then

[1]

else if i mod 2 = 0 then

i :: loop (i / 2)

else

i :: loop (3 * i + 1)

in

loop n

Let Expression Examples

​

• Function to list a “hailstone sequence” (from Collatz conjecture)

let hailstone_seq (n : int) : int list =

let rec loop (i : int) : int list =

if i = 1 then

[1]

else if i mod 2 = 0 then

i :: loop (i / 2)

else

i :: loop (3 * i + 1)

in

loop n

hailstone_seq 128;;

- : int list = [128; 64; 32; 16; 8; 4; 2; 1]

​

hailstone_seq 127;;

- : int list =

[127; 382; 191; 574; 287; 862; 431; 1294; 647; 1942;

971; 2914; 1457; 4372; 2186; 1093; 3280; 1640; 820;

410; 205; 616; 308; 154; 77; 232; 116; 58; 29; 88;

44; 22; 11; 34; 17; 52; 26; 13; 40; 20; 10; 5; 16;

8; 4; 2; 1]

​

Nested Functions: Style

• Good style to define helper functions inside if they are:
• Not useful elsewhere (avoid clutter)
• Likely to be misused elsewhere (improve reliability)
• Likely to be changed or removed (hide implementation detail)
• Fundamental tradeoff:
• Reusing code saves efforts and (usually) avoids bugs, BUT
• Makes it harder to change later (lots of folks depend on its details)

DANGER: Avoid Repeated Recursion ⚠️

• How much work does this function do?

let rec bad_max (xs : int list) : int =

if xs = [] then

0 (* bad style *)

else if List.tl xs = [] then

List.hd xs

else if List.hd xs > bad_max (List.tl xs) then

List.hd xs

else

bad_max (List.tl xs)

DANGER: Avoid Repeated Recursion ⚠️

• How much work does this function do?

let rec bad_max (xs : int list) : int =

if xs = [] then

0 (* bad style *)

else if List.tl xs = [] then

List.hd xs

else if List.hd xs > bad_max (List.tl xs) then

List.hd xs

else

bad_max (List.tl xs)

bad_max (List.rev (nats_upto 50));; (* [49; ...; 0] *)

- : int = 49 (* returns quickly *)

​

bad_max (nats_upto 50);; (* [0; ...; 49] *)

- : int = ... (* still running *)

DANGER: Avoid Repeated Recursion ⚠️

• How much work does this function do?

let rec bad_max (xs : int list) : int =

if xs = [] then

0 (* bad style *)

else if List.tl xs = [] then

List.hd xs

else if List.hd xs > bad_max (List.tl xs) then

List.hd xs

else

bad_max (List.tl xs)

bad_max (List.rev (nats_upto 50));; (* [49; ...; 0] *)

- : int = 49 (* returns quickly *)

​

bad_max (nats_upto 50);; (* [0; ...; 49] *)

- : int = ... (* still running *)

😳

Fast vs. Unusable

if List.hd xs > bad_max (List.tl xs)

then List.hd xs

else bad_max (List.tl xs)

bm [49; … ]

Fast vs. Unusable

if List.hd xs > bad_max (List.tl xs)

then List.hd xs

else bad_max (List.tl xs)

bm [49; … ]

bm [48; … ]

bm [47; … ]

bm [0]

...

Fast vs. Unusable

if List.hd xs > bad_max (List.tl xs)

then List.hd xs

else bad_max (List.tl xs)

bm [49; … ]

bm [48; … ]

bm [47; … ]

bm [0]

...

50 calls

Fast vs. Unusable

if List.hd xs > bad_max (List.tl xs)

then List.hd xs

else bad_max (List.tl xs)

bm [49; … ]

bm [48; … ]

bm [47; … ]

bm [0]

...

bm [0; … ]

50 calls

Fast vs. Unusable

if List.hd xs > bad_max (List.tl xs)

then List.hd xs

else bad_max (List.tl xs)

bm [49; … ]

bm [48; … ]

bm [47; … ]

bm [0]

...

bm [0; … ]

bm [1; … ]

bm [2; … ]

bm [49]

...

bm [2; … ]

bm [49]

...

bm [1; … ]

bm [2; … ]

bm [49]

...

bm [2; … ]

bm [49]

...

bm [49]

...

bm [49]

...

50 calls

Fast vs. Unusable

if List.hd xs > bad_max (List.tl xs)

then List.hd xs

else bad_max (List.tl xs)

bm [49; … ]

bm [48; … ]

bm [47; … ]

bm [0]

...

bm [0; … ]

bm [1; … ]

bm [2; … ]

bm [49]

...

bm [2; … ]

bm [49]

...

bm [1; … ]

bm [2; … ]

bm [49]

...

bm [2; … ]

bm [49]

...

bm [49]

...

bm [49]

...

50 calls

2⁵⁰

Calls

​

🤯

Using let to Avoid Repeated Recursion

• Now much work does this function do?

let rec better_max (xs : int list) : int =

if xs = [] then

0 (* bad style *)

else if List.tl xs = [] then

List.hd xs

else

let tl_max = better_max (List.tl xs) in

if List.hd xs > tl_max then

List.hd xs

else

tl_max

Using let to Avoid Repeated Recursion

• Now much work does this function do?

let rec better_max (xs : int list) : int =

if xs = [] then

0 (* bad style *)

else if List.tl xs = [] then

List.hd xs

else

let tl_max = better_max (List.tl xs) in

if List.hd xs > tl_max then

List.hd xs

else

tl_max

Recurse over the tail of the list once.

A Better Better Fix (still not great!)

let better_max (xs : int list) : int =

let rec loop (max : int) (l : int list) : int =

if l = [] then

max

else if max < List.hd l then

loop (List.hd l) (List.tl l)

else

loop max (List.tl l)

in

if xs = [] then

0 (* bad style *)

else

loop (List.hd xs) (List.tl xs)

A Better Better Fix (still not great!)

let better_max (xs : int list) : int =

let rec loop (max : int) (l : int list) : int =

if l = [] then

max

else if max < List.hd l then

loop (List.hd l) (List.tl l)

else

loop max (List.tl l)

in

if xs = [] then

0 (* bad style *)

else

loop (List.hd xs) (List.tl xs)

Helper function loops with “max up to this point”.

A Better Better Fix (still not great!)

let better_max (xs : int list) : int =

let rec loop (max : int) (l : int list) : int =

if l = [] then

max

else if max < List.hd l then

loop (List.hd l) (List.tl l)

else

loop max (List.tl l)

in

if xs = [] then

0 (* bad style *)

else

loop (List.hd xs) (List.tl xs)

Helper function loops with “max up to this point”.

Still wrong for empty lists 😫

Data?

What to do about partial functions?

• Many computations are not defined or “misbehave” for some inputs
• List.hd [], List.tl [], maximum element of [], 1 / 0, etc.
• OCaml does provide exceptions for such cases…
• We will see and use exceptions more later
• BUT exceptions don’t let us use the type system to track and handle potential misbehaviors
• AND exceptions can lead to surprising and undesirable control flow
• OCaml also provides an option type for handling partial functions

Options

• Basically: “lists” of length zero or one
• A value of type t option can either be:
• None
• Valid value of type t option for ANY type t (polymorphism!)
• Some v
• Where value v has type t

Options

• Basically: “lists” of length zero or one
• A value of type t option can either be:
• None
• Valid value of type t option for ANY type t (polymorphism!)
• Some v
• Where value v has type t

option is another

type constructor

Options

• Basically: “lists” of length zero or one
• A value of type t option can either be:
• None
• Valid value of type t option for ANY type t (polymorphism!)
• Some v
• Where value v has type t

option is another

type constructor

Just like our other friends:

t1 * t2

t1 -> t2

t list

Options : Build -- None

Syntax: None

Type Checking

• None has type ’a option

Evaluation

• None is a value

​

Options : Build -- None

Syntax: None

Type Checking

• None has type ’a option

Evaluation

• None is a value

​

None has type

t option for any t

Options : Build -- Some

Syntax: Some e

• Where e is an expression

Type Checking

• If e has type t
• Then Some e has type t option
• Else, report error and fail

Evaluation

• If e evaluates to value v
• Then Some e evaluates to value Some v

​

Options : Use -- Test for None

Syntax: e = None

• Where e is an expression

Type Checking

• If has e has type t option
• Then e = None has type bool
• Else, report error and fail

Evaluation

• If e evaluates to value None, then e = None evaluates to value true
• Otherwise, e = None evaluates to value false

​

Options : Use -- Get the element

Syntax: Option.get e

• Where e is an expression

Type Checking

• If has e has type t option
• Then Option.get e has type t
• Else, report error and fail

Evaluation

• If e evaluates to value Some v
• Then Option.get e evaluates to value v
• Otherwise, e evaluated to None so Option.get e will raise an exception

A Better Better Better Max

let better_max (xs : int list) : int option =

let rec loop (max : int) (l : int list) : int =

if l = [] then

max

else if max < List.hd l then

loop (List.hd l) (List.tl l)

else

loop max (List.tl l)

in

if xs = [] then

None

else

Some (loop (List.hd xs) (List.tl xs))

A Better Better Better Max

let better_max (xs : int list) : int option =

let rec loop (max : int) (l : int list) : int =

if l = [] then

max

else if max < List.hd l then

loop (List.hd l) (List.tl l)

else

loop max (List.tl l)

in

if xs = [] then

None

else

Some (loop (List.hd xs) (List.tl xs))

Can finally give a reasonable default answer for bogus inputs!

A Better Better Better Max

let better_max (xs : int list) : int option =

let rec loop (max : int) (l : int list) : int =

if l = [] then

max

else if max < List.hd l then

loop (List.hd l) (List.tl l)

else

loop max (List.tl l)

in

if xs = [] then

None

else

Some (loop (List.hd xs) (List.tl xs))

Can finally give a reasonable default answer for bogus inputs!

Option type means clients will be forced to consider error cases!

= versus ==

Equality in OCaml

• OCaml has two equality test operators: = and ==
• For CSE 341 always use =

Equality in OCaml

• OCaml has two equality test operators: = and ==
• For CSE 341 always use =

= is for structural equality

Data is equal if it “has the same stuff”

Equality in OCaml

• OCaml has two equality test operators: = and ==
• For CSE 341 always use =

= is for structural equality

Data is equal if it “has the same stuff”

== is for physical equality

Data is equal if it is the same primitive (bool, int, float, etc.) or

if it is compound and has the same address in memory

Equality in OCaml

• OCaml has two equality test operators: = and ==
• For CSE 341 always use =

1 = 1;;

- : bool = true

​

1 = 2;;

- : bool = false

​

(1, 2) = (1, 2);;

- : bool = true

​

(1, 2) <> (1, 2);;

- : bool = false

Equality in OCaml

• OCaml has two equality test operators: = and ==
• For CSE 341 always use =

1 = 1;;

- : bool = true

​

1 = 2;;

- : bool = false

​

(1, 2) = (1, 2);;

- : bool = true

​

(1, 2) <> (1, 2);;

- : bool = false

1 == 1;;

- : bool = true

​

1 == 2;;

- : bool = false

​

(1, 2) == (1, 2);;

- : bool = false

​

(1, 2) != (1, 2);;

- : bool = true

Equality in OCaml

• OCaml has two equality test operators: = and ==
• For CSE 341 always use =

1 = 1;;

- : bool = true

​

1 = 2;;

- : bool = false

​

(1, 2) = (1, 2);;

- : bool = true

​

(1, 2) <> (1, 2);;

- : bool = false

1 == 1;;

- : bool = true

​

1 == 2;;

- : bool = false

​

(1, 2) == (1, 2);;

- : bool = false

​

(1, 2) != (1, 2);;

- : bool = true

Comparing pointers (addresses in memory) can lead to unintuitive results!

Equality in OCaml

• OCaml has two equality test operators: = and ==
• For CSE 341 always use =
• Potential gotcha with not equal though ⚠️
• The negation of = is <>
• The negation of == is !=

Aliasing and Mutation

Indistinguishability

• What does it mean for two programs to be equivalent?
• Often: given their interfaces, no client can tell them apart
• Begs the question: what is a program’s interface?
• In imperative languages need to consider aliasing (multiple references to the same object)
• What if some code mutates (changes) part of an object?
• Should other code see that change? Should you make copy? Who is responsible for it?
• Most of the time in functional programming aliasing doesn’t matter!
• Our values in OCaml (so far) are immutable
• Client can never tell if we made a copy or not

Can you spot the difference? Can a client?

let sort_pair (pr : int * int) : int * int =

if fst pr < snd pr then

pr

else

(snd pr, fst pr)

let sort_pair (pr : int * int) : int * int =

if fst pr < snd pr then

(fst pr, snd pr)

else

(snd pr, fst pr)

Can you spot the difference? Can a client?

• Version on the left avoids making a copy for already-sorted pair (better style)
• But a client (caller of sort_pair) can NEVER tell the difference!
• No code can ever distinguish aliasing vs. identical copies
• No need to think about aliasing: focus on other things
• Can use aliasing, which saves space, without danger

let sort_pair (pr : int * int) : int * int =

if fst pr < snd pr then

pr

else

(snd pr, fst pr)

let sort_pair (pr : int * int) : int * int =

if fst pr < snd pr then

(fst pr, snd pr)

else

(snd pr, fst pr)

Can you spot the difference? Can a client?

• Version on the left avoids making a copy for already-sorted pair (better style)
• But a client (caller of sort_pair) can NEVER tell the difference!
• No code can ever distinguish aliasing vs. identical copies
• No need to think about aliasing: focus on other things
• Can use aliasing, which saves space, without danger

let sort_pair (pr : int * int) : int * int =

if fst pr < snd pr then

pr

else

(snd pr, fst pr)

let sort_pair (pr : int * int) : int * int =

if fst pr < snd pr then

(fst pr, snd pr)

else

(snd pr, fst pr)

Immutability restricts what clients can do → simplifies reasoning!

Can you spot the difference? Can a client?

• Version on the left avoids making a copy for already-sorted pair (better style)
• But a client (caller of sort_pair) can NEVER tell the difference!
• No code can ever distinguish aliasing vs. identical copies
• No need to think about aliasing: focus on other things
• Can use aliasing, which saves space, without danger

let sort_pair (pr : int * int) : int * int =

if fst pr < snd pr then

pr

else

(snd pr, fst pr)

let sort_pair (pr : int * int) : int * int =

if fst pr < snd pr then

(fst pr, snd pr)

else

(snd pr, fst pr)

Immutability restricts what clients can do → simplifies reasoning!

“negative expressiveness”

Aliasing with append

let rec append (xs : 'a list) (ys : 'a list) : 'a list =

if xs = []

then ys

else List.hd xs :: append (List.tl xs) ys

​

let a = [1; 2]

let b = [3; 4]

let c = append a b

Aliasing with append

let rec append (xs : 'a list) (ys : 'a list) : 'a list =

if xs = []

then ys

else List.hd xs :: append (List.tl xs) ys

​

let a = [1; 2]

let b = [3; 4]

let c = append a b

a ↦

b ↦

c ↦

Aliasing with append

let rec append (xs : 'a list) (ys : 'a list) : 'a list =

if xs = []

then ys

else List.hd xs :: append (List.tl xs) ys

​

let a = [1; 2]

let b = [3; 4]

let c = append a b

a ↦

b ↦

c ↦

a ↦

b ↦

c ↦

Aliasing with append

let rec append (xs : 'a list) (ys : 'a list) : 'a list =

if xs = []

then ys

else List.hd xs :: append (List.tl xs) ys

​

let a = [1; 2]

let b = [3; 4]

let c = append a b

a ↦

b ↦

c ↦

a ↦

b ↦

c ↦

Clients can never tell!

(but it’s actually the upper one)

Aliasing with append

let rec append (xs : 'a list) (ys : 'a list) : 'a list =

if xs = []

then ys

else List.hd xs :: append (List.tl xs) ys

​

let a = [1; 2]

let b = [3; 4]

let c = append a b

a ↦

b ↦

c ↦

a ↦

b ↦

c ↦

Can safely reuse and share data. Immutability can be more efficient!

Clients can never tell!

(but it’s actually the upper one)