Programming Language: New Types, Pattern Matching, Tail Recursion

Conceptual Ways to Build New Types

To create a compound type, there are really only three essential building blocks. Any decent programming language provides these building blocks in some way:

• Each-of: A compound type t describes values that contain each of values of type t1, t2, ..., and tn. Tuples are an example: int * bool describes values that contain an int and a bool. A Java class with fields is also an each-of sort of thing.
• One-of: A compound type t describes values that contain a value of one of the types t1, t2, ..., or tn. For a type that contains an int or a bool in ML, we need datatype bindings. In object-oriented languages with classes like Java, one-of types are achieved with subclassing, but that is a topic for much later in the course.
• Self-reference: A compound type t may refer to itself in its definition in order to describe recursive data structures like lists and trees. This is useful in combination with each-of and one-of types. For example, int list describes values that either contain nothing or contain an int and another int list.

Records: Another Approach to Each-of Types

Record types are “each-of” types where each component is a named field.

{foo : int, bar : int*bool, baz : bool*int}

In ML, we do not have to declare that we want a record type with particular field names and field types — we just write down a record expression and the type-checker gives it the right type.

Now that we know how to build record values, we need a way to access their pieces. For now, we will use #foo e where foo is a field name.

The truth of tuple

In fact, this is how ML actually defines tuples: A tuple is a record. That is, all the syntax for tuples is just a convenient way to write down and use records. The REPL just always uses the tuple syntax where possible, so if you evaluate {2=1+2, 1=3+4} it will print the result as (7,3). Using the tuple syntax is better style, but we did not need to give tuples their own semantics: we can instead use the “another way of writing” rules above and then reuse the semantics for records.

This is the first of many examples we will see of syntactic sugar. We say, Tuples are just syntactic sugar for records with fields named 1, 2, ..., n.

val z = (3,7) : int * int
val z = {1=3,3=7} : {1:int, 3:int}

Datatype Bindings: Our Own One-of Types

We now introduce datatype bindings, our third kind of binding after variable bindings and function bindings.

datatype mytype = TwoInts of int * int
                | Str of string
                | Pizza

Roughly, this defines a new type where values have an int * int or a string or nothing. Any value will also be tagged with information that lets us know which variant it is: These tags, which we will call constructors, are TwoInts, Str, and Pizza.

More precisely, the example above adds four things to the environment:

• A new type mytype that we can now use just like any other type
• Three constructors TwoInts, Str, and Pizza

A constructor is two different things. First, it is either a function for creating values of the new type (if the variant has of t for some type t) or it is actually a value of the new type (otherwise). In our example, TwoInts is a function of type int*int -> mytype, Str is a function of type string->mytype, and Pizza is a value of type mytype. Second, we use constructors in case-expressions as described further below.

datatype mytype = TwoInts of int * int 
                | Str of string 
                | Pizza

val a = Str "hi"
val b = Str
val c = Pizza
val d = TwoInts(1+2,3+4)
val e = a


(* val a = Str "hi" : mytype
val b = fn : string -> mytype
val c = Pizza : mytype
val d = TwoInts (3,7) : mytype
val e = Str "hi" : mytype *)

How ML Provides Access to Datatype Values: Case Expressions

fun f x = (* f has type mytype -> int*) 
    case x of
      Pizza => 3
    | TwoInts(i1,i2) => i1 + i2 
    | Str s => String.size s

In one sense, a case-expression is like a more powerful if-then-else expression: Like a conditional expression, it evaluates two of its subexpressions: first the expression between the case and of keywords and second the expression in the first branch that matches. But instead of having two branches (one for true and one for false), we can have one branch for each variant of our datatype (and we will generalize this further below). Like conditional expressions, each branch’s expression must have the same type (int in the example above) because the type-checker cannot know what branch will be used. Each branch has the form p => e where p is a pattern and e is an expression, and we separate the branches with the | character. Patterns look like expressions, but do not think of them as expressions. Instead they are used to match against the result of evaluating the case’s first expression (the part after case). This is why evaluating a case-expression is called pattern-matching.

Datatype Bindings and Case Expressions So Far, Precisely

We can summarize what we know about datatypes and pattern matching so far as follows: The binding

