julia> ex1 = :(a + b*c + 1)
:(a + b * c + 1)
julia> ex2 = :(1 + a + c*b)
:(1 + a + c * b)
Is there a way to naively rearrange each of these to some default representation, so that ex1 == ex2?
I understand that there might not be a way for Julia to know if – due to some side effects – one representation is truly equivalent to another, but assuming operator precedence etc, is there a good-enough way to accomplish something like this?
P.S.
This is not just for algebraic expressions but more for general programming stuff.
You don’t even need side effects for nonequivalence, you just need * to not be commutative (like division) and + to not be associative (like subtraction). Sounds odd, but it’s very possible to define such * and + methods depending on the input types. For example, * concatenation of Strings is not commutative. Symbolic math can compare and rearrange mathematical expressions because operators have fixed properties.
You can use the dump method to inspect the structure of an Expr. You can at least reach [1, :a, :(c * b)] with ex2.args[2:end], but I don’t know of a neat way to sort literals, symbols, and expressions. If you could do that (and recursively), you can figure out if they can be rearranged to the same expression, assuming the dispatched methods are commutative and associative.
Perhaps not naive enough, but an appropriate tool for expression rewriting and equality testing is Metatheory.jl.
julia> using Metatheory
julia> rewrite_rules = @theory a b c begin
a + (b + c) == (a + b) + c
a + b == b + a
a*b == b*a
end
3-element Vector{EqualityRule}:
a + (b + c) == (a + b) + c
a + b == b + a
a * b == b * a
julia> @areequal rewrite_rules :(a + b*c + 1) :(1 + a + c*b)
true