Lecture 03

​

Tuples, Lists

Programming Languages

UW CSE 341 - Spring 2023

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: No way to make compound data (like Java objects, arrays, …)
• That’s important, so let’s get to it!

Compound Data Types

• So far: integers, booleans, variables, conditionals, functions
• Now: 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

Example:

Build t1*t2*...*tn->t with function bindings, use with function calls

Example:

Build bool with true and false, use with if e1 then e2 else e3

​

More systematic approach to defining / understanding programming languages!

Pairs (2-tuples) : Build

Syntax: (e1, e2) where e1 and e2 are expressions

Type Checking

• If e1 has type t1 and e2 has type t2
• Then (e1, e2) has type t1 * t2
• Else, report error and fail (happens only if e1 or e2 does not type-check)

Evaluation

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

​

The Star of the Show

• * is a type constructor : it builds tuple types out of other types
• So int * bool, string * int, int * (int * int), are 3 of the infinite number of types we can construct with *
• Tuple types are also known as product types
• But the connection to multiplication is obscure and best ignored
• Just using the same character in unrelated syntax
• 3*4 is an expression that evaluates to 12, int*int is a type

Nested Pairs

Pairs can be nested

• Nesting is NOT a new feature!
• Simply a consequence of the syntax and semantics rules we set up

((1,4),(2,(true,3)) : (int * int) * (int * (bool * int))

• Compositionality is a hallmark of good design
• Often from orthogonality

​

Pairs (2-tuples) : Use

Syntax: fst e and snd e

• Where e is an expression

Type Checking

• If 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

Fib alert: fst and snd are actually library functions, but we will pretend they are “built in” for another week or so.

Tuples : Build

Syntax: (e1, …, eN)

• Where e1, …, eN are expressions and N >= 2
• This IS a new feature: (5,true,7) is a 3-tuple (triple), not any sort of nested pair

Type Checking

• If e1 has type t1 and … and eN has type tN
• Then (e1, …, eN) has type t1 * … * tN
• 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)

​

Tuples : Use

• OCaml does not have a built-in way to use arbitrary tuples…
• Instead, OCaml has a more general mechanism we will learn soon
• Pattern-matching
• But Homework 1 uses triples a lot
• So we wrote fst3, snd3, and thd3 for you to treat-like-primitives
• So fst and snd for pairs; fst3, snd3, and thd3 for triples
• Why can’t fst be used for triples? Type systems have limitations

Nested pairs vs. tuples

• OCaml didn’t need tuples, but they can be convenient.
• Parentheses matters in tuple types and tuple expressions!

let x = (5,7,9)

(* x : int*int*int *)

let seven = snd3 x

(* snd x doesn’t type-check *)

let x = (5,(7,9))

(* x : int*(int*int) *)

let seven = fst (snd x)

let pr = snd x

(* snd3 x doesn’t

type-check *)

Compound Data Types

• So far: integers, booleans, variables, conditionals, functions
• Now: 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.)

Lists : Build

Syntax: [e1; …; eN]

• Where e1, …, eN are expressions

Type Checking

• If 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 ⚠️

All same 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 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.

[]

• If e1 has type t and … and eN has type t
• Then [e1; …; eN] has type t list

​

So if all zero elements of [] have type t, then [] has type t list

• [] has type int list, bool list, int list list, (bool*int) list, ...
• OCaml writes, “any type of list” as ‘a list (or ‘b list, ‘c list, …)
• But all list elements of any list have the same type
• Will see these polymorphic types a lot in OCaml

Lists : Build with “cons” (::)

Syntax: e1 :: e2

• Where e1 and e2 are expressions

Type Checking

• If 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 v1 and e2 evaluates to [v2; …; vN]
• Then e1 :: e2 evaluates to [v1; v2;…; vN]

​

“Create (construct) a list with one more element at the front”

Two ways to build?

• :: is more common in code
• :: and [] is all we need
• e1::e2::e3::...::en::[] is the same as [e1;e2;e3;...;en]
• First of many examples of “syntactic sugar”
• List values are printed as [v1;v2;v3;...;vn]

Lists : Use

• For now, we will use lists with these features:
• Test if a list is empty with e = []
• Get the first element of a non-empty list with function List.hd
• Get the rest of a non-empty list with function List.tl
• (a list with everything after the first element)
• List.hd and List.tl will raise 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 true
• Else e = [] evaluates to 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
• Else e evaluated to [], so List.hd e raises an exception

Alternate definition:

List.hd has type ‘a list -> ‘a

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]
• Else e evaluated to [], so List.tl e raises an exception

Alternate definition:

List.tl has type ‘a list -> ‘a list

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)

Lists of tuples

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