Tutorial

using MatchMaker, SymbolicUtilsusing MatchMaker: RuleSet  # SymbolicUtils exports a different RuleSetusing SymbolicUtils: Sym, SymReal, FnType@syms x y z a b s t p q
(x, y, z, a, b, s, t, p, q)

Patterns and matching

A pattern is an ordinary expression containing marker terms. slot matches one term; segment matches a run of arguments; optional binds a default when absent:

pat = slot(a) + b * slot(t)m = compile_pattern(pat)match(m, x + b * z)
MarkersMap with 2 entries:
  t => z
  a => x

The same Sym in two markers is one variable — non-linear patterns just work:

match(slot(a) + slot(a), x + x)match(slot(a) + slot(a), x + y) # nothing — different values

Enumerating matches

match gives the first; matchall gives every binding:

matchall(segment(s) + slot(t), x + y + z)
3-element Vector{MarkersMap}:
 MarkersMap(s => y + z, t => x)
 MarkersMap(s => x + z, t => y)
 MarkersMap(s => x + y, t => z)

Collect lazily to skip the dict-building — boundmatches yields frozen BoundMatch snapshots you index like dictionaries:

[bm[t] for bm in boundmatches(segment(s) + slot(t), x + y + z)]
3-element Vector{SymbolicUtils.BasicSymbolicImpl.var"typeof(BasicSymbolicImpl)"{SymReal}}:
 x
 y
 z

boundmatches_at / matches_at answer "where does this pattern match inside the subject" — (bindings, subterm) pairs, deduplicated by shared structure:

collect(matches_at(sin(slot(a)), x + sin(y) * sin(z)))
2-element Vector{Tuple{MarkersMap, SymbolicUtils.BasicSymbolicImpl.var"typeof(BasicSymbolicImpl)"{SymReal}}}:
 (MarkersMap(a => y), sin(y))
 (MarkersMap(a => z), sin(z))

Instantiation

Feed bindings back into a template with instantiate — segments splice into the parent argument list:

subst = match(segment(s) + slot(t), x + y + z)instantiate(slot(t) + y, subst)
x + y

Rewriting

mmrule compiles lhs => rhs pairs; RuleSet bundles them into an immutable rule set; a RuleWorkspace owns the mutable state and is the rewriter callable:

rules = RuleSet(CompiledRule[    mmrule(slot(a) + slot(b) => slot(a) * slot(b)),    mmrule(sin(slot(a)) => slot(a)),])ws = RuleWorkspace(rules)ws(x + y)          # first match wins: x + y → x * yws(sin(p + q))     # one rule application per call: → p + q
p + q

rewrite walks the whole tree bottom-up; fixpoint_rewrite iterates to a fixed point:

rewrite(ws, sin(x + y) * sin(p + q))fixpoint_rewrite(ws, sin(x + y) + cos(p + q))
cos(p*q)*x*y

Choosing a rule index

RuleSet(rules, index) picks the dispatch structure that selects candidate rules at each site. Two are provided:

  • BucketIndex (the default) buckets rules by root-head signature and checks a subject's root in O(1). Tiny build cost; the right default for small and medium rule sets.
  • DiscrimNet builds a shared trie over every pattern's preorder obligations. It pays more up front, but survives better where many rules share a root head yet differ in literals or deeper structure — the shape of real simplify rule sets at tens-to-hundreds of rules. It only ever over-approximates candidates (the match engine still verifies each survivor), so it is never less correct, and in practice never slower once the net amortizes.
net_rules = RuleSet(CompiledRule[    mmrule(slot(a) + slot(b) => slot(a) * slot(b)),    mmrule(sin(slot(a)) => slot(a)),], DiscrimNet)ws_net = RuleWorkspace(net_rules)ws_net(x + y)
x*y

Operation traits

Symbolic heads need declared traits — set_operation_traits marks a function Sym associative/commutative so the matcher can reorder and flatten:

myop = Sym{SymReal}(:myop; type = FnType{Tuple{Vararg{Number}}, Number, Nothing})set_operation_traits(myop; associative = true)match(myop(segment(s), slot(t)), myop(x, y, z))
MarkersMap with 2 entries:
  s => myop(x, y)
  t => z