datatype t = C1 of t1 | C2 of t2 | ... | Cn of tn

introduces a new type t and each constructor Ci is a function of type ti->t. One omits the “of ti” for a variant that “carries nothing” and such a constructor just has type t. To “get at the pieces” of a t we use a case expression:

case e of p1 => e1 | p2 => e2 | ... | pn => en

A case expression evaluates e to a value v, finds the first pattern pi that matches v, and evaluates ei to produce the result for the whole case expression. So far, patterns have looked like Ci(x1,...,xn) where Ci is a constructor of type t1 * ... * tn -> t (or just Ci if Ci carries nothing). Such a pattern matches a value of the form Ci(v1,...,vn) and binds each xi to vi for evaluating the corresponding ei.

Type Synonyms

A type synonym simply creates another name for an existing type that is entirely interchangeable with the existing type.

For example, if we write:

type foo = int

then we can write foo wherever we write int and vice-versa.

for more complicated types, it can be convenient to create type synonyms. Here are some examples for types we created above:

type card = suit * rank

type name_record = { student_num : int option,
                    first : string,
                    middle : string option,
                    last : string }

Lists and Options are Datatypes

Because datatype definitions can be recursive, we can use them to create our own types for lists. For example, this binding works well for a linked list of integers:

datatype my_int_list = Empty
                        | Cons of int * my_int_list

We can use the constructors Empty and Cons to make values of my_int_list and we can use case expressions to use such values:

val one_two_three = Cons(1,Cons(2,Cons(3,Empty)))

fun append_mylist (xs,ys) = 
    case xs of
        Empty => ys
    | Cons(x,xs’) => Cons(x, append_mylist(xs’,ys))

For options, all you need to know is SOME and NONE are constructors, which we use to create values (just like before) and in patterns to access the values. Here is a short example of the latter:

fun inc_or_zero intoption = case intoption of
        NONE => 0
      | SOME i => i+1

<!-- val inc_or_zero = fn : int option -> int -->

The story for lists is similar with a few convenient syntactic peculiarities: [] really is a constructor that carries nothing and :: really is a constructor that carries two things, but :: is unusual because it is an infix operator (it is placed between its two operands), both when creating things and in patterns:

fun sum_list xs = 
    case xs:
        [] => 0
        | x::xs' => x + sum_list xs'

Notice here x and xs’ are nothing but local variables introduced via pattern-matching. We can use any names for the variables we want.

Pattern-Matching for Each-Of Types: The Truth About Val-Bindings

fun full_name (r : {first:string,middle:string,last:string}) = case r of
        {first=x,middle=y,last=z} => x ^ " " ^ y ^ " " ^z

However, a case-expression with one branch is poor style — it looks strange because the purpose of such expressions is to distinguish cases, plural. So how should we use pattern-matching for each-of types, when we know that a single pattern will definitely match so we are using pattern-matching just for the convenient extraction of values? It turns out you can use patterns in val-bindings too! So this approach is better style:

fun full_name (r : {first:string,middle:string,last:string}) = 
    let val {first=x,middle=y,last=z} = r
    in
        x ^ " " ^ y ^ " " ^z 
    end

fun sum_triple (triple : int*int*int) = 
    let val (x,y,z) = triple
    in
        x+y+z
    end

fun sum_triple (x,y,z) = x+y+z

This version of sum_triple should intrigue you: It takes a triple as an argument and uses pattern-matching to bind three variables to the three pieces for use in the function body. But it looks exactly like a function that takes three arguments of type int. Indeed, is the type intintint->int for three-argument functions or for one argument functions that take triples? It turns out we have been basically lying: There is no such thing as a multi-argument function in ML: Every function in ML takes exactly one argument! Every time we write a multi-argument function, we are really writing a one-argument function that takes a tuple as an argument and uses pattern-matching to extract the pieces. This is such a common idiom that it is easy to forget about and it is totally fine to talk about “multi-argument functions” when discussing your ML code with friends. But in terms of the actual language definition, it really is a one-argument function: syntactic sugar for expanding out to the first version of sum_triple with a one-arm case expression.

Digression: Type inference

In ML, every variable and function has a type (or your program fails to type-check) — type inference only means you do not need to write down the type.

fun sum_triple triple = case triple of
    (x,y,z) => z + y + x

