CSE 341 : Programming Languages� �Lecture 6

​

Nested Patterns, Exceptions

James Wilcox

Winter 2017

Pattern matching so far: one-of types

Have used pattern-matching for one-of types because we needed a way to access the values

​

2

datatype exp = Constant of int

| Negate of exp

| Add of exp * exp

| Multiply of exp * exp

fun eval e =

case e of

Constant i => i

| Negate e2 => ~ (eval e2)

| Add(e1,e2) => (eval e1) + (eval e2)

| Multiply(e1,e2) => (eval e1) * (eval e2)

​

Pattern matching with each-of types

Pattern matching also works for records and tuples:

• The pattern (x1,…,xn)

matches the tuple value (v1,…,vn)

• The pattern {f1=x1, …, fn=xn}

matches the record value {f1=v1, …, fn=vn}

(and fields can be reordered)

3

Example

This is poor style, but based on what I told you so far, the only way to use patterns

• Works but poor style to have one-branch cases

4

fun sum_triple triple =

case triple of

(x, y, z) => x + y + z

​

fun full_name r =

case r of

{first=x, middle=y, last=z} =>

x ^ " " ^ y ^ " " ^ z

Val-binding patterns

• New feature: A val-binding can use a pattern, not just a variable
• (Turns out variables are just one kind of pattern, so we just told you a half-truth in Lecture 1)

​

​

• Great for getting (all) pieces out of an each-of type
• Can also get only parts out (not shown here)

​

• Can also put a constructor pattern in a val-binding
• Tests for the one variant and raises an exception if a different one is there (like hd, tl, and valOf)
• I like to use this for basic testing

5

val p = e

Better example

This is okay style

• Though we will improve it again next
• Semantically identical to one-branch case expressions

6

fun sum_triple triple =

let val (x, y, z) = triple

in

x + y + z

end

​

fun full_name r =

let val {first=x, middle=y, last=z} = r

in

x ^ " " ^ y ^ " " ^ z

end

Function-argument patterns

A function argument can also be a pattern

• Match against the argument in a function call

​

​

Examples (great style!):

​

7

fun f p = e

fun sum_triple (x, y, z) =

x + y + z

​

fun full_name {first=x, middle=y, last=z} =

x ^ " " ^ y ^ " " ^ z

​

A new way to go

• For Homework 2:
• Do not use #1, #2, null, hd, tl
• Use pattern matching instead!

​

8

Hmm

A function that takes one triple of type int*int*int and returns an int that is their sum:

9

A function that takes three int arguments and returns an int that is their sum

fun sum_triple (x, y, z) =

x + y + z

fun sum_triple (x, y, z) =

x + y + z

See the difference? (Me neither.) ☺

The truth about functions

• In ML, every function takes exactly one argument

​

• What we call multi-argument functions are just functions taking one tuple argument, implemented with a tuple pattern in the function binding
• Elegant and flexible language design

​

• What we call zero-argument functions are just taking unit

​

• Enables cute and useful things you cannot do in Java, e.g.,

​

​

​

​

​

​

10

fun rotate_left (x, y, z) = (y, z, x)

fun rotate_right t = rotate_left(rotate_left t)

​

Nested patterns

• We can nest patterns as deep as we want
• Just like we can nest expressions as deep as we want
• Often avoids hard-to-read, wordy nested case expressions

​

• So the full meaning of pattern-matching is to compare a pattern against a value for the “same shape” and bind variables to the “right parts”
• More precise recursive definition coming after examples

​

11

Useful example: zip/unzip 3 lists

12

fun zip3 lists =

case lists of

([],[],[]) => []

| (hd1::tl1,hd2::tl2,hd3::tl3) =>

(hd1,hd2,hd3)::zip3(tl1,tl2,tl3)

| _ => raise ListLengthMismatch

​

fun unzip3 triples =

case triples of

[] => ([],[],[])

| (a,b,c)::tl =>

let val (l1, l2, l3) = unzip3 tl

in

(a::l1,b::l2,c::l3)

end

​

​

More examples to come (see code files)

Style

• Nested patterns can lead to very elegant, concise code
• Avoid nested case expressions if nested patterns are simpler and avoid unnecessary branches or let-expressions
• Example: unzip3 and nondecreasing
• A common idiom is matching against a tuple of datatypes to compare them
• Examples: zip3

​

• Wildcards are good style: use them instead of variables when you do not need the data
• Examples: len and hd

13

(Most of) the full definition

The semantics for pattern-matching takes a pattern p and a value v and decides (1) does it match and (2) if so, what variable bindings are introduced.

​

Since patterns can nest, the definition is elegantly recursive, with a separate rule for each kind of pattern. Some of the rules:

• If p is a variable x, the match succeeds and x is bound to v
• If p is _, the match succeeds and no bindings are introduced
• If p is (p1,…,pn) and v is (v1,…,vn), the match succeeds if and only if p1 matches v1, …, pn matches vn. The bindings are the union of all bindings from the submatches
• If p is C p1, the match succeeds if v is C v1 (i.e., the same constructor) and p1 matches v1. The bindings are the bindings from the submatch.
• … (there are several other similar forms of patterns)

​

14

Examples

​

• Pattern a::b::c::d matches all lists with >= 3 elements

​

• Pattern a::b::c::[] matches all lists with 3 elements

​

• Pattern ((a,b),(c,d))::e matches all non-empty lists of pairs of pairs

​

15

Exceptions

An exception binding introduces a new kind of exception

​

​

​

The raise primitive raises (a.k.a. throws) an exception

​

​

​

A handle expression can handle (a.k.a. catch) an exception

• If doesn’t match, exception continues to propagate

16

exception MyFirstException

exception MySecondException of int * int

raise MyFirstException

raise (MySecondException(7,9))

e1 handle MyFirstException => e2

e1 handle MySecondException(x,y) => e2

Actually…

Exceptions are a lot like datatype constructors…

​

• Declaring an exception adds a constructor for type exn

​

• Can pass values of exn anywhere (e.g., function arguments)
• Not too common to do this but can be useful

​

• handle can have multiple branches with patterns for type exn

17