Compiling Sample Matching

Introduction

This submit intends to supply a quick overview of the algorithm described in Luc Maranget’s
“Compiling Pattern Matching to Good Decision Trees”.

I’m keen on this formalisation because it has a simple implementation and outcomes
in affordable resolution bushes for almost all of sensible situations of sample matching
encountered in purposeful programming.
Moreover, the ensuing resolution tree is simple to purpose about and can be utilized as the premise
of associated transformations – resembling translating into matching over easy patterns (patterns with out nesting), or immediately into an middleman
illustration with be part of factors (a possible method to categorical branching management stream in normal-form intermediate representations).

The Matrix

The central knowledge construction within the algorithm is that of a sample matrix and related incidence and
motion vectors.

• Sample matrix – shops examinable patterns showing on the left-hand aspect of sample matching guidelines.
  The “examinable” refers to the truth that every cell shops a sample that may be scrutinised towards an identical standards (the refutable element of patterns) –
  as we’ll see on this scheme, tuples don’t immediately seem in cells of the sample matrix, however their elements do (as it’s assumed that the arity of a tuple can’t be refuted – in any other case prior typechecking would fail in ML).
  The core compilation algorithm works by performing transformations on the sample matrix, decomposing patterns that admit sure constructors (and values).
• Incidence vector – describes sequence of extractions required to fetch the related worth from a column within the sample matrix. Occurrences should be maintained throughout decomposition of the sample matrix as they
  successfully describe the entry paths to the scrutinees of the n-way branches of the inside nodes within the ensuing resolution tree.
• Motion vector – shops corresponding actions for every row within the sample matrix. These are the expressions that seem on the right-hand aspect of sample matching guidelines (or another figuring out worth, as they could seem in a number of leaves of the choice tree). Upon profitable matching of a sample, the related
  motion is executed (actions subsequently seem as leaves within the resolution tree or, as we’ll come to see, sink nodes within the related DAG illustration).

Matrix Operations

The next sections describe the transformations carried out throughout the algorithm.

Building

The development of the sample matrix and associated motion and incidence vectors requires some care.
The first problem comes from the inclusion of tuples.

Within the case of tuples, they’re by no means immediately saved in cells of the sample matrix – their elements are.
That is exemplified by the primary instance in Maranget’s paper regarding the implementation of a canonical
merge perform in an ML-like language:

enjoyable merge xs ys = 
  case (xs, ys) of
     (Nil, _) => (* 1 *)
   | (_, Nil) => (* 2 *)
   | (Cons (x, xs), Cons (y, ys)) => (* 3 *)

For readability, I’ve opted to call checklist constructors explicitly (as Nil and Cons).

The preliminary sample matrix and related vectors will appear to be this:

The v showing within the incidence vector denotes the scrutinee of the case ((xs, ys)).
The v.i notation denotes a projection.
It’s written this method to make the presentation shorter. Moreover, it’s implicitly assumed that
the bottom of occurrences will not be truly the unique expressions themselves, however a variable that refers to them.
It’s because, when producing code for every match case, you possibly can convey the related sample variables
into scope by introducing them with let bindings (that bind the results of translating occurrences into the related unwrappings and projections).
To keep away from doubtlessly duplicating an effectful operation when introducing these variables, it’s assumed a sort of
normalisation is carried out to present a reputation to the expression being matched upon.
This type of legalisation may be carried out earlier than match compilation
or doubtlessly throughout a mixed normalisation algorithm, the place normalising the scrutinee of a case will yield an atomic worth.

As you possibly can see within the above illustration, the sample matrix doesn’t retain the construction of the tuples
showing in every rule of the match. When translating a tuple sample right into a row for the sample matrix,
you introduce a column for every element. Every element is moreover labelled with an incidence that denotes
the projection from the related index of the tuple.

One other supply of complexity comes from the truth that patterns in a case needn’t have the identical form.
This state of affairs is typified by catch-all sample variables that will comply with tuple patterns.
Think about the next snippet of SML code:

case f () of 
   (SOME x, _) => (* 1 *)
 | t => (* 2 *)

The issue with the above is that t will disappear when setting up the sample matrix as a result of columns
for elements of the prior tuple are launched as a substitute.
An answer for this state of affairs could also be a previous legalisation that strikes top-level sample variables to the right-hand
aspect of match guidelines:

let val v = f () in
  case v of 
     (SOME x, _) => (* 1 *)
   | _ => let val t = v in (* 2 *) finish
finish

Doing this may be certain that t will likely be in scope for the code in (* 2 *).

