OOOOMM problem in `@rule` macro

[Bumblebee00]

Note

to know before reading: the rule matching process works with lots of macher functions definied at the creation of the rule. These functions are called recursively by one another. If a match is found, the rule rewrites the rhs swapping the slots ~x with the matched values.

The oooomm problem

oooomm stands for only one out of multiple matches.

one rule can have more than one match, if it contains a commutative operation such as + or *. for example
@rule (~x)^(~m)*(~y)^(~n) => (~x, ~m, ~y, ~n)
can match x^2 * x^3 with both m=2, n=3, or m=3, n=2, . Currently only one match of the possible ones is returned, the first found. But let's say we have some conditions on the rule, as is suggested in the documentation we will use the where keyword:
@rule (~x)^(~m)*(~y)^(~n) => (~x, ~m, ~y, ~n) where (~m)^(~n)==8
The where keyword is just syntactic sugar for condition ? result : nothing, so when the first match is found, the rule matcher finishes and returns the condition ? result : nothing expression. If the condition fails the rule returns nothing. But maybe another one of the possible matches satisfied the condition and the rule would have been applied, like in this example

julia> r = @rule (~x)^(~m)*(~y)^(~n) => (~x, ~m, ~y, ~n) where (~m)^(~n)==8
(~x) ^ ~m * (~y) ^ ~n => ((~x, ~m, ~y, ~n) where (~m) ^ ~n == 8)

julia> r((a^2)*(b^3)) 
(a, 2, b, 3)

julia> r((b^2)*(a^3)) 
nothing

Mathematica does this:

In[499]:= 
A[(x_^m_) (y_^n_)] := m
B[(x_^m_) (y_^n_)] := m /; m^n == 8

A[x^2 y^3]
Out[501]= 2

A[x^3 y^2]
Out[502]= 3

B[x^2 y^3]
Out[503]= 2

B[x^3 y^2]
Out[504]= 2

possibilities to circumnavigate this without solving the issue

Note that this could be somewhat solved putting conditions as predicates on the variables like this:

julia> ext_even(x::Number)=iseven(x)
ext_even (generic function with 1 method)

julia> ext_even(x)=false
ext_even (generic function with 2 methods)

julia> A = @rule (~x)^(~m) * (~y)^(~n) => (~x, ~y, ~m, ~n)
(~x) ^ ~m * (~y) ^ ~n => (~x, ~y, ~m, ~n)

julia> B = @rule (~x)^(~m::ext_even) * (~y)^(~n) => (~x, ~y, ~m, ~n)
(~x) ^ ~(m::ext_even) * (~y) ^ ~n => (~x, ~y, ~m, ~n)

julia> A((y^3) * (x^2))
(y, x, 3, 2)

julia> A((x^3) * (y^2))
(y, x, 2, 3)

julia> B((y^3) * (x^2))
(x, y, 2, 3)

julia> B((x^3) * (y^2))
(y, x, 2, 3)

in fact predicates are evaluated during the matching process. But this has two drawbacks:

• in those conditions you cannot use other variables matched in the expression, only the slot variable.
• you can put conditions on single variables but not a condition on the general rule match.

real word occurrencies of this problem

to see a real word occurrence of this problem, read this

[Bumblebee00]

this pr is a proposed solution, but still work in progress