Pattern-matching syntax
Contents
Pattern-matching syntax#
Patterns are written in JME syntax, but there are extra operators available to specify what does or doesn’t match.
The pattern-matching algorithm uses a variety of techniques to match different kinds of expression.
Data elements such as numbers, strings, booleans are matched by comparison: a pattern consisting of a single data element matches only that exact element.
A pattern consisting of a function application function application f(arguments...)
matches any expression consisting of an application of exactly that function, and whose arguments, considered as a sequence, match the sequence of patterns arguments
.
There are some special functions which match differently.
If the same group name is captured by more than one argument, then all the groups captured under that name are gathered into a list.
A pattern consisting of a sequence of terms joined by a binary operator, or a single term with a unary operator applied, is considered as a sequence. If a way of matching up the terms in the input expression with the terms in the pattern can be found, considering quantifiers and the properties of commutativity and associativity, then the expression matches the pattern. If the same group name is captured by more than one argument, then all the groups captured under that name are gathered into a sequence joined by the operator being matched.
A pattern consisting of a list matches any expression consisting of a single list, whose elements match the elements of the list in the pattern. Quantifiers allow you to write a pattern which matches lists with different numbers of terms.
Special names#
- ?#
Matches anything.
- $n#
Matches a number.
This only matches single number tokens, not expressions which would evaluate to a number, such as
-3
(unary negation) orsqrt(2)
.This does not match unary negation, but does match negative numbers which have been substituted into an expression. To robustly match a positive or negative number, use
`+- $n
.You can use the following annotations to restrict the kinds of numbers that are matched:
real
- has no imaginary part.complex
- has a non-zero imaginary part.imaginary
- has a non-zero imaginary part and zero real part.positive
- real and strictly greater than 0.nonnegative
- real and greater than or equal to 0.negative
- real and less than 0.nonone
- any number other than 1.nonzero
- any number other than 0.integer
- an integer.decimal
- written with at least one digit after the decimal place, or any real number with a fractional part.rational
- an integer, or the division of one integer by another. This doesn’t only match a single token - it’s equivalent to the patterninteger:$n / integer:n`?
.
- Examples:
real:$n
matches3
andpi
but not4+i
orsqrt(2)
.complex:$n
matches1+2i
andi
but not3
.decimal:$n
matches4.1
and2.0
but not2
.rational:$n
matches3/4
and2
but not4.1
.
- $v#
Matches any variable name.
- $z#
Match nothing. Use this as the right-hand side of a
+
or*
operation to force the pattern-matcher to match a sum or product, respectively, when the pattern would otherwise only contain one term, due to use of a quantifier.- Example:
($n `| $v)`+ + $z
matches a sum of any length consisting of numbers or variable names, such as3 + x + 1 + 2 + y
.
Arithmetic Operators#
- `+- X#
Match either
X
or-X
- `*/ X#
Match either
X
or1/X
- Example:
$n * (`*/ $n)
matches either the product or the quotient of two numbers, such as3*4
or6/2
.
Combining patterns#
- A `| B#
Match either
A
orB
.- Example:
x*x `| x^2
matches two different ways of writing “x squared”.
- A `& B#
The expression must match both
A
andB
.- Example:
? = ? `& m_uses(x)
matches an equation which contains the variablex
somewhere.
- `! X#
Match anything except
X
.- Example:
`! m_uses(x)
matches any expression which does not use the variablex
.
- X `where C#
The expression must match
X
, and then the conditionC
is evaluated, with any names corresponding to groups captured inX
substituted in. If the conditionC
evaluates totrue
, the expression matches this pattern.- Example:
$n;x + $n;y `where x+y=5
matches the sum of two numbers which add up to a total of 5.
- macros `@ X#
macros
is a dictionary of patterns. The macros are substituted intoX
to produce a new pattern, which the expression must match.- Example:
["x": a `| b] `@ ["trig": sin(x) `| cos(x) `| tan(x)] `@ trig*trig + trig*trig
matchessin(a)*cos(b) + cos(a)*sin(b)
.
Capturing named groups#
The capturing operator ;
attaches to a part of a pattern, and captures the part of the input expression matching that pattern under the given name.
- X;g#
Capture the input expression in the group named
g
if it matches the patternX
.- Example:
$n;a
captures a number asa
. For the expression15
,a=15
.$n;a + $n;b
captures two numbersa
andb
. For the expression3+4
,a=3
andb=4
.(x-$?;root);term
when matched against the expressionx-2
capturesroot = 2
andterm = x-2
.
- X;g:v#
Match
X
, and capture the valuev
in the group namedg
.You can use this to provide a default value for a value that’s missing or implied, for example a coefficient of \(-1\) in \(-x\).
- Example:
(`+- $n);a * x `| x;a:1 `| -x;a:-1
captures the coefficient ofx
asa
. When the expression is-x
,a = -1
.
- X;=g#
Match
X
only if it’s identical to every other occurrence captured under the nameg
.- Example:
?;=t + ?;=t
matches two copies of the same thing, added together. It matches1 + 1
,x+x
andsin(x*pi) + sin(x*pi)
, but not1+2
orx+y
. When the expression is2x + 2x
,t = 2x
.
Quantifiers#
Quantifiers are used to capture terms that may appear a variable number of times in a sequence.
- X `?#
Either one occurrence of
X
or none.- Example:
$n`? * x
matchesx
and5x
.
- X `: Y#
If the expression matches
X
, match that, otherwise match as the default valueY
.In a sequence, this acts the same as the
`?
quantifier, additionally capturing the default valueY
ifX
does not appear in the sequence.- Example:
($n `: 1);coefficient * x
matchesx
and5x
, and capturescoefficient
as1
when it’s omitted.x^(? `: 1);p
captures any power ofx
asp
, settingp=1
when the power is omitted.
- X `*#
Any number of occurrences of
X
, or none.- Examples:
x * integer:$n`*
matches the product ofx
and any number of integers, such asx
,x*5
orx*2*3
, but notx*x
orx*x*5
.[$n `*]
matches a list containing any number of numbers, such as[]
,[1]
or[6,2]
.
- X `+#
At least one occurrence of
X
.- Example:
x * integer:$n`+
matches the product ofx
and at least one integer, such asx*5
orx*5*6
, but notx
.
Matching modes#
The following functions change the way the matcher works.
- Allow other terms#
When matching an associative operation, allow the presence of terms which don’t match the pattern, as long as there are other terms which do satisfy the pattern. This allows you to write patterns which pick out particular parts of sums and products, for example, while ignoring the rest. This is equivalent to adding something like
+ ?`*
to the end of every sum, and likewise for other associative operations.- Use commutativity#
When matching an associative operation, allow the terms to appear in any order. A sequence matches if an ordering of the terms which satisfies the pattern can be found.
For non-symmetric operators with converses, such as \(\lt\) and \(\leq\), also match the converse relation, reversing the order of the operands.
- Use associativity#
For an associative operator \(\circ\), sequences of terms such as \(a \circ b \circ c\) will be considered together.
If this mode is not enabled, terms are not gathered into sequences before trying to match, so \((a \circ b) \circ c\) is not considered to be the same as \(a \circ (b \circ c)\).
- Gather as a list#
For an associative operator, when the same name is captured by multiple terms, the resulting captured group for that name is a list whose elements are the captured subexpressions from each term.
If this mode is not enabled, the subexpressions from each term are joined together by the associative operator. This doesn’t always make sense, particularly if the group captures only portions of each term.
- Strict inverse#
If this mode is not enabled, then
a-b
is matched as if it’sa+(-b)
, anda/b
is matched as if it’sa*(1/b)
. This makes matching sums of terms that may have negative coefficients easier.If this mode is enabled, then the behaviour described above is not used.
- m_exactly(X)#
Turn off allow other terms mode when matching
X
.
- m_commutative(X)#
Turn on use commutativity mode when matching
X
.
- m_noncommutative(X)#
Turn off use commutativity mode when matching
X
.
- m_associative(X)#
Turn on use associativity mode when matching
X
.
- m_nonassociative(X)#
Turn off use associativity mode when matching
X
.
- m_strictinverse(X)#
Turn on strict inverse mode when matching
X
.
- m_gather(X)#
Turn on gather as a list mode when matching
X
.
- m_nogather(X)#
Turn off gather as a list mode when matching
X
.
Special conditions#
- m_type(type)#
Match any item with the given data type.
- Example:
m_type("string")
matches"hi"
,"5,000"
and"x"
but not1
,true
orx
.
- m_func(name, arguments)#
Match a function whose name, as a string, matches the given pattern, and whose arguments, considered as a
list
, match the given pattern.- Example:
m_func(?, [?,?])
matches any function of two variables.
- m_op(name, operands)#
Match a binary or unary operator whose name, as a string, matches the given pattern, and whose operands, considered as a
list
, match the given pattern.Note that any properties of matched operators, such as commutativity or associativity, aren’t exploited with this matching method.
- m_uses(name)#
Match if the expression uses the variable with the given name as a free variable.
- Example:
m_uses(x)
matchesx
,1+x
andsin(x/2)
but noty
,4-2
, ormap(2x,x,[1,2,3])
.
- m_anywhere(X)#
Match if a sub-expression matching the pattern
X
can be found anywhere inside the input expression.The Allow other terms mode is turned on when matching
X
. You can turn it off as needed withm_exactly
.- Example:
m_anywhere(sin(?))
matchessin(x)
andsin(pi/2) + cos(pi/2)
but nottan(x)
.