In fact, type inference sometimes reveals that functions are more general than you might have thought. Consider this code, which does use part of a tuple/record:

fun partial_sum (x,y,z) = x + z
fun partial_name {first=x, middle=y, last=z} = x ^ " " ^ z

In both cases, the inferred function types reveal that the type of y can be any type, so we can call partial_sum (3,4,5) or partial_sum (3,false,5). This is okay because the polymorphism indicates that partial_sum has a more gen- eral type. If you can take a type containing ’a, ’b, ’c, etc. and replace each of these type variables consistently to get the type you “want,” then you have a more general type than the one you want.

Nested Patterns

It turns out the definition of patterns is recursive: anywhere we have been putting a variable in our patterns, we can instead put another pattern. Roughly speaking, the semantics of pattern-matching is that the value being matched must have the same “shape” as the pattern and variables are bound to the “right pieces.” (This is very hand-wavy explanation which is why a precise definition is described below.) For example, the pattern a::(b::(c::d)) would match any list with at least 3 elements and it would bind a to the first element, b to the second, c to the third, and d to the list holding all the other elements (if any). The pattern a::(b::(c::[])) on the other hand, would match only lists with exactly three elements. Another nested patterns is (a,b,c)::d, which matches any non-empty list of triples, binding a to the first component of the head, b to the second component of the head, c to the third component of the head, and d to the tail of the list.

In general, pattern-matching is about taking a value and a pattern and (1) deciding if the pattern matches the value and (2) if so, binding variables to the right parts of the value. Here are some key parts to the elegant recursive definition of pattern matching:

exception BadTriple

fun zip3 list_triple = case list_triple of
    ([],[],[]) => []
        | (hd1::tl1,hd2::tl2,hd3::tl3) => (hd1,hd2,hd3)::zip3(tl1,tl2,tl3) 
        | _ => raise BadTriple

fun unzip3 lst =
    case lst of
        [] => ([],[],[])
      | (a,b,c)::tl => let val (l1,l2,l3) = unzip3 tl
                       in
                           (a::l1,b::l2,c::l3)
end

Exceptions

ML has a built-in notion of exception. You can raise (also known as throw) an exception with the raise primitive. For example, the hd function in the standard library raises the List.Empty exception when called with []:

fun hd xs =
    case xs of
[] => raise List.Empty | x::_ => x

You can create your own kinds of exceptions with an exception binding. Exceptions can optionally carry values with them, which let the code raising the exception provide more information:

exception MyUndesirableCondition
exception MyOtherException of int * int

Kinds of exceptions are a lot like constructors of a datatype binding. Indeed, they are functions (if they carry values) or values (if they don’t) that create values of type exn rather than the type of a datatype. So Empty, MyUndesirableCondition, and MyOtherException(3,9) are all values of type exn, whereas MyOtherException has type int*int->exn.

Tail Recursion and Accumulators

This topic involves new programming idioms, but no new language constructs. It defines tail recursion, describes how it relates to writing efficient recursive functions in functional languages like ML, and presents how to use accumulators as a technique to make some functions tail recursive.

fun sum1 xs =
    case xs of
        [] => 0
      | i::xs’ => i + sum1 xs’

fun sum2 xs =
    let fun f (xs,acc) =
            case xs of
                [] => acc
              | i::xs’ => f(xs’,i+acc)
    in
        f(xs,0)
    end

Why might sum2 be preferred when it is clearly more complicated? To answer, we need to understand a little bit about how function calls are implemented. Conceptually, there is a call stack, which is a stack (the data structure with push and pop operations) with one element for each function call that has been started but has not yet completed. Each element stores things like the value of local variables and what part of the function has not been evaluated yet. When the evaluation of one function body calls another function, a new element is pushed on the call stack and it is popped off when the called function completes.

there is nothing more for the caller to do after the callee returns except return the callee’s result.

This situation is called a tail call (let’s not try to figure out why it’s called this) and functional languages like ML typically promise an essential optimization: When a call is a tail call, the caller’s stack-frame is popped before the call — the callee’s stack-frame just replaces the caller’s. This makes sense: the caller was just going to return the callee’s result anyway. Therefore, calls to sum2 never use more than 1 stack frame.