SOFTWARE−PRACTICE AND EXPERIENCE
Softw. Pract. Exper., 29(9), 793-813 (1999)

Efficient Automata Driven Pattern Matching for
Equational Programs
NADIA NEDJAH*¶, COLIN D. WALTER AND STEPHEN E. ELDRIDGE
Computation Department, UMIST, PO Box 88, Manchester M60 1QD, UK(email: {nn, cd , see}@sna.co.umist.ac.uk)

SUMMARY
We propose a practical technique to compile left-to-right pattern-matching of prioritised overlapping
function definitions in equational languages to a matching automaton from which efficient code can bederived. First, a matching table is constructed using a compilation method similar to the technique that
YACC employs to generate parsing tables. The matching table obtained allows for the pattern-matchingprocess to be performed without any backtracking. Then, the known information about right sides ofthe equations is inserted in the matching table in order to speed-up the pattern-matching process. Mostof the discussion assumes that the processed pattern set is left-linear, the non-linear case being handled
by an additional pass following the matching stage. Copyright  1999 John Wiley & Sons, Ltd.
KEY WORDS: compilation; equational programming; pattern-matching; rewriting; reduction strategy

1. INTRODUCTION
As research has proved so far, the pattern-matching feature of equational and functional
languages is very expressive, fully compensating for the lack of side effects in such languages.
The operational semantics behind the rewriting-based programming paradigm is now wellknown [1−3]. It consists of using a set of equations considered as left-to-right rewrite rules tosimplify a given term, called the subject term. Starting from this term, the evaluation process
produces a sequence of expressions by repeatedly replacing instances of left sides of rules with
their corresponding right sides until no further replacements are possible. An instance of a left
side in the subject expression is called a redex, and an expression with no redex is said to be innormal form.
The pattern-matching process provides a rule whose left side matches the expression
considered. As patterns can overlap, several rules can be matched at the same time. In thiscase, a meta-rule allowing for the selection of a single matched rule is used. Examples of sucha meta-rule are the first matched rule (textual order) and the most specific matched rule [4].
The textual order meta-rule will be used here in the case of overlapping patterns. However,*Correspondence to: N. Nedjah, Computation Department, UMIST, PO Box 88, Manchester M60 lQD, UK.

¶

The author was initially sponsored by the British Council and the Algerian High Education Ministry, and is presently
sponsored by the Fundação de Amparo à Pesquisa no Estado do Rio de Janeiro (FAPERJ). On leave of absence from
Institut d'Informatique, Université de Annaba, B.P. 12, Annaba 23000, AIgerie.
CCC 0038−0644/99/090793−21$17.50
Copyright  1999 John Wiley & Sons, Ltd.

Received 1 September 1996
Revised 23 December 1998
Accepted 17 February 1999

794

N. NEDJAH, C. D. WALTER AND S. E. ELDRIDGE

the method presented through this paper is easily adapted to any meta-rule which can beestablished at compile-time.
Usually, the pattern set is pre-processed producing an intermediate representation allowing
for the matching process to be performed efficiently. Different kinds of such representations
have been studied: conditional constructs, like those in procedural languages, have been
exploited for this purpose. Examples include the if-then-else construct [5] and the caseexpression [6,7]. Another kind of representation consists of a matching tree (also called theindex tree) [3,8]. Similarly, pattern-matching definitions have been compiled into a finite
matching automaton in References [1,9,10,11,12].
Pattern-matching automata have been studied for over a decade. Gräf [9], Maranget [13]and Christian [14] describe matching automata for unambiguous patterns based on left-toright traversal. Gräf [9] adds instances of patterns using a closure operation, so symbol reexamination could be avoided. Maranget [13] describes two techniques to compile lazy
pattern-matching. The first technique generates a deterministic matching automaton that isequivalent to that obtained by Gräf [9]. The second technique, however, generates automata
with failures that allow non-deterministic pattern-matching (i.e. with symbol re-examination).
These automata possess a static exception construct that enables some code sharing. In
functional programming, Augustsson [6] and Wadler [7] describe pattern-matching techniquesthat are also based on left-to-right traversal, but allow prioritised overlapping patterns. They
compile patterns into CASE constructs using four compilation rules: the empty rule, theconstructor rule, the variable rule and the mixture rule. Although the latter methods arepractical and economical in terms of space usage, they may re-examine symbols in the input
term. In the worst case, these methods can degenerate to the naive method of checking the
input term against each pattern individually. In contrast, Christian’s [14] and Gräf’s [9]methods, together with Maranget’s [13] first technique, avoid symbol re-examination at thecost of increasing the space requirements, while Maranget’s [13] second technique guaranteethat the size the resulting automaton is linear in the size of the patterns. However, one has tobear in mind that the functional approach followed by Wadler [7] and Maranget [13] combines
the operations of forcing weak normalisation of the subterm whose the head symbol
mismatches the symbol in the pattern and examining the resulting head symbol while in theterm rewriting approach followed by Christian [14] and Gräf [9], symbols are examined
without forcing any evaluation.
The practical method we shall describe in this paper is similar to a method of automatic
generation of parsers [15,16], which has been used for many years to compile imperative
languages. Backtracking in the pattern-matching process can consume considerable time aswell as space. So, through the matching table generation process, we convert the original
pattern set to an equivalent closed pattern set which avoids the need for backtracking. We use
a different approach from that described by Gräf [9] to compute the closure of pattern sets. In
contrast with his method, we also deal with prioritised overlapping patterns. Furthermore,
Gräf [9] does not show how to use the constructed matching automaton in the context of agiven rewriting strategy. After the method of generating the matching table is described, we
describe how to interpret such a matching table through an abstract rewriting machine. We
show that the rewriting machine is simple yet expressive, and any rewriting strategy can beused after minor changes to it. We illustrate this machine using the three most popular
strategies namely, leftmost-innermost [17,18], leftmost-outermost [12] and the adaptive
strategy [19] used in most lazy functional languages such as Miranda [19], LML [20] andHaskell [21]. The adaptive strategy implements the functional approach described in
Reference [7]. Our method, like most others, is restricted to the subclass of left-linear
programs for which a variable can occur only once in the left side of an equation.
Copyright  1999 John Wiley & Sons, Ltd.

Softw. Pract. Exper., 29(9), 793-813 (1999)

EFFICIENT AUTOMATA-DRIVEN PATTERN-MATCHING

795

