Cover.0Cover.0CoverCoverCover.0

Titlepage.0Titlepage.0TitlepageTitlepageTitlepage.0

RWTH Aachen University
Aachen Institute for Advanced Study in Computational Engineering Science
High-Performance and Automatic Computing Group

Master Thesis
Non-linear Associative-Commutative Many-to-One Pattern Matching with Sequence
Variables
Manuel Krebber

1\. Reviewer

Prof. Paolo Bientinesi, Ph.D.

AICES, HPAC Group

RWTH Aachen University

2\. Reviewer

Dr. Diego Fabregat-Traver

AICES, HPAC Group

RWTH Aachen University

Supervisor

Henrik Barthels, M.Sc.

April 24, 2017

Manuel Krebber
Non-linear Associative-Commutative Many-to-One Pattern Matching with Sequence
Variables
Master Thesis, April 24, 2017
Reviewers: Prof. Paolo Bientinesi, Ph.D. and Dr. Diego Fabregat-Traver
Supervisor: Henrik Barthels, M.Sc.
RWTH Aachen University
High-Performance and Automatic Computing Group
Aachen Institute for Advanced Study in Computational Engineering Science
Rogowski Building
Schinkelstr. 2
52062 Aachen

Abstract.0Abstract.0AbstractAbstractAbstract.0

##  chapterAbstract

Pattern matching is a powerful tool which is part of many functional
programming languages as well as computer algebra systems such as Mathematica.
Among the existing systems, Mathematica offers the most expressive pattern
matching. Unfortunately, no open source alternative has comparable pattern
matching capabilities. Notably, these features include support for associative
and/or commutative function symbols and sequence variables. While those
features have individually been subject of previous research, their
comprehensive combination has not yet been investigated. Furthermore, in many
applications, a fixed set of patterns is matched repeatedly against different
subjects. This many-to-one matching can be sped up by exploiting similarities
between patterns. Discrimination nets are the state-of-the-art solution for
many-to-one matching. In this thesis, a generalized discrimination net which
supports the full feature set is presented. All algorithms have been
implemented as an open-source library for Python. In experiments on real world
examples, significant speedups of many-to-one over one-to-one matching have
been observed.

Contents

toc

##  chapter 1chapterIntroduction

Pattern matching is a powerful tool which is part of many functional
programming languages as well as computer algebra systems such as Mathematica.
It is useful for many applications including symbolic computation, term
simplification, term rewriting systems, automated theorem proving, and model
checking. Term rewriting systems can be used with pattern matching to find
matches for the rewrite rules and transform terms. In functional programming
languages, pattern matching enables a more readable and intuitive expression
of algorithms.

Among the existing systems, Mathematica offers the most expressive pattern
matching. It is similar to Perl Compatible Regular Expressions [1], but for
symbolic tree structures instead of strings. Patterns are used widely in
Mathematica, e.g. in function definitions or for manipulating expressions.
Users can define custom function symbols which can also be associative and/or
commutative. Mathematica also offers sequence variables which can match a
sequence of expressions instead of a single expression. They are especially
useful when working with variadic function symbols.

There is currently no open source alternative to Mathematica with comparable
pattern matching capabilities. In particular, we are interested in similar
pattern matching for an experimental linear algebra compiler. Unfortunately,
Mathematica is proprietary and nothing has been published on the underlying
pattern matching algorithm.

Previous work predominantly covers syntactic pattern matching, i.e.
associative/commutative/variadic function symbols are not supported.
Specifically, no existing work allows function symbols which are either
commutative or associative but not both. However, there are domains where
functions have those properties, e.g. matrix multiplication in linear algebra.
Furthermore, most existing publications focus on finding a single match, but
we are also interested in finding all matches for a pattern.

In many applications, a fixed set of patterns will be matched repeatedly
against different subjects. The simultaneous matching of multiple patterns is
called many-to-one matching, as opposed to one-to-one matching which denotes
matching with a single pattern. Many-to-one matching can be sped up by
exploiting similarities between patterns. This has already been the subject of
research for both syntactic and AC pattern matching, but not with the full
feature set described above. Discrimination nets are the state-of-the-art
solution for many-to-one matching. Our goal is to generalize this approach to
support the aforementioned full feature set.

We implemented pattern matching with sequence variables and
associative/commutative function symbols as an open-source library for Python.
In addition, we implemented an efficient many-to-one matching algorithm that
uses generalized discrimination nets. In our experiments we observed
significant speedups of the many-to-one matching over one-to-one matching.

In Chapter 2, we cover the basics of pattern matching as well as our
extensions to syntactic pattern matching. Furthermore, an overview of the
related work and existing solutions is presented. Chapter 3 introduces
algorithms for one-to-one pattern matching which can handle the previously
proposed extensions. Then, in Chapter 4, a generalized version of
discrimination nets for many-to-one matching is described. The performance of
those algorithms is evaluated in Chapter 5. Finally, conclusions and ideas for
future work are presented in Chapter 6.

##  chapter 2chapterPreliminaries

The notation and definitions used are based on what is used in term rewriting
systems literature [2, 3, 4]. For some extensions to the basic syntactic
pattern matching, new notation is introduced.

###  section1 sectionSyntactic Pattern Matching

Syntactic pattern matching works on terms. Terms are algebraic data structures
constructed from a countable set of function symbols $\mathcal{F}$ and a
countable set of variables $\mathcal{X}$.

The function symbol set is composed of function symbols with different
arities, i.e. $\mathcal{F}=\bigcup_{n\geq 0}\mathcal{F}_{n}$ where
$\mathcal{F}_{n}$ contains symbols with arity $n$. The function symbols can
either have a fixed arity (i.e. they only occur in one $\mathcal{F}_{n}$) or
be variadic (i.e. occur in all $\mathcal{F}_{n}$ for $n\geq n_{0}$ and some
fixed $n_{0}$). Specifically, $\mathcal{F}_{0}$ contains all constant
(function) symbols.

In the following, $f$, $g$, and $h$ are used as function symbols and $a$, $b$,
and $c$ refer to constant symbols. Variables are usually called $x$, $y$, and
$z$. We usually write common function symbols such as $+$ and $\times$ in
infix notation and leave the braces out if unnecessary, i.e. we write $+(a,b)$
as $a+b$.

######  Definition 2.1 (Terms).

The set of all terms $\mathcal{T}(\mathcal{F},\mathcal{X})$ is the smallest
set such that

  1. 1.

$\mathcal{X}\subseteq\mathcal{T}(\mathcal{F},\mathcal{X})$ and

  2. 2.

for all $n\geq 0$, all $f\in\mathcal{F}_{n}$, and all $t_{1},\dots
t_{n}\in\mathcal{T}(\mathcal{F},\mathcal{X})$ we have
$f(t_{1},\dots,t_{n})\in\mathcal{T}(\mathcal{F},\mathcal{X})$.

Whenever the actual symbols and variables are not important, the set is
shortened to $\mathcal{T}$. We also call all terms from
$\mathcal{X}\cup\mathcal{F}_{0}$ _atomic terms_ and all others _compound
terms_. The set
$\mathcal{T}(\mathcal{F},\emptyset)\subseteq\mathcal{T}(\mathcal{F},\mathcal{X})$
is the set of _ground terms_ and is called $\mathcal{G}(\mathcal{T})$ or
simply $\mathcal{G}$. Since ground terms are variable-free, they are also
called constant. The set of variables occurring in a term is denoted by
$\mathcal{V}ar(t)$. A pattern $t$ is called _linear_ if every variable in
$\mathcal{V}ar(t)$ occurs at most once.

h $f$$g$$a$$x$$y$

Figure 1: Example of a Term as a Tree

Terms can be viewed as finite ordered trees. Therefore, the pattern matching
considered in this thesis is more closely related to tree pattern matching [5,
6, 7, 8] than to sequence pattern matching [9, 10]. The leafs of these trees
are labeled with either constants or variables. The inner nodes are labeled
with function symbols. In Figure 1, the tree representation of $f(g(a,x),y)$
is displayed. The _position_ of a subterm can be uniquely identified by the
position in this tree and can be expressed by a sequence of positive integers,
e.g. in the previous example $g$ has the position $1$ and $x$ has the position
$1\,2$. The term itself (the root of the tree) has the empty position sequence
$\epsilon$. For a position $\nu$, the subterm in $t$ at that position is
denoted by $t|_{\nu}$, e.g. $f(g(a,x),y)|_{1\,2}=x$. The set of all positions
in a term $t$ is called $\mathcal{P}os(t)$, e.g.
$\mathcal{P}os(f(g(a,x),y))=\\{\epsilon,1,1\,1,1\,2,2\\}$. The _size_ or
_length_ of a term $t$ is written as $|t|$ and is given by the number of nodes
in its tree, i.e. $|t|=|\mathcal{P}os(t)|$. We also define the _head_ of a
term to be the function symbol of a compound term and to be the atomic term
itself otherwise.

The interpretation as a tree also leads to the concept of preorder traversal.
This sequence is intuitively given by the term without the braces, i.e. for
$f(a,g(b,c),d)$ it would be $f\,a\,g\,b\,c\,d$. However, in the following we
define the preorder traversal in terms of positions, i.e. for the previous
example, we would get the sequence $\epsilon,1,2,2\,1,2\,2,3$. Formally, the
preorder sequence of a term is defined as

######  Definition 2.2 (Preorder Traversal of Term).

We define a function
$next:\mathcal{T}\times\mathbb{N}^{*}\rightarrow\mathbb{N}^{*}\cup\\{\top\\}$
that gives the next position in the preorder traversal sequence (or $\top$ if
its end is reached) as

$next(t,\nu):=\min\\{\nu^{\prime}\in\mathcal{P}os(t)\mid\nu<\nu^{\prime}\\}.$

where $<$ is the lexicographical order of positions extended with a new
minimum element $\top$ such that $\forall\nu\in\mathbb{N}^{*}:\top>\nu$.

The preorder traversal sequence $pre(t)$ is then given by
$\nu_{1}<\dots<\nu_{k}<\top$ where $\nu_{1}=\epsilon$,
$\nu_{i+1}=next(t,\nu_{i})$ for $i=1,\dots,k$ and $\nu_{k+1}=\bot$. Note that
$\mathcal{P}os(t)=\\{\nu_{1},\dots,\nu_{k}\\}$ and $k=|\mathcal{P}os(t)|$.

Similarly, we define the the next sibling’s position which is the next in
preorder traversal if we skip all children of the current node. For example,
in the term $f(a,g(b,c),d)$, the next sibling of $a$ is $g(b,c)$ and the next
sibling of both $g(b,c)$ and $c$ that is $d$.

######  Definition 2.3 (Next Sibling of Term).

Analogously to 2.2, we define a function
$skip:\mathcal{T}\times\mathbb{N}^{*}\rightarrow\mathbb{N}^{*}\cup\\{\top\\}$
that gives the position of the next sibling if it exists. If it does not
exists, the first parent that has a next sibling is found and that sibling’s
position is used. If no such parent exists, $skip$ returns $\top$. Formally,
$skip$ is defined as

$skip(t,\nu):=\min\\{\nu^{\prime}\in\mathcal{P}os(t)\mid\nu<\nu^{\prime}\wedge|\nu^{\prime}|\leq|\nu|\\}.$

Replacing the subterm at position $\nu$ in term $t$ with some other term $s$
is denoted by $t[s]_{\nu}$. A special case of replacements are
_substitutions_.

######  Definition 2.4 (Substitution).

A substitution is a partial function
$\sigma:\mathcal{X}\nrightarrow\mathcal{G}$. The substitution can be extended
to a total function
$\hat{\sigma}:\mathcal{T}(\mathcal{F},\mathcal{X})\rightarrow\mathcal{T}(\mathcal{F},\mathcal{X})$
by defining
$\hat{\sigma}(f(t_{1},\dots,t_{n}))=f(\hat{\sigma}(t_{1}),\dots,\hat{\sigma}(t_{n}))$
and $\hat{\sigma}(x)=\sigma(x)$ if $x\in Dom(\sigma)$ or $\hat{\sigma}(x)=x$
otherwise.

In the following, when we talk about substitutions, we usually mean the
extended substitution and for simplicity we also write $\sigma(t)$ instead of
$\hat{\sigma}(t)$. We often write substitutions as $\sigma=\\{x_{1}\mapsto
t_{1},\dots,x_{n}\mapsto t_{n}\\}$ where $\\{x_{1},\dots,x_{n}\\}=Dom(\sigma)$
are the variables _instantiated_ by the substitution. The set of all
substitutions is called $\mathcal{S}ub(\mathcal{T}(\mathcal{F},\mathcal{X}))$
or simply $\mathcal{S}ub$. In order to combine multiple substitutions, we need
to define which substitutions are compatible:

######  Definition 2.5 (Union of Substitutions).

Two substitutions $\sigma_{1}$ and $\sigma_{2}$ are _compatible_ (written as
$\sigma_{1}\triangle\sigma_{2}$) iff for every $x\in Dom(\sigma_{1})\cap
Dom(\sigma_{2})$ we have that $\sigma_{1}(x)=\sigma_{2}(x)$. We write the
_union_ of two compatible substitutions as $\sigma_{1}\sqcup\sigma_{2}$.

Finally, we can define the core of pattern matching, i.e. what constitutes a
match:

######  Definition 2.6 (Match).

A pattern term $t$ _matches_ a subject term $s$, iff there exists a
substitution $\sigma$ such that $\sigma(t)=s$. Such a substitution is also
called a _match_.

The goal of pattern matching is to find a match if it exists. For syntactic
pattern matching, this substitution is unique. In contrast to term
unification, the subject must always be constant for pattern matching.

###  section2 sectionExtensions

Because syntactic pattern matching is very limited in its power, several
extensions have been proposed, e.g. to allow matching with associative or
commutative function symbols.

####  subsection2.1 subsectionSequence Variables

In order to fully exploit the flexibility of variadic function symbols in
patterns, variables with similar flexibility are needed. Sequence variables
are the variable counterpart to variadic functions. In contrast to regular
variables, the sequence variables match a sequence of terms instead of a
single term. Sequence variables are denoted analogously to the notation used
in regular expressions. $x^{*}$ matches any number of terms including the
empty sequence, $x^{+}$ needs at least one term to match. Sequence variables
have been introduced by Mathematica, but have been discussed in the context of
term rewriting systems as well [11, 12, 13, 14].

Therefore, the definition of a substitution is extended to be a partial
function $\sigma:\mathcal{X}\nrightarrow\mathcal{G}^{*}$. More precisely, the
variable set can be split into three disjoint subsets: The _regular_ variables
$\mathcal{X}_{1}$, the _star_ variables $\mathcal{X}_{*}$ and the _plus_
variables $\mathcal{X}_{+}$. The substitution is a union
$\sigma=\sigma_{1}\sqcup\sigma_{*}\sqcup\sigma_{+}$ with
$\sigma_{1}:\mathcal{X}_{1}\rightarrow\mathcal{G}$,
$\sigma_{*}:\mathcal{X}_{*}\rightarrow\mathcal{G}^{*}$ and
$\sigma_{+}:\mathcal{X}_{+}\rightarrow\mathcal{G}^{+}$.

When applying a substitution, the replacement of a sequence variable is
integrated into the sequence of function symbol arguments:
$\sigma(f(a,x^{*},b))=f(a,c,d,b)$ for $\sigma=\\{x^{*}\mapsto(c,d)\\}$.

Patterns with sequence variables may yield multiple valid matches. For
instance, the pattern $f(x^{+},y^{+})$ and the subject $f(a,b,c)$ have both
$\sigma=\\{x^{+}\mapsto(a,b),y^{+}\mapsto(c)\\}$ and
$\sigma=\\{x^{+}\mapsto(a),y^{+}\mapsto(b,c)\\}$ as valid matches.

However, pattern matching with sequence variables is much harder than
syntactic pattern matching. As an example, consider the pattern
$f(x_{1}^{+},\dots,x_{m}^{+})$ and the subject $f(a_{1},\dots,a_{n})$. The
matches are analogous to integer partitions of $n$ with $m$ parts. There are
$\binom{n-1}{m-1}$ many distinct solutions (see Proposition 5.14 of [15]),
i.e. $\mathcal{O}(n^{m})$ many. The problem of finding all matches is
therefore exponential in the number of sequence variables.

####  subsection2.2 subsectionAssociative Functions

