Overview and basic concepts

This library implements compilation and analysis facilities for language compilers supporting ML- or Haskell-style pattern matching. It provides a compiler from a matching to a decision tree, an efficient representation mapping easily into low level languages. It supports most features one would expect, such as variable bindings, or- and as-patterns, etc. and is also able to detect anomalies in the maching, such as non-exhaustivity or redundantness. It is based on Compiling pattern-matching to good decision trees and Warnings for pattern matching by Luc Maranget.

Pattern matching

Patterns are assumed to be linear and matched “from top to bottom”. This library adopts a simplified view of patterns, or pattern Skeletons, that should be rich enough to accomodate most compilers need. It is either a catch-all pattern, eventually binding an identifier or a constructor pattern made of a tag and subpatterns, filtering only those expression sharing the same tag and whose subexpressions are also filtered by the subpatterns.

As-patterns and or-patterns are also supported, while as-patterns have there own Skeleton, or-patterns must first be decomposed into distinct lists of patterns.

In this documentation, a “row” is a list of patterns associated with an output, that will be selected if an expression matches all those patterns, while a “column” is a list of patterns that are tested against an expression from top to bottom.

Decision trees

Decision trees can be thought of as cascading switches. Each Switch checks the constructor of an expression to decide what path to take, until it reaches a Leaf (success) or encounters a dead-end 'Fail. Consider this Haskell example:

case e of
 ([], 0)    -> 0
 (_ : _, 1) -> 1

A possible decision tree corresponding to this expression could be:

Switch e +--- (,) ---> Switch e(,).0 +---  [] ----> Switch e(,).1 +---- 0 ----> Leaf 0
                                     |                            |
                                     |                            \---- _ ----> Fail [([], 1), ([], 2), ...]
                                     |
                                     \--- _:_ ----> Switch e(,).1 +---- 1 ----> Leaf 1
                                                                  |
                                                                  \---- _ ----> Fail [(_:_, 0), (_:_, 2), (_:_, 3), ...]

First, the expression e is checked for the tag (,). Since there is no other constructor for (,), this always succeeds. Matching on a tuple yields to subexpression that we name e(,).0 and e(,).1 (the Select type handles subexpression selection), that must be matched to two “columns” of patterns: e(,).0 against [] or _:_ and e(,).1 against 0 or 1. Note that we have a choice which test to perform first. Here we decide to check e(,).0 against [] and _:_. Since this is the set of all possible constructors for lists, there is no possibility for the match to fail here. We are then left with e(,).1 to match against 0,in the branch where e(,).0 is [] and 1 when e(,).0 is _:_. In either case, the matching can fail since 0 and 1 do not cover the full range of integers.

Characteristics of decision trees

A decision tree is only one possible target to compile pattern-matching. An alternative is to compile to backtracking automata (see, for instance Compiling pattern matching). Unlike decision trees, backtracking automata guarantee linear code size, however, as the name suggests, they may backtrack, thus testing more than once the same expression, which decision trees are guaranteed never to do.

Heuristics

In the example above, we choose to test e(,).0 before e(,).1, but we could have made the opposite choice. Also, in the _:_ branch we entirely ommited to test e(,).0(_:_).0, e(,).0(_:_).1 (i.e. the head and the tail of the list introducing by matching on _:_) against the two wildcards of _:_. This would of course have been useless, since matching against a wildcard always succeeds. The algorithm can make similar choices as the one we did through the use of Heuristics. The role of Heuristics is to attribute a score to a given list of patterns, so that the algorithm will first match against the list of patterns with the best score. In this case, we attributed a bigger score to the pattern 1 than to the two wildcards. A detailed list of how heuristics work, as well as all the heuristics studied by Maranget are presented later.

How to use?

The library is centered around the match and anomalies functions. match compiles a matching to a decision tree while anomalies simply gathers the anomalies in a matching. Note that the anomalies can only be retrieved from the structure of the decision tree.

The documentation makes heavy use of polymorphism to accomodate the internal representation of most languages. The convention for the names of the parameters is:

• ident is the type of identifiers bound in patterns,
• tag is the type of tags of constructors,
• pat is the type of patterns in the user's language,
• expr is the type of expressions in the user's language,
• out is the type of the outputs of a matching.

To work, these functions need three things from the user (apart from the actual matching):

• a way to decompose the user's language patterns into the simplified representation. This is a function of type pat -> [Skel ident tag], returning a list allows to account for or-patterns. The list of skeletons returned is tested from left-to-right.
• for the tag type to be a member of the IsTag typeclass. This requires to be able to compute some informations from a tag, such as the range of tags it belongs to. Further information is given with the IsTag class.

Complete example

Consider the following typed language with its own Pattern representation:

data Typ     = TInt
             | TList Typ

data Pattern = VarPat Typ  String
             | IntPat      Int
             | NilPat  Typ                  -- NilPat typ has type TList typ
             | ConsPat Typ Pattern Pattern  -- ConsPat typ _ _ has type TList typ
             | OrPat       Pattern Pattern
             | AsPat       Pattern String

This language supports variables, integers and lists. It can have or- and as-patterns.

This custom representation must first be converted into a Skel-based representation. This implies defining the tag of constructors:

data Tag = NilTag | ConsTag Typ | IntTag Int