Using the technique of partial evaluation [22], Strandh [3] transforms the code generated
for equational programs so that the code obtained allows for some matching and rewriting
steps to be avoided. Similar work can be found in References [23-25]. Instead, we customise
the idea of partial evaluation so it can be used directly on the equational program itself, not on
the code generated for it. For the adaptive strategy, it is possible to avoid some matching andrewriting steps if the equation’s right sides are analysed at compile-time. The rewritingmachine permits this analysis to be done easily, and it generates a new equivalent set of
equations which is more efficient. Finally, an evaluation of an implementation of the proposed
ideas is provided.
2. NOTATION AND DEFINITIONSDefinition 2.1. An equational program can be defined as a 4-tuple EP = 〈F, V, R, T〉 whereF = {f, g, h, ...} is a set of function symbols, V = {x, y, z, ...} is a set of variable symbols and R ^ 1 → 1,
2 → 2, ...} is a set of rewrite rules called the term rewriting system, ZKHUH i
DQG i are terms, called the pattern and template, respectively. T is the subject term, which isthe expression to evaluate.
For convenience, in most of the paper, we will consider the patterns to be written from thesymbols in F ∪ ^ ` ZKHUH is a meta-symbol used whenever the symbol representing a
YDULDEOHGRHVQRWPDWWHU)RUDSDWWHUQVHW ZHGHQRWHE\ F the subset of F containing only
WKHIXQFWLRQV\PEROVLQWKHSDWWHUQVRI $ term is either a variable, a constant symbol or has
the form f 1, 2,  n) ZKHUH HDFK i (1  i  n) is itself a term and n is the arity of thefunction symbol f denoted by #f. The subject term is supposed to be a ground term, i.e. a term
containing no variable occurrences. Terms are interpreted syntactically as trees labelled withsymbols from F ∪ V. An instance of a term t can be obtained by replacing leaves labelled withvariable symbols by other terms. In practice, however, both the subject term and templates areturned into Directed Acyclic Graphs (DAGs) so that common subterms may be shared(represented physically once). This allows for the evaluation of such subterms to be
performed at most once during the whole rewriting process.
Definition 2.2. A position in a term is a path specification which identifies a node in the graphof that term, and therefore both the subterm rooted at that point and the symbol which labels
WKDW QRGH  $ SRVLWLRQ LV VSHFLILHG KHUH XVLQJ D OLVW RI SRVLWLYH LQWHJHUV  7KH HPSW\ OLVWdenotes the graph root, the position k denotes the kth child of the root, and the position p.kdenotes the kth (k  FKLOGIURPWKHSRVLWLRQJLYHQE\ p. The symbol, respectively subterm,rooted at position p in a term t is denoted by t[p] , respectively t / p. A position in a term isvalid LIDQGRQO\LIWKHWHUPKDVDV\PERODWWKDWSRVLWLRQ 6R  LV YDOLG IRU DQ\ WHUP DQG D
position p = q.k is valid if, and only if, the position q is valid, the symbol f at q is a function
symbol and k f.
For instance, in the term t = f(g(a, h(a, a), b(a, x), c), t> @ denotes the single occurrenceof f, t[2.2] denotes the variable symbol x, whereas t[2] denotes the symbol b while t/2 indicatesthe subterm b(a,x) and the positions 2.2.1 and 1.3 are not valid. In the following, we will
abbreviate terms by removing parentheses and commas. For instance, t abbreviates tofgahaabaac. This will be unambiguous, since the given function arities (i.e. #f = 3, #g = #h =#b = 2, #a = #c = 0) will be kept unchanged throughout all examples. In particular, the arities#f = 3, #g = 2 and #a = 0 will be used in the running example.
Definition 2.3. $SDWWHUQVHW LVRYHUODSSLQJLIWKHUHLVDJURXQGWHUPWKDWLVDQLQVWDQFHRIDW
OHDVWWZRGLVWLQFWSDWWHUQVLQ 

Copyright  1999 John Wiley & Sons, Ltd.

Softw. Pract. Exper., 29(9), 793-813 (1999)

796

N. NEDJAH, C. D. WALTER AND S. E. ELDRIDGE} is an overlapping pattern set because the term faac  ^ID, IF } is a non-overlapping
LV DQ LQVWDQFH RI ERWK SDWWHUQV ZKHUHDV WKH VHWpattern set. A similar notion is that of pattern prefix-overlapping:)RULQVWDQFHWKHVHW 

,I

^ID

D

Definition 2.4. $ SDWWHUQ VHW  LV prefix-overlapping if there is a ground term with a nonHPSW\SUHIL[WKDWLVDQLQVWDQFHRISUHIL[HVRIDWOHDVWWZRGLVWLQFWSDWWHUQVLQ ,F} is a non-overlapping pattern set, but it is a prefixoverlapping because the prefix faa of the term faaa is an instance of both prefixes I D and.
I)RULQVWDQFHWKHVHW



^I

DD I

When overlapping patterns are allowed in equational programming, a meta-rule is needed
to decide which rule should be matched when a conflict due to overlapping patterns arises.
The meta-rule defines a priority relationship among overlapping patterns. Thus, given a
SDWWHUQVHW DQGDPHWDUXOHZHFDQIRUPDOLVHWKHQRWLRQRISDWWHUQPDWFKLQJDVIROORZVDefinition 2.5. A term t matches DSDWWHUQ i ∈ LIDQGRQO\LIt LVDQLQVWDQFHRI i and t is not
DQLQVWDQFHRIDQ\SDWWHUQ j ∈ VXFKWKDWWKHSULRULW\RI j LVKLJKHUWKDQWKDWRI i .
Definition 2.6. A term t1 is more general than a term t2 at a given common valid position p if
and only if t1[p] ∈ V, t2[p] ∈ F and the prefixes of t1 and t2 ending immediately before P are
the same.
Definition 2.7. The closed pattern set π  FRUUHVSRQGLQJ WR D JLYHQ SDWWHUQ VHW  LV WKH VHW
REWDLQHGE\DSSO\LQJWR WKHFORVXUHRSHUDWLRQGHILQHGE\*Uäf [9] as follows:
For any s ∈ F ∪ { `OHW  s EHWKHVHWRIHOHPHQWVRI VWDUWLQJZLWKs but with the firstsymbol s UHPRYHG'HILQH DQG f, f ∈ F by= #f f ∪ LI  f 
 f =
otherwise.

®

{®

The closure operation is then defined recursively by: 

π =

{ U

sπ s

if = { } orotherwise.

®

s∈F ∪{ω }is the empty string and #f is a repetition of #f symbols . 7KH VHW f includes all theSDWWHUQV LQ  VWDUWLQJ ZLWK f, but with f removed. In addition, while factorising a pattern set
according to a function symbol f LHFRPSXWLQJ f ), the operation above takes account of thecomponents starting with a variable symbol as well; the symbol  is considered as possibly
representing a subterm whose root symbol is f. Therefore, a new component is added to the
VHW f. This component is obtained by replacing
 by a sequence ofs whose length is #f.
This sequence stands for the arguments of f.
The closure operation supplies the pattern set with some instances of the original patterns.
In effect, if one pattern is more general than another at some position p then the pattern with#f
LV DGGHG  )RU LQVWDQFH WKH SUHIL[RYHUODSSLQJ SDWWHUQ VHW   ^I D , replaced by I
I
D, I JJ
} FDQ EH FRQYHUWHG WR DQ HTXLYDOHQW FORVHG SDWWHUQ VHW  XVLQJ WKH FORVXUH
operation computed as follows:Here

π = f π f = f {ωaω , ωωa, ωgωωgωω }= fω{aω , ωa, gωωgωω } = fω P ,Copyright  1999 John Wiley & Sons, Ltd.

Softw. Pract. Exper., 29(9), 793-813 (1999)

EFFICIENT AUTOMATA-DRIVEN PATTERN-MATCHING

797

where

P = a Pa ∪ ω Pω ∪ g Pg
= a{ω , a} ∪ ω{a} ∪ g{ωωgωω , ωωa}= {D , aa,

,

D J

7KHQWKHFORVHGSDWWHUQVHWFRUUHVSRQGLQJWR

π = {I DD,I D ,I J

,J

J

}.

D

is:
,

D I

J

J

,I

}.

D