One other approach of making certain the form of patterns don’t introduce annoying edge instances or require writing this system is to bookkeep every sample when it comes to its occurrences.
For instance, in my very own easy implementation of the match compilation algorithm (here), building of the sample matrices is finished by gathering
dictionaries (one for every sample), mapping occurrences to their associated sample elements. Then, a matrix is constructed by filling in a desk whose columns are the occurrences traversed throughout the dictionary creation course of (within the left-to-right order they have been visited). From this attitude, a lot of the match compilation algorithm may be seen as constructing and decomposing tables (matrices).

Specialisation

With the intention to rework the matrix and vectors right into a state that represents the profitable matching of a price or constructor upon a group of rows, specialisation is carried out. Specialisation is an operation that retains solely the rows of the matrix that admit a specified worth or constructor,
concurrently decomposing value-carrying sub-patterns into their corresponding entries within the sample matrix and incidence vector (with necessities just like that of the preliminary building of the sample matrix).

Think about the next code snippet and related preliminary sample matrix and vectors:

case v of
   Some (1, x) => (* 1 *)
 | Some (y, 2) => (* 2 *)
 | None => (* 3 *)

Specialisation of the Some constructor yields the next:

Right here, [v], denotes accessing the worth held by the constructor.
The attraction of the matrix formalism for simultaneous matching is evident when you think about that the resultant matrix successfully fashions the internal case of the
following snippet:

case v of
   Some z =>
     case z of 
        (1, x) => (* 1 *)
      | (y, 2) => (* 2 *)
     finish
 | None => (* 3 *)
finish

the place z is a reputation given to the unwrapping incidence.
It isn’t exhausting to see that the resultant resolution tree can be utilized to rewrite sample matching into matching over easy patterns.

Equally, specialising the unique matrix from above upon None yields the next:

Be aware that, for consistency, nullary constructors resembling None should be handled as if they carry unit, (), which – when launched to the sample matrix – will
assemble a row with a single wildcard sample. The rationale for that is for consistency and to keep away from a case of the algorithm (described in a later part)
that might deal with an empty matrix as indicative of matching failure.

Defaulting

Producing the default matrix of a given sample matrix retains solely the rows that match constructors or values not already current
within the column being scrutinised.
In different phrases, if the column being scrutinised accommodates an irrefutable (both a sample variable or wildcard) entry, then its decomposition
is included within the default matrix.
Or, within the case the place matching is inexhaustive, defaulting creates an empty sample matrix (since there are not any rows to confess any constructor or worth).
Intuitively, if every inside node of the choice tree swapes on a column’s worth (utilizing the occurence for that column), then
defaulting is used to create the default case (to account for constructors or values not current).

Be aware that specialisation and defaulting might produce matrices with rows in widespread.
Moreover, it might be necessary that defaulting retains variables and their occurrences (so as to introduce sample variables into scope upon a sucessful match).
This concern is mitigated in Maranget’s rationalization of the algorithm as their paper
dispenses of sample variables, contemplating solely wildcards (which may be considered regionally distinctive sample variables with no makes use of).

Swapping

To assist with implementation of the algorithm, an auxiliary operation that swaps columns of the sample matrix (and, consequentially, the incidence vector) should be applied. As you will note within the following part that describes the algorithm, all prior references to the “column being scrutinised” truly refer solely to the primary column, as matching proceeds left-to-right; making certain that there’s all the time a refutable sample within the first column by doubtlessly swapping it for an additional.

The Algorithm

The algorithm is effectively described within the paper, however I’ll recite it right here anyway.
It’s outlined as recursive perform that performs case evaluation over the supplied matrix.
The instances are as follows:

1. If the sample matrix is empty, that suggests it was produced by a defaulting operation that would discover
   no row to incorporate, so it’s indicative of matching failure. A leaf node indicating failure is returned.

2. If the primary row of the sample matrix is irrefutable (i.e. solely sample variables or wildcards), then
   matching has succeeded and we return a leaf node containing a reference to the motion vector entry the for the primary row.

   If there are different rows within the sample matrix which are additionally irrefutable then that suggests the sample equivalent to the primary row
   subsumes them. In different phrases, these further rows are redundant as they will by no means be reached.

3. If neither of the earlier instances maintain then we search for a column that accommodates no less than one refutable entry.
   If the discovered column is just not the primary one, we make it the primary by swapping their positions.

   Now that the primary column is refutable, we accumulate a type of signature by analysing every entry.
   If the column’s sort is a variant, then we accumulate all of the names of constructors from entries that comprise
   variant constructor patterns (for instance, we’d accumulate Some if we encounter Some (1, x)). An analogous assortment is finished for different kinds of refutable patterns, resembling integer constants.

   As soon as the signatures are collected, a specialised matrix is produced for every one. These matrices are then recursively compiled by the
   algorithm and the resultant resolution bushes are recorded as targets of an n-way switching node within the resolution tree.

   If the signature is just not full, i.e. doesn’t comprise all potential constructors for a given sort, then the default matrix is computed
   for the unique matrix – the resultant resolution tree is then included among the many alternate options of the returned swap node because the default case.

   See Also

   

   Stat Arb – An Straightforward Walkthrough

