How to compile pattern matching

Jules Jacobs

May 2, 2021

Abstract

This is a note about compiling ML-style pattern matching to decision trees. I try to keep it
simple while still presenting the key idea of efficient pattern match compilation [Mar08].

1 Introduction
Our goal is to compile ML-style pattern matching:

match a with
| Add(Zero, Zero) =⇒ e1
| Mul(Zero, x) =⇒ e2
| Add(Succ(x), y) =⇒ e3
| Mul(x, Zero) =⇒ e4
| Mul(Add(x, y), z) =⇒ e5
| Add(x, Zero) =⇒ e6
|x =⇒ e7

In order to keep things straight, I’ll use green variables a for bound local variables that have a
value and red variables x for variables that will be given a value by pattern matching.
The naive way to compile this is to test the patterns from top to bottom, and try to match
a against each pattern. This is inefficient: if the outer constructor of a is an Add but the first
pattern fails, then the second pattern will test if a is a Mul, even though it is already known to be
an Add at this point. Then the third pattern will test once more whether a is an Add, which is
redundant. We’d like to compile pattern matching to code that does no unnecessary tests.
This does mean that we must start by trying to match the first pattern: if the first pattern
succeeds then any work trying to match other patterns is unnecessary. So our strategy will be to
emulate the naive strategy that tries to match the first pattern completely, but when we fail in the
middle of the matching process, we remember what we learnt to compile a specialised version of
the remaining pattern matches that takes what we learnt into account.

1
2 Compiling the example
It will be useful to represent a match expression not as a list of patterns implicitly testing against
an outer variable a, but as a list of clauses that each specify explicitly what it tests against:

match
| a is Add(Zero, Zero) =⇒ e1
| a is Mul(Zero, x) =⇒ e2
| a is Add(Succ(x), y) =⇒ e3
| a is Mul(x, Zero) =⇒ e4
| a is Mul(Add(x, y), z) =⇒ e5
| a is Add(x, Zero) =⇒ e6
| a is x =⇒ e7

In general, each clause can have multiple tests and will be of the form

| a1 is pattern1 , . . . , ak is patternk =⇒ e