does, since the added
patterns are all instances of the original ones. The closure operation terminates and can becomputed incrementally (for full detailed description and formal proofs see Reference [9]).
:LWKFORVHGSDWWHUQVHWVLIDSDWWHUQ 1 LVPRUHJHQHUDOWKDQDSDWWHUQ 2 at position p, then[p
2 @ LV FKHFNHG ILUVW  7KLV GRHV QRW H[FOXGH D PDWFK IRU 1 because the closed pattern set# 2[p]
GRHVFRQWDLQDSDWWHUQWKDWLV 1 ZLWK 1[p] UHSODFHGE\ 2[p]. Under this assumption, an
important property of such closed pattern sets is that they make it possible to determine
whether a target term is a redex merely by scanning that term from left-to-right without
backtracking over its symbols [9].
Symbol re-examination cannot be avoided in the case of non-closed prefix-overlapping
be theSDWWHUQVHWVZKDWHYHUWKHRUGHULQ ZKLFK WKH SDWWHUQV DUH SURYLGHG  )RU LQVWDQFH OHW
prefix-overlapping set {IF F, I JD D}. Using the textual order meta-rule, the first patternmust be matched first, if possible. Then the term fcgaaa cannot be identified as an instance ofthe second pattern without backtracking to the first occurrence of c when the last symbol a isencountered. However, the closure π = {IFJD F, IFJD D, IFJ F, IF F, I JD D} allows
matching without backtracking. Then the term will match the second pattern.
,W LV FOHDU WKDW WKH QHZ SDWWHUQ VHW DFFHSWV WKH VDPH ODQJXDJH DV

3. MATCHING TABLE GENERATIONIn this section, we describe a different approach to compute the closure of a pattern set  via
We
GLUHFW FRPSLODWLRQ UDWKHU WKDQ YLD WKH VHWV f, as in Reference [9] (see Definition 2.7).
compile pattern sets into matching tables. In general, the pattern-matching compilation
technique at the heart of this paper can be thought of as a table-driven method inspired by the
LALR method used in YACC [15,16] to generate parsers for LR-languages. In that context,
the pattern set to be compiled is considered as the set of right sides of syntactic productions.
The left sides of these productions are non-terminals representing the types of the patterns,
and each variable symbol is a non-terminal for its type. Since we are dealing only with
untyped systems, there is only one non-terminal. As with YACC [15,16] the compilation
process creates a finite automaton, for which we must define the states and the state transition
function.
Definition 3.1. A matching item is a pattern which is split into a prefix and suffix by inserting
the matching dot ( · ) at some point.
In general, for the pattern  the matching item  · means that the symbols in the prefix
have been matched and those in have not been checked yet. Thus, the matching item ·represents the initial state prior to matching the pattern , whilst the matching item ·represents the final state after matching the whole pattern .
Definition 3.2. A set of matching items in which every item has the same prefix before thematching dot is called a matching set. The initial matching set contains all the matching items

Copyright  1999 John Wiley & Sons, Ltd.

Softw. Pract. Exper., 29(9), 793-813 (1999)

798

N. NEDJAH, C. D. WALTER AND S. E. ELDRIDGEi ∈ ZKHUHDVPDWFKLQJ VHWV FRQWDLQLQJ LWHPV RI WKH IRUP i· are final matching sets.
Note that final matching sets can contain only one matching item.

Â iVW$ SDWWHUQ VHW

 LV FRPSLOHG LQWR D GHWHUPLQLVWLF ILQLWH PDWFKLQJ DXWRPDWRQ  7KH VWDWHV RI

this matching automaton are computed using the following transition operation . For eachsymbol s ∈ F ∪ { } and matching set I, a new matching set (I, s) is defined by(I,s) = { V· | ·V ∈ I} ∪ { V·I #f | ·V ∈ I andfor some f ∈ F and term , ·VI ∈ I}
Notice that the presence of the items V·  together with the items V·I  in the same
matching set creates a non-deterministic situation for a pattern-matcher, since  can besubstituted with a term having f as head symbol. The items V·I #f are added to remove such
QRQGHWHUPLQLVP DQG DYRLG EDFNWUDFNLQJ  )RU LQVWDQFH OHW   ^I
D, IF F}, and let M be
the matching set obtained after accepting the root symbol f so M = {f· D, f·F F} ∪ {f·F D}.
The item f·F Dis added because a target term with the prefix fc could match the pattern I D
too if the last argument of f were a rather than c. So supplying the instance IF Dwould allow
the pattern-matcher to decide deterministically which option to take. Without this new item,the pattern-matcher would need to backtrack to the first argument of f if the option offered byD were taken, and a symbol c encountered as the last argument of f in the target term.
I
Notice that the transition operation thus described implements exactly the main step in theclosure operation due to Gräf [9], but replaces his recursive description with a straightforward
iterative construction. Therefore, the union of the final pattern sets resulting from theautomaton construction procedure coincides with the closure of the initial pattern set.
Each matching set is associated with a state in the matching automaton, namely that
accepting the common prefix (before the matching dot) in the given pattern set. The initialstate and final states correspond to the initial matching set and final matching sets,
respectively. The edges of the finite automaton are traversed according to the current input
symbol, namely s causes the transition from I to (I, s). The matching automaton ^I D , I
D, I JJ
} is given in Figure 1. Transitions
FRUUHVSRQGLQJ WR
corresponding to failure are omitted.
The finite matching automaton corresponding to a given pattern set is represented using amatching table. Matching tables are simple, compact and expressive. Also, they allow a directaccess to a given matching state (see Section 5). A matching table is an N × (L + 1) matrix oftransitions, where N is the number of non-final states in the automaton (10 in the example of
Figure 1) and L is the number of function symbols in F . The extra column of N entries is usedfor variable occurrences in the patterns, all of which are denoted by . The distinction
between and the other symbols permits a concise representation of the matching table. This
enables the use of matching tables for equational programs with an infinite alphabet.
For a matching state I and a symbol s ∈ F ∪ { } , let (I, s) = J. Then the matchingtable entry MT[I, s] is
accept-symbolJ if J is not a final state and s ∈ F .
accept-termJ
if J is not a final state and s = .
reducer
if J is a final state and r is the matched rule (see the next section).
fail
Otherwise, i.e. J is empty.

Copyright  1999 John Wiley & Sons, Ltd.

Softw. Pract. Exper., 29(9), 793-813 (1999)

EFFICIENT AUTOMATA-DRIVEN PATTERN-MATCHING

799

·f D
·f
D
·f J
J

s0

f
f· D
f·
D
f· J
J

s1

f
f
f
f
f

s2
a

s3

f DÂ
f DÂD

s4

ÂD
Â D
ÂJ
J
ÂDD
ÂJ
D

f

a
f DDÂ

g

ÂD

s5

f JÂ
f JÂ

J
D

s6

f J Â Jf J Â D

s7

f J
f J

a
f D Â

f

DÂ

ÂJ
ÂD

g

Figure 1. Pattern-matching automaton for

s8

f J

JÂ

s9

f J

J Â

f J

J

= {I

D

,I

a
f J

DÂ

Â

,

D I

J

J

}

Here the subscript J indicates the next state to enter. Accept-symbol and accept-term meanthat the current input symbol (respectively the current input term) is matched, and the state(I, s) is entered. Reducer means that the rule number r has been matched and should beapplied, whereas fail means matching has failed at the given symbol s.
The rules given are used straightforwardly. In all cases, an -transition is chosen only
when the matching table entry for the specific current input symbol is fail. So if s ∈ F is thecurrent input symbol and I the current state, then action MT[I, f] is performed if it is not a fail,and otherwise MT[I, ] is performed. Setting an entry to reducer requires solving an
additional problem if the matched pattern has been added by the construction process. For
original patterns the rule number to use is uniquely defined. However, two or more original
patterns could match any added patterns. The selection is made by applying the rule priorities
provided to associate a unique rule with each added pattern.
For instance, for the pattern set = {1: I D , 2: I D, 3: I J J } of Figure 1, theadded patterns I DD and I J D would be associated respectively with the rule numbers 1
and 2 if the textual order rule were used.

Copyright  1999 John Wiley & Sons, Ltd.

Softw. Pract. Exper., 29(9), 793-813 (1999)

800

N. NEDJAH, C. D. WALTER AND S. E. ELDRIDGE

7DEOH,0DWFKLQJWDEOHIRU 

0
1
2
3
4
5
6
7
8
9

^I

D

,I

,

D I

f
a
g
accept-symbol1
fail
fail
fail
"
"
"
accept-symbol3 accept-symbol5"
reduce1
fail"
reduce2
"
"
fail
"
"
"
"
"
reduce2
accept-symbol8
"
fail
fail
"
"
"

J

J

}

fail
accept-term2
accept-term4
reduce1
fail
accept-term6
accept-term7
failaccept-term9
reduce3

Ambiguity arises for patterns introduced that belong to the overlap of any original
3 EH WKH SDWWHUQ DGGHG EHFDXVH SDWWHUQ 1 is more general than
SDWWHUQ 2 at a given position p. 5HFDOO WKDW 3 LV REWDLQHG IURP 1 by replacing the subterm
 E\ D WHUP RI ZKLFK WKH VXEWHUP 2[p] LV DQ LQVWDQFH 7KXV 3 LV DQ LQVWDQFH RI 1.
