Apple announce a new programming language today: Swift. I’m excited because it includes pattern matching, which I consider the most important language feature from academic languages (ML, Haskell) that had not yet crossed over into mainstream languages. (Sorry, F# and Scala, you aren’t mainstream. Swift already has Flappy Bird.)

Pattern matching is a very compact and readable way to deconstruct tree-structured datatypes. In ML, a canonical example is a tree type like this:

type tree =
  Leaf of int
| Node of tree * tree

So, for example, a binary tree with leaves 1, 2, 3, 4 can be written

let t = Node(Leaf 1,Node(Node(Leaf 2, Leaf 3), Leaf 4))

and left and right subtrees can be extracted with the pattern

match t with
  Node(left, right) -> ...

Here left is a variable that is bound by the pattern to Leaf 1, and right is a variable bound to the pattern to

Node(Node(Leaf 2, Leaf 3), Leaf 4)

Swift, which traces its lineage to C, has a more C-like syntax. I haven’t been able to download the latest Xcode to try this out, but it should look something like this:

enum Tree {
    case Leaf(Int)
    case Node(Tree, Tree)
}

for the type declaration,

let t = Tree.Node(Tree.Leaf(1),
                  Tree.Node(Tree.Node(Tree.Leaf(2), Tree.Leaf(3)),
                            Tree.Leaf(4)))

to build the tree value, and

switch (t) {
case .Node(let left, let right): ...
case .Leaf(let x): ...
}

for the pattern matching. The Swift syntax is actually a bit like what we used in Cyclone, an experimental language that added pattern matching (among other things) to C. No surprise, given their common roots in C.

[UPDATE: the code should work but currently triggers a bug in the Swift compiler.]

In Swift, as in ML, patterns are required to be exhaustive, that is, in a switch statement there must be at least one case that matches every possible value. Most people don’t know this, but exhaustiveness checking is an NP-complete problem. It doesn’t seem to arise in ordinary programming, but it’s something to be aware of if you are going to be compiling code produced by unknown and possibly-malicious parties.

Pattern matching was my introduction to the world of academic programming language research—I implemented the first pattern match compiler for Standard ML of New Jersey at Bell Laboratories in 1986. However, pattern matching goes back much farther than that. The somewhat-lame Wikipedia page on pattern matching currently says that the first language with tree-based pattern matching was McBride’s extension of LISP from 1970, but, in fact, it may go back as early as 1957, and certainly existed by the early 1960’s (see my post on John Reynolds for the history). Pattern matching is thus one of those innovations that take more than 30 years to make it to the mainstream. So, celebration is in order!