Instance

Beneath is a whole annotated instance of the conceptual means of computing the choice tree for the next SML snippet:

case v of
   Some (1, x) => (* 1 *)
 | Some (y, 2) => (* 2 *)
 | None => (* 3 *)

Additional examples

Beneath are a number of instance SML snippets and their corresponding resolution bushes, produced by my implementation of the algorithm described above:

First, the instance given within the paper (for merge or an analogous perform, resembling zip):

case e of
    (Nil, _) => (* 1 *)
  | (_, Nil) => (* 2 *)
  | (Cons (x, xs), Cons (y, ys)) => 

Secondly, a extra compact presentation of the operating instance used on this article:

case e of
   Some (1, x) => (* 1 *)
 | Some (y, 2) => (* 2 *)
 | None => (* 3 *)

Lastly, Okasaki’s red-black tree stability perform (from “Purely Practical Information Buildings”):

case e of
   (B,T (R,T (R,a,x,b),y,c),z,d) => (* 1 *)
 | (B,T (R,a,x,T (R,b,y,c)),z,d) => (* 2 *)
 | (B,a,x,T (R,T (R,b,y,c),z,d)) => (* 3 *)
 | (B,a,x,T (R,b,y,T (R,c,z,d))) => (* 4 *)
 | physique => (* 5 *)

I embody this instance as a result of it illustrates an necessary level – these conscious of the implementation of stability
will know that each case, besides the final, has the identical physique. So, in SuccessorML, one would write this as a disjunctive sample:

case e of
   (B,T (R,T (R,a,x,b),y,c),z,d)
 | (B,T (R,a,x,T (R,b,y,c)),z,d)
 | (B,a,x,T (R,T (R,b,y,c),z,d))
 | (B,a,x,T (R,b,y,T (R,c,z,d))) => (* 1 *)
 | physique => (* 2 *)

If compilation have been to naively proceed by duplicating the physique at (* 1 *) for every case, we’d get the identical resolution tree as above.
A extra concerned strategy would try to attain sharing by setting up a DAG (directed acyclic graph) so as to deduplicate the repeated rule our bodies.
Nonetheless, naively doing this from the above tree might produce a DAG that accommodates redundant selections (e.g. worth and default branches which have the identical vacation spot).
A attainable strategy can be to try to optimise the DAG after-the-fact after which, when emitting code for the choice tree, the shared rule physique turns into its personal perform that
receives its variables (these certain as sample variables and free variables – just like lambda lifting) as arguments. Then, depending on the trail adopted to get there, the variables will likely be projected from the scrutinee and
supplied as arguments to the deduplicated perform.

The easy strategy is to determine sharing upon building of nodes within the resolution tree, by way of hash consing.
This strategy is described in Pettersson’s ebook “Compiling Pure Semantics” and the one I took for my very own implementation.

Beneath, you possibly can see the choice DAG (for the stability instance) ensuing from an implementation that makes use of hash consing:

An Implementation

Within the time since writing this text, I’ve created a quite simple implementation of the algorithm here.
Together with offering a devoted implementation of the core concepts described on this article, it additionally supplies a small person interface for enjoying round with seeing potential resolution bushes.

Additional Studying

• [Augustsson 85] – compiles sample matching to backtracking automata, thus making certain code dimension that’s linear within the dimension of the unique sample matching expression, however doubtlessly checking subterms a number of occasions.
• [Pettersson 92] – fashions the match compilation drawback as the development of a DFA for an everyday language, thus enabling
  sure types of optimisations (seen as minimisation of the DFA) and checking of assorted matching properties resembling exhaustiveness and redundancy.
• [Pettersson 99] – Pettersson’s ebook “Compiling Pure Semantics” accommodates a extra detailed retelling of the algorithm described within the work above.
• [Reppy et al. 19] – considers compilation of Successor ML guards. The linked repository additionally has a number of implementations of assorted approaches to the compilation
  of sample matching.

Afterword

In efforts to show the core concept of the algorithm described on this weblog article,
I’ve discovered that it’s useful to start out with easier examples – consisting purely of tuples of, say, integers patterns (no wildcards or variable patterns).
Then, as soon as somebody is acquainted with the overall strategy (matrix specialisation), including all of the bookkeeping for sample variables, defaulting of the matrix, deconstructing nested patterns into the matrix, and so on. change into affordable extension initiatives for them to program round.

For instance, within the OCaml compiler, sample matching over fixed strings truly follows the easier subset of the match compilation algorithm described on this article. I hope to dedicate a future article to this – however, till then, a wonderful description of the core concept has been given by Gabriel Scherer on the OCaml discussion board here.