Introduction

The elimination form for constructed data is pattern matching (the case expression). Constructed data is a tree: an internal node is a block that represents an application of a value constructor, and a leaf may be a bare value constructor or any other value. This tree is called the subject tree. Pattern matching selects a choice in a case statement based on which value constructors are used in a subject tree, with what arities, at what points.

An efficient implementation of pattern matching often uses code that is structured as a decision tree. Each node of a decision tree examines one node of the subject tree. Based on the value constructor at the subject node and the number of arguments the value constructor is applied to, the decision node may have enough information to transfer control directly to code that matches a pattern, or it may need to examine some other part of the subject tree, which means transferring control to a subtree of the decision tree. In a decision tree, no node in the subject tree is examined more than once.

A typical target machine (VMs or native code) doesn’t implement decision trees directly. Instead, it implements a computed goto that transfers control based on a single value. In our SVM, that value is a labeled constructor. (In native code, the value is typically a small integer.)

The process of turning a single case expression into a decision tree is match compilation. Match compilation is the centerpiece of this module. We’ll implement an algorithm described by Kevin Scott¹ and Norman Ramsey in their unpublished paper “When do Match-Compilation Heuristics Matter?”.

Your match compiler will be called from the K-normalizer and will work with expressions in K-normal form. It will therefore have to handle some details about registers that you won’t find in the paper. In particular, your decision trees will have a form of node that serves only to put a subject-tree value into a VM register.

From paper to code

Scott and Ramsey’s paper is really about the heuristics that might be used to decide in which order to scrutinize the nodes of a subject tree that is being matched. But the paper also presents a match-compilation algorithm, which our match compiler will use. We’ll ignore heuristics.

Before you begin working on your match compiler, you’ll read the first part of the paper, up to and including section 3.1. Skim section 1; focus on sections 2 and 3.

Reading Scott and Ramsey

When reading section 2, be aware of two correspondences:

The paper’s “constructor” \(C\) is our “labeled constructor” \(C/n\).
In a match, the paper’s substitution \(\sigma\) is going to correspond to a set of let bindings of registers to values.

When reading section 3, be aware of this difference:

Their decision tree must test values from the subject tree. Each value is specified by the path used to reach that value from the root of the subject tree. Each leaf of the decision tree also includes an environment that gives the location of each bound variable, also as a path.

Since our match compiler runs during K-normalization, we will instead put each tested value and each bound value into its own VM register.

In order to get those values into registers, we will extend our decision trees with an additional binding form.

The algorithm we will implement is described in the paper in Figure 8 on page 8. The algorithm compiles a list of frontiers, and I summarize it as follows:

Does the first frontier match? If so, return a match node.
If not, start planning a test node. What path do we want to test? Call it \(\pi\).
What constructors appear at path \(\pi\) (in any frontier)? Call them \(\mathit{CS}\).
For each constructor \(C\) that appears at path \(\pi\), compute an edge leaving the test node we plan to generate. Refine the frontiers using the \(\mathit{project}\) functions, and point the edge to a tree obtained by compiling the refined frontiers recursively.
At path \(\pi\), the subject tree might contain a constructor that is not mentioned in any frontier. Any frontier that could match such a constructor should go into \(\mathit{defaults}\). Compile them too.
Return the test node.

To explain the figure in more detail I will replace the paper’s constructor \(C\) with our fully labeled constructor \(C/n\). This change of notation won’t make any difference to the code, but it will make the specification easier to follow.

Study Figure 8 with the following analysis in mind:

