Lecture 06

​

Let Patterns, Tail Recursion, Exceptions

Programming Languages

UW CSE 341 - Winter 2021

Updates 2021-01-22

• Homework 2 is out!
• Due Friday 2021-01-29 by 5pm
• Start early! (Great job so far!)
• POPL 2021 is happening… right now ;)
• My PhD students have a talk at 9:40. Field Trip?

Pattern Matching

& let Bindings

let binds with patterns

• Writing match … with ... to use variants just one way to pattern match
• We can also use patterns with “each of” types (e.g., tuples and records)
• We have been using pattern matching since the beginning!
• Every let binding actually allows a pattern on the left-hand side (LHS)
• Remember: a lone variable is a pattern!

let binding patterns

• Primarily useful for taking an “each value” apart
• Recall: pattern (x1, …, xN) matches value (v1, …, vN)
• Pattern {f1 = x1; …; fN = xN} matches value {f1 = v1; …; fN = vN}
• Field order doesn’t matter in record patterns!

Let Expressions : Local Variable Binding

Syntax: let p = e1 in e2

• Where p is a pattern and e1 and e2 are expressions

Let Expressions : Local Variable Binding

Syntax: let p = e1 in e2

Type Checking

• If e1 has type t1 in current static environment AND
• If p is a pattern that matches values of type t1 AND
• If e2 has type t2 in static environment extended with “bindings from matching p”
• Then let x = e1 in e2 has type t2
• Else, report error and fail

Let Expressions : Local Variable Binding

Syntax: let p = e1 in e2

Evaluation

• If e1 evaluates to value v1 in current dynamic environment AND
• If p matches v1 AND
• If e2 evaluates to value v2 in dynamic environment extended with “bindings from matching p”
• Then let x = e1 in e2 evaluates to value v2

let binding patterns : really for “each of”

• Technically can match variants in a let binding, almost always a BAD IDEA!

​

(* very bad style! *)

​

let first xs =

let x :: _ = xs in

x

​

let get oa =

let Some a = oa in

a

let binding patterns

• Not just for variable bindings! Can also use patterns in function definitions!

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

• Where p1, …, pN are patterns and e1 and e2 are expressions

​

• Have to extend type checking and evaluation “as expected” too!

​

let binding patterns

(* still not great style,

but shows patterns *)

​

type date = int * (int * int)

​

let get_day (d, (_, _)) = d

let get_month (_, (m, _)) = m

let get_year (_, (_, y)) = y

let binding patterns

(* still not great style,

but shows patterns *)

​

type date = int * (int * int)

​

let get_day (d, (_, _)) = d

let get_month (_, (m, _)) = m

let get_year (_, (_, y)) = y

(* a bit better, but patterns overkill *)

type date =

{ day : int

; month : int

; year : int }

​

let get_day {day = d; month = _; year = _} = d

let get_month {day = _; month = m; year = _} = m

let get_year {day = _; month = _; year = y} = y

Nesting Patterns

• Notice that our definition of patterns and pattern matching is recursive
• So you can nest patterns! Usually better to nest patterns than nest matches

​

let rec zip3 xs ys zs =

match xs, ys, zs with

| [], [], [] ->

[]

| x :: xs', y :: ys', z :: zs' ->

(x, y, z) :: zip3 xs' ys' zs'

| _, _, _ ->

failwith "zip3: bogus”

let unzip3 trips =

let rec loop xyzs (xs, ys, zs) =

match xyzs with

| [] ->

(xs, ys, zs)

| (x, y, z) :: rest ->

loop rest (x :: xs, y :: ys, z :: zs)

in

loop trips ([], [], [])

Tail Recursion

Recursion

• In functional programming, we generally use recursion instead of loops
• “Code follows the data” -- recursive data processed by recursive code!
• But every recursive call needs to get “fresh space” for local variables
• Remember: when calls recurse, they locally extend the dynamic environment!
• Next: let’s refine our mental model of how calls execute (call stacks)
• Also next: let’s see how to make recursion as efficient as a loop!

Call Stacks

While a program runs, a call stack tracks function calls “in progress”

• Calling f pushes a stack frame for f on the stack
• When f finishes, its stack frame is popped from the stack

Each stack frame records:

• Values of local variables
• “What’s left to do” in the function (“context”, “continuation”, etc.)

With recursion, same function may have many active stack frames

• One per started-but-not-yet-returned recursive call

Example

Example

Example

Do we ALWAYS need a stack frame? (Hint: No.)

• If a recursive is the result, then nothing left to do when it returns
• Such calls known as tail calls
• Instead we could “cut out the middle” and just have callee return the value to the caller!
• ML handles tail calls specially
• Pop caller’s frame BEFORE the call
• Allow callee to just reuse caller’s stack space!
• This can take O(N) space usage down to O(1) 🤯

How OCaml really executes last

Moral of Tail Recursion

• When efficiency is important (> 10,000-ish recursive calls) use tail recursion
• Not always possible or elegant
• There is a methodology to transform functions into tail-recursive style
• Create a recursive helper with an accumulator argument
• Old base case becomes initial value for accumulator
• New base case just returns the accumulator
• Be careful with order though! Tail-recursive version often reversed
• See code and links for more examples:
• Length, reverse, sum, etc.
• RWO, Cornell CS 3110

Always use Tail Recursion?

• Not always possible to use constant stack space (e.g., tree traversals)
• In such cases, just use “normal recursion” -- often such data structures not “too deep”
• Always beware of premature optimization!
• Write code to be read by humans!!
• Of course, crashing is bad
• Avoiding stack overflows requires tail recursion sometimes
• Need to develop taste and exercise judgement

Definition of a Tail Call

A tail call is a function call in tail position. An expression is in tail position when:

• In let f p = e, the expression e is in tail position
• If if e1 then e2 else e3 is in tail position
• Then e2 and e3 are in tail position
• BUT e1 is NOT in tail position!
• If let p = e1 in e2 is in tail position
• Then e2 is in tail position
• BUT e1 is NOT in tail position
• If e is NOT in tail position, then neither are any of its subexpressions

Exceptions

Exceptions

Exception bindings declare new kinds of exception:

​

raise expressions can throw an exception:

​

try … with … expressions can catch exceptions

exception Bogus

exception BadNum of int

raise Bogus

raise (BadNum 1)

try (* ... *) with Bogus -> 0

try (* ... *) with BadNum n -> n

Exceptions as “One Big Variant”

• Exceptions are very similar to variants, except:
• A single “global exception variant type” called exn
• Unlike normal variants, we never know all the ways to build an exception
• So can never be sure that try/with matches are exhaustive!
• Declaring a new exception binding adds a constructor to exn
• Exceptions are values! Can pass them as arguments, return them as results
• try … with … is like pattern matching on exn
• Syntax and semantics “work as expected”
• Formalizing needs a bit more machinery than we will dig into right now