Pattern-matching mathematical expressions¶
Page status: Draft
This article is pretty much complete, but needs to be proofread and might change.
Problem¶
In Numbas, we have two related tasks: give feedback based on the form of a student’s answer, and “simplify” expressions according to a configurable set of rules.
Both of these tasks involve pattern-matching in some form: to give feedback, different forms of algebraically equivalent expressions must be described in some general way; to simplify an expression, a rewriting rule must recognise expressions in a certain form and identify particular sub-expressions to produce a new form.
Pattern-matching on trees is not as simple as on strings.
If you’ve done some coding, you might have encountered regular expressions: these are a standard way of describing patterns in text strings, often used to perform text replacements. Regular expressions aren’t appropriate for mathematical expressions, because there’s a lot of structure that regular expressions can’t pick up. The most obvious of these is that regular expressions can’t deal with matching brackets. For example, in the simplification rule \(a \times (-b) \to -(a \times b)\), \(a\) and \(b\) are arbitrary expressions which may contain any number of nested brackets. There’s also a wealth of semantic information about mathematical operations, such as commutativity and associativity, that a pattern-matching system should know about and take into account.
So, we need a pattern-matching system which operates on mathematical expressions with all of their structure, not strings. This isn’t a new idea: most computer algebra systems, such as Mathematica and Maple, are fundamentally pattern-matching and term-rewriting systems.
The problem is that how the algorithms in those systems work on a technical level isn’t well documented, and because Numbas runs entirely on the client, we need an algorithm written in JavaScript.
Thanks to a very fruitful discussion with a couple of attendees at EAMS 2018, I came up with a rough description of the tools that a good pattern-matching system should offer.
I’ve spent the time since then implementing the system, and in using it I came up with some more features that greatly widened the range of possible uses.
Things we want:
Consider all terms of an associative operation together, e.g. terms in a sum, joined by \(+\) or \(-\).
Match if a subset of the terms match the given pattern, leaving the other terms unmatched.
Accept several different forms with the same rule, to avoid repetition, e.g. \(x+By\) is a special case of \(Ax+By\) with \(A=1\).
It would be nice to have built-in matchers for common non-atomic objects, e.g. rational polynomials, complex numbers in Cartesian or polar form, diagonal matrices.
A fairly readable (and writable) syntax for defining patterns which match expressions.
It doesn’t need to make immediate sense, but shouldn’t be too complicated: regular expressions don’t make sense to someone who hasn’t seen them before, but there are very few things to learn.
Capture a missing term with a default value.
Identify equivalent terms that appear in more than one place, for collecting or cancelling.
Once you’ve got pattern-matching and rewriting, you can do lots of things:
Check the form of an answer.
Simplify expressions.
Symbolic differentiation and integration.
Obtain canonical forms for (some classes of) expressions.
Other CAS techniques.
Rewriting an expression¶
To define a rewriting rule, we need a pattern that the expression must match and a result expression, which might have parts of the matched expression substituted into it.
If the language for patterns is not expressive enough, there could be combinatorial explosion in the number of rules that must be defined. (But a more expressive pattern language could lead to combinatorial explosion in the algorithm’s running time).
Rewriting rules should ignore parts of the expression that remain unchanged, and keep them roughly where they were in the rewritten expression.
It must be possible to evaluate a captured term to an object that you can do arithmetic with, for example collecting together constant terms.
It’s often much easier to use several rules together, rather than writing one rule which does everything. For example, when simplifying the fraction \(\frac{18}{6}\), one rule could first cancel the common factor to obtain \(\frac{3}{1}\), and then another rule could remove the denominator \(1\) to obtain \(3\).
Examples¶
Take negation out of a fraction:
\(\frac{-x}{y}\) becomes \(- \frac{x}{y}\).
Collect constants:
\(1 + x + 3\) becomes \(x + 4\).
Collect coefficients of arbitrary terms:
\(5 \times (x + \sin(z)) - 3 \times (x+\sin(z))\) becomes \(2 \times (x+\sin(z))\).
Remove terms with a factor of zero:
\(\cos(t) + 0 \times e^{5t} + z\) becomes \(\cos(t) + z\).
Simplify square roots of square numbers:
\(\sqrt{16}\) becomes \(4\), but \(\sqrt{3}\) is unchanged.
Apply trigonometric identities:
\(\cos(\pi/2)\) becomes \(0\), \(\sin(3\pi/2)\) becomes \(-1\), but \(\sin(0.34 \pi)\) is unchanged.
Cancel common factors on the top and bottom of a fraction:
\(\displaystyle \frac{4 \, a^2 \, b \, c}{6 \, a \, b}\) becomes \(\displaystyle \frac{2 \, a \, c}{3}\).
Extract a scalar factor from the elements of a matrix:
\(\begin{pmatrix} 2\lambda & 0 \\ 0 & - \lambda \, x \end{pmatrix}\) becomes \(\lambda \begin{pmatrix} 2 & 0 \\ 0 & -x \end{pmatrix}\).
Determining the form of an expression¶
In a ‘mathematical expression’ question, the student’s answer \(S\) is an algebraic expression which must match the teacher’s expected answer \(T\).
We can numerically establish that the student has given an equivalent expression by substituting values for \(x\) into both \(S\) and \(T\), but this tells us nothing about the form of \(S\).
Often, valid forms of answer to a particular question differ substantially from each other. The order of terms in a sequence of commuting operations usually doesn’t matter, and some terms may be optional or not present in some randomisations of the question.
Examples¶
The student must expand \((x+\alpha)(x+\beta)\).
The expanded expression will be of the form \(x^2+Ax+B\).
Necessary conditions for ‘expanded’ include ‘contains no brackets’, and ‘each term is an integer multiplied by a power of \(x\)’.
The \(x\) and constant terms might be omitted.
If the coefficient \(A = 1\), it can be omitted.
The opposite task, factorise \(x^2+Ax+B\), will produce an expression of the form \((x+\alpha)(x+\beta)\).
A condition for ‘factorised’ is ‘the expression is a product of irreducible polynomials’.
Write a complex number in argument-modulus form, \(r\,e^{i\theta}\) - \(r\) and \(\theta\) could be literal real numbers, or expressions producing real numbers.
If either of \(r\) or \(\theta\) are \(1\), they can be omitted.
If \(\theta = 0\), then the whole exponent could be written as \(e^0\), \(1\), or omitted entirely.
Some complex numbers in argument-modulus form:
\(5e^{-2i}\)
\(5e^{3i}\)
\(e^i\)
\((1+\sqrt{2})e^{\frac{\pi}{2}i}\)
\(1.32445e^0\)
\(1\)
Previous work¶
WeBWorK¶
WeBWorK uses ‘bizarro arithmetic’ to force expressions which would be equivalent in standard arithmetic to be non-equivalent. It then uses the trick of evaluating at randomly chosen points to establish equivalence. Still unable to give reliable feedback on the form of the student’s answer. Quite a lot of work to set it all up (add flags to context, etc.)
bizarro math for sine and cosine - Davide suggests directly inspecting the Formula object to test if it’s of the form \(\sin(\cdot)\).
Adaptive parameters try to allow for free variables which change the value of an expression linearly, i.e. \(Af(x) + B\) instead of \(f(x)\). Another randomised algorithm is used to establish how the parameters affect the expression, as a matrix - pick some random values for the parameters, and solve the resulting system of equations.
Prolog¶
(Because Chris Sangwin told me to look at it).
Prolog uses a variant of the Martelli-Montanari unification algorithm to identify values of free variables on either side of an equation so that they are equivalent.
It doesn’t allow for missing values, or alternate forms in one expression - you’d have to give an equation for each form.
STACK¶
STACK has a few answer tests to do with the form of the student’s answer: LowestTerms, Expanded, FacForm, SingleFrac, PartFrac, CompletedSquare.
For anything else, you can apply simplification rules to expressions before comparing - the two expressions should end up exactly equal after simplifying.
Maxima¶
Maxima deals with everything as S-expressions, and seems to require quite a lot of code to add new rules.
expreduce, Mathics, Mathematica¶
expreduce is a project in Go. Inspired by Mathics, but some syntax differences.
A video by Brian Beckman about how term rewriting in the style of Mathematica works. Jacquard is a JavaScript clone of Mathematica’s syntax.
Mathics pattern-matching seems to have many of the same operators I’ve come up with. Turns out it’s basically a clone of Mathematica.
Mathematica‘s functionality is similar to what I came up with.
Maple¶
Maple’s pattern matching commands don’t look as sophisticated as Mathematica, but there are some shorthands for common patterns: algebraic, linear, multilinear.
Matchpy¶
Matchpy is a library for pattern-matching symbolic expressions in Python.
It seems to be inspired by Mathematica, and isn’t very sophisticated at the moment.
It has a “many-to-one “matcher which tries to match an expression against several patterns at once. Where patterns are similar, it only needs to check once. Could this be modelled with a nondeterministic finite state automaton?
Rewriting rules are implemented as patterns, with a Python function whose parameters are the captured names, returning a transformed expression.
Solution¶
To define patterns, I added several new symbols to the JME language, for quantifiers, conjunctions and atoms.
I originally had lots of functions of the form m_X
, which led to quite long and hard-to-read patterns.
Operators are a lot easier to read, especially the postfix quantifiers which look more like regex
quantifiers, e.g. x `?
rather than m_maybe(x)
.
The pattern-matching algorithm takes a pattern written with these operators and an input expression, and decides if there’s a match, producing a collection of captured parts analogous to regular expression capturing groups.
Similarities with regular expressions.¶
The matching algorithm is backtracking, like many implementations of regular expression matchers. When there is a choice to make, due to a quantifier or the order of terms, the matcher can backtrack and make a different choice if one path turns out not to lead to a match.
Quantifiers allow arbitrarily many similar terms to be captured without repetition in the pattern.
The `&
operator for specifying two patterns that an expression must match is analogous to positive lookahead in regular expressions.
Unlike most regular expression matchers, patterns can specify arbitrarily complicated conditions on parts of the expression in the middle of the matching process. For example, a regular expression can’t test that a number is prime in one pass.
Syntax trees¶
A string representing a mathematical expression or pattern is parsed into a syntax tree.
The pattern-matcher operates on these trees.
- class Tree¶
A tree consists of a token, which has a type, and an ordered list of arguments, which are themselves trees.
The types include, but are not limited to:
Function application
Operator (binary, unary prefix or unary suffix)
Variable name
Number
So \(\sin(x)+1\) would be:
operator '+' function 'sin' variable x number 1
Options¶
- Commutative
When matching terms joined by a commutative operation such as \(\times\) or \(+\), match terms in any order.
- Associative
When matching terms joined by an associative operation, collect as many terms as possible to match at once, instead of just the two subtrees of the first application of the operation. e.g., \((a+b)+c\) is matched as a list of three terms \(a\), \(b\), \(c\), not two terms \(a+b\) and \(c\).
- Allow other terms
Match a sequence of terms where the pattern is satisfied by a subset of the terms. e.g., \(1+2+x\) matches
n +n
- the extra \(x\) is ignored. In a non-commutative match, the pattern must match a contiguous subsequence of the terms.- Strict inverse
If turned off,
x-y
will be considered asx+(-y)
, so will match patterns like?+?
.Similar for
x/y
being interpreted asx*(/y)
. If turned on, plus means plus!- Gather as a sequence
If turned off, then multiple terms matched under the same name will be stored in a list.
If turned on, then they will be captured as a sequence of terms joined by the same operator used to find them, e.g. addition or multiplication.
Matching a pattern¶
- matchTree(ruleTree, exprTree)¶
To decide whether the given
exprTree
matches the givenruleTree
, and return any matched names if so.This algorithm operates recursively. Its behaviour depends on the type of the token at the top of
ruleTree
:A capturing operator: the rule must be of the form
subRule ; name
- ifexprTree
matchessubRule
, then capture it undername
.An identified capturing operator: the rule must be of the form
subRule ;= name
. All parts of the expression that are captured under this name must be equal.A name: use
matchName()
.A function application: use
matchFunction()
.An operator: use
matchOp()
.A list: use
matchList()
.Anything else: use
matchToken()
.
These produce either
false
if there is no match, or a match object, mapping captured names to the corresponding parts ofexprTree
.Most of these cases are quite easy. The hardest task is to match a sequence of terms - that’s where quantifiers come in.
- matchName(ruleTree, exprTree)¶
When the
ruleTree
is a single name token, it is either a special name representing some built-in pattern, or a generic name.If the name is not special, it matches
exprTree
ifexprTree
is also exactly that single name token.The special names are:
?
- matches any expression.$n
- matches a literal number. Annotations on this can specify extra conditions, or match other kinds of numbers, such as fractions or complex numbers.$v
- matches any variable name.$z
- never matches. Used as a dummy term when matching sequences of terms, all of which are matched by a single pattern.
- matchFunction(ruleTree, exprTree)¶
Match the application of a function.
ruleTree
is a function application token, with an ordered list of arguments.If it’s a special function, run the logic for that.
Otherwise, match as an ordinary function:
If the expression is not a function application, return false.
If the name of the function in the expression is not the same as the one in the rule and the rule function’s name is not
?
, return false.Consider the arguments of both function applications as a sequence, and run
matchTermSequence()
. Collect names matched in the arguments as follows: if a name is only matched by one argument, keep the match as returned by matchTermSequence. If it’s matched by more than one argument, the name is matched to a list, with an entry for each argument the name was captured in.
The special matching functions either change options for the sub-pattern they enclose, or specify conditions:
m_uses(names)
- Matches ifexprTree
uses all of the given names as free variables.m_exactly
- Turns off the “Allow other terms” option.m_commutative
- Turns on the “Commutative” option.m_noncommutative
- Turns off the “Commutative” option.m_associative
- Turns on the “Associative” option.m_nonassociative
- Turns off the “Associative” option.m_strictinverse
- Turns on the “Strict” option.m_gather
- Turns on the “Gather as a sequence” option.m_nogather
- Turns off the “Gather as a sequence” option.m_type(type)
- Matches if the token at the top ofexprTree
is of the given type.m_func(name,arguments)
- Matches ifexprTree
is the application of the function with the given name, and its arguments match the given list.m_op
- Matches ifexprTree
is the application of the operator with the given name, and the operands read from left to right match the given list.m_anywhere(subpattern)
- Matches if thesubpattern
matches anywhere withinexprTree
- perform a breadth-first search ofexprTree
, returning the first match.
- matchOp(ruleTree, exprTree)¶
Match the application of an operator.
ruleTree
is an operator token, with a list of operands.If it’s a special operator, run the logic for that.
Otherwise, match an ordinary operator:
The operator being matched is the operator at the top of
ruleTree
.The match is commutative if the commutative option is turned on and the operator is commutative.
The match is associative if the associative option is turned on and the operator is associative.
Run
getTerms()
to identify terms inruleTree
andexprTree
.If the match is not associative, and the expression is not an application of the operator being matched, and it’s a unary operation, then there is no match.
Run
matchTermSequence()
on the terms. Unmatched terms are allowed if the “Allow other terms” option is turned on and the match is associative.Collate the named groups: for names which are matched more than once, combine them. If the “Gather as a sequence” option is turned off, the name matches to a list with an entry for each time the name was matched. If it’s turned on, the occurrences are joined together by applications of the operator.
When gathering multiplicative terms as a sequence, the invented unary reciprocal operator must be removed: replace each instance of
x*(/y)
withx/y
.Capture the operator token under the name
__op__
, to be used by a rewriting rule if there are unmatched terms in the sequence.The special matching operators specify quantifiers, allow for plus/minus or times/divide matches, or express combinations of patterns:
Quantifiers:
subpattern`?
- matchsubpattern
if possible, otherwise ignore it.subpattern`*
- match any number of terms matchingsubpattern
.subpattern`+
- match one or more terms matchingsubpattern
.
Combining patterns:
a `| b
- “eithera
orb
”. IfexprTree
matches patterna
, return that, otherwise try to matchb
.`! subpattern
- “notsubpattern
”.exprTree
only matches if it does not matchsubpattern
.a `& b
- “botha
andb
”. Test botha
andb
, and combine their matched names.
Conditions:
subpattern `where condition
.exprTree
must matchsubpattern
, and then after substituting matched names intocondition
, it must evaluate totrue
.
Inverses:
`+- subpattern
. “Plus or minussubpattern
”.exprTree
must match eithersubpattern
, or-(subpattern)
.`*/ subpattern
. “subpattern
or its reciprocal”.exprTree
must match eithersubpattern
, or/(subpattern)
. The unary reciprocal operator is added when collecting the terms in a sequence, replacingx/y` with ``x*(/y)
.
Other special operators:
subpattern `: v
. “Default value for missing term”. When matching a sequence, ifsubpattern
is not matched, then this term is matched as the default valuev
instead.macros `@ subpattern
.macros
is a dictionary mapping names to patterns. The macros are substituted intosubpattern
before runningmatchTree()
to find a match.
- matchList(ruleTree, exprTree)¶
ruleTree
has a list token at the top, and its arguments are a sequence of patterns.If the token at the top of
exprTree
is not a list, return false.Consider the elements of both lists as a sequence of
terms
.Run
matchTermSequence()
on the terms.Each matched name is captured as a list with an entry for each time the name was matched.
- matchToken(ruleTree, exprTree)¶
There is a match if the tokens at the top of
ruleTree
andexprTree
are equal.
Matching a sequence of terms¶
Function arguments, list elements, and the operands of associative operations are considered as sequences of terms.
Both the pattern and the expression being matched produce a sequence of terms. The aim is to match up terms in the pattern with terms in the expression. Quantifiers on each term in the pattern specify how many terms in the expression can match against it.
To identify a sequence, we might need to apply the law of associativity for binary operations.
When matching a sequence pattern we might need to apply the law of commutativity, to match terms which appear in a different order to that used in the pattern.
It’s convenient when matching sums or products of terms to treat x-y
as x+(-y)
and x/y
as x*(/y)
.
There’s no conventional symbol for a unary “reciprocal” operator analogous to the unary “negation” operator, but it’s useful here.
- class Term(tree)¶
A
Term
objects represents a single term in a sequence.The same
Term
class is used for terms in both the pattern and the expression. Terms in the expression only fill in thetree
property; the rest of the defined properties are only for terms in the pattern.- property tree: Tree¶
The syntax tree corresponding to this term, with the outermost quantifiers, default value operators, or capturing operators removed.
- property names¶
Names under which this term should be captured.
- property inside_equalnames¶
Names captured inside a quantifier that have an equality condition - each term matching this term will be considered individually for equality.
- property outside_equalnames¶
Names captured outside a quantifier that have an equality condition - all terms matching this term will be grouped together, and then any later matches to the same name will be considered for equality with these as a single expression.
- property quantifier¶
How many terms in the expression can match against this pattern term.
Possible values:
0
- this term must not match.1
- match once`?
- match once or not at all.`*
- match any number of times.`+
- match at least once.
- property defaultValue¶
A value to capture if this term is not matched.
To compute these values, any special operators on the outside of the input
tree
are peeled off, one by one:The initial value of
quantifier
is1
, or0
if the term is$z
.Quantifiers are pulled through unary operations, so
-(x`?)
is equivalent to(-x)`?
.;
Add a name to
names
.;=
Add a name to
names
, and also add it tooutside_equalnames
if a quantifier has not been encountered yet, orinside_equalnames
otherwise.`?
,`*
or`+
Change
quantifier
.There are precedence relations between the current value of
quantifier
and the one being unpeeled:0
takes precedence over all others.1
has the lowest precedence.`?
followed by`*
or`+
, or the other way round, produce`*
.Otherwise, the new quantifier takes precedence.
`:
- setdefaultValue
.If
quantifier
is1
, change it to`?
. If it’s`+
, change it to`*
. (Implicitly, this term is optional)
Once these operators have been peeled off, the remaining tree is saved as the
tree
property.Finally, any more identified capturing operators
;=
inside the tree are found and saved. Those under a quantifier are ignored.
- getTerms(tree, op, commutative, associative, strictInverse)¶
Given a
tree
representing a series of termst1 op t_2 op t_3 op ... op t_n
, return the terms as a list ofTerm
objects.If the top of the tree is a unary minus operation, move it inside the tree so that it applies to the leftmost factor. For example, rewrite
-((x*y)*z)
to((-x)*y)*z
.If the “Strict inverse” option is not turned on, and
op
is+
or*
, then replacex-y
withx+(-y)
andx/y
withx*(/y)
.If
op
is a binary relation, then we want to make sure that the operation and its converse are handled together. For example,>
is the converse of<
. Ifop
is<
, then replace all instances in the tree ofa > b
withb < a
.If the token at the top of the tree is the operator
op
, thenargs
is the list of arguments. Otherwise,args
is the list whose only element istree
.For each argument
arg
inargs
:Make a
Term
objectterm
containingarg
.Remove any capturing operators
;
or;=
from the top ofarg
.If
op
is*
and the token at the top ofarg
is a unary minus, then remove that (theTerm
object will remember that it’s there).If using associativity and the token at the top of
arg
is the operatorop
, then split it into more terms:Run
getTerms()
onarg
to obtain a list of terms.Add the captured names from
item
to each of these terms.If the
quantifier
foritem
is not1
, then combine the quantifiers on each of these terms, using the same logic as used when constructingTerm
objects. For example,(x`+ * y)`?
is equivalent tox`* * y`?
.Add each of these terms to the list of terms to output.
Otherwise, add
term
to the list of terms to output.Return the list of identified terms.
- matchTermSequence(ruleTerms, exprTerms, options)¶
Given a list of rule terms and a list of expression terms, try to come up with an assignment of expression terms to rule terms.
A rule term might match more than one expression term, if quantifiers allow.
An expression term might not match any rule terms, if the “Allow other terms” option is turned on. In order to allow rewriting rules to keep terms in roughly the same order, we track whether unmatched expression terms are towards the start or the end of the expression.
Keep track of what names have been matched for each term in the expression.
An expression term
exprTerm
matches a rule termruleTerm
ifmatchTree(exprTerm.tree, ruleTerm.tree)()
returnstrue
.An assignment is valid if, for each identified name captured in an expression term, it’s equal to all matches of the name in previous terms.
There might be more than one valid matching of expression terms to rule terms: an expression term could match several rule terms, and a rule term might have a quantifier that allows it to match different numbers of expression terms. If “Allow other terms” is turned on, then for each expression term we could decide not to try to match it at all.
The strategy is to move the input pointer along the list of expression terms, trying to match them greedily with the first rule term they match against. If either pointer reaches the end of the corresponding list and there are any unmatched terms, then backtrack, either looking to match an expression term against a later rule, or if “Allow other terms” is turned on, don’t match it at all.
When the “Commutative” option is turned on, there are lots more possible matches, increasing the maximum running time of the algorithm.
The process of finding a match works as follows.
Define:
capture
A list storing which pattern term each expression term is matched against. Values are either an index in the list
ruleTerms
or the constantsUNCAPTURED
,START
orEND
, denoting a term that did not match a rule term, not captured, at the start of the sequence or at the end. Initially, every value in this list isUNCAPTURED
.start
The index of the first term in the expression to consider matching, initially
0
, meaning the first term in the list. Terms before this are not included in the match.pc
‘Pattern pointer’ - a pointer into the list of rule terms. Initially
0
, meaning the first term.ic
‘Input pointer’ - a pointer into the list of expression terms. Initially
0
, meaning the first term.- Consumed
A rule term is consumed if its quantifiers allow no more expression terms to be matched against it.
- Enough
A rule term has had enough if the number of expression terms matched against it is at least the minimum required by its quantifiers.
To find a match, repeat the following loop until done:
Algorithm (Main loop)Move to the next unconsumed rule term: as long as the rule term pointed to by
pc
is consumed, incrementpc
.If the input pointer
ic
has reached the end of the expression terms:Move to the next rule term that hasn’t had enough: while the rule term at
pc
has had enough, incrementpc
.If
pc
has reached the end of the list of rule terms:If there is any rule term that has not had enough, Backtrack.
Otherwise, this is a match.
Otherwise, there are still some unmatched rule terms, so Backtrack.
Otherwise, if the pattern pointer
pc
has reached the end of the rule terms, there are unconsumed expression terms:If “Allow other terms” isturned on:
If “Commutative” is turned on, then mark the expression term pointed to by
ic
asEND
, and Advance input.Otherwise, capture all the remaining expression terms as
END
, and move the input pointeric
to the end.
Otherwise, Backtrack.
Otherwise, check if the expression term pointed to by
ic
matches the rule term pointed to bypc
.If it does, and all captured name assignments are valid, capture
ic
as matchingpc
and Advance input.Otherwise, this expression term doesn’t match the current rule term. If “Commutative” is turned on, or if the rule terms pointed to by
pc
has had enough, incrementpc
.If none of those apply, Backtrack.
Algorithm (Backtrack)Find the last place we made a choice:
If “Allow other terms” is turned on,
ic = start
, the number of captured terms is equal tostart
and less than the number of input terms, then try ignoring the term pointed to byic
:Capture the expression term pointed to by
ic
asSTART
, and Increment start.Otherwise:
Move
ic
back at least one place, to the last term beforestart
or the last term not captured asEND
orUNCAPTURED
, whichever is last.If
ic < start
:If “Allow other terms” is turned on and
start
is not at the end:Capture all terms before
start
asSTART
.
Otherwise, there is no match: no expression terms have matched any rule terms.
Set
pc
to the position after the one which the expression term pointed to byic
is captured as (or just the end, if the term atic
is captured asEND
).Mark all expression terms after
ic
asUNCAPTURED
.
Algorithm (Incrementstart
)Set
ic = start
, so we ignore expression terms before that.Set
pc = 0
, since we’re effectively starting the matching process again with a smaller list of expression terms.
Algorithm (Advance input)Increment
ic
.If “Commutative” is turned on, set
pc = 0
, so that each expression term can eventually be tried against every rule term.
If a match is found, then we need to match up captured names from each term to produce a final match result.
For each expression term
exprTerm
matched against a rule termruleTerm
, record thatexprTerm
was matched against each of the names captured byruleTerm
, and merge this with any names captured insideruleTerm
.For each rule term with a
Term.defaultValue
that did not match any expression terms, match the default value against all the rule term’s capturing names.Record expression terms captured as
START
orEND
in separate lists, as well as the operator. These will be used inrewrite()
.
Simplification rules¶
A simplification rule is a term rewriting rule \(l \to r\). For example, \(x \times (y \times z) \to (x \times y) \times z\) changes the order in which a product of three terms is evaluated. In this instance, \(x\), \(y\) and \(z\) are arbitrary sub-expressions.
If this rule was applied repeatedly to an arbitrarily bracketed product of several terms, the final expression would end up looking like:
- simplify(rules, exprTree)¶
Apply this loop:
- rewrite(ruleTree, resultTree, exprTree)¶
Match
exprTree
againstruleTree
.If there’s no match, return
exprTree
unchanged.We now have a set of captured names, and a corresponding sub-expression for each of them constructed from parts of
exprTree
or default values defined in the rule.For names defined in
ruleTree
that did not capture anything, associate them with a ‘nothing’ value.For each name captured in the match, substitute the corresponding values into
resultTree
.Apply post-replacement rules:
Replace
eval(expr)
with the result of evaluatingexpr
.Replace binary operations where one argument is ‘nothing’ with just the other argument, i.e. replace
nothing (op) x
andx (op) nothing
withx
.
If the match has any expression terms that were ignored in
matchTermSequence()
, add these: using the recorded operatorop
, ignored termsrest_start
andrest_end
, and the rewritten treeresult
, producerest_start (op) result (op) rest_end
.
This is a naive algorithm - with the wrong set of rules, it can get stuck in an infinite loop.
Problems¶
“Identified names”, when interacting with commutative match, needs some
kind of backtracking over trees.
For example, in order for ?*?;=y + ?*?;=y
to match 3*x + x*5
, each of the additive terms
needs to know about the others while matching the product operation.
It’s not enough just to tell the second term that the name \(y\) has
been matched to \(x\) in the first term: it might be that the first
term needs to match differently.
So the identified names should maybe be applied at the very end, to the whole expression, but we then need a way of asking for “the next” way of matching each set of terms.