1[p] =
1RUPDOO\ 3ZLOOIDLOWRRYHUODSZLWK 2, DQGVRWKHUXOHIRU 1ZLOODOVREHDVVRFLDWHGZLWK 3.
+RZHYHU LI 1 DQG 2 RYHUODS 3 PD\ DOVR EH DQ LQVWDQFH RI 2. Therefore, the template
DVVRFLDWHGZLWKHLWKHU 1RU 2 could be selected to rewrite the subexpression being evaluated.
The use of the given meta-rule allows for the selection of such a template. This is performed at
FRPSLOHWLPHE\DVVRFLDWLQJWKHSUHVFULEHG UXOH QXPEHU DPRQJ WKRVH FRUUHVSRQGLQJ WR 1 and
2, WRWKHDGGHGSDWWHUQ 3.
SDWWHUQV )RU H[DPSOH OHW

7KH PDWFKLQJ WDEOH FRUUHVSRQGLQJ WR WKH SDWWHUQ VHW

 RI )LJXUH  LV VKRZQ LQ 7DEOH , ,Wcorresponds to the finite automaton of that figure. For convenience, the states/matching sets
have been numbered as before. Notice that rows representing final states do not exist in thematching table. The decision to reduce the target expression using the matched rewriting rule
is anticipated in the state leading to the corresponding final state. This allows for the reductionof the matching table by r rows, where the number r of final states is also the number ofpatterns in the closure of the original pattern set.

4. REWRITING MACHINE APPLICATIONIn this section, we show how the matching table constructed so far can be used in rewriting.
This detail was not covered by Gräf [9] for his associated finite automaton. We illustrate therewriting process using the three most popular reduction strategies, namely leftmostinnermost,which is used for strict functional languages such as HOPE [17], and ML [18] leftmostoutermost [12], and the adaptive strategy which is used in most lazy functional languages such
as LML [20], Haskell [21] and Miranda [19]. The last strategy is sometimes called ‘top-tobottom left-to-right lazy strategy’ [4], and is defined after the next example.
Consider the prioritised equational program, which has the following set of rewrite ruleswith the subject term t = f(c, f(a, a, a), a):f(x, a, y)f(x, y, a)c→ y (r1)→ a (r2)→ c (r3)

Closure would add the pattern f(x, a, a) which overlaps both left sides. Then assuming a
textual order meta-rule, f(x, a, a) would be associated with r1. The leftmost-outermost
Copyright  1999 John Wiley & Sons, Ltd.

Softw. Pract. Exper., 29(9), 793-813 (1999)

EFFICIENT AUTOMATA-DRIVEN PATTERN-MATCHING

801

strategy would reduce t using r2, and a would be the normal form obtained whilst the leftmostinnermost (or applicative) strategy would result in an infinite computation, since it would
cause the repeated reduction of c. Arguably, the reduction sequence that best captures thesemantics [19] of the prioritised system above is as follows. Contracted redexes areunderlined:r2

f(c, f(a, a, a), a) →r1

f(c, a, a) → aThis strategy, which we will call the adaptive strategy, selects the leftmost-outermost redex
after reducing the arguments needed to normal form. That is, if during pattern-matching theroot symbol of a subterm fails to match a function symbol f in the pattern, then the subterm isevaluated before re-attempting the match. If the root symbol of the normal form of thesubterm is different from f, the matching of that pattern fails and the next pattern is tried.
In some cases, the adaptive strategy terminates when the leftmost-outermost strategy doesnot. For instance, consider the rewriting system {f(x, a, y) → a, g(x, y) → a, c → c}. The
evaluation of the term f(c, g(a, a), c) using the leftmost-outermost strategy fails to terminate,since it would try to rewrite the subterm c that represents the outermost-leftmost redex.
However, the adaptive strategy would try to match the pattern of the first rule by rewriting thesecond argument of f to a. It does this, and hence succeeds in rewriting f(c, g(a, a), c) to a.
The adaptive strategy requires equational programs to follow the constructor discipline [26].
This can be formalised as follows:
Definition 4.1. A function symbol is a constructor for the pattern set
the root of any pattern in .



if it does not appear atDefinition 4.2. Let R be a term rewriting system, and suppose every symbol position in apattern of R, other than the first, is a constructor symbol for the set of patterns of R. Then R
is called a constructor system.
For instance, consider the term rewriting system (E) that follows. The initial symbols f, g
and h are not constructors, whereas the symbols a and b are. Therefore, (E) is a constructor
system.
1. f(x, a, y)=a
2. f(x, y, a)=a
3. f(x, b(s, y), b(t, z)) = h(b(y, a), g(x, a))

4. g(x, a)=x
5. h(b(x, a), a) = a
6. h(x, a)= g(a, x)

The constructor discipline entails almost no loss of generality, since the majority ofequational programs observes this discipline [12] and the majority of those that do not, can be
syntactically transformed so as to follow it [26,27]. For the remainder of this paper, we
assume, in common with most researchers in the area, that the term rewriting system is aconstructor system.
The pattern-matching process is incorporated into a simple abstract rewriting machine
represented by the 5-tuple RM = 〈I, P, MT, R, T〉, which will be used to rewrite the term T to
its normal form. I is the current matching state which corresponds to a row index in thematching table MT. R represents the root position of the subterm in T currently being
matched. P is the current position the matching process has reached in the subterm T[R].
Now, let 〈I, P, MT, R, T〉 be the current state of RM. Then its next state is determinedaccording to the reduction strategy used, MT[I, T[R.P]] and MT[I, ]. Possible statetransition rules for the abstract machine using the leftmost-innermost and leftmost-outermost
strategies are described in Figures 2 and 3 respectively. The transition rule of Figure 2 uses
the adaptive strategy. In each of these three figures, MatchingAction represents the matching

Copyright  1999 John Wiley & Sons, Ltd.

Softw. Pract. Exper., 29(9), 793-813 (1999)

802

N. NEDJAH, C. D. WALTER AND S. E. ELDRIDGE

