Understanding the algorithm

core.match employs the algorithm described in Luc Maranget's paper [Compiling Pattern Matching to good Decision Trees]((http://www.cs.tufts.edu/~nr/cs257/archive/luc-maranget/jun08.pdf). What follows is a slower paced description of the algorithm.

Necessity and Specialization

Consider the following pattern match:

(let [x true
      y true
      z true]
  (match [x y z]
    [_ false true] 1
    [false true _ ] 2
    [_ _ false] 3
    [_ _ true] 4
    :else 5))

It's clear that the above expression will return 4, as the values match the fourth clause.

As a visual aid we will show the pattern matrix as it goes through a series of transformations in the following form:

Fig. 1

 x y z
-------
[_ f t] 1
[f t _] 2
[_ _ f] 3
[_ _ t] 4
[_ _ _] 5

Note that we've replaced true with t and false with f. Note that the final line is represented as a line of wildcards. Finally we label the columns with the variables (in this context we will use the word "occurrence") and the rows.

Maranget's algorithm is based on a surprisingly simple insight. The semantics of pattern matching dictate that we evaluate the clauses one at a time from top to bottom. Each clause itself is evaluated left to right. Even so this gives us a surprising amount of leeway because of wildcards.

Observe that for the first line to succeed we need never consider x. But this is an important observation! Maranget's algorithm approach produces optimal decisions trees by finding the columns that must be tested and testing them first.

So how do we score a column? Wilcards obviously shouldn't add anything to a column's score. But in addition real patterns below a wildcard should also not add to a column's score. Given these simple rules the matrix when changed to represent the scoring process looks something like this:

Fig. 2

 x y z
-------
[0 1 1] 1
[0 1 0] 2
[0 0 0] 3
[0 0 0] 4
[0 0 0] 5

It's now immediately clear that the y column should be tested first. Maranget's algorithm modifies the pattern matrix by swapping the column that should be tested so that it is the new first column, giving us:

Fig. 3

 y x z
-------
[f _ t] 1
[t f _] 2
[_ _ f] 3
[_ _ t] 4
[_ _ _] 5

At this point we now can generate the first switch of the decision tree. From this step we will compute two new pattern matrices - one will represent a specialized matrix - the matrix that remains after we've made successful match, and the default matrix - the matrix if we don't find a match.

The specialized matrix will look like the following:

Fig. 4

 x z
-----
[_ t] 1

And the default matrix will look like the following:

Fig. 5

 x z
-----
[f _] 2
[_ f] 3
[_ t] 4
[_ _] 5

At this point it should hopefully be clear that we can now recursively apply the above process of selecting the necessary column, and once again splitting between the specialized matrix and the default matrix.

For completeness we illustrate the remaining steps for Fig. 4. We pick the necessary column.

Fig. 6

 z x
-----
[t _] 1

When we specialize this matrix on t we'll be left with:

Fig. 7

 x
-----
[_] 1

Note that there is not default matrix and we are left with a pattern matrix that only has one row and it is a row of wildcards - we have arrived at a terminal node of the decisions tree and should return 1.

Constructors