Where a1 , . . . ak are bound variables, and pattern1 , . . . , patternk are patterns. This additional
flexiblity will turn out to be useful during pattern match compilation.
Our goal will be an algorithm that takes as input such a list of clauses, and outputs a tree of
simple primitive pattern matches (match#) that test against a single constructor:

match# a with
| C(a1 , . . . , an ) =⇒ [A]
|_ =⇒ [B]

Let’s see how to do this for the example. We start working on the first test by testing a against
the Add constructor with the following pattern match:

match# a with
| Add(a1 , a2 ) =⇒ [A]
|_ =⇒ [B]

Then we have to solve the following sub problem for A:

[A] =
match
| a1 is Zero, a2 is Zero =⇒ e1
| a1 is Succ(x), a2 is y =⇒ e3
| a1 is x, a2 is Zero =⇒ e6
| a is x =⇒ e7

Notice how we now have multiple tests per clause, corresponding to the a1 and a2 in the generated
match, which become bound variables a1 and a2 in A.
We can simplify these problems by pushing test against bare variables such as a2 is y into the
right hand sides. Then the sub problem for A becomes:

[A] =
match
| a1 is Zero, a2 is Zero =⇒ e1
| a1 is Succ(x) =⇒ let y = a2 in e3
| a2 is Zero =⇒ let x = a1 in e6
| =⇒ let x = a in e7

2
(actually, we could have done this for the last test already in the previous step)
We now continue matching by trying to match a1 = Zero, by generating the pattern match:

match# a1 with
| Zero =⇒ [C]
|_ =⇒ [D]

And continuing recursively for [C] and [D].

The sub problem for [B] is obtained by removing all the clauses with a is Add(. . . , . . . ) from the
original problem:

[B] =
match
| a is Mul(Zero, x) =⇒ e2
| a is Mul(x, Zero) =⇒ e4
| a is Mul(Add(x, y), z) =⇒ e5
| a is x =⇒ e7

3 The general algorithm

Let’s generalise and see what’s going on. Given a list of clauses to generate a pattern matching
tree for, we use this algorithm:
1. Push tests against bare variables a is y into the right hand sides using let y = a, so that all
the remaining tests are against constructors.
2. Select one of the tests a is C(P1 , . . . , Pn ) in the first clause using some heuristic.
3. Generate this pattern match:

match# a with
| C(a1 , . . . , an ) =⇒ [A]
|_ =⇒ [B]

4. Create the two sub problems [A] and [B] as follows by iterating over all the clauses. One of
three cases can happen:
(a) The clause contains a test a is C(P1 , . . . , Pn ), . . . REST . . . for a.
Add the expanded clause a1 is P1 , . . . , an is Pn , . . . REST . . . to A.
Make sure that the fresh variable names a1 , . . . , an are used consistently in
match a with C(a1 , . . . , an ) and in the tests a1 is P1 , . . . , an is Pn .
(b) The clause contains a test a is D(P1 , . . . , Pn ), . . . REST . . . where D ̸= C.
Add this clause to B unchanged.
(c) The clause contains no test for a. Add this clause to both A and B.
(note that each clause can only have one test for a)
5. Recursively generate code for [A] and [B].
The recursion has two base cases:
• The list of clauses is empty: all patterns failed, so generate an error:
“Error: Non-exhaustive pattern match.”
• The first clause is empty (has zero tests): the first clause succeeded to match, so simply
return the right hand side ei .

4 Heuristic
How do we decide which test to pick from the first clause to branch on? Any test works, but we’d
like to generate a compact pattern matching tree. Whenever we are in case (c) for one of the
other clauses, we have to add that clause to both A and B. That can cause code explosion. To
avoid it we want to select the test that causes the least code explosion. We therefore select a test
that is present in the maximum number of other clauses.

3
 Consider this example:

match a with
| Add(Add(x, y), Zero) =⇒ e1
| Add(Mul(x, y), Zero) =⇒ e2
| Add(x, Mul( y, z)) =⇒ e3
| Add(x, Add( y, z)) =⇒ e4
| Add(x, Zero) =⇒ e5

For the outer constructor we have no choice, but for the inner constructors we can either test
Add(x, y) first or Zero first. If we test Add(x, y) first, then we end up duplicating the e3 and e4
clauses. Our heuristic chooses to match on Zero instead, which leads to optimal code without any
duplication:

match# a with
| Add(a1 , a2 ) =⇒
match# a2 with
| Zero =⇒
match# a1 with
| Add(x, y) =⇒ e1
| Mul(x, y) =⇒ e2
|_ =⇒ e5
| Mul( y, z) =⇒ e3
| Add( y, z) =⇒ e4
|_ =⇒ ERR
|_ =⇒ ERR

(I’ve merged subsequent tests of the same variable into a single match – see below)

5 Discussion
This algorithm is a bit different than the algorithms in the literature. It is based on the following
observations and considerations.
Some of the literature spends effort on avoiding exponential code explosion, and opts to
generate redundant tests instead [Aug85]. Exponential code explosion doesn’t occur in practice
[SR00]. Therefore the right approach seems to me to never generate redundant tests, and to try
to avoid code duplication using a heuristic as e.g. [Mar08] does.
In fact, the literature shows that for real world code, different pattern matching algorithms
generate almost identical code [SR00, Mar08]. Our approach here is to (1) always work on match-
ing the first clause first, to avoid unnecessary tests and (2) greedily try to minimize duplication
using the heuristic. This isn’t exactly what is in the literature, but it is similar to the heuristics in
[Mar08].
Generating binary tests instead of n-way tests that simultaneously branch on several possible
constructors may be necessary to avoid duplication:

match (a, b) with

| (A, _) =⇒ e1
| (_, A) =⇒ e2
| (_, B) =⇒ e3
| (_, C) =⇒ e4
| (_, D) =⇒ e5
| (B, E) =⇒ e6
| (C, F ) =⇒ e7

4
If we do a 3-way branch on a = A, B, C, then we have to duplicate the middle clauses for both B
and C. On the other hand, if we simply test if a = A, and then test b = A, B, C, D, E, F , then we
have no duplication.
Executing an n-way branch may be compiled more efficiently using a jump table than a series
of 2-way branches. It is not difficult to detect a series of 2-way branches on the same variable,
and convert those back into an n-way branch.
Some of the literature uses decision DAGs instead of decision trees. The easiest way to generate
a decision DAG is simply to generate a decision tree and then compress it to a DAG using hash
consing [Mar08]. A simpler though less optimal solution is to only do this for the right hand sides,
and not for the internal nodes of the decision tree: we could generate a separate basic block for
each unique right hand side, and replace the right hand sides by a jump to the corresponding
basic block.
To take advantage of types, you can keep track of the remaining possible constructors of each
variable. This way you can avoid generating the error cases when there are no remaining possible
constructors. You can then do exhaustiveness checking by looking if an error case was generated
or not. You can check for redundant patterns by looking at whether one of the orignal right hand
sides ei doesn’t appear in the decision tree.

6 Code
Scala code that implements the algorithm can be found at
[Link]
Yorick Peterse implemented a much more advanced version in Rust. His version supports con-
structors, integer literals and ranges, or-patterns, guards, and exhaustiveness and redundancy
checking. The repository also contains a good README explaining the algorithm and how to
implement the advanced features. The syntax “a is pattern” was invented by Yorick. I initially
used “a = pattern”, but I think Yorick’s syntax is clearer.

References
[Aug85] Lennart Augustsson. Compiling pattern matching. In Proc. of a conference on Functional
programming languages and computer architecture, pages 368–381, Berlin, Heidelberg,
January 1985. Springer-Verlag.
[Mar92] Luc Maranget. Compiling lazy pattern matching. In Proceedings of the 1992 ACM
conference on LISP and functional programming, LFP ’92, pages 21–31, New York, NY,
USA, January 1992. Association for Computing Machinery.
[Mar08] Luc Maranget. Compiling pattern matching to good decision trees. In Proceedings of
the 2008 ACM SIGPLAN workshop on ML, ML ’08, pages 35–46, New York, NY, USA,
September 2008. Association for Computing Machinery.
[Pet92] Mikael Pettersson. A Term Pattern-Match Compiler Inspired by Finite Automata Theory.
In Proceedings of the 4th International Conference on Compiler Construction, CC ’92, pages
258–270, Berlin, Heidelberg, October 1992. Springer-Verlag.
[Ses96] Peter Sestoft. ML pattern match compilation and partial evaluation. In Olivier Danvy,
Robert Glück, and Peter Thiemann, editors, Partial Evaluation, pages 446–464, Berlin,
Heidelberg, 1996. Springer Berlin Heidelberg.
[SR00] Kevin Scott and Norman Ramsey. When Do Match-compilation Heuristics Matter?
Technical Report, University of Virginia, USA, 2000.