action to be performed. This is either MT[I, T[R.P]] or fail, depending on whether or not thesymbol T[R.P] is a function symbol that actually appears in a pattern.
〈I, P, MT, R, T〉 →Case MatchingAction of
accept-symbolJ: If U = {i | 1 i  #T[R.P], ¬IsNormal(P.i) } 
For i ∈ U do Normalise(T/R.P.i)® thenelse 〈J, Next(P), MT, R, t〉;
reducer :
fail:

〈

07



ApplyRuler(T, R)〉;

Case MT[I, ] ofaccept-termJ:〈J, NextArg(P), MT, R, T〉;

reducer:

〈

fail:

If Next(R) Defined then 〈else MarkAsNormal(T);07



ApplyRuler(T, R)〉;
07

Next(R), T〉

End
End
Where MatchingAction = If T[R.P] ∈ F then MT[I, T[R.P]] else failFigure 2. State transition rule for innermost-leftmost strategy

All of these strategies require each subterm of T to be marked initially as not normal (i.e.
not known to be in normal form). The normal form of a given term T is obtained by applying
the appropriate state transition rule repeatedly until the root of T is marked as normal. Suchan iteration sequence will be called Normalise(T). It starts in the initial state 〈  MT, T〉,
with all the nodes in the graph of T marked as not normal.
〈I, P, MT, R, T〉 →Case MatchingAction of
accept-symbolJ: 〈J, Next(P), MT, R, T〉;
reducer:

〈

fail:

Case MT[I, ] of

07



ApplyRuler(T, R)〉;

accept-termJ:〈J, NextArg(P), MT, R, T〉;

reducer:

〈

fail:

If Next(R) Defined then 〈07



ApplyRuler(T, R)〉;
07

Next(R), T〉

else MarkAsNormal(T);End
End
Where MatchingAction = If T[R.P] ∈ F then MT[I, T[R.P]] else failFigure 3. State transition rule for leftmost-outermost strategy

The function Next(P) returns the position of the symbol after that at position P in the term
T whereas NextArg(P) returns the position of the next argument (i.e. the next sibling in that

Copyright  1999 John Wiley & Sons, Ltd.

Softw. Pract. Exper., 29(9), 793-813 (1999)

EFFICIENT AUTOMATA-DRIVEN PATTERN-MATCHING

803

graph). Here NextArg will travel back up towards the root of T to find the lowest ancestor of
P which has a branch to the right of P .
For instance, let T = fagaahaa. Then applying the functions Next WR SRVLWLRQV   
and 2.2 returns the positions 1, 2.1, 2.2 and 3, respectively. For both of positions 2 and 2.2,function NextArg returns position 3. The function Next is undefined for the position of the last
symbol in the term, whilst NextArg is undefined for all positions between the root and theright-most leaf of the parse tree of T. Regarding the example term T above, Next is undefinedfor position 3.2 while NextArg is undefined for positions 3.2 and 3. Where NextArg is used in
the transition rules, it is always defined, but when Next(R) becomes undefined the machine
halts.
In the transition rule for the adaptive strategy, when a rule is applied, R remains the root of
the subterm in which the next redex is searched for, whereas for the other two strategies, the
new root R EHFRPHV   Apply-ruler(T, R) instantiates the template of the matched rule r,
replaces the variable nodes by their actual graph-values, and finally, rewrites the subterm
T / R using the newly constructed template instance. Given a position P, the Boolean function
IsNormal checks whether the graph rooted at position P is known to be in normal form,
whereas the function MarkAsNormal(T) marks the root of the term T when this term is known
WREHLQQRUPDOIRUP(YHQWXDOO\WKHPDFKLQHKDOWVDW   MT, L, T), where T is marked as
normal and L is the position of the last symbol in the term T.
The machine state transition rules of Figures 2 and 3 are used in the obvious way. For theadaptive strategy, whenever a function symbol f labels the current matching position P and theentry MT[I, f] is fail, two alternatives are possible according to whether there is anotherfunction symbol g for which MT[I, g] is not fail. When such a symbol exists, the subterm
rooted at position P is normalised then, the transition rule tried again (in the hope that g might
be matched). Otherwise, the entry MT [I, ] is tried.
For instance, consider a rewriting system for which the matching table is that of Table I.
Suppose rule 1 is fxay → a and the subject term is T = fcfcaac. Using the transition rule of
Figure 2 first causes the normalisation of argument fcaa of the root symbol f, since the entry
MT[0, f] is accept-symbol1 and not all of the arguments of the first f in T are in normal form.
The subterm fcaa readily matches the pattern of rule 1 so T reduces to fcac. Then state 1 isentered. Once the prefix fca is accepted, I and P become 3 and 3, respectively. Subsequently,
with c at T[3], MT[3, ] indicates that the pattern of rule 1 is matched, so T reduces to a. The
same outcome arises from the use of the transition rule of Figure 3. There the prefix fc isaccepted and state 2 entered; then the subterm fcaa is skipped because MT[2, f] is fail and so
MT[2, ] is performed. Thus state 4 is entered, and so matching at the root fails.
Subsequently, the strategy fails to find a redex at position 1, but succeeds in identifying theredex fcaa at position 2. This readily matches the pattern of rule 1, and is rewritten to a, so T
reduces to fcac. Once again, the strategy succeeds in matching the pattern of rule 1 at
SRVLWLRQ VR WKDW T reduces to a. A similar result obtains from using the transition rule of
Figure 4. This accepts the prefix fc; enters state 2 with P = 2; since MT[2, f] is fail and T[P] is
not in normal form, the normalisation of subterm fcaa takes place so that T reduces to fcac;
the match of the symbol at position 2 is re-attempted; the symbol T[2] = a is accepted andstate 3 entered; with the normal form c at position 3, MT[3, ] indicates that the pattern ofrule 1 is matched. The adaptive strategy then applies that rule, and so T reduces to a.
When a pattern is matched the pattern-matching process needs to provide the actual
substitutions for s in that pattern. This is to enable template instantiation so that redexes canbe reduced. Gräf’s technique [9] does not mention such a detail. Since variable occurrencesin patterns are known, their positions can be pre-computed and stored at compile-time. Once arule has been matched and the value of a variable is needed, the subterm corresponding to the
Copyright  1999 John Wiley & Sons, Ltd.

Softw. Pract. Exper., 29(9), 793-813 (1999)

804

N. NEDJAH, C. D. WALTER AND S. E. ELDRIDGE

position of that variable can be retrieved from the target expression. This is then provided tothe template instantiating process which uses it to replace occurrences of the variable.
〈I, P, MT, R, T〉 →Case MatchingAction of
accept-symbolJ: 〈J, Next(P), MT, R, T〉 ;reducer :fail:〈 075ApplyRuler(T, R)〉;
If T[R.P]∈ F and ∃f∈F (MT[I,f]IDLO and ¬IsNormal(P) thenNormalise(T/R.P)
else Case MT[I, ] ofaccept-termJ:〈J, NextArg(P), MT, R, T〉;

reducer:

〈

fail:

If Next(R) Defined then 〈else MarkAsNormal(T);075

ApplyRuler(T, R)〉;
07

Next(R), T〉

End
End
Where MatchingAction = If T[R.P] ∈ F then MT[I, T[R.P]] else failFigure 4. Machine state transition rule for the adaptive strategy

However, as backtracking has been eliminated, the cost of dynamically collecting pointers
to variable instances during pattern-matching may be cheaper. Let 〈I, P,MT, R, T〉 be thecurrent state of RM. It is clear that when the matching action to perform is MT[I, ] (i.e.
either accept-term or reduce), the subterm T / R.P is the actual value of the variable [P] if
matching of pattern succeeds. This collects substitutions for the matched pattern, not for theoriginal pattern in the rule which is to be applied. For instance, consider the pattern set of
Figure 1 and let faaa be the subject term. Because faaa would match the non-original pattern
I DD, only one variable substitution would be available when matching concludes. However,faaa has to be rewritten using rule 1 whose pattern I D  requires two substitutions, not one.
In this case, the missing substitution is always the instance a at position 3 in the matchedpattern.
To be able to collect the missing substitutions when non-original patterns are matched, weneed to consider some cases for which the matching action to perform is MT[I, f] for f ∈ F .
When the matching action to perform is MT[I, f], a substitution needs to be collected only if
MT[I, ] is distinct from fail. Then in the example above, two additional variable instances
would be collected when the second and last symbols a in faaa are accepted in states 2 and 3,
respectively. This is because the actions to be performed are MT[2, a] = accept-symbol3 andMT[3, a] = reduce1 with MT[2, ] = accept-term4 and MT[3, ] = reduce1, respectively, but
not fail. No substitution would be collected when the symbol f is accepted in state 0, because
MT[0, ] = fail. The substitution for the second occurrence of a is collected because faaa is
an instance of the pattern I D (rule 2) too. Then the required substitutions would beavailable if rule 2 were to be applied (in case rule 2 has higher priority than rule 1).
In some cases, even if the target term can match only one original pattern, there may be
more variable substitutions than are required. For instance, when the non-original patternD in Figure 1 is matched, four variable instances would be collected, namely those
I J

Copyright  1999 John Wiley & Sons, Ltd.

Softw. Pract. Exper., 29(9), 793-813 (1999)

EFFICIENT AUTOMATA-DRIVEN PATTERN-MATCHING

805

rooted at positions 1, 2, 2.1 and 2.2 in the target term: three correspond to the occurrences of and one to the occurrence of g. No substitutions are collected for the occurrences of f anda in states 0 and 4, respectively, because MT[0, ] and MT[4, ] are fail. Since I J D is
associated with rule 2 whose pattern is I D, only the variable instances rooted at positions 1
and 2 would be used, and the rest ignored.
5. ANALYSIS OF RIGHT-HAND SIDES
Exploiting the idea of partial evaluation in the compilation of equational programs, we canfeed the templates into a partial evaluator for further processing. The result may enable theskipping of some matching steps every time a rewrite rule is performed. In the best case, theconstruction of some terms will be avoided. In this section, we describe how to takeadvantage of known information in the templates by partially evaluating them at compile-time.
In general, partial evaluation consists of transforming a given program Prog (perhaps
using some partial input) into another program Prog’ which produces the same result. The
main transformations [22] are known as constant folding, function specialisation and callunfolding. Constant folding simplifies expressions by replacing known subexpressions by theirvalues, while function specialisation specialises function definitions to take advantage of some
information concerning some of its arguments. Finally, call unfolding unfolds function calls to
expose it to some improvements due to a particular calling context.
Partial evaluation for equational programming was first introduced by Strandh [3] andcontinued by Durand [23,24], Sherman [25] and Miniussi [28]. In most of these works, theequational program is compiled into intermediate code, then using the information known
about the equations’ right sides, this code is specialised by means of the transformations
above. The specialised code avoids the construction of some nodes and the checking of aknown part of the templates. However, rather than applying the transformations to the code
generated for the equational program, we instead apply them instead directly to the rewrite
rules of the program.
The right-hand side analysis at compile-time exploits the first two transformations, namely
constant folding and function specialisation, (i) to transform the templates themselves so theconstruction of some terms will be avoided at run-time, and (ii) to specialise the pattern-matcher so that it avoids checking the known part of the template. The analysis consists ofmatching and rewriting the templates as far as they allow it using the matching automaton.
This process halts when the template considered is not defined enough to continue matchingor rewriting. Then the current matching state K and position Q are returned with the current
template. This new template decorated with K and Q is used to replace the appropriate
rewrite rule right side in the original equation system. K and Q are used to specialise thepattern-matcher so that when the rule is applied at run-time, pattern-matching will commencein state K at position Q.
For instance, consider the template hbyagxa of rule 3 in the system (E) of Section 4.
While trying to match the whole template to the pattern of rule 5, the subterm gxa is
encountered. The adaptive rewrite strategy requires this to be rewritten if possible. When it isanalysed, rule 4 can be applied, and so gxa is rewritten to x. The strategy now requires theresulting term hbyax to be rewritten, if possible. However, pattern-matching halts at the last
symbol because it is not known whether the value of x will match a as in the pattern of rule 5,
or not. So hbya·x is returned as the new template. The analysis recognises the first foursymbols (they match those of the pattern of rule 5), and so pattern-matching can safely

Copyright  1999 John Wiley & Sons, Ltd.

Softw. Pract. Exper., 29(9), 793-813 (1999)

806

N. NEDJAH, C. D. WALTER AND S. E. ELDRIDGE

commence at the fifth symbol at run-time. Now, let the subject term be fabaabaa. In theoriginal equation system (E), the evaluation would proceed by
3

fabaabaa →54hbaagaa → hbaaa → a

where redexes are underlined. However, when the template of rule 3 is replaced by hbya·x togive a rule 3’ the evaluation would proceed by
3’

5

fabaabaa → hbaa·a → athereby skipping one rewriting step and some pattern-matching.
5.1. Template pattern-matching
Pattern-matching of templates or their subterms differs from that earlier on because we
may now have variable symbols in the subject term. Functions are treated in the same way as
before. However, when a variable is encountered at position P, there are three possible
courses of action. First, suppose that there is only an -transition from the current matchingstate in the matching automaton. (So every pattern in the current matching set has a variable
symbol at P, and the matching table contains fail under each function symbol.) Then, thevariable in the pattern can be instantiated to the run-time value of the variable in the subject
term. So pattern-matching will succeed at run-time, and analysis can continue as determinedby the matching table entry. Secondly, suppose every transition from the current matchingstate is either fail or is identical to the entry under in the matching table. Again at run-time,
the non-fail action will be performed anyway (whether via a function or  symbol entry).
Thus, matching will again succeed at P, and so the analysis may proceed as before. Finally,
and otherwise, for some function symbol f there is a (non-fail) f-transition from the current
matching state that is different from the -transition. In this case, the analysis must halt andreturn P paired with the current state because at run-time, the template variable may either
match f or default to , so that the next state is not determined.
The order of analysing the right sides depends upon the choice of reduction strategy.
Clearly, after applying a given rule the whole template or one of its subterms, or even asuperterm of the template, may be the next candidate for rewriting. The analysis must use thisstrategy to determine the next term to consider. Therefore, a good choice of the reduction
strategy will enable more to be gained from template knowledge, more compile-timeevaluation to be done, and hence lead to more efficient programs. In particular, this is thecase for the adaptive strategy of Section 4. Whenever a term is rewritten, a further attempt
can be made to rewrite the result: a template is always the next candidate term to be rewritten,
and the right side analysis can therefore consider at least this term.
So, we will present the analysis process using that adaptive strategy on the example above,
and assume a constructor discipline as before. In general, the analysis proceeds by inspecting
in pre-order the nodes of the template graph starting from its root, i.e. taking the symbols in
left-to-right order. The presence of variable symbols in the subject term means that theanalysis transition rule (see Figure 5) is a version of that of Figure 3 which is modified in theway described above. A further modification is necessary because the run-time subject term is
not known, and the strategy applies differently to subterms, which the template may represent.

Copyright  1999 John Wiley & Sons, Ltd.

Softw. Pract. Exper., 29(9), 793-813 (1999)

EFFICIENT AUTOMATA-DRIVEN PATTERN-MATCHING

807〈,3075 〉 →Case MatchingAction of
accept-symbolJ: 〈J, Next(P), 075 〉 ;accept-termJ:

If ∀f∈F (MT[I, f] = fail) then 〈J, NextArg(P), 075 〉else MarkAsHeadNormal 

reducer :If >53@∈ F or ∀f∈F (MT[I, f] = fail or reduce ) then

fail:



〈 075ApplyRuler  R)〉;else MarkAsHeadNormal If ∃f∈F (MT[I, f] IDLO and >53@∈ F and ¬IsHeadNormal(P) then
HeadNormalise 53
else Case MT[I, ] ofaccept-termJ:
reducer:
fail:
End〈J, NextArg(P), 075 〉;〈 075ApplyRuler
MarkAsHeadNormal 



R)〉;

End
Where MatchingAction = If >53@∈ F then07>, >53@@else failFigure 5. Machine state transition rule for template analysis

In general, there are three possible outcomes at each pattern-matching step: failure,
halting and success. The process halts when run-time knowledge of the value of a variable isrequired, or when the run-time context of the template is required before the strategy candetermine the next candidate term for rewriting. Success leads to a rewrite and the strategy
seeks the next redex, bearing in mind that the new template may not be the whole of thesubject term being evaluated. If analysis of the whole template produces failure, then no
rewrite of the current term is possible, and another redex is sought, as in the case of success.
For the strategy here, once the current template as a whole returns fail, the process does not
try to analyse the subterms. This is because it is not known whether the whole template, oneof its subterms or another subterm of the subject term, may become the next candidate to
rewrite. Thus, until some variables are instantiated, the template obtained by the analysis isroot-redex free, and is therefore said to be in head normal form [3,7].

5.2. Transition rules for template analysis
The analysis transition rule for the adaptive strategy is given in Figure 5. The head normal
form of a template  is obtained by repeating that transition rule, starting from the initial state MT, ) until it marks  as head normal. Initially, all the nodes in the graph of ,
except those labelled with constructors, are marked as not head normal (i.e. not known to be
in head normal form). Subterms with a constructor root are already in head normal form, andso are marked as such. As before, MatchingAction is either MT[I, [R.P]] or fail, dependingon whether [R.P] is a symbol that appears in the patterns or not. Notice that [R.P] may be
the symbol . Therefore, we must follow MT[I, ], only if there exists no function symbol fof F such that MT[I, f] fail.