In a frontier \((i, f)\), the \(i\) keeps track of what code should be branched to when the decision tree reaches a leaf. The \(i\) has an unknown type \(\alpha\) (’a in our code), and it’s not important to the algorithm. The important thing is the list \(f\), which contains pairs of the form \((\pi,p)\). Each one of these pairs represents a fragment of the original pattern, and the pair acts as a constraint:
- A constraint \((\pi,p)\) is satisfied if the subject tree at path \(\pi\) matches pattern \(p\).
- A frontier matches if and only if all its constraints are satisfied.
When every constraint in the first frontier uses a variable pattern or a wildcard pattern, all the constraints are satisfied, and the frontier matches.
The heuristics that we are ignoring are used in the figure at the first \(\mathbf{else}\) clause, which says “\(\mathbf{let}\) \(\pi\) be a path.” When more than one path is eligible, a heuristic chooses one from all the eligible paths.
\(\mathit{CS}\) is the set of all labeled constructors that occur at path \(\pi\), across the entire case expression.
Each edge of the decision tree is labeled with a constructor \(C/n\), and that edge points to a tree that has only the frontiers that match \(C/n\).
At run time, the subject tree might contain a labeled constructor \(C'/n'\) that is not in the set \(\mathit{CS}\). In that case, it executes the tree \(\mathit{compile}\) \(\mathit{defaults}\). The \(\mathit{defaults}\) list contains all the frontiers that match every value at path \(\pi\). A frontier is in that set if it doesn’t constrain \(\pi\) or if it constrains \(\pi\) to match a wildcard or a variable.
The function \(\mathit{project}(C/n,\pi)(i, f)\), which you will implement as refineFrontier, has this contract:
- If every constraint in \(f\) is compatible with having constructor \(C\) applied to \(n\) arguments at path \(\pi\) in the subject tree, return SOME \((i, f')\), where \(f'\) is a refinement of \(f\) that accounts for \(C/n\).
  
  The refinement replaces each constraint of the form \((\pi, C(p_1, \ldots, p_n))\) with a list of constraints of the form \([(\pi.1, p_1), \ldots, (\pi.n, p_n)]\).
- If any constraint in \(f\) is incompatible with having constructor \(C\) applied to \(n\) arguments at path \(\pi\) in the subject tree, return NONE. A constraint \((\pi, C'(p_1, \ldots, p_k))\) is incompatible if either \(C' \ne C\) or \(k \ne n\).
The compatible frontiers are tagged with SOME so they can be selected by List.mapPartial during the computation of \(\mathit{edges}\).

Paths, registers, and `let` bindings

Given a nested pattern like

SOME x :: xs

The paper will produce the set of bindings \(\{\mathtt{x} \mapsto \Lambda.1.1, \mathtt{xs} \mapsto \Lambda.2 \}\).² \(\Lambda\) stands for the register that holds the root of the subject tree, and each dot stands for a getblockslot primitive. But our match compiler is part of our K-normalizer, and an expression like getblockslot(getblockslot(\(\Lambda\), 1), 1) isn’t in K-normal form. To ensure K-normality, we’ll restrict the forms of paths and decision trees:

Every path refers either to the value in some register \(r\) or to the direct child of a value in a register.
A \(\mathit{TEST}\) node may not test a value at an arbitrary path \(\pi\); it may only test a value that is in a register.

To get a value into a register when necessary, the match compiler will introduce a let binding using continuation-passing style. It works just like other parts of the K-normalizer.
A constraint in a \(\mathit{MATCH}\) node may not associate a variable with an arbitrary path \(\pi\); each constraint must have the form \((r, x)\), where \(r\) is a register and \(x\) is the name of a bound variable.

The restrictions on nodes and paths are embodied in these datatype definitions:

datatype 'a tree = TEST      of register * 'a edge list * 'a tree option
                 | MATCH     of 'a * register Env.env
                 | LET_CHILD of (register * int) * (register -> 'a tree)
and      'a edge = E of labeled_constructor * 'a tree

datatype path = REGISTER of register | CHILD of register * int

The TEST and MATCH forms are as in the paper. The LET_CHILD form carries two arguments:

The register * int pair contains the path \(r.i\): a register that holds a block in the subject tree, plus an integer slot number within that block.
The other argument is a continuation that takes a temporary register and returns a decision tree.

A LET_CHILD tree is translated into K-normal form something like this:

𝓡\(r\)⟦LET_CHILD ((\(r\), \(i\)), \(k\))⟧ = let \(t\) = getblockslot(\(r\), \(i\)) in \(k\) \(t\),

where \(t\) is a fresh (temporary) register.

Path aliasing

During lab I was asked what happens if, say, REGISTER r and CHILD (r’, i) refer to the same location? Or more generally, what if π ≠ π’ but both π and π’ refer to the same location. It can’t actually happen, but what if it did?

The match compiler satisfies all the constraints it sees. Since it assumes that different paths refer to different locations, information about π doesn’t affect a constraint at π’. If π ≠ π’ and the match compiler sees constraints at both π and π’, it will eventually generate TEST nodes for both π and π’, even if both paths refer to the same location. The generated code will still work, but it will test the same part of the subject tree more than once, violating a claim of the match-compilation algorithm.

But paths never alias during match compilation. New paths are introduced by refineConstraint (at TEST nodes) and by LET_CHILD nodes. These new paths never introduce aliasing. That is, it is an invariant of the system that if π ≠ π’, then π and π’ refer to distinct locations:

Initially there is only one path (the root), so the invariant holds trivially.
One way to introduce a new path is by refinement. But for any register r and index i, CHILD (r, i) always refers to a different location from REGISTER r. So if there is no aliasing in the system, aliasing can’t be introduced by refinement.
The other way to introduce a new path is by generating a LET_CHILD node. But whenever the K-normalizer introduces a fresh register t (via the LET_CHILD continuation), it always stands for a path of the form CHILD (r, i), and t is immediately substituted for CHILD (r, i) everywhere. So there is still no aliasing.

Implementing Figure 8

Before implementing Figure 8, look over the code I provide in match-compiler.sml.

The code is functorized, and the register type is abstract. The abstraction helps the type checker help you.
To help with the refinement operation (\(\mathit{project}\) in the paper), I’ve defined type ’a compatibility, which is supported by functions mapCompatible and compatibilityConcat.
Functions maybeConstructed, refineConstraint, and refineFrontier are meant to implement key parts of the match compiler. Take note of their types and contracts.

Once you start coding, you may benefit from this guidance:

When you implement “\(\mathbf{let}\) \(\pi\) be a path,” \(\pi\) might have the form \(r.i\). In that case, return a LET_CHILD node whose continuation calls the match compiler recursively.
To implement “\(\mathbf{let}\) \(\pi\) be a path,” our heuristic will be “grab the first eligible path you find.” That is, our code will find a path \(\pi\) by looking for a constraint of the form \((\pi, C(p_1, \ldots, p_n))\). That constraint gives us path \(\pi\) and labeled constructor \(C/n\).
When computing \(\mathit{CS}\), you may find a use for this function:
```
fun nub xs = Set.elems (Set.ofList xs)
```