Julia-lang comparison of expression and commutativity

Question

OK my title isn't great but it's easily explainable with an example.

julia>a = :(1 + 2)
julia>b = :(2 + 1)

julia>a == b
false

I have two expressions a and b. I would like to know if they will give me the same results without being evaluated.

I though that commutative operators like + or * could infer that the results would be the same.

EDIT: Another way to understand it is to compare a very specific subset of expressions that can infer the commutativity of the function: Expr(:call, +, a, b) <=> Expr(:call, +, b, a)

Harrison Grodin Harrison Grodin · Accepted Answer · 2018-10-21T19:35:31

We can write a fairly simple function to check if two arrays have the same elements, modulo ordering:

function eq_modulo_ordering!(xs, ys)  # note !, mutates xs and ys
    while !isempty(xs)
        i = findfirst(isequal(pop!(xs)), ys)
        i === nothing && return false
        deleteat!(ys, i)
    end
    isempty(ys)
end
eq_modulo_ordering(xs, ys) = eq_modulo_ordering!(copy(xs), copy(ys))

We can use then use this function to check if two top-level expressions are equivalent.

function expr_equiv(a::Expr, b::Expr, comm)
    a.head === b.head || return false
    a.head === :call || return a == b
    a.args[1] ∈ comm || return a == b

    eq_modulo_ordering(a.args, b.args)

end
expr_equiv(a, b, comm) = a == b
expr_equiv(a, b) = expr_equiv(a, b, [:+])

In the case that we want to check that two expressions are fully equivalent beyond the top-level, we could modify our functions to use mutual recursion to check if the subexpressions are expr_equiv, rather than isequal.

function eq_modulo_ordering!(xs, ys, comm)  # note !, mutates xs and ys
    while !isempty(xs)
        x = pop!(xs)
        i = findfirst(b -> expr_equiv(x, b, comm), ys)
        i === nothing && return false
        deleteat!(ys, i)
    end
    isempty(ys)
end
eq_modulo_ordering(xs, ys, comm) = eq_modulo_ordering!(copy(xs), copy(ys), comm)

function expr_equiv(a::Expr, b::Expr, comm)
    a.head === b.head || return false
    a.head === :call || return a == b
    a.args[1] ∈ comm || return all(expr_equiv.(a.args, b.args, Ref(comm)))

    eq_modulo_ordering(a.args, b.args, comm)
end
expr_equiv(a, b, comm) = a == b
expr_equiv(a, b) = expr_equiv(a, b, [:+])

We can now use expr_equiv as expected, optionally supplying a list of functions which are commutative.

julia> expr_equiv(:((a + b + b) * c), :((b + a + b) * c))
true

julia> expr_equiv(:((a + a + b) * c), :((b + a + b) * c))
false

julia> expr_equiv(:(c * (a + b + b)), :((b + a + b) * c), [:+, :*])
true

Julia-lang comparison of expression and commutativity

2 Answers