Copyright  1999 John Wiley & Sons, Ltd.

Softw. Pract. Exper., 29(9), 793-813 (1999)

808

N. NEDJAH, C. D. WALTER AND S. E. ELDRIDGE

Table II. Decorated matching table for the equation set (E)

0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

f
g
h
a
b
accept-symbol1 accept-symbol2 accept-symbol3
fail
fail
fail
fail
fail
"
"
"
"
"
"
"
"
"
"
"
accept-symbol7"""
accept-symbol10 accept-symbol8
"
"
"
fail
reduce4,〈 〉""""reduce6,〈5,2〉
"
"
"
fail
"
"
"
"
"
"
"
"
"
"
reduce2,〈 〉""""reduce1,〈 〉"""accept-symbol14
"
"
"
"
fail
"
"
"
"
"
reduce6,〈5,2〉""""reduce5,〈 〉accept-symbol16"""
reduce2,〈 〉
"
"
"
fail
fail
"
"
"
"
"









fail
accept-term4
accept-term5
accept-term6
accept-term9
fail"
accept-term1
accept-term2
failreduce1,〈 〉accept-term13
accept-term15
fail"accept-term16
accept-term17
reduce3’,〈14,2〉
Eventually, after repeatedly applying the transition of Figure 5, the machine halts in〈I, P, MT, R, 〉 with marked as head normal. Then the symbol [P] or the context of is notdefined enough to progress in the matching of . In both cases, the decoration returned ismerely the value of the pair 〈I, P〉 at this final stage. The repetition of the transition rule of
Figure 5 until it halts is called HeadNormalise( ), and it may need to call itself recursively for
subterms. The Boolean function IsHeadNormal(P) checks whether the subterm rooted at
position P is known to be in head normal form, whereas the function MarkAsHeadNormal( )marks the root of the template when this template is known to be in head normal form.
Overall, analysis of all right sides of the equation system (E) yields a revised template list(a, a, KE D , , a, JD ), in which the third has changed, and a corresponding list ofdecorations (〈  〉, 〈  〉, 〈14, 2〉, 〈  〉, 〈  〉, 〈5, 2〉). The new matching table is given in
Table II, complete with decorations. Four of the decorations are 〈  〉, which indicate thatno progress at all was made in matching the templates.
The analysis of the template KE DJ D of rule 3 is described in Table III. This is doneusing the transition rule of Figure 5 and the original matching table which is the same as theundecorated version of Table II in this instance.