A binary function symbol $f$ is called _associative_ iff
$f(x,f(y,z))=f(f(x,y),z)$ for all $x,y,z$. We also write $t_{1}=_{A}t_{2}$ if
two terms are equivalent modulo associativity. To emphasize that a function
symbol is associative, we often write $f_{A}$ instead of $f$. We also use
$\mathcal{F}_{A}$ to denote the set of all associative function symbols. We
call a compound term with an associative function symbol as head an
_associative term_.

In order to easily check for equivalence modulo associativity, we use a
_canonical_ form of terms and a canonization function $c_{A}$ such that
$c_{A}(t_{1})=c_{A}(t_{2})\Leftrightarrow t_{1}=_{A}t_{2}$. Because the order
of the operand application does not matter as long as the order of the
operands is unchanged, we use variadic function symbols for associative
functions. Then $c_{A}$ simply _flattens_ nested associative terms, e.g.
$c_{A}(f_{A}(x,f_{A}(y,z)))=c_{A}(f_{A}(f_{A}(x,y))=f_{A}(x,y,z)$. From now
on, terms involving associative functions are always assumed to be in
canonical form.

In addition, associativity influences what regular variables can match.
Consider the pattern $1+x$ and the subject $1+a+b$. Because the latter is
equivalent to $1+(a+b)$, the substitution $\sigma=\\{x\mapsto(a+b)\\}$ is a
match. Essentially, regular variables behave like sequence variables within
associative function terms. The problem of associative matching can be reduced
to a matching problem with sequence variables by replacing every variable $x$
which is an argument of an associative function with a plus variable $x^{+}$.
For example, $f_{A}(x,a)$ matches a subject iff $f(x^{+},a)$ also matches it.
Note that the substitution may be different, e.g. for $\sigma_{A}=\\{x\mapsto
f_{A}(a,b)\\}$ and $\sigma_{S}=\\{x^{+}\mapsto(a,b)\\}$ we have that
$\sigma_{A}(f_{A}(x,a))=\sigma_{S}(f(x^{+},a))=f(a,b,a)$.

It has been shown that associative matching is NP-complete [16].

####  subsection2.3 subsectionCommutative Functions

A binary function symbol $f$ is called commutative iff $f(x,y)=f(y,x)$ for all
$x,y$. We also write $t_{1}=_{C}t_{2}$ if two terms are equivalent modulo
commutativity. To emphasize that a function symbol is commutative, we often
write $f_{C}$ instead of $f$. We also use $\mathcal{F}_{C}$ to denote the set
of all commutative function symbols. We call a compound term with a
commutative function symbol as head a _commutative term_.

In order to test equality modulo commutativity, we use a _canonical_ form with
a canonization function $c_{C}$ such that
$c_{C}(t_{1})=c_{C}(t_{2})\Leftrightarrow t_{1}=_{C}t_{2}$. To define such a
canonical form, we require a total order over $\mathcal{F}\cup\mathcal{X}$.
This order can be extended inductively to a total order of terms as defined
below.

######  Definition 2.7 (Order of terms).

Given a total order over $\mathcal{X}\cup\mathcal{F}$, the total strict order
of terms is inductively extended from it such that
$f(t_{1},\dots,t_{n})<g(s_{1},\dots,s_{m})$ iff

  1. 1.

$f<g$, or

  2. 2.

$f=g$ and $n<m$, or

  3. 3.

$f=g$ and $n=m$ and there is an $i$ such that $t_{i}<s_{i}$ and for all $1\leq
j<i$ we have $t_{j}=s_{j}$.

The canonical form of a commutative function term is then defined as the
minimal term in its equivalence class, i.e.

$c_{C}(t):=\min\\{t^{\prime}\in\mathcal{T}\mid t=_{C}t^{\prime}\\}.$

A term can be transformed to this form by recursively sorting the arguments of
each commutative function subterm. For example, the canonical form of
$f_{C}(b,a,g(a,b),\allowbreak g(c),h(a))$ is $f_{C}(a,b,g(c),g(a,b),h(a))$
assuming $a<b<c<f_{C}<g<h$. In the following, we assume that any term
containing commutative function symbols is in the commutative canonical form
described above.

Alternatively, we can also interpret the arguments of a commutative function
as a multiset of terms instead of a sequence. The interpretation as multiset
is also crucial for distributing terms among sequence variables without
enumerating duplicate substitutions. We further extend the codomain of the
substitution to include multiset replacements:
$\sigma:\mathcal{X}\nrightarrow\mathcal{G}^{*}\cup MS(\mathcal{G})$. We use
$\Lbag$ and $\Rbag$ to distinguish multisets from regular sets, e.g. $\Lbag
a,a,b\Rbag\neq\\{a,b\\}$. We use the notation $\pi_{M}(x)$ for the
multiplicity of the element $x$ in the multiset $M$, e.g. $\pi_{\Lbag
a,a,b\Rbag}(a)=2$. We use $\uplus$ to denote the multiset union of sets, e.g.
$\\{1,2\\}\uplus\\{1,3\\}=\Lbag 1,1,2,3\Rbag$. We write the scalar
multiplication of a multiset as $a\times M$, i.e. a repeated union of $M$ $a$
times such that if $M^{\prime}=a\times M$ we have
$\pi_{M^{\prime}}(x)=a\pi_{M}(x)$ for all $x$. As an example, $2\times\Lbag
1,3\Rbag=\Lbag 1,1,3,3\Rbag$.

Commutative matching can yield more valid substitutions than syntactic
matching. Consider the pattern $f_{C}(x,y)$ and the subject $f_{C}(a,b)$. This
yields two valid matches instead of one, i.e. $\sigma_{1}=\\{x\mapsto
a,y\mapsto b\\}$ and $\sigma_{2}=\\{x\mapsto b,y\mapsto a\\}$. Generally, for
a pattern $f_{C}(x_{1},\dots,x_{n})$ and a subject $f_{C}(a_{1},\dots,a_{n})$
a total of $n!$ distinct valid matches can be found. Just finding one
substitution in commutative matching has been shown to be NP-complete [16].

When combined with sequence variables, the number of matches can be
exponential in the subject size. Consider the pattern $f_{C}(x^{+},y^{+})$ and
a subject of the form $f_{C}(a_{1},\dots,a_{n})$. Because each symbol $a_{i}$
can be assigned to either variable independently, the matches are equivalent
to bitstrings of length $n$. Hence there are $2^{n}$ distinct matches and
enumerating all of them is an exponential problem.

####  subsection2.4 subsectionAssociative-Commutative Functions

Most function symbols which are either associative or commutative actually
possess both properties. Those function symbols are often called AC function
symbols and pattern matching with them is called AC pattern matching. We write
$t_{1}=_{AC}t_{2}$ if two terms are equivalent modulo associativity and
commutativity. Similarly, $f_{AC}$ denotes a function symbol which is both
associative and commutative.

The canonical forms for associative and commutative functions can be combined
into one form with a canonization function $c_{AC}:=c_{C}\circ c_{A}$. From
now on, every term is assumed to be in this canonical form.

It has been shown that the problem of AC pattern matching is NP-complete [16].
However, this only applies to the problem of finding one match. If the goal is
to find every possible match, the number of matches can be exponential and
hence the problem is only NP-hard. This can easily be seen with an example
analogous to the one for commutativity and sequence variables: For the pattern
$f_{AC}(x,y)$ and a subject of the form $f_{AC}(a_{1},\dots,a_{n})$ there are
again $2^{n}$ distinct matches.

While the subject of AC pattern matching has already been well researched [17,
16, 18, 19, 20, 21, 22, 23], pattern matching with just one of the properties
has not been explored exhaustively. Still, there are functions such as matrix
multiplication which are not commutative but associative. There are even
functions like the arithmetic mean which are commutative but not associative.
Therefore, e.g. in the case of linear algebra, further research is needed to
apply pattern matching to domains with such functions.

####  subsection2.5 subsectionGuards

Guards are logical predicates that can be attached to a pattern. This
predicate restricts what the pattern can match. The pattern only matches iff
the predicate is satisfied by the match substitution. Hence, a predicate
$\varphi$ can be seen as a function
$\mathcal{S}ub\rightarrow\\{true,false\\}$. We write a guard $\varphi$ on a
pattern $t$ as $t\ \mathbf{if}\ \varphi$.

While having one predicate for a whole pattern is easier for theoretical
reasoning, practically it is desirable to prune invalid matches early during
the match finding algorithm. Therefore, attaching a predicate to a subterm can
be helpful. As an example, we can stop matching on a pattern
$f(x,y^{+},z^{+})\ \mathbf{if}\ x\neq a$ once we discover the first argument
of $f(a,b,c,\dots)$ does not satisfy the guard.

###  section3 sectionRelated Work

There are numerous applications and implementations of pattern matching.
Pattern matching can be used to implement term rewriting systems where it is
used to find applicable rewrite rules. In that context, support for
associative and commutative function symbols is often essential. Pattern
matching has also been used as a tool in code generation for compilers [6].

Rewriting can also be used as a programming language [22]. This requires
deterministic pattern matching in order for the programs to be deterministic
as well. Especially the order in which multiple matches are found needs to be
deterministic. Such rewrite systems are Turing complete.

Previous research [18, 24, 21] only uses two kinds of function symbols:
syntactic and AC function symbols. The former have fixed arity and no special
properties. The latter are variadic, associative and commutative. They do not
support function symbols which only have some of those properties. Most
research assumes patterns to be linear and only Kutsia has included sequence
variables in his research [25, 26].

Even Mathematica can be considered a rewriting language [27], but it deserves
a special section as is has much more expressive pattern matching than other
term rewriting languages.

####  subsection3.1 subsectionMathematica

Several programming languages have some form of pattern matching built in.
Most of them are functional or multi-paradigm languages. For example, Haskell
[28], Elixir [29], Erlang [30], Rust [31], Scala [32], F# [33] and Swift [34]
all support syntactic pattern matching. Most of those languages also allow
guards on the pattern. The programming language Racket [35] even supports
pattern matching with sequence variables, but not commutative or associative
matching. The logic programming language Prolog [36] uses syntactic term
unification which is more general than pattern matching as both terms can
contain variables.

Out of all programming languages with pattern matching, the Wolfram Language
used in Mathematica [37] has the most powerful pattern matching support. It
supports both associative (flat) and commutative (orderless) function symbols
as well as sequence variables. Therefore, we will mostly focus on Mathematica
for comparisons.

In the Wolfram Language, variables are written as x_ for
$x\in\mathcal{X}_{0}$, x__ for $x^{+}\in\mathcal{X}_{+}$, and x___ for
$x^{*}\in\mathcal{X}_{*}$. Functions terms are expressed with square brackets
instead of braces, e.g. f[a, b] instead of $f(a,b)$. Mathematica also supports
anonymous variables (_, __ and ___). Guards are written as term /; guard.

Some of Mathematica’s features enable more powerful pattern matching than what
has been described in section 2. For example, there is an additional operator
p1|p2 to denote alternatives in a pattern, i.e. p1|p2 matches if either p1 or
p2 matches. While the alternatives operator can be replicated by using
multiple patterns, their number grows exponentially with the number of
alternatives in the worst case. Mathematica also allows a pattern to be
repeated an arbitrary number of times using the Repeated operation similar to
the Kleene plus in regular expressions. For example, f[Repeated[a]] matches
f[a, …], i.e. any f function with one or more a arguments.

Furthermore, similarly to regular expressions, the “greediness” of sequence
variables can be controlled, i.e. whether they match the shortest or longest
possible sequence. In case only one match is needed, this removes the non-
determinism of the matching, because the greediness determines the order for
the exploration of potential matches. For example, matching the pattern f[x__,
Longest[y__]] with the subject f[a, b, c] will always yield the substitution
$\\{x^{+}\mapsto a,y^{+}\mapsto(b,c)\\}$ first, because the $y^{+}$ variable
is made “greedy”. Therefore, when using the pattern matching for writing
programs, it is easier to reason about its behavior in cases where multiple
matches are possible.

Nonetheless, the Mathematica implementation has some limitations. First, when
using ReplaceList to get all matches for a commutative term, it generates
duplicate results:

SetAttributes[fc, Orderless];ReplaceList[fc[a, b, a], fc[x___, ___] -> {x}]

{{a,a,b},{a,b},{a,b},{a,a},{b},{a},{a},{}}While Mathematica converts
commutative terms to a sorted canonical form (i.e. fc[b, a] becomes fc[a, b]),
apparently the position of the arguments is used to distinguish otherwise
equivalent arguments when using ReplaceList. By using all argument
permutations instead of just distinct subsets of the argument multiset this
duplication is created. The duplication is amplified when the function symbol
is associative as well, since in that case each of the substitutions in Out[1]
is repeated an additional time.

There is also an inconsistency in Mathematica’s commutative matching. As
expected, commutative matching works when only using commutative functions:

MatchQ[fc[a, b], fc[b, a]]

True

MatchQ[fc[b, a], fc[a, b]]

TrueWhen using the same variable in both commutative and non-commutative
functions, Mathematica does find the matches in some cases:

MatchQ[f[f[a, b], fc[a, b]], f[f[x___], fc[x___]]]

TrueBut, if the order of the argument in the first subterm is changed, it does
not find a match even though there is one:

MatchQ[f[f[b, a], fc[a, b]], f[f[x___], fc[x___]]]

FalseThis problem even goes so far that the following pattern does not match
even though the order of the arguments is the same in both subterms:

MatchQ[f[fc[b, a], f[b, a]], f[fc[x___], f[x___]]]

FalseIt seems that this problem arises because Mathematica sorts the arguments
of commutative functions and then does a direct comparision between the
sequences if the same variable is encountered later. For non-commutative
functions, the arguments in substitutions are not sorted. This means that if a
sequence variable encounters arguments in a non-commutative subterm which are
not sorted, it can never match them in a commutative subterm, because there
the arguments will be sorted. In those cases, Mathematica will not find a
match even though there is one. While this is an edge case and most patterns
will not mix sequence variables in commutative and non-commutative functions,
it is still inconsistent and unexpected behavior. There are workarounds to get
such patterns to behave as expected.

Even though Mathematica has powerful pattern matching features, it has some
major drawbacks. The possibilities to access Mathematica’s features from other
programming languages is very limited. Writing large programs in Mathematica
can be cumbersome and slow for some applications. Also, Mathematica is a
commercial and proprietary product. Instead, it is desirable to have a free
and open source pattern matching implementation that also enables other
researchers to use and extend it.

##  chapter 3chapterOne-to-One Pattern Matching

In this chapter, algorithms for matching various types of patterns are
described. First, the basic case of syntactic patterns is covered. Then the
algorithm is extended to support sequence variables and associative functions.
Finally, an algorithm for commutative matching is outlined.

###  section4 sectionSyntactic Matching

Syntactic one-to-one pattern matching is straightforward, as both subject and
pattern can be traversed parallelly in preorder and compared at each node. The
matching algorithm is given in pseudocode in Algorithm 1.

Algorithm 1 Syntactic Matching

1 Subject $s\in\mathcal{T}$, pattern $p\in\mathcal{T}$, and an initial
substitution $\sigma\in\mathcal{S}ub$.

2 The match $\sigma$ or $\lightning$ iff there is no match.

3 function SyntacticMatch($s,p,\sigma$)

4  if $p\in\mathcal{X}$ then return $\\{p\mapsto s\\}$

5  if $p=f(p_{1},\dots,p_{n})$ and $s=f(s_{1},\dots,s_{n})$ for some
$f\in\mathcal{F},n\in\mathbb{N}$ then

6  for all $i=1\dots n$ do

7  $\sigma^{\prime}$ $\leftarrow$
$\textsc{SyntacticMatch}(s_{i},p_{i},\sigma)$

8  if $\sigma^{\prime}=\lightning$ or
$\sigma^{\prime}\centernot\triangle\sigma$ then return $\lightning$

9  $\sigma$ $\leftarrow$ $\sigma\sqcup\sigma^{\prime}$

10  return $\sigma$

11  return $\lightning$

For a given subject $s$ and a pattern $p$,
$\textsc{SyntacticMatch}(s,p,\emptyset)$ yields the match $\sigma$ or
$\lightning$ if there is no match. Note that there is at most one match in
syntactic matching. This algorithm has a worst case complexity of
$\mathcal{O}(min(|p|,|s|))$. One optimization in this algorithm is the early
abort when subject and pattern have different number of arguments. Because
syntactic matching does not involve associative function symbols or sequence
variables, in those cases there can be no match.

###  section5 sectionMatching with Sequence Variables

In Algorithm 2, the pseudocode for an algorithm that returns all matches for a
given subject and a given non-commutative pattern is displayed. An algorithm
for matching commutative patterns is discussed in the next section.

Algorithm 2 Matching with Sequence Variables

1 Subject sequence $s_{1}\dots s_{n}\in\mathcal{T}$, pattern
$p\in\mathcal{T}$, an optional associative function symbol
$f_{a}\in\mathcal{F}_{A}\cup\\{\bot\\}$, and initial substitutions
$\Theta\subseteq\mathcal{S}ub$.

2 The set of matches.

3 function MatchOneToOne($s_{1}\dots s_{n},p,f_{a},\Theta$)

4  if $p\in\mathcal{F}_{0}$ then $\triangleright$ Constant symbol pattern

5  if $n=1$ and $s_{1}$ = p then return $\Theta$

6  else if $p\in\mathcal{X}_{0}$ and $f_{a}=\bot$ then $\triangleright$
Regular variable pattern

7  $\sigma^{\prime}$ $\leftarrow$ $\\{p\mapsto s_{1}\\}$

8  if $n=1$ then return
$\\{\sigma\sqcup\sigma^{\prime}\mid\sigma\in\Theta\wedge\sigma\triangle\sigma^{\prime}\\}$

9  else if $p\in\mathcal{X}$ then $\triangleright$ Sequence variable pattern

10  if $p\in\mathcal{X}_{0}$ and $f_{a}\neq\bot$ then $\triangleright$ Regular
variable in assoc. function?

11  $\sigma^{\prime}$ $\leftarrow$ $\\{p\mapsto f_{a}(s_{1},\dots,s_{n})\\}$

12  else

13  $\sigma^{\prime}$ $\leftarrow$ $\\{p\mapsto(s_{1},\dots,s_{n})\\}$

14  if $p\in\mathcal{X}_{*}$ or $n\geq 1$ then return
$\\{\sigma\sqcup\sigma^{\prime}\mid\sigma\in\Theta\wedge\sigma\triangle\sigma^{\prime}\\}$

15  else if $n=1$ then $\triangleright$ Compound pattern

16  $h$ $\leftarrow$ $head(p)$

17  if $h=head(s_{1})$ then

18  $p_{1}\dots p_{k}$ $\leftarrow$ $args(p)$

19  $q_{1}\dots q_{l}$ $\leftarrow$ $args(s_{1})$

20  if $h\in\mathcal{F}_{a}$ then

21  $f_{a}^{\prime}$ $\leftarrow$ $h$

22  else

23  $f_{a}^{\prime}$ $\leftarrow$ $\bot$

24  return $\textsc{MatchSequence}(q_{1}\dots q_{l},p_{1}\dots
p_{k},f_{a}^{\prime},\Theta)$

25  return $\emptyset$

The algorithm matches a sequence of subject terms against the pattern. Using a
sequence of subjects instead of a single subject argument is needed to
correctly match sequence variables. The set of matches for subject $s$ and
pattern $p$ is returned by $\textsc{MatchOneToOne}(s,p,\bot,\\{\emptyset\\})$.

We use a set of substitutions here, because for non-syntactic patterns there
can be multiple matches. Hence, in Algorithm 2, $\emptyset$ as a result is
equivalent to $\lightning$ in Algorithm 1. Note that this is different from
$\\{\emptyset\\}$ as a result. The latter means there is a single match which
is the empty substitution, i.e. when the pattern does not contain any
variables.

We pass an initial set of substitutions into the function to be able to chain
them together for matching the argument subpatterns of a compound pattern.
Consider a pattern $f(g(x),g(x,a,b),\dots)$ and a subject
$f(g(a),g(c,a,b),\dots)$. There is no match as the substitutions of the
subpatterns for $x$ are not compatible. When calls to MatchOneToOne are
chained and the current set of substitutions gets passed around, matching can
be aborted early when there is a mismatch. In the previous example, at some
point $\textsc{MatchOneToOne}(c,x,\bot,\\{\\{x\mapsto a\\}\\})$ gets called
and returns an empty substitution set, aborting the matching.

An alternative solution would be to match each pattern argument separately and
only check whether the substitutions are compatible once all submatching has
completed. The disadvantage of this approach is that in case of a mismatch,
backtracking cannot occur early. However, by making the submatches
independent, they could be parallelized for better performance. We chose the
chained solution because in our application the overhead of parallelization
would likely outweigh the benefits.

The base cases of constant symbol and variable patterns are handled in the
MatchOneToOne function directly, while the handling of compound terms is
deferred to the MatchSequence function displayed in Algorithm 3. In the case
of a variable pattern, the MatchOneToOne function checks for all substitutions
$\sigma$ in the initial substitution set if the new variable substitution
$\sigma^{\prime}$ is compatible with $\sigma$. For those that are compatible,
the union substitution is constructed and the set of all these substitutions
is returned. While the constant symbols are only a special case of function
symbols and would be handled correctly by MatchSequence, they are treated
separately for performance reasons.

##### Description of Algorithm 3

In the following, a line-by-line description of the algorithm for sequence
matching is given:

2+4

The numbers of star and plus variables in the pattern are counted111These
values can be cached if the pattern becomes large enough for their computation
to become a bottleneck., respectively.

3

The matching aborts early, if the total number of arguments required in the
pattern exceeds the number of arguments in the subject. As an example,
consider the pattern $f(x^{+},y^{*},a,b)$ which requires a subject argument
each for $a$ and $b$ and at least one for $x^{+}$ to match. Hence, in total, a
match requires a subject term with at least 3 arguments. Given a subject
$f(a,b)$, we have that $m-n_{*}=4-1=3>2=n$ and hence the pattern cannot match.

5–6

Regular variables in associative functions are treated as plus sequence
variables and hence their number is added to the plus variable count.

1 Subject sequence $s_{1}\dots s_{n}\in\mathcal{T}$, pattern sequence
$p_{1}\dots p_{m}\in\mathcal{T}$, an optional associative function symbol
$f_{a}\in\mathcal{F}_{A}\cup\\{\bot\\}$, and initial substitutions
$\Theta\subseteq\mathcal{S}ub$.

2 The set of matches.

3 function MatchSequence($s_{1}\dots s_{n},p_{1}\dots p_{m},f_{a},\Theta$)

4  $n_{*}$ $\leftarrow$ $\sum_{i=1}^{m}[p_{i}\in\mathcal{X}_{*}]$
$\triangleright$ Number of star variables

5  if $m-n_{*}>n$ then return $\emptyset$

6  $n_{+}$ $\leftarrow$ $\sum_{i=1}^{m}[p_{i}\in\mathcal{X}_{+}]$
$\triangleright$ Number of plus variables

7  if $f_{a}\neq\bot$ then

8  $\triangleright$ Count regular vars as plus vars in assoc. function

9  $n_{+}$ $\leftarrow$ $n_{+}+\sum_{i=1}^{m}[p_{i}\in\mathcal{X}_{0}]$

10  $n_{free}$ $\leftarrow$ $n-m+n_{*}$ $\triangleright$ Number of free
arguments in the subject

11  $n_{seq}$ $\leftarrow$ $n_{*}+n_{+}$ $\triangleright$ Total number of
sequence variables

12  $\Theta_{R}$ $\leftarrow$ $\emptyset$ $\triangleright$ Result
substitutions

13  $\triangleright$ For every distribution of free arguments among the seq.
vars…

14  for all $(k_{1},\dots,k_{n_{seq}})\in\\{v\in\mathbb{N}^{n_{seq}}\mid\sum
v=n_{free}\\}$ do

15  $i$ $\leftarrow$ $0$ $\triangleright$ Subject argument index

16  $j$ $\leftarrow$ $0$ $\triangleright$ Sequence var index

17  $\Theta^{\prime}$ $\leftarrow$ $\Theta$ $\triangleright$ Intermediate
substitutions

18  $\triangleright$ For every pattern argument…

19  for all $l=1\dots m$ do

20  $l_{sub}$ $\leftarrow$ $1$ $\triangleright$ Length of subject argument
subsequence

21  $\triangleright$ If the argument is a sequence variable…

22  if $p_{l}\in\mathcal{X}_{+}\cup\mathcal{X}_{*}$ or
$p_{l}\in\mathcal{X}_{0}$ and $f_{a}\neq\bot$ then

23  $l_{sub}$ $\leftarrow$ $l_{sub}+k_{j}$

24  if $p_{l}\in\mathcal{X}_{*}$ then

25  $l_{sub}$ $\leftarrow$ $l_{sub}-1$

26  $j$ $\leftarrow$ $j+1$

27  $s^{\prime}$ $\leftarrow$ $s_{i}\dots s_{i+l_{sub}}$ $\triangleright$
Subject argument subsequence

28  $\Theta^{\prime}$ $\leftarrow$
$\textsc{MatchOneToOne}(s^{\prime},p_{l},f_{a},\Theta^{\prime})$

29  if $\Theta^{\prime}=\emptyset$ then break$\triangleright$ No match for
distribution

30  $i$ $\leftarrow$ $i+l_{sub}$

31  $\Theta_{R}$ $\leftarrow$ $\Theta_{R}\cup\Theta^{\prime}$

32  return $\Theta_{R}$

Algorithm 3 Matching a non-commutative function

7

The total number of “free” arguments in the subject can be determined, i.e.
how many arguments need to be distributed among the sequence variables. As an
example, consider the pattern $f(x^{+},y^{*},a,b)$ again, but this time with a
subject $f(a,b,c,a,b)$. We have $n_{free}=5-4+1=2$ free arguments (in this
case $b$ and $c$ can go in either $x^{+}$ or $y^{*}$).

8

The number of sequence variables is needed to enumerate all distributions of
the free arguments among them.

9

We use result substitution set $\Theta_{R}$ to collect all the intermediate
matches found for each generated distribution (see line 25).

10

Here we enumerate all possible distributions of the arguments among the
sequence variables. This is related to the combinatorial problem of
enumerating the $n_{free}$-multicombinations of $n_{seq}$ objects222This is
case four of the Twelvefold Way [38] [38, 39]. The solutions are also known as
the weak compositions of $n_{free}$ with $n_{seq}$ parts. Algorithms to
enumerate all these solutions efficiently have been developed, e.g. by [40]
and [41]. Generating the next weak composition can be done in
$\mathcal{O}(1)$, but there are $\binom{n-1}{m-1}$ many distinct weak
compositions [15] resulting in a total complexity of $\mathcal{O}(n^{m})$.
Note that the set of weak compositions for $n_{seq}=n_{free}=0$ contains the
empty tuple $()$ as single argument, so the case without sequence variables is
also covered. Similarly, if $n_{seq}=0$ and $n_{free}\geq 1$, the composition
set is empty and there is no match.

11–21

For each weak composition $k$ we map every pattern argument $p_{l}$ to a
subsequence $s^{\prime}$ of the subject arguments $s$. As an example, consider
the pattern $f(x^{+},y^{+})$ and the subject $f(a,b,c)$. We enumerate weak
compositions of $1$ with $2$ parts, i.e. $k\in\\{(0,1),(1,0)\\}$. These
correspond to the substitutions $\\{x^{+}\mapsto(a),y^{+}\mapsto(b,c)\\}$ and
$\\{x^{+}\mapsto(a,b),y^{+}\mapsto(c)\\}$ which are both collected and
returned as the overall result.

11

The index $i$ is used to track the next subject argument to assign.

12

The index $j$ is used to determine which part of the composition $k$ is used
for the next sequence variable.

13

An intermediate substitution set $\Theta^{\prime}$ is used to iteratively
merge submatches for a single composition.

14

We use the index $l$ to loop over all pattern arguments $p$.

15–21

Depending on whether the pattern argument is a sequence variable or not, we
assign a subsequence of subject arguments $s^{\prime}$ to the pattern argument
$p_{l}$. The subsequence always starts at index $i$ and has a length of
$l_{sub}$. We start off with a default length of $1$, i.e. one required
subject argument for every pattern argument. For all sequence variables we add
the corresponding part of the composition $k_{j}$ to the length, and for star
variables we subtract the initial $1$ because the star variable does not
require an argument.

22

Here the recursion occurs as MatchOneToOne is called to match the subject
argument subsequence against the pattern argument. The intermediate
substitution set $\Theta^{\prime}$ is updated to reflect the effects of this
submatch on the substitutions.

23

If $\Theta^{\prime}$ becomes empty, there is a mismatch for the current
sequence argument distribution. Therefore, the matching can continue with the
next composition.

24

Otherwise, we move the subject argument index $i$ to the end of the last
subsequence and continue with the next pattern argument.

25

The matches for every possible argument distribution are collected.

Note that the above algorithm does not include the support for commutative
patterns. The algorithm for commutative matching will be discussed in the next
section.

###  section6 sectionCommutative Matching

For commutative patterns, the argument order does not matter for matching.
This can be achieved with a brute force approach by applying non-commutative
matching to all permutations of the subject arguments and merging the results.
However, for a commutative term with $n$ arguments there are $n!$
permutations. As discussed in the previous section, there are exponentially
many potential matches for each of those permutations. Furthermore, this
approach will result in enumerating equivalent matches multiple times: Let the
pattern $f_{c}(x^{+},y^{+})$ and the subject $f_{c}(a,b,c)$ serve as an
example. Using non-commutative matching on the permutations $f_{c}(a,b,c)$ and
$f_{c}(b,a,c)$ yields the substitution $\\{x^{+}\mapsto\Lbag
a,b\Rbag,y^{+}\mapsto\Lbag c\Rbag\\}$ in both cases. For this example, every
match is enumerated twice by the brute force approach.

Still, our approach is to take all distinct mappings between patterns and
subjects and recursively apply MatchOneToOne to find matches for each
individual pattern-subjects pair. However, the goal is to only check each
distinct mapping once and to overall reduce the search space. Because the
problem of commutative matching is NP-complete, in the worst case, matching
can be exponential in the size of the subject. However, by choosing an
efficient order for the matching, large portions of the match search space can
potentially be pruned. This reduces the cost of matching in most common cases.
With this idea in mind, we propose the following order of matching for
argument patterns $p$ of commutative compound patterns:

  1. 1.

Constant patterns, i.e. patterns that are ground terms ($p\in\mathcal{G}$)

  2. 2.

Matched variables, i.e. variables that already have a value assigned in the
current substitution, ($p\in\mathcal{X}$ and $p\in Dom(\sigma)$)

  3. 3.

Non-variable patterns ($p\in\mathcal{T}\setminus\mathcal{X}$)

  4. 4.

Regular variables ($p\in\mathcal{X}_{0}$)

  5. 5.

Sequence variables ($p\in\mathcal{X}_{*}\cup\mathcal{X}_{+}$)

Let us take a look again at the size of the search space. For a subject with
$n$ arguments and a pattern with $m$ arguments we have up to $m^{n}$ potential
combinations333If all pattern arguments are star variables, we can assign each
subject to any of them independently. If all subject arguments are distinct,
that yields a total of $m^{n}$ combinations which are all valid matches,
assuming there are no further constraints. that need to be checked. Reducing
both $n$ and $m$ can dramatically reduce the number of possibilities which
need to be considered. As an example, covering constant patterns early means
the corresponding subjects do not need to be considered later for sequence
variables. The overall goal of this approach is to perform cheap submatches
early to reduce the search space for the more expensive matches.

To integrate the commutative matching into Algorithm 2, it suffices to replace
the line 24 with a branch that, depending on whether the function is
commutative or not, proceeds to call the commutative matching algorithm or
MatchSequence, respectively. The commutative matching algorithm is not given
as pseudocode because it would be too long, but its steps are outlined in the
next section.

####  subsection6.1 subsectionMatching Steps

For matching individual pattern arguments and subject sequences in commutative
terms, MatchOneToOne can be used again. As stated earlier, we want to
enumerate all possible mappings between subject and pattern arguments and
match them. In the following, the matching steps are described and we use $S$
to denote the multiset of subject arguments and $P$ for the multiset of
pattern arguments:

##### Constant patterns

To match constant arguments, we can construct the multiset
$P_{const}=P\cap\mathcal{G}$ of constant pattern arguments. If
$P_{const}\not\subseteq S$, a match is impossible, because at least one
constant argument in the pattern has no matching subject argument, and the
matching can be aborted. Otherwise we remove all matched constants from $S$
and $P$ and proceed, i.e. $S\leftarrow S\setminus P_{const}$ and $P\leftarrow
P\setminus P_{const}$ .

##### Matched variables

Similarly to constant patterns, checking variables which already have a value
in the current substitution is very cheap. If $x\in Dom(\sigma)$, we construct
a multiset $P_{x}:=\pi_{P}(x)\times\Lbag\sigma(x)\Rbag$ from the existing
substitution. This accounts for a variable occurring multiple times in the
pattern by multiplying the substitution by the number of occurrences, e.g. if
$\sigma(x)=(a,b)$ and $x$ occurs two times in the pattern, then $P_{x}=\Lbag
a,a,b,b\Rbag$. Again, if $P_{x}\not\subseteq S$, a match is impossible.
Otherwise we remove the matched terms from $S$ and $x$ from the pattern set,
i.e. $S\leftarrow S-x$ and $\pi_{P}(x)\leftarrow 0$. This can reduce the
search space considerably, because for those variables no potential matches
need to be enumerated. If there is more than one initial substitution, this
has to be done once per initial substitution and the remaining patterns need
to be matched separately.

##### Non-variable patterns

This set of patterns encompasses all the remaining pattern arguments except
single variables. However, these patterns do contain variables (otherwise they
would be constant) and hence any match for them is not empty. Therefore,
exhaustive matching has to be performed to find these matches. By grouping
patterns and subjects by their head, we can limit the pairwise combinations
between subjects and patterns to consider, because only those with the same
head can match. Each pairing can recursively be matched by using
MatchOneToOne. The matches are not necessarily independent, as two patterns
can contain the same variable. Consequently, we use an iterative process
similarly to the process in Algorithm 3. Instead of processing subpattern
matching independently, the calls to MatchOneToOne are chained together for
all combinations of pairings to find the overall match. Note that after
matching the non-variable patterns, the step of matching already matched
variables can be repeated, because new variables might have been added to the
substitution during this step.

Let the pattern $f_{c}(g(a,x),g(x,y),g(z^{+})$ and the subject
$f_{c}(g(a,b),g(b,a),g(a,c))$ serve as an example. There is only one match in
this example, namely $\\{x\mapsto b,y\mapsto a,z^{+}\mapsto(a,c)\\}$. However,
there is a total of $3!=6$ distinct mappings between the pattern arguments and
the subject arguments all of which could potentially match. In Figure 2 and
Figure 3 two different search trees for the matching are displayed. Each level
in the tree corresponds to a pattern argument that needs to be matched. Each
edge is labeled with the subject that is mapped to the respective pattern
argument at that level. Every node corresponds to a call to MatchOneToOne and
the resulting substitution. Failing matches are denoted with $\lightning$.

$\emptyset$$\\{x\mapsto b\\}$$\\{x\mapsto b,y\mapsto a\\}$$\\{x\mapsto
b,y\mapsto
a,$$z^{+}\mapsto(a,c)\\}$$g(a,c)$$g(b,a)$$\lightning$$g(a,c)$$g(a,b)$$\lightning$$g(b,a)$$\\{x\mapsto
c\\}$$\lightning$$g(a,b)$$\lightning$$g(b,a)$$g(a,c)$$g(a,x)$$g(x,y)$$g(z^{+})$final
Figure 2: Search Tree for order $g(a,x)$, $g(x,y)$, $g(z^{+})$

$\emptyset$$\\{z^{+}\mapsto(a,b)\\}$$\\{z^{+}\mapsto(a,b),$$x\mapsto
b,$$y\mapsto a\\}$$\lightning$$g(a,c)$$g(b,a)$$\\{z^{+}\mapsto(a,b),$$x\mapsto
a,$$y\mapsto
c\\}$$\lightning$$g(b,a)$$g(a,c)$$g(a,b)$$\\{z^{+}\mapsto(b,a)\\}$$\\{z^{+}\mapsto(b,a),$$x\mapsto
a,$$y\mapsto b\\}$$\lightning$$g(a,c)$$g(a,b)$$\\{z^{+}\mapsto(b,a),$$x\mapsto
a,$$y\mapsto
c\\}$$\lightning$$g(a,b)$$g(a,c)$$g(b,a)$$\\{z^{+}\mapsto(a,c)\\}$$\\{z^{+}\mapsto(a,b),$$x\mapsto
a,$$y\mapsto b\\}$$\lightning$$g(b,a)$$g(a,b)$$\\{z^{+}\mapsto(a,b),$$x\mapsto
b,$$y\mapsto a\\}$$\\{z^{+}\mapsto(a,b),$$x\mapsto b,$$y\mapsto
a\\}$$g(a,b)$$g(b,a)$$g(a,c)$$g(z^{+})$$g(x,y)$$g(a,x)$final Figure 3: Search
Tree for order $g(z^{+})$, $g(x,y)$, $g(a,x)$

In Figure 2, the matching can be aborted early in a lot of cases because of a
mismatch between variable substitutions. Therefore, only a total of 8 child
nodes are visited, corresponding to 8 calls to MatchOneToOne. For the order in
Figure 3, the match always fails only at the last pattern argument. Hence, the
matching cannot abort early and a total of 15 calls to MatchOneToOne need to
be made. This example illustrates, how iterative matching can lower the costs
of matching in some cases, because matching can abort early without fully
matching each subpattern. If independent matching of the subpatterns was
employed, the full search space as depicted in Figure 3 needs to be searched.
However, we do not propose to order the non-variable pattern arguments in a
special way, we just take advantage of the order if it already exists. In the
worst case, the whole search space still has to be explored.

##### Regular variables

For every regular variable $x\in\mathcal{X}_{0}$, if the the surrounding
function is not associative, every mapping of subject arguments onto the
variable needs to be checked. The multiplicities of the variable and of each
subject argument needs to be taken into account, i.e. only arguments from
$S_{x}:=\\{s\in S\mid\pi_{S}(s)\geq\pi_{P}(x)\\}$ are used to match the
variable $x$. For every substitution that is checked, the corresponding
subject arguments are removed from the subject set temporarily, i.e. we set
$\pi_{S}(s)\leftarrow\pi_{S}(s)-\pi_{P}(x)$. This process is applied
iteratively again for every regular variable shrinking the subject set at
every step. Each step also involves backtracking to the previous step after
completing the match to choose a different variable substitution for $x$ from
$S_{x}$. Again, each regular variable matching step is depending on the
previous one and needs to be repeated for every choice made in the previous
step.

To illustrate the issue with multiplicities, examine the pattern
$f_{c}(x,x,y^{*})$ and the subject $f_{c}(a,a,a,b,b,c)$. Only $a$ and $b$ are
candidates for the variable $x$, since there is only one $c$ but two
occurrences of $x$. Hence we have $S_{x}=\\{a,b\\}$ in this case. Assuming
that $a$ has been chosen as a substitution for $x$, we get an updated subject
set $\Lbag a,b,b,c\Rbag$ and proceed with matching $y^{*}$. After that is
completed, we backtrack and choose $b$ as a substitution obtaining the
remaining subject set $\Lbag a,a,a,c\Rbag$. After processing that, the
matching is finally done because there are no more choices left for $x$.

##### Sequence Variables

Sequence variables are the most expensive part of matching, as there can be
exponentially many combinations between subject arguments and sequence
variables. In general, there can be up to $n^{m}$ different matches given $n$
sequence variables and $m$ subject arguments. The algorithm for finding all
sequence variable matches is described in the next section.

####  subsection6.2 subsectionSequence Variables

To enumerate all distributions of subjects onto sequence variables without
duplicate results, the problem is modeled with several disjoint linear
diophantine equations. For every sequence variable $x$ and every symbol $a$,
we have a variable $x_{a}$ in the equations that determines how many $a$ are
contained in the solution multiset for $x$. Hence, each non-negative integer
solution to the equation system corresponds to a valid substitution for the
sequence variables.

As an example consider the multiset of remaining terms $\Lbag
a,b,b,c,c,c\Rbag$ and the variable multiset $\Lbag x^{*},y^{+},y^{+}\Rbag$.
This yields the following equations:

$\displaystyle 1$ $\displaystyle=x_{a}+2y_{a}$ $\displaystyle 2$
$\displaystyle=x_{b}+2y_{b}$ $\displaystyle 3$ $\displaystyle=x_{c}+2y_{c}$

We are looking for all non-negative solutions that satisfy the additional
constraint $y_{a}+y_{b}+y_{c}\geq 1$ (because $y^{+}$ is a plus variable).
Note that while these equations have infinitely many integer solutions, there
are only finitely many non-negative solutions. For the above example there are
three solutions:

$\displaystyle x_{a}$ $\displaystyle=1$ $\displaystyle\ \wedge\ $
$\displaystyle x_{b}$ $\displaystyle=2$ $\displaystyle\ \wedge\ $
$\displaystyle x_{c}$ $\displaystyle=1$ $\displaystyle\ \wedge\ $
$\displaystyle y_{a}$ $\displaystyle=0$ $\displaystyle\ \wedge\ $
$\displaystyle y_{b}$ $\displaystyle=0$ $\displaystyle\ \wedge\ $
$\displaystyle y_{c}$ $\displaystyle=1$ $\displaystyle x_{a}$
$\displaystyle=1$ $\displaystyle\ \wedge\ $ $\displaystyle x_{b}$
$\displaystyle=0$ $\displaystyle\ \wedge\ $ $\displaystyle x_{c}$
$\displaystyle=3$ $\displaystyle\ \wedge\ $ $\displaystyle y_{a}$
$\displaystyle=0$ $\displaystyle\ \wedge\ $ $\displaystyle y_{b}$
$\displaystyle=1$ $\displaystyle\ \wedge\ $ $\displaystyle y_{c}$
$\displaystyle=0$ $\displaystyle x_{a}$ $\displaystyle=1$ $\displaystyle\
\wedge\ $ $\displaystyle x_{b}$ $\displaystyle=0$ $\displaystyle\ \wedge\ $
$\displaystyle x_{c}$ $\displaystyle=1$ $\displaystyle\ \wedge\ $
$\displaystyle y_{a}$ $\displaystyle=0$ $\displaystyle\ \wedge\ $
$\displaystyle y_{b}$ $\displaystyle=1$ $\displaystyle\ \wedge\ $
$\displaystyle y_{c}$ $\displaystyle=1$

These correspond to the substitutions

$\displaystyle\sigma_{1}$ $\displaystyle=\\{x\mapsto\Lbag a,b,b,c\Rbag,$
$\displaystyle y\mapsto\Lbag c\Rbag\\}$ $\displaystyle\sigma_{2}$
$\displaystyle=\\{x\mapsto\Lbag a,c,c,c\Rbag,$ $\displaystyle y\mapsto\Lbag
b\Rbag\\}$ $\displaystyle\sigma_{3}$ $\displaystyle=\\{x\mapsto\Lbag
a,c\Rbag,$ $\displaystyle y\mapsto\Lbag b,c\Rbag\\}.$

Formally we define the set of equations as follows:

######  Definition 3.1 (Sequence Variable Equations).

Let $S$ and $V$ be the multisets of subject terms and variables respectively,
let $s_{1},\dots,s_{n}\in\mathcal{T}$ and
$x_{1},\dots,x_{m}\in\mathcal{X}_{*}\cup\mathcal{X}_{+}$ be the distinct
elements of $S$ and $V$ respectively, let $d_{i}:=\pi_{S}(s_{i})$ for
$i=1,\dots,n$, and let $c_{j}:=\pi_{V}(x_{j})$ for $j=1,\dots,m$. Then the
sequence variable equations for $S$ and $V$ are

$\begin{array}[]{ccccccc}d_{1}&=&c_{1}X_{1,1}&+&\dotsb&+&c_{m}X_{1,m}\\\
\vdots&&\vdots&&\ddots&&\vdots\\\
d_{n}&=&c_{1}X_{n,1}&+&\dotsb&+&c_{m}X_{n,m}\end{array}$

with variables $X_{i,j}$ for $i=1,\dots,n$ and $j=1,\dots,m$ and the
additional constraint

$\bigwedge_{j=1}^{m}\left(x_{j}\in\mathcal{X}_{+}\rightarrow\sum_{i=1}^{n}X_{i,j}\geq
1\right).$

Each solution $\alpha:X\rightarrow\mathbb{N}$ to these equations corresponds
to a substitution $\sigma_{\alpha}$ where
$\sigma_{\alpha}(x_{j})=M_{{}_{\alpha},j}$ for the smallest multiset
$M_{{}_{\alpha},j}$ with $\pi_{M_{{}_{\alpha},j}}(s_{i})=\alpha(X_{i,j})$ for
$i=1,\dots,n$ and $j=1,\dots,m$.

Extensive research has been done on solving linear diophantine equations and
linear diophantine equation systems [42, 43, 44, 45, 46]. Our equation system
is however not a real system, because the equations are disjoint and can be
solved independently. Also, since we are only interested in the non-negative
solutions, these solutions can be found more easily. We implemented an
algorithm that is an adaptation of the algorithm used in SymPy [47, in
sympy.solvers.diophantine]. The algorithm recursively reduces any linear
diophantine equation to equations of the form $ax+by=d$ that can be solved
efficiently with the Extended Euclidian algorithm [48, see 2.107]. Then the
solutions for those can be combined into a solution for the original equation.

In all practical applications that we have considered, both the multiplicities
of the variables and the multiplicities of terms in commutative patterns are
small. Hence, for a sequence variable equation $c_{1}x_{1}+\dots
c_{n}x_{n}=c$, all coefficients $c_{i}$ and $c$ are usually small.
Furthermore, the number $n$ of distinct sequence variables in a pattern is
also typically small. Hence, the number of solutions for these equations is
usually also small and we can cache the results instead of recomputing them
every time. The number of distinct cases can be reduced by sorting the
coefficients and hence the storage for the caching can be reduced. This makes
the time cost of enumerating all distributions of the terms onto the sequence
variables effectively linear per distribution.

For each sequence variable substitution that is enumerated by the above
method, the compatibility with the existing substitutions is checked and the
resulting union is yielded as are result if they are compatible.

##  chapter 4chapterMany-to-One Pattern Matching

For many problems there is a fixed set of patterns which are all matched
against different subjects repeatedly. While this can be solved by matching
each pattern separately there is room for optimization. In this chapter we
present data structures and algorithms to do many-to-one matching more
efficiently.

######  Definition 4.1 (Many-to-one Pattern Matching).

Many-to-one pattern matching is the process of matching a single subject
against multiple patterns simultaneously.

###  section7 sectionDiscrimination Net

For syntactic patterns, Discrimination Nets (DNs), also known as left-to-right
tree automata, have proven to be fast for many-to-one matching [24, 49, 50].
In this section we discuss existing kinds of DNs and propose extensions which
can match a wider set of patterns.

####  subsection7.1 subsectionSyntactic Discrimination Net

DNs are a specialized form of finite automata which can be either
deterministic or non-deterministic. A deterministic DN can match a subject of
size $n$ against all its patterns in $\mathcal{O}(n)$. However, its size can
potentially grow exponentially with the number of patterns. Non-deterministic
DNs take up smaller space ($\mathcal{O}(m)$ where $m$ is the sum of pattern
lengths), but also have a worst case runtime of $\mathcal{O}(m)$. We mostly
focus on deterministic DNs for syntactic matching, because for the cases that
we considered they offer the best performance.

[24] also proposed the use of a _flatterm_ representation instead of a tree
based one. This representation is based on the preorder traversal of the tree
and hence speeds up algorithms relying mostly on that. The flatterm
representation of a term is a word formed by the symbols as they are
encountered in preorder traversal of the tree structure, e.g. the flatterm for
$f(a,g(b,c))$ would be $f\,a\,g\,b\,c$. This notation as well as DNs in the
literature only support function symbols with fixed arity. In the
implementation, additional pointers are used to preserve some of the tree
structure while providing fast preorder traversal.

$g(a)$$a$$g$$f(g(a),y)$$f(x,b)$$b$$f(g(a),b)$$f(x,b)$$f(g(a),y)$$\omega$$a$$g$$f(x,b)$$b$$\omega$$f$
Figure 4: Example of a Discrimination Net

Usually, the patterns are treated as if they were linear, i.e. variable
symbols are all treated the same and replaced with $\omega$ which acts as a
general placeholder. Therefore, in case of non-linear patterns, the
equivalence of variable replacements has to be checked in an extra step.
Figure 4 gives an example of a DN for the pattern set
$\\{f(g(a),b),\allowbreak f(x,b),f(g(a),y),g(a)\\}$. The leafs of the DN are
labeled with the matched patterns. Matching is done by interpreting the tree
as an automaton and run it on the flatterm representation of the subject. The
initial state is the root of the tree and the leafs are the final states. An
$\omega$ transition covers all symbols for which there is no other outgoing
transition yet. Note that an $\omega$ transition skips the whole subterm if a
function symbol is read. If the automaton accepts, its final state determines
the set of matching patterns. Otherwise, none of the patterns match.

The construction of a deterministic DN is straight-forward and can be done by
using product automaton construction. For every pattern $p=s_{1}\dots s_{n}$
in flatterm form we construct a simple linear net like in Figure 5. These can
be combined with standard DFA product construction while merging the pattern
sets of each state. Other (incremental) construction methods are described in
[24, 49, 50]. While theoretically the resulting DN can have exponentially many
nodes444Consider the pattern set
$P_{n}:=\\{\,f(x_{1},\dots,x_{i-1},a,x_{i+1},\dots,x_{n})\mid 1\leq i\leq n\
\,\\}$ which contains $n$ patterns and results in $2^{n}$ distinct leaf nodes
as all patterns can match independently of each other., for many practical
pattern sets this does not pose a problem (for an example, see Figure 17).

$q_{0}$$q_{1}$$q_{n-1}$$q_{n}$$p$$s_{n}$$s_{1}$ Figure 5: Discrimination Net
for a Single Pattern

However, we cannot use this DN to match variadic functions as it cannot
distinguish between different terms having the same flatterm representation.
Consider the previous example but now $f$ and $g$ are variadic function
symbols. Because e.g. $f(g(a),b)$ and $f(g(a,b))$ have the same flatterm
representation $f\,g\,a\,b$, they are treated the same by the DN. In the
following section, a generalized version of the DN which supports variadic
function symbols.

####  subsection7.2 subsectionVariadic Syntactic Discrimination Net

In order to use variadic function symbols with DNs, we include a special
symbol “$\rangle$” denoting the end of a compound term in the preorder
traversal. We add this symbol as the last argument to every compound term,
e.g. $f(a,g(b),c)$ is transformed to $f(a,g(b,\rangle),c,\rangle)$ resp.
$f\,a\,g\,b\,\rangle\,c\,\rangle$ as a flatterm instead.

######  Definition 4.2 (Variadic Syntactic Discrimination Net).

A Varidic Syntactic Discrimination Net (VSDN) $\mathfrak{D}$ is defined
similar to a DFA as $\mathfrak{D}=(Q,\Sigma,\delta,q_{0},F)$ where

  * •

$Q$ is a finite set of states,

  * •

$\Sigma=\mathcal{F}\cup\\{\rangle\\}$ is the finite alphabet,

  * •

$\delta:Q\times\Sigma\rightarrow Q\times\\{0,1\\}$ is the transition function
where the second result component is $1$ iff an $\omega$ transition was used,

  * •

$q_{0}\in Q$ is the initial state, and

  * •

$F:Q\rightarrow 2^{\mathcal{T}(\mathcal{F},\mathcal{X})}$ which maps each
(leaf) state to a set of patterns it covers.

A _run_ of $\mathfrak{D}$ on a term $t$ is a sequence of states with positions
$\rho=(q_{1},\nu_{1})\dots(q_{n},\nu_{n})$ such that for every $i=2,\dots,n$
we have either

  * •

$\delta(q_{i-1},h)=(q_{i},0)$ where $h=head(t|_{\nu_{i-1}})$ and
$\nu_{i}=next(t,\nu_{i-1})$, or

  * •

$\delta(q_{i-1},h)=(q_{i},1)$ and $\nu_{i}=skip(t,\nu_{i-1})$.

A pattern $p$ _matches_ a subject $s$ in $\mathfrak{D}$ iff there exists a run
$\rho=(q_{0},\epsilon)\dots(q_{n-1},\nu_{n-1})\allowbreak(q_{n},\top)$ on $s$
where $q_{0}$ is the initial state, $\nu_{i}\in\mathcal{P}os(p)$ for
$i=0,\dots,n-1$, and $p\in F(q_{n})$.

In Figure 6, a VSDN net for the pattern set $\\{f(a,x),f(a),\allowbreak
f(y,b)\\}$ is shown. Note that $f$ is a variadic function symbol here and we
added a “$\langle$” to function symbols to distinguish them from constant
symbols.

$f(a)$$\rangle$$f(a,x)$$f(y,b)$$\rangle$$b$$f(a,x)$$\rangle$$\omega$$a$$f(y,b)$$\rangle$$b$$\omega$$f\langle$
Figure 6: Example of a Variadic Syntactic Discrimination Net

The VSDN could be extended to support sequence variables as well by adding
$\omega$-loops to states. By interpreting the VSDN as a NFA, one can use
$\epsilon$-transitions and use powerset construction to get a minimal VSDN for
a pattern with sequence variables. These individual VSDNs can be combined
using product construction.

Nonetheless, experiment with sequence variables have shown to increase the
size of the VSDN beyond the point where it is beneficial (see Figure 17). A
non-deterministic approach is more suitable to deal with sequence variables
and associativity. In the next section, such an approach is discussed.

####  subsection7.3 subsectionAssociative Discrimination Net

In this section we propose a new type of non-deterministic discrimination net
that supports sequence variables and associative function symbols. We can
later use multiple layers of this Associative Discrimination Net (ADN) to
perform commutative matching as well. Furthermore, in contrast to most
existing work, non-linear patterns are handled by the ADN itself, because that
enables earlier backtracking when a variable mismatch occurs.

######  Definition 4.3 (Associative Discrimination Net).

An ADN $\mathfrak{A}$ is a non-deterministic extension of a VSDN which is
defined as $\mathfrak{A}=(Q,\Sigma,\delta,q_{0},F)$ where

  * •

$Q$ is a finite set of states,

  * •

$\Sigma=\mathcal{F}\cup\mathcal{X}\cup\\{\rangle\\}$ is the finite alphabet,

  * •

$\delta\subseteq Q\times\Sigma\times Q$,

  * •

$q_{0}\in Q$ is the initial state, and

  * •

$F:Q\rightarrow\mathcal{T}(\mathcal{F},\mathcal{X})\cup\\{\emptyset\\}$ which
maps each (leaf) state to the patterns it accepts.

A _run_ of $\mathfrak{A}$ on a term $t$ is a sequence of states with positions
and substitutions
$\rho=(q_{1},\nu_{1},\sigma_{1})\dots(q_{n},\nu_{n},\sigma_{n})$ such that for
every $i=2,\dots,n$ we have that $\sigma_{i-1}\triangle\sigma^{\prime}_{i}$,
$\sigma_{i}=\sigma_{i-1}\sqcup\sigma^{\prime}_{i}$, and either

  * •

$(q_{i-1},h,q_{i})\in\delta$ where $h=head(t|_{\nu_{i-1}})$,
$\nu_{i}=next(t,\nu_{i-1})$ and $\sigma^{\prime}_{i}:=\emptyset$, or

  * •

$(q_{i-1},x,q_{i})\in\delta$ for some $x\in\mathcal{X}$,
$\nu_{i}=skip(t,\nu_{i-1})$ and $\sigma^{\prime}_{i}=\\{x\mapsto
t|_{\nu_{i-1}}\\}$, or

  * •

$(q_{i-1},x,q_{i})\in\delta$ for some $x\in\mathcal{X}_{*}$,
$\nu_{i}=\nu_{i-1}$ and $\sigma^{\prime}_{i}=\\{x\mapsto\epsilon\\}$, or

  * •

$(q_{i-1},x,q_{i})\in\delta$ for some
$x\in\mathcal{X}_{+}\cup\mathcal{X}_{*}$,
$\nu_{i-1}=\nu_{p}k<\nu_{p}j\in\mathcal{P}os(t)$ for some
$\nu_{p}\in\mathcal{P}os(t)$ and $k,j\in\mathbb{N}$,
$skip(t,\nu_{p}j)=\nu_{i}$ and
$\sigma^{\prime}_{i}=\\{x\mapsto(t|_{\nu_{p}k},\dots,t|_{\nu_{p}j})\\}$, or

  * •

$(q_{i-1},x,q_{i})\in\delta$ for some $x\in\mathcal{X}_{0}$,
$\nu_{i-1}=\nu_{p}k<\nu_{p}j\in\mathcal{P}os(t)$ for some
$\nu_{p}\in\mathcal{P}os(t)$ and $k,j\in\mathbb{N}$, $f=head(t|_{\nu_{p}})$ is
associative, $skip(t,\nu_{p}j)=\nu_{i}$ and $\sigma^{\prime}_{i}=\\{x\mapsto
f(t|_{\nu_{p}k},\dots,t|_{\nu_{p}j})\\}$.

A pattern $p$ _matches_ a subject $s$ with a substitution $\sigma$ in
$\mathfrak{A}$ iff there exists a run
$\rho=(q_{0},\epsilon,\emptyset)\dots(q_{n-1},\nu_{n-1},\sigma_{n})(q_{n},\top,\sigma)$
on $s$ where $q_{0}$ is the initial state, $\nu_{i}\in\mathcal{P}os(p)$ for
$i=0,\dots,n-1$, and $p=F(q_{n})$.

Furthermore, to support guards directly attached to subterms, we can extend
the definition of a run: In addition to allowing a transition
$(q_{i-1},s,q_{i})\in\delta$ for some $s$, we we also allow $(q_{i-1},s\
\mathbf{if}\ \varphi,q_{i})\in\delta$ for some $s$ and $\varphi$. For those
guarded transitions it is required that $\varphi(\sigma_{i})=true$ for them to
be included in a valid run.

0123$f(a)$$\rangle$45$f(a,x^{*})$$\rangle$$x^{*}$$a$678$f(y,b)$$\rangle$$b$$y$$f\langle$
Figure 7: Example of an Associative Discrimination Net

Figure 7 shows the same example as Figure 6, but as non-deterministic version
with non-linear variables. Given the subject $f(a,b)$, both $f(a,x^{*})$ and
$f(y,b)$ match. For $f(a,x^{*})$ we get the run

$(0,\epsilon,\emptyset)(1,1,\emptyset)(2,2,\emptyset)(4,3,\sigma_{1})(5,\top,\sigma_{1})$

with $\sigma_{1}=\\{x^{*}\mapsto(b)\\}$. For $f(y,b)$ we have the run

$(0,\epsilon,\emptyset)(1,1,\emptyset)(6,2,\sigma_{2})(7,3,\sigma_{2})(8,\top,\sigma_{2})$

with $\sigma_{2}=\\{y\mapsto a\\}$. When only syntactic pattern are used, the
ADN specializes to a non-deterministic VSDN. The advantage of the ADN emerges
when patterns share some common structure and contain sequence variables, as
the non-deterministic partitioning of terms among sequence variables needs
only be done once. Because the partitioning is the most expensive part of the
(non-commutative) matching, this improves the efficiency of the matching. In
the worst case matching with an ADN is equivalent to one-to-one matching,
because the decision branches in Algorithm 2 and Algorithm 3 map directly to
the structure of the ADN.

Algorithm 1 Adding a pattern to an ADN

1 Discrimination net $\mathfrak{A}=(Q,\Sigma,\delta,q_{0},F)$ and pattern in
flatterm representation $p=s_{1}\dots s_{n}$ with $s_{i}\in\Sigma$ for
$i=1,\dots,n$.

2 function addPattern($\mathfrak{A},p$)

3  $q$ $\leftarrow$ $q_{0}$

4  for all $i\in 1,\dots,n$ do

5  if $\exists q^{\prime}\in Q:(q,s_{i},q^{\prime})\in\delta$ then

6  $q$ $\leftarrow$ $q^{\prime}$

7  else

8  Create new state $q^{\prime}$

9  $Q$ $\leftarrow$ $Q\cup\\{q^{\prime}\\}$

10  $\delta$ $\leftarrow$ $\delta\cup\\{(q,s_{i},q^{\prime})\\}$

11  $q$ $\leftarrow$ $q^{\prime}$

12  $F$ $\leftarrow$ $F[q\mapsto F(q)\cup\\{p\\}]$

Algorithm 2 Matching with an ADN

1 Discrimination net $\mathfrak{A}=(Q,\Sigma,\delta,q_{0},F)$, subject
$s\in\mathcal{T}$, a state $q\in Q$, a position $\nu\in\mathcal{P}os(s)$ and a
substitution $\sigma\in\mathcal{S}ub$.

2 function ADNMatch($\mathfrak{A},s,q,\nu,\sigma$)

3  if $\nu=\top$ then return $\\{(F(q),\sigma)\\}$

4  else

5  $m$ $\leftarrow$ $\emptyset$

6  $h$ $\leftarrow$ $head(s|_{\nu})$

7  $\triangleright$ Symbol transition

8  if $\exists q^{\prime}\in Q,\exists\varphi:(q,h\ \mathbf{if}\
\varphi,q^{\prime})\in\delta$ and $\varphi(\sigma)=true$ then

9  $m$ $\leftarrow$
$m\cup\textsc{ADNMatch}(\mathfrak{A},s,q^{\prime},next(s,\nu),\sigma)$

10  for all $(q,x\ \mathbf{if}\ \varphi,q^{\prime})\in\delta$ for some
$x\in\mathcal{X}$, $q^{\prime}\in Q$ and $\varphi$ do

11  $\triangleright$ Variable transition matching a single term

12  if $\sigma\triangle\\{x\mapsto s|_{\nu}\\}$ and $\varphi(\sigma)=true$
then

13  $m$ $\leftarrow$
$m\cup\textsc{ADNMatch}(\mathfrak{A},s,q^{\prime},skip(s,\nu),\sigma\sqcup\\{x\mapsto
s|_{\nu}\\})$

14  $\triangleright$ Star variable transition matching empty sequence

15  if $x\in\mathcal{X}_{*}$ and $\sigma\triangle\\{x\mapsto\epsilon\\}$ and
$\varphi(\sigma)=true$ then

16  $m$ $\leftarrow$
$m\cup\textsc{ADNMatch}(\mathfrak{A},s,q^{\prime},\nu,\sigma\sqcup\\{x\mapsto\epsilon\\})$

17  if $\nu=\nu_{p}k$ for some $\nu_{p}\in Pos(s)$ and $k\in\mathbb{N}$ then

18  $\triangleright$ Parent term has position $\nu_{p}$ and current term is
argument no. $k$

19  $f$ $\leftarrow$ $head(s|_{\nu_{p}})$

20  if $x\in\mathcal{X}_{+}\cup\mathcal{X}_{*}$ or $f$ is associative then

21  $j$ $\leftarrow$ $\operatorname*{\arg\\!\max}_{j\in\mathbb{N}}\nu_{p}j\in
Pos(s)$ $\triangleright$ $j$ is no. of last argument

22  for all $i=k+1\dots j$ do

23  $t$ $\leftarrow$ $(s|_{\nu_{p}k},\dots,s|_{\nu_{p}i})$

24  if $x\in\mathcal{X}_{0}$ and $f$ is associative then

25  $t$ $\leftarrow$ $f(t)$ $\triangleright$ Wrap regular variable in assoc.
function

26  $\triangleright$ Sequence variable transition matching

27  if $\sigma\triangle\\{x\mapsto t\\}$ and $\varphi(\sigma)=true$ then

28  $m$ $\leftarrow$
$m\cup\textsc{ADNMatch}(\mathfrak{A},s,q^{\prime},skip(s,\nu_{p}i),\sigma\sqcup\\{x\mapsto
t\\})$

29  return $m$

The construction of the ADN can be done by iteratively adding new patterns to
it starting from the initial state as outlined in Algorithm 1. In order to
maximize the potential similarity between patterns, their variables can be
renamed to a position-based canonical schema. We replace every variable $x$
with a name based on its first occurrence in $t$, i.e. replace $x$ with a new
variable $x_{p_{1}(x)}$ for every $x\in\mathcal{V}ar(t)$ where

$p_{1}(x):=\min\\{p\in\mathcal{P}os(t)\mid t|_{p}=x\\}.$

As an example, $f(x,y,g(z))$ would become $f(x_{1},x_{2},g(x_{3\,1}))$. This
way, terms with similar structure but differently named variables can still be
combined in the discrimination net. Note that this does not change that
regular and sequence variables still need to be handled differently. While
$f(x)$ and $f(y)$ are treated as equivalent by the ADN, $f(x^{+})$ has
different transitions and a distinct final state from the other two. After a
match is found, the renaming of the variables is reverted to obtain the
correct substitution.

The matching with an ADN is done be trying all possible runs with
backtracking. For simplicity, the pseudo code for the algorithm assumes that
every subterm has a guard. If a term does not have a guard, we replace it with
the equivalent term that has a $true$ guard, e.g. $f(x,a)$ would become $f(x\
\mathbf{if}\ true,a\ \mathbf{if}\ true)\ \mathbf{if}\ true$. This reduces the
number of cases that need to be distinguished for the pseudo code, but in an
implementation guards can easily be separated. In Algorithm 2, the pseudo code
for a many-to-one match function is listed. It yields the set of all matching
pairs of patterns and substitutions, i.e.
$\textsc{ADNMatch}(\mathfrak{A},s,q_{0},\epsilon,\emptyset)$ yields all
matches for a subject $s$.

###  section8 sectionMany-to-one Matcher

In order to use the ADN for patterns with commutative function symbols as
well, we handle them in a separate step. For that we add a special state for
every commutative subpattern of a pattern and use another ADN to match its
children. Finally, we find matches for the whole commutative subpattern by
finding maximum matchings in a bipartite graph constructed from the matches
for the subject’s subterms in the ADN. This is similar to the approach of the
AC discrimination nets described in [21], but we perform the full non-linear
matching directly at a commutative symbol state instead of just using it as a
filter.

####  subsection8.1 subsectionMultilayer Discrimination Net

5$a$$a$4$h(a)$$\rangle$$a$3$h(b)$$\rangle$$b$2$h(x)$$\rangle$$x$$h\langle$1$x$$x$$f(g_{c}(a,x,x))$$\rangle$$\Lbag
1,1,5\Rbag$$f(g_{c}(a,h(x),$$h(a)))$$\rangle$$\Lbag
2,4,5\Rbag$$f(g_{c}(h(b),$$h(x)))$$\rangle$$\Lbag 2,3\Rbag$$g_{c}$$f\langle$
Figure 8: Example of a Multilayer Discrimination Net

In Figure 8, a Multilayer Discrimination Net (MLDN) for the pattern set

$\\{f(g_{c}(a,x,x)),\allowbreak f(g_{c}(a,h(x),h(a))),f(g_{c}(h(b),h(x)))\\}$

is shown. For the $g_{c}$ compound term, a special state containing another
ADN is added. The outgoing transitions from that state are labeled with a
_requirement multiset_ that defines which subpatterns are required to match in
order for the whole $g_{c}$ term to match. These sets are later used to
construct bipartite graphs to find all valid matches.

As an example, consider the subject $f(g_{c}(a,h(a),h(a)))$. $a$ and $h(a)$
are both run through the inner ADN. $a$ matches both $a$ and $x$ (with a
_match set_ $\\{1,5\\}$). $h(a)$ matches $x$, $h(x)$, and $h(a)$ (with a match
set $\\{1,2,4\\}$).

To exclude patterns which cannot match from further processing, we check
multiset union of the match sets against each requirement multiset. The
multiplicity of each subpattern is used when building the multiset union. In
the above example the multiset union would be

$P:=\\{1,5\\}\uplus\\{1,2,4\\}\uplus\\{1,2,4\\}=\Lbag 1,1,1,2,2,4,4,5\Rbag.$

Note that the match set for $h(a)$ is included two times since the term
appears two times in the subject. Hence, $f(g_{c}(h(b),h(x)))$ cannot match
the subject, because $\Lbag 2,3\Rbag\not\subseteq P$. For the other two
patterns, we have both $\Lbag 1,1,5\Rbag\subseteq P$ and $\Lbag
2,4,5\Rbag\subseteq P$ so both could match and need to be processed further.

To show that this check is not sufficient for determining whether a pattern
matches consider the subject $f(g_{c}(a,a,h(a)))$ with its multiset union
$P^{\prime}=\Lbag 1,1,1,2,\allowbreak 4,5,5\Rbag$. Despite $\Lbag
1,1,5\Rbag\subseteq P$, there is no match for $f(g_{c}(a,x,x))$ because
$\\{x\mapsto a\\}$ and $\\{x\mapsto h(a)\\}$ are not compatible. Similarly,
even though $\Lbag 2,4,5\Rbag\subseteq P$, there is no match for
$f(g_{c}(a,h(x),h(a)))$ because multiple both $h(x)$ and $h(a)$ would have to
be covered by the single term $h(a)$.

Therefore, confirming if one of the patterns actually matches requires a more
involved check. This is solved by constructing bipartite graphs from the match
sets and finding maximum bipartite matchings. However, the filtering step
described above can reduce the number of more expensive bipartite matching
problems that need to be solved.

####  subsection8.2 subsectionBipartite Graphs

We construct a bipartite graph where one set of nodes contains the distinct
subpatterns and the other one consists of the distinct terms of the subject.
Then the matches found by running the terms through the ADN induce the edges,
i.e. a subpattern node and a term node are connected by an edge iff the
subpattern matches the term. We label the edge with the set of match
substitutions. The resulting bipartite graph for the previous example with
subject $f(g_{c}(a,h(a),h(a)))$ is shown in Figure 9.

$a$$x$$h(a)$$h(x)$$a$$h(a)$PatternsSubjects$x\mapsto a$$x\mapsto
h(a)$$\emptyset$$\emptyset$$x\mapsto a$ Figure 9: Full Bipartite Graph

For matching the whole commutative pattern we use the subgraph induced by only
including the nodes of this particular pattern’s subpatterns. Furthermore, for
terms in the patterns or subject which occur multiple times, we need to
duplicate the corresponding nodes, e.g. for the above subject example the
$h(a)$ node would need to be duplicated in the graph that is used to find the
maximum matchings.

$x$1$x$2$a$3$h(a)$1$h(a)$2$a$3PatternsSubjects1234567 Figure 10: Induced
Bipartite Graph

In Figure 10 the induced graph for the pattern $f(g_{c}(a,x,x))$ and the
subject $f(g_{c}(a,\allowbreak h(a),h(a)))$ is shown. The substitutions on the
edges have been left out here for readability, but they are the same as in the
original graph. Instead we have labeled every edge with a number for later
reference. All nodes are also labeled with consecutive natural numbers to
distinguish duplicated nodes. Note that patterns and subject are counted
separately. The problem of finding all matches for a commutative pattern and
subject can be reduced to finding all maximum matchings in the induced
bipartite graph and checking that the substitutions of the matching edges are
compatible. The union of the matching edge substitutions then yields a valid
match for the whole commutative term.

However, because we duplicated some nodes, we have some redundant matchings
that result in the same substitution. Here we can use the additional number
labels on the nodes to define a canonical maximum matching for every distinct
match and disregard non-canonical maximum matchings:

######  Definition 4.4 (Canonical Matching).

Let $P$ be a set of patterns and $S$ be a set of subjects. A matching
$M\subseteq E$ on an induced bipartite graph $B$ with (directed) edge set
$E\subseteq(P\times\mathbb{N})\times(S\times\mathbb{N})$ over $P$ and $S$ is
canonical iff $\forall(p,n_{p},s,n_{s})\in
M,\forall(p^{\prime},n_{p}^{\prime},s^{\prime},n_{s}^{\prime})\in
M:(s=s^{\prime}\wedge n_{p}>n_{p}^{\prime})\implies n_{s}>n_{s}^{\prime}$.

For example, in Figure 10, the edges $1,4,7$ form a canonical maximum matching
while $2,3,7$ do not. All other matchings are not maximal, so this matching
yields the only match with $\sigma=\\{x\mapsto h(a)\\}$. For finding the first
maximal matching we use the Hopcroft-Karp algorithm [51], but any algorithm
for finding a maximum matching can be used. This initial matching can be found
in $\mathcal{O}(m\sqrt{n})$ where $n$ is the number of nodes and $m$ the
number of edges in the bipartite graph. Once an initial maximum matching has
been found, we can apply the algorithm described by Uno, Fukuda and Matsui in
[52, 53] to enumerate all maximum matchings. Each successive matching can be
found in $\mathcal{O}(n)$ so in total we have a time complexity of
$\mathcal{O}(m\sqrt{n}+N_{m}n)$ where $N_{m}$ is the number of matchings. For
every matching the compatibility and every combination of substitutions in the
matching the compatibility needs to be checked and, if successful, a union
substitution is created.

####  subsection8.3 subsectionSequence Variables

So far, we have only considered commutative patterns without sequence
variables. In this case, every maximum matching is also a perfect matching,
because the number of subterms in both pattern and subject must be exactly the
same in order for a match to exist. When we introduce sequence variables into
a commutative pattern, this constraint is loosened and we only need at least
as many subterms in the subject as we have non-sequence-variable terms in the
pattern. The remaining subject terms are distributed among the sequence
variables.

Consider the pattern $f(g_{c}(a,x,x,y^{*}))$, which is one of the previous
examples except for an additional sequence variable $y^{*}$. However, now it
matches the subject $f(g_{c}(a,a,a,h(a),h(a)))$, e.g. with $\\{x\mapsto
h(a),y^{*}\mapsto\Lbag a,a\Rbag\\}$. For that purpose, once a maximum matching
in the bipartite graph is found, the remaining unmatched terms are distributed
among the sequence variables. If the resulting substitution is compatible with
the one from the matching, the union of the substitutions yields a valid
match. For finding the sequence variable matches, the algorithm discussed in
section 6.2 is used.

##  chapter 5chapterExperimental Results

This chapter contains a brief introduction of our implementation of the
previously described algorithms as well as a description of our experiments.
Finally, the results of those experiments are given and discussed.

###  section9 sectionPython Implementation

We have implemented the matching algorithms described in the previous chapters
in Python. The code is open source and licensed under the MIT license. It is
hosted on Github555https://github.com/HPAC/matchpy. It has also been made
available as the PyPI package MatchPy666https://pypi.python.org/pypi/matchpy
for easy installation for anyone who wants to use it in their Python code. The
documentation for the code can be found on
ReadTheDocs777https://matchpy.readthedocs.io/.

The choice to use Python as a language had two main reasons. The first is
simply that the application in which the pattern matching was going to be used
was written in Python. The second reason is a powerful language construct in
Python called generators. Generators make writing code with backtracking
easier.

Python does have a disadvantage in terms of speed compared to other languages
though: Typically, python programs are one or two magnitudes slower than
programs written in languages such as C or C++ [54]. Still, the simpler
implementation and easier integration outweighed the performance loss for us.

####  subsection9.1 subsectionGenerators

Generators are an extension of the iterator concept which a lot of languages
support. Usually, an iterator is an object that enables a user to loop over a
set of values yielded from it. This is often used to traverse data structures
or to programmatically create sequences of values. The programmer has to
manage the state of the iterator object to be able to return the correct next
value upon request.

In Python, generators are special functions or methods, that use the yield
keyword instead of a regular return. Instead of just returning a value to the
caller, the state of the generator function is saved and the execution can
resume from the same state once the caller is done processing the yielded
value. This way, multiple values can be “returned” iteratively with additional
processing in between. The main difference compared to iterators in other
languages is the management of state. In Python, the state of the generator
function is managed automatically between yields. In contrast, regular
iterators require manual state management by the programmer.

In addition, there is the yield from keyword in Python that allows passing all
values yielded by another generator on to the caller. This enabled us to
implement the algorithms described previously in a way that yields the matches
one by one. Therefore, not every match has to be enumerated if the consumer of
the matches decides that no further matches are needed. Generators also
encapsulate the state of each submatching step and make backtracking to the
last choice point in the exploration of the match search space easier.

Another advantage of generators is their lazy evaluation, i.e. the next match
is only computed if it is needed. Lazy AC pattern matching has previously been
discussed by Belkhir [55].

####  subsection9.2 subsectionTerms

Terms are represented by classes that reflect the tree structure. For each
function symbol in the problem domain, a subclass needs to be created. The
class structure allows to store additional information specific to the problem
domain along with the terms. An example for this would be matrix dimensions in
the linear algebra domain.

In addition, we separate two distinct ideas which so far were united in the
concept a variable. First, we allow to give a name to any subpattern and
capture whatever it matches in the match substitution. Secondly, the ability
to match anything is implemented in so called _wildcards_. A regular wildcard
can match any term and a sequence wildcard can match a sequence of terms. A
named wildcard is equivalent to a variable. However, unnamed wildcards
function as anonymous variables, i.e. their values are not captured in the
substitution. Assigning a variable name to terms other than a wildcard is
mostly a convenience feature that allows easier access to complex matched
terms from the substitution.

Furthermore, in some domains, symbols belong to disjoint classes. As an
example, in the domain of linear algebra, symbols can either be matrices,
vectors, and scalars. Since these need to be distinguished by patterns
frequently, we decided to make this kind of type constraint a first-class
feature of the pattern matching: Users can create symbol subclasses and use
special _symbol wildcards_ to match only symbols of that type.

We always represent terms in their canonical form as described in sections 2.2
and 2.3. Hence, term arguments are flattened and sorted on creation if
necessary.

####  subsection9.3 subsectionConstraints

Patterns can have any number of additional constraints imposed on them. Users
can create their own constraint subclasses or use anonymous functions as
constraints. Constraints can either be global, i.e. they are only applied
after the whole matching is completed, or they can be local. Local constraints
must define the set of variables upon which they depend, so that they can be
evaluated once all those variables have been assigned a substitution during
the matching. This enables early backtracking in case the constraint fails
while freeing the user from having to decide when to evaluate a constraint
themselves. Local constraints are only evaluated once, unless a substitution
for one of their dependency variables changes.

###  section10 sectionExample Problems

We carried out experiments to compare the performance of one-to-one and many-
to-one pattern matching. For those experiments, we used two example problems
from two different domains. The first problem is finding subexpressions of
linear algebra expressions that match a kernel, i.e. a library function which
can compute the result of the subexpression efficiently. The second problem is
based on Abstract Syntax Trees (ASTs) of Python source code. It adapts a set
of patterns used in the Python tool 2to3 which is a tool used to translate
Python source code from version 2 to 3. This translation is necessary, because
there were significant changes between those versions making them source-
incompatible. In the following sections, those problems and their respective
patterns are discussed.

####  subsection10.1 subsectionLinear Algebra

The terms of the linear algebra problem consist of the function symbols shown
in Table 1. Constant symbols can either be scalars, vectors or matrices. In
addition, matrices may have properties like being square, diagonal,
triangular, etc. While matrices and vectors have associated dimension
information, it is not relevant for the pattern matching.

Operation | Symbol | Arity | Properties
---|---|---|---
Multiplication | $\times$ | variadic | associative
Addition | $+$ | variadic | associative, commutative
Transposition | T | unary |
Inversion | -1 | unary |
Inversion and Transposition | -T | unary |
Table 1: Operations for LinAlg

As an example for a pattern, consider

$\alpha\times A\times B+\beta\times C$

which describes an expression that can be computed using the dgemm routine in
the Basic Linear Algebra Subprograms [56, 57, 58] (BLAS). Here, $\alpha$ and
$\beta$ are scalar variables and $A$, $B$, and $C$ are matrix variables
without special property requirements. Similarly, the pattern

$A^{T}\times B\mbox{ {if} A is square and upper triangular}$

can be computed by with the dtrmm BLAS routine. To allow these pattern to
match any part of a sum or product, respectively, we add sequence variables
capturing the rest of the subject term:

$\alpha\times A\times B+\beta\times C+c^{*}$ $c_{1}^{*}\times A^{T}\times
B\times c_{2}^{*}\mbox{ {if} A is square and upper triangular}$

We call these added variables context variables.

For the experiments, a total of 199 distinct patterns similar to the ones
above were used. Out of those, 61 have an addition as outermost operation, 135
are patterns for products, and 3 are patterns for single matrices. A lot of
these patterns only differ in terms of constraints, e.g. there are 10 distinct
patterns matching $A\times B$ with different constraints on the two matrices.
Without the context variables, the product patterns are syntactic except for
the associativity of the multiplication. Because those patterns only contain
symbol variables, the associativity does not influence the matching and we can
consider them to be syntactic. In the following, we refer to the set of
patterns with context variables as LinAlg and the set of syntactic product
patterns as Syntactic.

For subjects, we used randomly generated terms with a specific number of
operands. For products, each operand has a probability to either be a scalar
(${\sim}16.67\%$), vector (${\sim}27.78\%$) or matrix (${\sim}55.55\%$).
Vectors have a $40\%$ probability of being transposed, while matrices have a
$60\%$ probability to be either transposed, inverted or both. The matrices
also have random properties, i.e. they can be square, diagonal, triangular,
and symmetric. Note that some of the properties imply or exclude each other,
e.g. every diagonal matrix is also triangular. Hence, only valid property
combinations were included in the experiments.

####  subsection10.2 subsectionAbstract Syntax Trees

The lib2to3 module in python contains “fixers” that can translate some aspect
of Python 2 code to Python 3 code. These fixers utilize patterns to discover
their targets in the AST. Figure 11 shows an example of such a pattern as it
is defined in the custom language lib2to3 uses to express patterns. In that
language, quoted strings denote atomic symbols, names with angle brackets
correspond to function symbols, any is a wildcard and variable names can be
assigned with an equal sign. The example pattern in Figure 11 matches a call
to the builtin function isinstance with a tuple as second argument. The fixer
is used to clean up after other fixers, e.g. to simplify isinstance(x, (int,
int)) to isinstance(x, int).

⬇

power<

’isinstance’

trailer< ’(’ arglist< any ’,’ atom< ’(’

args=testlist_gexp< any+ >

’)’ > > ’)’ >

>

Figure 11: Pattern for isinstance with a tuple of types

To represent this pattern in our notation, we have to define the function
symbols $power,trailer,arglist,atom,testlist\\_gexp\in\mathcal{F}$. Also, the
constant symbols $s_{l},s_{r},s_{c},isinstance\in\mathcal{F}_{0}$ are used to
represent left parenthesis, right parenthesis, command and isinstance,
respectively. Finally, the variables $x\in\mathcal{X}_{0}$ and
$y^{+}\in\mathcal{X}_{+}$ are used. The converted pattern for the above
example then becomes

$power(isinstance,trailer(s_{l},arglist(x,s_{c},atom(s_{l},testlist\\_gexp(y^{+}),s_{r})),s_{r})).$

The variables were renamed, but their names are not important for the
experiments.

The original patterns support some features thesis not covered in this thesis,
i.e. features similar to Mathematica’s Repeated and Alternatives (see section
3.1). Therefore, some of the patterns could not be implemented in our pattern
matching framework. For patterns with alternative subpatterns, a separate
pattern for every alternative was generated. From the original 46 patterns, 36
could be converted. Because of the heavy usage of nested alternatives, a total
of 1223 patterns without alternatives were generated.

Some features of our pattern matcher like commutative function symbols are not
used in these patterns. Nonetheless, the first-class support for symbol types
is useful here. AST symbols can have different types, e.g. names, string
literals, number literals or interpunctuation. Hence, symbol wildcards are
used to distinguish between them.

For subjects, we used 613 examples extracted from the unit tests for the
lib2to3 fixers. We concatenated all these example codes into a single file and
parsed the AST from it. Then each subexpression in that tree is used as a
subject.

The goal of our experiments on this problem is not to perform better than the
existing problem specific implementation in lib2to3, but to show that pattern
matching can be adapted to different domains and to evaluate whether many-to-
one matching is beneficial in those cases as well. We did not compare the
speed of our pattern matching and the pattern matching as implemented in
lib2to3, since the features of both are too different for a meaningful
comparison. We will refer to this problem as AST.

###  section11 sectionComparisons

This section compares the performance of various matching algorithms on the
problems described in the previous section. First, we compare one-to-one match
and many-to-one matching. Then, the performance of discrimination nets vs.
many-to-one matching on syntactic patterns is compared. Finally, we evaluate
whether Mathematica contains any optimization for many-to-one matching.

All experiment were executed on an Intel Core i5-2500K 3.3 GHz CPU with 8GB of
RAM. Since the algorithms are not parallelized, only one core was used per
experiment. Nonetheless, multiple experiments were run in parallel on the same
machine. The experiments focus on the relative performance of the algorithms
rather than absolute performance.

####  subsection11.1 subsectionOne-to-One vs. Many-to-One

In the first series of experiments, the one-to-one matching algorithm was
compared to the many-to-one matching with regard to the size of the pattern
set. A fixed set of subjects was generated, containing 100 terms. Out of
those, 30 were sums and 70 were products, matching the distribution in the
pattern set. The number of operands was generated with a normal distribution
with $\mu=5$ and $\sigma=\frac{5}{3}$. The size of the pattern set was varied
by choosing random subsets of the 199 patterns. Across multiple subsets and
repetitions per subject, the mean match and setup times were measured.

$20$$40$$60$$80$$100$$120$$140$$160$$180$$0$$20$$40$$60$Number of PatternsTime
[ms] (a) Average Setup Time

$20$$40$$60$$80$$100$$120$$140$$160$$180$$0$$2$$4$$6$$8$$10$Number of
PatternsTime [ms]one-to-onemany-to-one (b) Average Match Time

Figure 12: Times for LinAlg

The results for setup time (construction of the DN) and match time are shown
in Figure 12 and Figure 12, respectively. The match time is the total time it
takes to match all patterns from the respective pattern set against a single
subject. As expected, the construction time for the many-to-one matcher and
its MLDN increases with the number of patterns. Likewise, the match time for
one-to-one matching increases linearly with the number of patterns, while the
match time for the many-to-one matcher increases significantly slower. This is
also expected, because the many-to-one matching can exploit similarities
between the patterns to match more efficiently. Therefore, the setup time of
the many-to-one matcher and the match time of the one-to-one matching is
interesting, because those are influenced the most by the increase in pattern
set size. For repeated matching against the same pattern set, the setup has to
be done only once and the question is whether it outweighs the matching in
terms of time costs.

In Figure 13, the speedup of many-to-one matching over one-to-one matching is
shown depending on the pattern set size. In every case, many-to-one matching
is faster with a factor between five and 20. Therefore, when exceeding a
certain threshold for the number of subjects, many-to-one matching is overall
faster than one-to-one matching. However, the setup time needs to be amortized
for many-to-one matching to pay off.

$20$$40$$60$$80$$100$$120$$140$$160$$180$$0$$5$$10$$15$$20$Number of
PatternsSpeedup (a) Average Speedup

$20$$40$$60$$80$$100$$120$$140$$160$$180$$0$$2$$4$$6$$8$Number of
PatternsNumber of Subjects (b) Average Break Even Point

Figure 13: Results for LinAlg

The plot in Figure 13 shows the break even point for many-to-one matching
depending on the number of patterns. The break even point is the solution $n$
of

$n\cdot t_{match\ one-to-one}=n\cdot t_{match\ many-to-one}+t_{setup\ many-to-
one}.$

If the matching is used at least $n$ times, many-to-one matching is faster
than one-to-one matching. Otherwise, the setup time dominates the total time
and one-to-one matching is faster. For example, when matching at least 9 times
against the whole pattern set, many-to-one matching is already faster than
one-to-one matching. Every additional match call is then about 18 times faster
than using one-to-one matching.

With the AST patterns, similar results were observed. The speedup is even
greater as can be seen in Figure 14. The significant speedup is most likely
due to most patterns not matching a given subject. While the many-to-one
matcher can quickly exclude most patterns at once, one-to-one matching needs
to exclude every pattern individually. However, as Figure 14 indicates, the
setup time for the underlying MLDN is also much higher, because it has
substantially more states. Therefore, the setup time outweighs the faster
matching time until up to about 200 subjects. For the 2to3 application, the
python files will likely have hundreds of lines resulting in thousands of
nodes in the AST. Hence it is faster to use many-to-one matching here in
practice.

$0$$100$$200$$300$$400$$500$$600$$700$$800$$900$$1000$$1100$$1200$$20$$40$$60$Number
of PatternsSpeedup (a) Average Speedup

$0$$100$$200$$300$$400$$500$$600$$700$$800$$900$$1000$$1100$$1200$$50$$100$$150$$200$Number
of PatternsNumber of Subjects (b) Average Break Even Point

Figure 14: Results for AST

In terms of size, the MLDN for the full pattern set of LinAlg has about 300
states, while the one for all AST patterns has about 5000 states. The growth
of the MLDNs is shown in Figure 15. Because a lot of the patterns for linear
algebra only differ in terms of constraints, the growth slows down with more
patterns as there is more overlap between patterns.

$20$$40$$60$$80$$100$$120$$140$$160$$180$$50$$100$$150$$200$$250$$300$Number
of PatternsNumber of States (a) LinAlg

$0$$100$$200$$300$$400$$500$$600$$700$$800$$900$$1000$$1100$$1200$$0$$1000$$2000$$3000$$4000$$5000$Number
of PatternsNumber of States (b) AST

Figure 15: Average MLDN Sizes

####  subsection11.2 subsectionMany-to-One vs. Discrimination Net

In the second set of experiments, our many-to-one matching algorithm was
compared with deterministic discrimination nets for syntactic pattern
matching. Again, subsets of the 138 syntactic product patterns were used and
matched against each of a set of 200 subjects. Each subject had between one
and three factors, because that is the range of the pattern operand counts.
The factors were chosen as described in section 10.1.

The results are displayed in Figure 16. The graph shows that the DN is about
twice as fast as the MLDN. However, it also has a higher setup time, because
for the construction of the product net is expensive. This is reflected by the
break even point for the VSDN which increases even though its speedup also
increases with the number of patterns. Nonetheless, with more than 120 match
calls, the deterministic VSDN is the fastest solution, with a speedup of about
two over the many-to-one matcher.

$10$$20$$30$$40$$50$$60$$70$$80$$90$$100$$110$$120$$130$$0$$20$$40$$60$Number
of PatternsSpeedupMLDNVSDN (a) Speedup

$10$$20$$30$$40$$50$$60$$70$$80$$90$$100$$110$$120$$130$$0$$20$$40$$60$$80$$100$$120$Number
of PatternsNumber of SubjectsMLDNVSDN (b) Break Even

Figure 16: Results for Syntactic

In this case, there is no significant difference in the number of states
between MLDN and VSDN. This is because there is is not a lot of structural
overlap between patterns, i.e. if two patterns match the same subject, the
patterns must be equal except for constraints. For example, there is never a
situation where both $x$ and $y^{T}$ could match the same term (e.g. $A^{T}$),
because both variables are symbol variables that can only match a matrix
symbol. For the syntactic subset of patterns from AST, the resulting VSDN had
3985 states, while the MLDN had 2716 states which is about 32% less. Because
of the deterministic structure used by the VSDN, its size can grow
exponentially in the worst case, while providing a speedup which scales
linearly with the number of patterns in the best case. Whether that is a
useful tradeoff depends on the application and the actual pattern set.

We also tried to use the VSDN with patterns that have sequence variables.
While it is possible, the size of the DN grows exponentially as illustrated in
Figure 17. With just 15 patterns, we have more than a million states already.
Therefore, it is not feasible to use a deterministic DN for patterns with
sequence variables that overlap.

$10$$20$$30$$40$$50$$60$$70$$80$$90$$100$$110$$120$$130$$50$$100$$150$Number
of PatternsNumber of States (a) Syntactic

$0$$2$$4$$6$$8$$10$$12$$14$$16$$10^{1}$$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$Number
of PatternsNumber of States (b) Product Patterns from LinAlg

Figure 17: Size of VSDN

####  subsection11.3 subsectionMathematica

To see whether Mathematica implements any kind of optimization for many-to-one
matching, we converted the LinAlg patterns to the Wolfram Language. We
prefixed all our custom defined symbols with “LinAlg” to avoid collisions with
existing symbols.

For the matrix properties, we use an association that maps a matrix to a list
of properties. An association is similar to a dictionary or hashmap in other
languages:

LinAlgProperties = <||>;We define the properties of the addition and
multiplication symbols. Here Orderless means commutative, Flat means
associative, and OneIdentity means that an operation with a single operand is
equivalent to just that operand.

SetAttributes[LinAlgPlus, {Orderless, OneIdentity,
Flat}];SetAttributes[LinAlgTimes, {OneIdentity, Flat}];We define shortcut
functions for the symbol types, which we implemented using LinAlgProperties,
e.g. every matrix will have the property “Matrix”.

LinAlgIsMatrix[x_] := MemberQ[LinAlgProperties[x], "Matrix"]LinAlgIsVector[x_]
:= MemberQ[LinAlgProperties[x], "Vector"]LinAlgIsScalar[x_] :=
MemberQ[LinAlgProperties[x], "Scalar"]Finally, we define the list of patterns
as LinAlgPatterns. Every pattern is given as a replacement rule, because the
only way to get a list of all matches in Mathematica is via the ReplaceList
function. As an example, we will use the pattern for the dtrmm BLAS routine
again:

$c_{1}^{*}\times A^{T}\times B\times c_{2}^{*}\mbox{ {if} A is square and
upper triangular}$

In Mathematica, this is equivalent to this:

(LinAlgRoot[LinAlgTimes[ctx1___, LinAlgTranspose[A_?LinAlgIsMatrix],
B_?LinAlgIsMatrix, ctx2___]] /; SubsetQ[LinAlgProperties[A], {"Square",
"UpperTriangular"}]) -> {54, {{"ctx2", ctx2}, {"A", A}, {"B", B}, {"ctx1",
ctx1}}}We surround the whole pattern with “LinAlgRoot” to get the same
behaviour in Mathematica as in our implementation, i.e. that the pattern will
only match at the root of the expression, not anywhere. SubsetQ is used to
check if the matrix $A$ has the right properties. The replacement contains a
unique id that identifies the pattern (54 here), and the substitution list.

For our subjects, we first set all the properties of the symbols:

AppendTo[LinAlgProperties, a0 -> {"Scalar"}];AppendTo[LinAlgProperties, M0 ->
{"Matrix", "UpperTriangular", "Square"}];...Then, we define a list of subjects
in LinAlgSubjects. As an example, a subject could look like this:

LinAlgRoot[LinAlgTimes[M8, LinAlgTranspose[v3], M7, LinAlgTranspose[M4], M5,
v3, LinAlgInverse[M9]]]With the list of 199 patterns and 100 subjects, we get
a total of 178 matches:

AllMatches = Map[Function[s, ReplaceList[s, LinAlgPatterns]],
LinAlgSubjects];NumTotalMatches = Length[Flatten[AllMatches, 1]]

178Finally, this matching process can be repeated for different pattern set
sizes:

ManyToOneTimingStep[n_][_] := (ps = RandomSample[LinAlgPatterns, n];
Table[First[AbsoluteTiming[ReplaceList[s, ps]]], {s,
LinAlgSubjects}]);ManyToOneResults = Table[{n,
Mean[Flatten[Map[ManyToOneTimingStep[n], Range[100]]]]*1000}, {n, 10,
Length[LinAlgPatterns], 10}];ManyToOneTimingStep creates a table of the
matching times for each subject for a random pattern subset of size $n$. Note
that all patterns are passed to ReplaceList at once, making this the many-to-
one case. The timing set is then repeated 100 times for each subset size and
the mean time is calculated. The times are converted to milliseconds to be
better comparable to the other results.

The same process is repeated for one-to-one matching:

OneToOneTimingStep[n_][_] := (ps = RandomSample[LinAlgPatterns, n];
Table[Total[Table[First[AbsoluteTiming[ReplaceList[s, {p}]]], {p, ps}]], {s,
LinAlgSubjects}]);OneToOneResults = Table[{n,
Mean[Flatten[Map[OneToOneTimingStep[n], Range[100]]]]*1000}, {n, 10,
Length[LinAlgPatterns], 10}];The main difference lies in OneToOneTimingStep
where every pattern is passed to ReplaceList separately and the total sum of
those times is averaged.

$20$$40$$60$$80$$100$$120$$140$$160$$180$$0$$1$$2$$3$$4$Number of PatternsTime
[ms]OneToOneResultsManyToOneResults Figure 18: Timing Results for Mathematica

The resulting times are displayed in Figure 18. The matching time seems to be
growing linearly with the number of patterns. There is no notable difference
between the times of one-to-one and many-to-one matching. This indicates that
there is no many-to-one optimization implemented in Mathematica.

##  chapter 6chapterConclusions and Future Work

###  section12 sectionConclusions

In this thesis we presented algorithms for pattern matching with sequence
variables and associative/commutative functions for both one-to-one and many-
to-one matching. Because non-syntactic pattern matching is NP-hard, in the
worst case the pattern matching will take exponential time. Nonetheless, our
experiments on real world examples indicate that many-to-one matching can give
a significant speedup over one-to-one matching. However, the MLDN comes with a
one-time construction cost which needs to be amortized before it is faster
than one-to-one matching. In our experiments, the break even point for many-
to-one matching was always reached well within the magnitude of the pattern
set size. Therefore, for applications that match more than a few hundred
subjects, many-to-one matching can result in a compelling speedup.

For syntactic patterns, we also compared MLDNs with VSDNs. As expected, VSDNs
are faster at matching, but also have a significantly higher setup time.
Furthermore, their number of states can grow exponentially with the number of
patterns, making them unsuitable for some pattern sets.

Which pattern matching algorithm is the fastest for a given application
depends on many factors. Hence, it is not possible to give a general
recommendation. Yet, the more subjects are matched against the same pattern
set, the more likely it is that many-to-one matching pays off. A higher number
of patterns increases the speedup of the many-to-one matching. In terms of the
size of the MLDN, the growth of the net seems to be sublinear in practice. The
efficiency of using MLDNs also heavily depends on the actual pattern set, i.e.
the degree of similarity and overlap between the patterns.

The presented algorithms were implemented in the open-source Python library
MatchPy which is available as a PyPI
package.888https://pypi.python.org/pypi/matchpy We plan on extending the
library with more powerful pattern matching features to make it useful for an
even wider range of applications.

###  section13 sectionFuture Work

There are many possibilities for extending the presented work. The greatest
challenge with additional features is likely to implement them for many-to-one
matching.

##### Additional pattern features

In the future, we plan to implement similar functionality to the Repeated,
Sequence, and Alternatives functions from Mathematica. These provide another
level of expressive power which cannot be replicated with the current feature
set of our pattern matching. Another useful feature are context variables as
described by Kutsia [25]. They allow matching subterms at arbitrary depths
which is especially useful for structures like XML. With context variables,
our pattern matching would be as powerful as XPath [59] or CSS selectors [60]
for such structures. Similarly, function variables that can match any function
symbol would also be useful for those applications.

##### SymPy integration

Integrating MatchPy with the data structures of SymPy (a popular Python
library for symbolic mathematics) would provide the users of SymPy with more
powerful pattern matching tools. However, in SymPy, associativity and
commutativity are implemented differently: Within a function some types of
symbols can commute and other do not. For example, in multiplications, scalars
would be commutative while matrices do not commute. Hence, equivalent
functionality would need to be added to MatchPy.

##### Performance

Reimplementing the pattern matching in a more performance-oriented language
like C or C++ would likely result in a substantial speedup. While Python is a
useful language for prototyping, it tends to be significantly slower than
compiled languages. Alternatively, adapting the code to Cython [61] could be
another option to increase the speed. Furthermore, generating source code for
a pattern set similar to parser generators for formal grammars could improve
matching performance. While code generation for syntactic pattern matching has
been the subject of various works [62, 63, 64, 65], its application with the
extended feature set presented in this thesis is another potential area of
future research.

##### Functional pattern matching

Since Python does not have pattern matching as a language feature, MatchPy
could be extended to provide a syntax similar to other functional programming
languages. Furthermore, in addition to custom symbols, MatchPy could be
extended to match on native structures such as tuples and lists inherently.
This would permit writing code in a manner closer to functional languages.

## References

  * [1] Philip Hazel  “Pcre - Perl Compatible Regular Expressions”, 2017  University of Cambridge Computer Laboratory  URL: http://www.pcre.org/
  * [2] Nachum Dershowitz and Jean-Pierre Jouannaud  “Rewrite Systems”  In _Handbook of Theoretical Computer Science (vol. B)_ Cambridge, MA, USA: MIT Press, 1990, pp. 243–320
  * [3] Franz Baader and Tobias Nipkow  “Term Rewriting and All That”  New York, NY, USA: Cambridge University Press, 1998
  * [4] Marc Bezem Jan Willem Klop  “Term Rewriting Systems”  New York, NY, USA: Cambridge University Press, 2001
  * [5] Christoph M. Hoffmann and Michael J. O’Donnell  “Pattern Matching in Trees”  In _Journal of the ACM_ 29.1 New York, NY, USA: ACM, 1982, pp. 68–95  DOI: 10.1145/322290.322295
  * [6] Alfred V. Aho and Mahadevan Ganapathi  “Efficient Tree Pattern Matching: An Aid to Code Generation (extended Abstract)”  In _Proceedings of the 12 th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages - POPL '85_ Association for Computing Machinery (ACM), 1985  DOI: 10.1145/318593.318663
  * [7] R. Ramesh and I. V. Ramakrishnan  “Nonlinear Pattern Matching in Trees”  In _Automata, Languages and Programming_ Springer Nature, 1988, pp. 473–488  DOI: 10.1007/3-540-19488-6_135
  * [8] Jean-Marc Steyaert and Philippe Flajolet  “Patterns and Pattern-matching in Trees: An Analysis”  In _Information and Control_ 58.1-3 Elsevier BV, 1983, pp. 19–58  DOI: 10.1016/s0019-9958(83)80056-4
  * [9] Henning Fernau and Markus L. Schmid  “Pattern Matching with Variables: A Multivariate Complexity Analysis”  In _Combinatorial Pattern Matching: 24 th Annual Symposium, Cpm 2013, Bad Herrenalb, Germany, June 17-19, 2013. Proceedings_, 2013, pp. 83–94  DOI: 10.1007/978-3-642-38905-4_10
  * [10] Henning Fernau, Florin Manea, Robert Mercas and Markus L. Schmid  “Pattern Matching with Variables: Fast Algorithms and New Hardness Results”  In _32 nd International Symposium on Theoretical Aspects of Computer Science (stacs 2015)_ 30, Leibniz International Proceedings in Informatics (LIPIcs)  Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2015, pp. 302–315  DOI: 10.4230/LIPIcs.STACS.2015.302
  * [11] Makoto Hamana  “Term Rewriting with Sequences”  In _Proceedings of the First International Theorema Workshop, Report Series No. 97-20. Risc-linz, Johannes Kepler University, 1997._ , 1997
  * [12] Temur Kutsia  “Pattern Unification with Sequence Variables and Flexible Arity Symbols”  In _Electronic Notes in Theoretical Computer Science_ 66.5 Elsevier BV, 2002, pp. 52–69  DOI: 10.1016/s1571-0661(04)80514-0
  * [13] Temur Kutsia  “Theorem Proving with Sequence Variables and Flexible Arity Symbols”  In _Logic for Programming, Artificial Intelligence, and Reasoning_ Springer Nature, 2002, pp. 278–291  DOI: 10.1007/3-540-36078-6_19
  * [14] Temur Kutsia  “Unification with sequence variables and flexible arity symbols and its extension with pattern-terms”  In _Lecture Notes in Computer Science (including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)_ 2385, 2002, pp. 290–304  DOI: 10.1007/3-540-45470-5
  * [15] Jean Gallier  “Discrete Mathematics, Second Edition”  Springer New York, 2016
  * [16] Dan Benanav, Deepak Kapur and Paliath Narendran  “Complexity of Matching Problems”  In _Journal of Symbolic Computation_ 3.1 Elsevier BV, 1987, pp. 203–216  DOI: 10.1016/S0747-7171(87)80027-5
  * [17] J. M. Hvllot  “Associative Commutative Pattern Matching”  In _Proceedings of the 6 th International Joint Conference on Artificial Intelligence - Volume 1_, IJCAI’79  Tokyo, Japan: Morgan Kaufmann Publishers Inc., 1979, pp. 406–412
  * [18] Leo Bachmair, Ta Chen and I. V. Ramakrishnan  “Associative-commutative Discrimination Nets”  In _Tapsoft9́3: Theory and Practice of Software Development: 4 th International Joint Conference Caap/fase Orsay, France_, 1993, pp. 61–74  DOI: 10.1007/3-540-56610-4_56
  * [19] S. M. Eker  “Associative-commutative Matching Via Bipartite Graph Matching”  In _The Computer Journal_ 38.5 Oxford University Press (OUP), 1995, pp. 381–399  DOI: 10.1093/comjnl/38.5.381
  * [20] E. Kounalis and D. Lugiez  “Compilation of Pattern Matching with Associative-commutative Functions”  In _TAPSOFT '91_ Springer Nature, 1991, pp. 57–73  DOI: 10.1007/3-540-53982-4_4
  * [21] Leo Bachmair et al.  “Experiments with Associative-commutative Discrimination Nets”  In _Proceedings of the 14 th International Joint Conference on Artificial Intelligence - Volume 1_, IJCAI’95  Morgan Kaufmann, 1995, pp. 348–354
  * [22] Hélène Kirchner and Pierre-Etienne Moreau  “Promoting Rewriting to a Programming Language: A Compiler for Non-deterministic Rewrite Programs in Associative-commutative Theories”  In _International Journal of Foundations of Computer Science_ 11.2 World Scientific Pub Co Pte Lt, 2001, pp. 207–251  DOI: 10.1142/S0129054101000412
  * [23] D. Lugiez and J.L. Moysset  “Tree Automata Help One to Solve Equational Formulae in AC-theories”  In _Journal of Symbolic Computation_ 18.4 Elsevier BV, 1994, pp. 297–318  DOI: 10.1006/jsco.1994.1049
  * [24] Jim Christian  “Flatterms, Discrimination Nets, and Fast Term Rewriting”  In _Journal of Automated Reasoning_ 10.1 Springer Nature, 1993, pp. 95–113  DOI: 10.1007/BF00881866
  * [25] Temur Kutsia  “Context Sequence Matching for XML”  In _Electronic Notes in Theoretical Computer Science_ 157.2 Elsevier BV, 2006, pp. 47–65  DOI: 10.1016/j.entcs.2005.12.045
  * [26] Temur Kutsia  “Solving Equations with Sequence Variables and Sequence functions”  In _Journal of Symbolic Computation_ 42.3 Elsevier BV, 2007, pp. 352–388  DOI: 10.1016/j.jsc.2006.12.002
  * [27] B. Buchberger  “Mathematica as a Rewrite Language”  In _Functional and Logic Programming (Proceedings of the 2 nd Fuji International Workshop on Functional and Logic Programming, November 1-4, 1996, Shonan Village Center)_, 1996, pp. 1–13
  * [28] Simon Marlow  “Haskell 2010 Language Report”, 2010
  * [29] “Elixir”, 2017  Plataformatec  URL: http://elixir-lang.org/
  * [30] “Pattern Matching”  In _Erlang Reference Manual User’s Guide_ Ericsson AB, 2016  URL: http://erlang.org/doc/reference_manual/patterns.html
  * [31] “Patterns”  In _The Rust Programming Language_ Mozilla Research, 2017  URL: https://doc.rust-lang.org/stable/book/
  * [32] Martin Odersky and al.  “An Overview of the Scala Programming Language”, 2004
  * [33] “F#”, 2017  URL: http://fsharp.org/
  * [34] “Patterns”  In _The Swift Programming Language (swift 3.0.1)_ Apple Inc., 2017  URL: https://swift.org/
  * [35] Matthew Flatt and PLT  “Reference: Racket”, 2010  URL: https://racket-lang.org/tr1/
  * [36] Jan Wielemaker, Tom Schrijvers, Markus Triska and Torbjörn Lager  “SWI-Prolog”  In _Theory and Practice of Logic Programming_ 12.1-2, 2012, pp. 67–96
  * [37] Wolfram Research, Inc.  “Mathematica”
URL: https://www.wolfram.com, 2016

  * [38] Richard P. Stanley  “Enumerative Combinatorics: Volume 1”  Cambridge University Press, 2011
  * [39] Donald E. Knuth  “The Art of Computer Programming, Volume 4, Fascicle 3: Generating All Combinations and Partitions”  Addison-Wesley Professional, 2005
  * [40] Frank Ruskey and Aaron Williams  “The Coolest Way to Generate Combinations”  In _Discrete Mathematics_ 309.17 Elsevier BV, 2009, pp. 5305–5320  DOI: 10.1016/j.disc.2007.11.048
  * [41] Daniel R. Page  “Generalized Algorithm for Restricted Weak Composition Generation”  In _Journal of Mathematical Modelling and Algorithms in Operations Research_ 12.4 Springer Nature, 2012, pp. 345–372  DOI: 10.1007/s10852-012-9194-4
  * [42] Robert Weinstock  “Greatest Common Divisor of Several Integers and an Associated Linear Diophantine Equation”  In _The American Mathematical Monthly_ 67.7 JSTOR, 1960, pp. 664  DOI: 10.2307/2310105
  * [43] James Bond  “Calculating the General Solution of a Linear Diophantine Equation”  In _The American Mathematical Monthly_ 74.8 JSTOR, 1967, pp. 955  DOI: 10.2307/2315274
  * [44] J.L. Lambert  “Finding a Partial Solution to a Linear System of Equations in Positive Integers”  In _Computers & Mathematics with Applications_ 15.3 Elsevier BV, 1988, pp. 209–212  DOI: 10.1016/0898-1221(88)90172-1
  * [45] Michael Clausen and Albrecht Fortenbacher  “Efficient Solution of Linear Diophantine Equations”  In _Journal of Symbolic Computation_ 8.1-2 Elsevier BV, 1989, pp. 201–216  DOI: 10.1016/s0747-7171(89)80025-2
  * [46] Karen Aardal, Cor A. J. Hurkens and Arjen K. Lenstra  “Solving a System of Linear Diophantine Equations with Lower and Upper Bounds on the Variables”  In _Mathematics of Operations Research_ 25.3 Institute for Operations Researchthe Management Sciences (INFORMS), 2000, pp. 427–442  DOI: 10.1287/moor.25.3.427.12219
  * [47] Aaron Meurer et al.  “Sympy: Symbolic Computing in Python”  In _Peerj Computer Science_ 3, 2017, pp. e103  DOI: 10.7717/peerj-cs.103
  * [48] Alfred J. Menezes, Scott A. Vanstone and Paul C. Van Oorschot  “Handbook of Applied Cryptography”  Boca Raton, FL, USA: CRC Press, Inc., 1996
  * [49] Albert Gräf  “Left-to-right Tree Pattern Matching”  In _Proceedings of the 4 th International Conference on Rewriting Techniques and Applications_, RTA-91  Como, Italy: Springer-Verlag New York, Inc., 1991, pp. 323–334
  * [50] Nadia Nedjah, Colin D. Walter and Stephen E. Eldridge  “Optimal Left-to-right Pattern-matching Automata”  In _Algebraic and Logic Programming: 6 th International Joint Conference Alp ’97 — Hoa ’97 Southampton, Uk, September 3–5, 1997 Proceedings_, 1997, pp. 273–286  DOI: 10.1007/BFb0027016
  * [51] John E. Hopcroft and Richard M. Karp  “An $n^{5/2}$ Algorithm for Maximum Matchings in Bipartite Graphs”  In _SIAM Journal on Computing_ 2.4 Society for Industrial & Applied Mathematics (SIAM), 1973, pp. 225–231  DOI: 10.1137/0202019
  * [52] K. Fukuda and T. Matsui  “Finding All the Perfect Matchings in Bipartite Graphs”  In _Applied Mathematics Letters_ 7.1 Elsevier BV, 1994, pp. 15–18  DOI: 10.1016/0893-9659(94)90045-0
  * [53] Takeaki Uno  “Algorithms for Enumerating All Perfect, Maximum and Maximal Matchings in Bipartite Graphs”  In _Algorithms and Computation_ Springer Nature, 1997, pp. 92–101  DOI: 10.1007/3-540-63890-3_11
  * [54] Isaac Gouy  “The Computer Language Benchmarks Game”
URL: http://benchmarksgame.alioth.debian.org/, 2017

  * [55] Walid Belkhir and Alain Giorgetti  “Lazy AC-Pattern Matching for Rewriting”  In _10 th International Workshop on Reduction Strategies in Rewriting and Programming_ 82, Proceedings 10th International Workshop on Reduction Strategies in Rewriting and Programming, 2012, pp. 37–51  DOI: 10.4204/EPTCS.82.3
  * [56] C. L. Lawson, R. J. Hanson, D. R. Kincaid and F. T. Krogh  “Basic Linear Algebra Subprograms for Fortran Usage”  In _ACM Transactions on Mathematical Software_ 5.3 Association for Computing Machinery (ACM), 1979, pp. 308–323  DOI: 10.1145/355841.355847
  * [57] Jack J. Dongarra, Jeremy Du Croz, Sven Hammarling and Richard J. Hanson  “An Extended Set of FORTRAN Basic Linear Algebra Subprograms”  In _ACM Transactions on Mathematical Software_ 14.1 Association for Computing Machinery (ACM), 1988, pp. 1–17  DOI: 10.1145/42288.42291
  * [58] J. J. Dongarra, Jeremy Du Croz, Sven Hammarling and I. S. Duff  “A Set of Level 3 Basic Linear Algebra Subprograms”  In _ACM Transactions on Mathematical Software_ 16.1 Association for Computing Machinery (ACM), 1990, pp. 1–17  DOI: 10.1145/77626.79170
  * [59] Jonathan Robie, Michael Dyck and Josh Spiegel  “XML Path Language (XPath) 3.1”, 2017  URL: https://www.w3.org/TR/2017/REC-xpath-31-20170321/