Chapter 8 Compiling Moby patterns

This note desribes the algorithms used by the Moby compiler to translate pattern matches to simpler form. Our approach is based on that of Pettersson [Pet92], but handle a richer language for specifying patterns.

8.1 Pattern matching in Moby

Along with function application, pattern matching is one of the two mechanisms for control-flow in functional languages. In Moby, we have enhanced the power of pattern matching over that found in SML in several ways:

Or-patterns allow two or more alternatives to be specified. For example, the pattern
(_::a::b::_ | a::b::Nil)
matches a list of length two or greater; if the list has length two, then the elements are bound to a and b, if the list has length greater than two, then the second and third elements are bound to a and b.
When-clauses allow a predicate to be associated with a rule.
Abstract value constructors [AR92]
Tagtype constructors
Negative pattens allow the programmer to specify the values that are not matched by a pattern. For example, assuming the color type has constructors Red, Blue, Green, the pattern
(x isnot Red)
has the same effect as
(x is (Green|Blue))
The subpattern of a negative pattern cannot have free variables.

8.2 Pettersson's algorithm

In this section, we describe our version of Pettersson's algorithm [Pet92].

8.2.1 Step 1 --- pattern canonicalization

We are given as input a list of rules, where each rule consists of a tuple of patterns, an optional when clause, and an action. Typechecking ensures that each rule in the match has the same arity. Our representation for this is as follows:

datatype rule = RULE of (pat list * exp option * exp) datatype match = M of rule list

The first step of the algorithm is to canonicalize the patterns in the match.

8.2.2 Step 2 --- DFA construction

æ
ç
ç
ç
ç
ç
ç
è

path₁	···	path_n
¯		¯
p_1,1	···	p_1,n	Þ	act₁
· · ·	· · ·	· · ·		· · ·
p_m,1	···	p_m,n	Þ	act_m

ö
÷
÷
÷
÷
÷
÷
ø

8.2.3 Step 3 --- DFA optimization

8.3 Extensions to the basic algorithm

8.3.1 Or-patterns

8.3.2 When clauses

8.3.3 Abstract value constructors

8.3.4 Tagtype constructors

8.3.5 Negative pattens

Simple implementation is to translate to when clause, but we can do better in some situations.

8.4 Choosing the column

8.5 Related work

There have been a number of algorithms published for pattern matching in lazy languages ([]), but we are only aware of a couple of descriptions of compiling pattern matching in strict languages.

The core of our approach is based on Pettersson's algorithm, but we have extended his approach to handle a much richer pattern language. Leroy [Ler90] describes an approach that is similar to Pettersson's, although without the DFA analogy.