5.3. New machine state transition rule
Using the decorated matching table, together with the new template set, it is now possible
to skip all the known nodes in a template and avoid all those reductions that have been done atcompile-time while analysing the templates. Whenever a rule r is used to rewrite a subterm
the new template is used and the corresponding decoration 〈K, Q〉 from MT is used to set thecurrent matching state and matching position. Figure 6 depicts the transition rule for themachine augmented with these decorations.

Copyright  1999 John Wiley & Sons, Ltd.

Softw. Pract. Exper., 29(9), 793-813 (1999)

EFFICIENT AUTOMATA-DRIVEN PATTERN-MATCHING

809

Table III. Analysis of the template KE DJ D
Current State I
0
3
7
11
14
0
2
5
0
14
14

Current Position P

Current term
·KE DJ D
h·E DJ D
hb· DJ D
KE ·DJ D
KE D·J D
·J D
g· D
J ·a
·
KE D·
KE D·

1
1.1
1.2
2
1
2
2
2

Matching Action
accept-symbol3
accept-symbol7
accept-term11
accept-symbol14
fail − HeadNormalise(J D)
accept-symbol2
accept-term5
reduce4
fail − HeadNormalise( )fail − MarkAsHeadNormal(KE D )return 〈14,2〉 and KE D·〈I, P, MT, R, T〉 →Case MatchingAction of
accept-symbolJ: 〈J, Next(P), MT, R, T〉 ;reduce 〈K, Q〉 :fail :
〈K, Q, MT, R, ApplyRuler(T, R)〉;
If T[R.P]∈ F and ∃f∈F (MT[I,f]IDLO and ¬IsNormal(P) thenNormalise(T/R.P)
else Case MT[I, ] ofaccept-termJ :〈J, NextArg(P), MT, R, T〉;

reduce 〈K, Q〉 :〈K, Q, MT, R, ApplyRuler(T, R)〉;

fail:

If Next(R) Defined then 〈07

Next(R), T〉

else MarkAsNormal(T);End
End
Where MatchingAction = If T[R.P] ∈ F then MT[I, T[R.P]] else failFigure 6. New machine state transition rule

6. EVALUATION
An experimental implementation of the term rewriting machine described in Sections 4 and 5
was built to evaluate the automaton-driven pattern-matcher, which takes advantage of known
right side information. The number of matching actions and rewrites, as well as the evaluation
times, has been recorded to show the effect on the evaluation process. Two different toy
equational programs, Prog1 and Prog2, have been written to illustrate the effect of different
degrees of overlap between the templates and the patterns. We also report the evaluation time
for some common problems which were also used as benchmarks to evaluate HIPER [14].
In both programs Prog1 and Prog2, the function arities are as in the equation system (E).
Program Prog1 (with the equation set below) gains little advantage from the right-hand side
analysis. It results in few decorations different from the default decoration. The decoration
list is (〈  〉, 〈5, 2〉, 〈13, 2〉, 〈7, 2〉, 〈15, 3〉, 〈  〉, 〈  〉, 〈  〉) and the templates remainunchanged (they are already in head normal form):

Copyright  1999 John Wiley & Sons, Ltd.

Softw. Pract. Exper., 29(9), 793-813 (1999)

810

N. NEDJAH, C. D. WALTER AND S. E. ELDRIDGE

1. f(x, a, y)=c
2. f(x, y, a)= h(a, x)
3. f(x, b(s, y), b(t, z)) = h(b(y, a), z)
4. g(x, c)= f (b(a, x), x, b(a, x))

5. g(x, y)= f (x, b(x, y), h(y, x))
6. h(b(x, a), c) = b(a, x)
7. h(b(x, a), y) = c
8. h(x, a)= b(a, x)

Table IV. Number of rewrites, accept-symbols and accept-term-operations

Prog1
Prog2

_______Rewrites_______ Accept-symbol operations
Without
With
Without
With
decorations decorations decorations decorations
60
60
137
67
42
18
132
24

Accept-term operations
Without
With
decorations decorations
153
85
166
36

However, for program Prog2 (with the equation set below), more decorations are different
from the default decoration. The list is (〈  〉, 〈15, 3〉, 〈5, 2〉, 〈  〉, 〈15, 3〉, 〈  〉, 〈10, 3〉,〈6, 2〉), and some templates are rewritten. Therefore, Prog2 should gain more from theanalysis:
1. f(x, a, y)=c
2. f(x, y, a)= h(a, a)
3. f(x, b(s, y), b(t, z)) = h(b(y, a), z)
4. g(x, c)= f (b(a, x), a, b(a, x))

5. g(x, y)= f (x, b(x, y), g(y, c))
6. h(b(x, a), c) = g(a, c)
7. h(b(x, a), y) = f (c, g(x, a), y)
8. h(x, a)= g(a, x)

After the analysis of right side rewrites and matches, the rewrite rules for Prog2 become:
1. fxay
2’. fxya
3’. fxbsybtz
4’. gxc= ·c= fabaa·c= hfybyac·z= ·c5’. gxy= fxbxy·c
6’. hbxac = ·c
7’. hbxay = fcfxbxac·y
8. hxa= ga·xThe rule number r is replaced with r’ if the template was rewritten in the analysis and thematching dot indicates the position where matching can safely begin when the template
instance is matched at run-time.
The numbers of rewrites provided in Table IV clearly show that the use of the decorating
information did indeed improve the evaluation time, and the gain depends upon how much of
the templates are successfully pattern-matched. Moreover, in our rewriting machine there wasvirtually no run-time overhead caused by using the decorations.
The terms evaluated are rather large (130 symbols for Prog1 and 513 for Prog2), and used
a combination of the rewrite rules provided. It is of little interest to provide them here. Table
IV provides the numbers of rewrites, accept-symbol and accept-term operations performed for
Prog1 and Prog2 when the result of the analysis was considered/neglected.
The evaluation times obtained for both programs in those two cases are given in Table V,
along with the evaluation times under the OBJ3 system [29]. The timings were taken on a 50
MHz microSPARC I. Notice that under OBJ3, the same (adaptive) strategy has been used toobtain those figures, and the numbers of rewrites performed was identical to those obtained
when the decorations were not considered. Of course, the OBJ3 times include type-checking,etc., which is not the case for our implementation, and so are greater. These timings clearlyshow that for some equational programs, partial evaluation can provide significant run-time
efficiency gains.

Copyright  1999 John Wiley & Sons, Ltd.

Softw. Pract. Exper., 29(9), 793-813 (1999)

EFFICIENT AUTOMATA-DRIVEN PATTERN-MATCHING

811

Table V. Evaluation times

Prog1
Prog2

_Evaluation time (sec.)_
Without
With
decorations decorations
0.481
0.421
0.337
0.149

OBJ3
time
(sec.)
0.562
0.399

Table VI. Evaluation times for miscellaneous benchmarks

Kbl
Comm
Ring
Groupl_Evaluation time (sec.)_
Without
With
decorations decorations
0.088
0.079
0.130
0.079
2.139
2.060
2.487
1.880

HIPER
time
(sec.)
0.067
0.10
2.83
2.00

Table VI shows the performance of our machine together with that of HIPER [14] onsome common problems. These problems were first used by Christian [14] to evaluate his
system HIPER which uses flatterms to perform pattern-matching. The Kbl is the ordinary
three-axiom group completion problem. The Comm is the commutator theorem for groups.
The Ring problem is to show that if x2 = x in a ring, then the ring is commutative. Finally, theGroupl problem derives a complete set of reductions for Highman’s single-law axiomatizationof groups using division. Times under HIPER are for Sun 4, while times for our
implementation are for MicroSPARC I.

7. CONCLUSION
In the first part of this paper, we described a practical method allowing for the compilation of
a set of patterns to an equivalent deterministic automaton which does not need any
backtracking to pattern-match terms. In contrast with the method described by Gräf [9], ourmethod presented a simple iterative algorithm for closure, and can handle prioritised
overlapping patterns. Patterns are compiled into matching tables which are simple, compact
and expressive. Where necessary, the textual order meta-rule was used to resolve conflict due
to overlapping patterns. However, we explained how any other meta-rule could easily be
implemented.
Unlike Gräf [9], we explain how the pattern-matching method is used in the context of areduction strategy. In fact, we showed that with minor changes to the abstract machinetransition rule, any strategy can be accommodated. We outlined the three most popular
rewriting strategies, namely the leftmost-innermost, the leftmost-outermost and the adaptive
strategy, the last of which respects the semantics of prioritised equation systems. We
described the compile-time analysis of rule right-hand sides that could speed-up the evaluation
process, although the advantage gained is heavily dependent upon the choice of evaluation
strategy. An important consequence of this compile-time analysis is, that the redex graph may
not need to be checked completely each time a pattern-match operation is attempted.
Copyright  1999 John Wiley & Sons, Ltd.

Softw. Pract. Exper., 29(9), 793-813 (1999)

812

N. NEDJAH, C. D. WALTER AND S. E. ELDRIDGE

Moreover, we explained how the construction of some terms could be avoided using new
templates generated by the analysis procedure.
Finally, in Section 6, results from an implementation have been given. These results show
a substantial improvement in some evaluation times for the version that includes right-handside analysis relative to that which does not.

REFERENCES
1. C. M. Hoffman and M. J. O’Donnell, ‘Pattern-matching in trees’, J. ACM, 68-95 (January 1982).
2. C. M. Hoffman and M. J. O’Donnell, ‘Programming with equations’, ACM TOPLAS, pp. 83-112(January 1982).
3. R. I. Strandh, ‘Compiling equational programs into efficient code’, PhD Thesis, The Johns
Hopkins University, 1988.
4. J. R. Kennaway, ‘The specificity rule for lazy pattern-matching in ambiguous term rewriting
systems’, Proc. European Symposium on Programming; LNCS 432, Springer-Verlag, 1990, pp.
256-270.
5. Ph. Schnobelen, ‘Refined compilation of pattern-matching for functional programming’, Proc.
Algebraic and Logic Programming; LNCS 343, Springer-Verlag, 1988, pp. 233-243.
6. L. Augustsson, ‘Compiling pattern-matching’, Proc. Functional Programming Languages on
Computer Architecture; LNCS 201, Springer-Verlag, 1985, pp. 368-381.
7. P. Wadler, ‘Efficient compilation of pattern-matching’, in S. L. Peyton Jones (ed.), The
Implementation of Functional Programming Languages, Prentice Hall, 1987.
8. A. J. Field, L. S. Hunt and R. L. While, ‘Best-fit pattern-matching for functional languages’,
Technical Report, Department of Computing, Imperial College, 1988.
9. A. Gräf, ‘Left-to-right pattern-matching’, Proc. Rewriting Techniques and Applications; LNCS
488, Springer-Verlag, 1991, pp. 323-334.
10. C. M. Hoffman, M. J. O’Donnell and R. I. Strandh, ‘Implementation of an interpreter for abstract
equations’, Software − Practice and Experience, 15(12), pp. 1185-1204 (1985).
11. G. Huet and J. J. Levy, ‘Computations in orthogonal term rewriting systems’, in J. L. Lassez and
G. Plotkin (eds.), Computational logic: Essays in honour of Alan Robinson, 1992, pp. 415-443.
12. M. J. O’Donnell, Equational Logic as a Programming Language, Foundations of Computing
Series, The MIT Press, 1985.
13. L. Maranget, ‘Two techniques for compiling lazy pattern-matching’, Research Report 2385,
Institut National de Recherche en Informatique et Automatique INRIA, France, 1994.
14. J. Christian, ‘Flatterms, discrimination nets and fast term rewriting’, J. Automatic Reasoning, 10,
pp. 95-113, 1993.
15. A. V. Aho, R. Sethi and J. D. Ulmann, Compilers: Principles, Techniques and Tools, AddisonWesley, 1986.
16. S. C. Johnson, ‘Yacc Yet another compiler compiler’, Computing Science Technical Report 32,
AT&T Laboratories, Murray Hill, NJ, 1975.
17. R. M. Burstall, D. B. MacQueen and D. T. Sannella, ‘HOPE: an experimental applicative
language’, Proc. 1st ACM LISP Conference, 1980, pp. 218-225.
18. R. Harper, R. Milner and M. Tofte, ‘The definition of standard ML’, Technical Report ECSLFCS-88-62, Laboratory for Foundations of Computer Science, University of Edinburgh, 1988.
19. D. A. Turner, ‘Miranda: a non-strict functional language with polymorphic types’, Proc.
Functional Programming and Computer Architecture; LNCS 201, Springer-Verlag, 1985, pp. 116.
20. L. Augustsson, ‘A compiler for Lazy ML’, Proc. Conference on LISP and Functional
Programming, 1984, pp. 218-225.
21. P. Hudak and P. Wadler, ‘Report on the functional programming language Haskell’, Technical
Report YALEU/DCS/RR656, Department of Computer Science, Yale University, 1988.
Copyright  1999 John Wiley & Sons, Ltd.

Softw. Pract. Exper., 29(9), 793-813 (1999)

EFFICIENT AUTOMATA-DRIVEN PATTERN-MATCHING

813

22. N. Jones, ‘Automatic program specialization’, in J. Bjorner (ed.), Partial Evaluation and Mixed
Computations, Elsevier, 1988, pp. 225-282.
23. I. Durand, D. J. Sherman and R. I. Strandh, ‘Fine-grain partial evaluation of intermediate codefrom equational programs’, Bigre J., 74, (1991).
24. I. Durand, D. J. Sherman and R. I. Strandh, ‘Optimisation of equational programs using partial
evaluation’, Proc. ACM/IFIP Symposium on Partial Evaluation and Semantics-Based Program
Manipulation, ACM Sigplan, 26, pp. 72-81 (1991).
25. D. J. Sherman, ‘Run-time and compile-time improvement to equational programs’, PhD thesis, The
University of Chicago, Illinois, June 1994.
26. S. Thatte, ‘On the correspondence between two classes of reduction systems’, Information
Processing Letters, 20, pp. 83-85 (1985).
27. B. Salinier, ‘Simulation de systèmes de réécriture de termes par des systèmes constructeurs’, PhD
thesis, Université Bordeaux I, 1995.
28. A. Miniussi and D. J. Sherman, ‘Squeezing intermediate construction in equational programs’,
Proc. Partial Evaluation International Seminar; LNCS 1110, Springer-Verlag, 1996, pp. 284302.
29. J. A. Goguen and T. Winkler, ‘Introducing OBJ3’, Technical Report SRI-CSL-88-9, Computer
Science Laboratory, SRI International, August 1988.

Copyright  1999 John Wiley & Sons, Ltd.

Softw. Pract. Exper., 29(9), 793-813 (1999)