search

JuliaSymbolics / Metatheory.jl

Makes Julia reason with equations. General purpose metaprogramming, symbolic computation and algebraic equational reasoning library for the Julia programming language: E-Graphs & equality saturation, term rewriting and more.
https://juliasymbolics.github.io/Metatheory.jl/dev/
MIT License
355 stars 46 forks source link

Compiled Pattern Matching #204

Closed 0x0f0f0f closed 4 months ago

0x0f0f0f commented 4 months ago

Change base to ale/3.0 after tests green

Compile classical rewriting matchers as functions, same style as ematch_compiler.

Basically 

julia> r = @rule f(~~x, 3, ~~y, 5, ~~z, 7) => (~~x, ~~y, ~~z)
f(~x..., 3, ~y..., 5, ~z..., 7) => (x, y, z)

julia> @btime  r(:(f(1,2,2,3,4,4,5,6,7,7)))
  472.199 ns (14 allocations: 944 bytes)
(Any[1, 2, 2], Any[4, 4], Any[6, 7])

Compared to SU:

julia> r = SymbolicUtils.@rule f(~~x, 3, ~~y, 5, ~~z, 7) => (~~x, ~~y, ~~z)
       t = term(f, 1, 2, 2, 3, 4, 4, 5, 6, 7, 7)

       @btime r(t)
  2.019 μs (111 allocations: 4.83 KiB)
(Any[1, 2, 2], Any[4, 4], Any[6, 7])

cc @shashi @ChrisRackauckas

codecov-commenter commented 4 months ago

Codecov Report

Attention: Patch coverage is 84.92780% with 167 lines in your changes are missing coverage. Please review.

Project coverage is 74.76%. Comparing base (a8331d6) to head (414bcbc). Report is 3 commits behind head on master.

Files Patch % Lines
src/EGraphs/egraph.jl 80.88% 43 Missing :warning:
src/utils.jl 6.25% 30 Missing :warning:
src/matchers.jl 44.73% 21 Missing :warning:
src/Patterns.jl 67.39% 15 Missing :warning:
src/Syntax.jl 86.45% 13 Missing :warning:
src/EGraphs/saturation.jl 94.48% 8 Missing :warning:
ext/Plotting.jl 0.00% 6 Missing :warning:
src/Rewriters.jl 53.84% 6 Missing :warning:
src/Rules.jl 66.66% 6 Missing :warning:
src/ematch_compiler.jl 95.83% 6 Missing :warning:
... and 6 more

:exclamation: Your organization needs to install the Codecov GitHub app to enable full functionality.

Additional details and impacted files ```diff @@ Coverage Diff @@ ## master #204 +/- ## ========================================== + Coverage 69.17% 74.76% +5.58% ========================================== Files 16 20 +4 Lines 1353 1581 +228 ========================================== + Hits 936 1182 +246 + Misses 417 399 -18 ```

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

0x0f0f0f commented 4 months ago

cc @thautwarm - after years, we ended up compiling the patterns. I remember you recommending me not to interpret them!