and doing the conversion:

toSkel :: Pattern -> [Skel String Tag]
toSkel (VarPat typ var)   = [WildSkel (rangeOfTyp typ) (Just var)]
toSkel (IntPat i)         = [ConsSkel (cons (IntTag i) [])]
toSkel (NilPat _)         = [ConsSkel (cons NilTag [])]
toSkel (ConsPat typ p ps) = [ ConsSkel (cons (ConsTag typ) [subp, subps])
                            | subp  <- toSkel p
                            , subps <- toSkel ps
                            ]
toSkel (OrPat p1 p2)      = toSkel p1 ++ toSkel p2
toSkel (AsPat p i)        = [ AsSkel s i
                            | s <- toSkel p
                            ]

where rangeOfTyp defines the range of Tags patterns of a certain type can have:

rangeOfTyp :: Typ -> [Tag]
rangeOfTyp TInt        = fmap IntTag [minBound .. maxBound]
rangeOfTyp (TList typ) = [NilTag, ConsTag typ]

Finally, Tag must be made an instance of IsTag. IsTag has two functions: tagRange :: tag -> [tag] that outputs the signature a given tag belongs to and subTags :: tag -> [[tag]]. subTags t defines the range of tags that can be found in the subpatterns of a constructor with tag t. For instance, a constructor tagged with ConsTag TInt will have two subfields: the first one (the head of the list), can contain any integers, the second one (the tail of the list), can be either the NilTag or another ConsTag. This gives us the following instance:

instance IsTag Tag where
 tagRange NilTag     = [NilTag, ConsTag]
 tagRange ConsTag    = [NilTag, ConsTag]
 tagRange (IntTag j) = fmap IntTag [minBound..maxBound]

 subTags NilTag        = []
 subTags (ConsTag typ) = [rangeOf typ, rangeOf (TList typ)]
 subTags (IntTag _)    = []

and this all one needs to do (apart from choosing a Heuristic) to use the compiler.

Preserving sharing

The presence of or-patterns, like in this example, can cause duplication of outputs in leaves of the decision tree. Consider this example in OCaml syntax:

match e with
| 0 | 1 -> e1
| _ -> e2

The resulting decision tree, would be:

Switch e +--- 0 ---> e1
         |
         \--- 1 ---> e1
         |
         \--- _ ---> e2

with e1 being duplicated, which is undesirable when compiling this decision tree further to machine code as it would lead to increased code size. As a result, it might be worth to consider using labels for outputs and a table linking these labels to expressions. This would make the decision tree suitable for compilation using jumps, avoiding duplication.

Most of the time, there are multiple ways to construct a decision tree, since we are often faced with a choice as to which column of pattern to match first. Doing the wrong choice can lead to larger decision trees or to more tests on average. Heuristics allows us to choose between those different choices.

In there simplest form, heuristics attribute a score to a column, given it's position in the list of columns to match, the expression to match it against and the column of patterns. Some more complicated heuristics exist that require having access to the entire list of columns.

Combining heuristics

A single heuristic may give the same score to several columns, leading to ambiguity on the one to choose. Combining heuristic allows to use a second heuristic to break such a tie.

Note that if there is a tie after applying the heuristic supplied by the user, the algorithm will choose the left-most pattern with the highest score.

Influence on the semantic

Heuristics might have an influence on the semantic of the language if the resulting decision tree is used to guide evaluation, as it can be the case in a lazy language.

“But how do I choose?”

Detailed benchmarks are given in section 9 of Maranget's paper, in terms of code size and average path length in a prototype compiler, both for single and combined heuristics (up to 3 combinations). A conclusion to his findings is given in section 9.2 and is reproduced here:

1. Good primary heuristics are firstRow, neededPrefix and constructorPrefix. This demonstrates the importance of considering clause order in heuristics.
2. If we limit choice to combinations of at most two heuristics, fewerChildRule is a good complement to all primary heuristics. smallBranchingFactor looks sufficient to break the ties left by neededPrefix and constructorPrefix.
3. If we limit choice to heuristics that are simple to compute, that is if we eliminate neededColumns, neededPrefix, fewerChildRule and leafEdge , then good choices are:

• seqHeuristics [firstRow, smallDefault smallBranchingFactor],
• seqHeuristics [constructorPrefix, smallBranchingFactor],
• seqHeuristics [constructorPrefix, smallBranchingFactor] (eventually further composed with arity or smallDefault).

A set of simple and cheap to compute heuristics.

The following heuristics are deemed expensive as they require manipulation on the matrix of patterns to compute a score.

A column \(i\) is deemed necessary for row \(j\) when all paths to \(j\), in all possible decision trees, tests column \(i\). A column \(i\) is necessary if it is necessary for all outputs.

It seems sensible to favour useful columns over non-useful ones as, by definition a useful column will be tested in all paths, whether we choose it or not. Choosing it early might however result in shorter paths.

Necessity is computed according to the algorithm in section 3 of Warnings for pattern matching.

The following heuristics are called pseudo-heuristics as they do not compute a score based on the patterns but rather on the expressions being matched, such as shorterOccurence or simply on the position of the column in the matrix, such as noHeuristic or reverseNoHeuristic. They make for good default heuristic, either alone or as the last heuristic of a combination.