I’ve noticed recently that several contributors to Symbolics.jl and SymbolicUtils.jl like to use @rule for pattern matching, and for good reason. It’s a convenient way to check/rewrite expressions. However, I keep having to discourage this. The implementation of @rule is outdated. It is highly recursive, type-unstable, and slow. It also does not match associative-commutative patterns accurately, has problems with literals in certain positions as well as patterns involving callable structs in the operation slot, and does not scale to large/deep expressions. In short, it was written for a past era of Julia and Symbolics.
MatchMaker.jl fixes all of that! It is algorithmically inspired by MatchPy and related pattern matching literature (cited in the README). The implementation is highly specialized on the way SymbolicUtils.jl does things, and takes advantage of newer data structures such as IRStructure. It matches associative/commutative/associative-commutative patterns, supports single-expression slots, multi-argument “segments”, optional matches, various forms of predicates, and is (compared to @rule) exceptionally fast. If the bot is to be believed, several of the benchmarks in the repository are bottlenecked on expression construction and not the actual pattern matching.
In addition, the package also includes a RuleSet API to compile a list of rules into one data structure that is more efficient than matching each rule sequentially. It also has optimized implementations of replacing all matches in an expression tree, and fixpoint iteration.
The goal for the package is to become the de-facto standard for pattern matching on SymbolicUtils’ expressions. I have plans to refactor parts of Symbolics.jl to leverage this.
Disclaimer: This entire package is AI-generated. I do not currently have the time to dedicate to hand-writing a project like this, but I feel like it’s an important missing piece in the JuliaSymbolics ecosystem. That said, this is not a completely hands-off implementation, which is why it took almost a month. It started with a literature review, a survey of existing tools, then a design document and staged implementation. I have manually reviewed almost all of the source code and a large part of the tests, and several implementation aspects have been iterated on for improved performance. The design document and a rough TODO list are included in the repository. The README also mentions papers/packages used as a reference.
This is also why it is a separate package. I do not feel comfortable throwing a few thousand lines of pure AI code into SymbolicUtils.jl. While this does mean we cannot use it from within SymbolicUtils, I think that that is an acceptable tradeoff.
I plan to add benchmarks to SciMLBenchmarks. If anyone would like to suggest other pattern matching implementations that should be included, please let me know. The package is in the process of being registered, so early adopters will need to manually add it from the git URL.
In case anyone is curious, this took 521M tokens.