# A default representation for Expr

**URL:** <https://discourse.julialang.org/t/a-default-representation-for-expr/82956>\
**Category:** General Usage\
**Tags:** metaprogramming\
**Created:** [June 18, 2022, 8:02am UTC](https://discourse.julialang.org/t/a-default-representation-for-expr/82956 "2022-06-18T08:02:18Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![yakir12](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yakir12/32/297_2.png) [@yakir12](https://discourse.julialang.org/u/yakir12)\
**Post date:** [June 18, 2022, 8:02am UTC](https://discourse.julialang.org/t/a-default-representation-for-expr/82956/1 "2022-06-18T08:02:18Z")

</div>

Say I have two equivalent expressions:

```julia
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.

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [June 18, 2022, 8:28am UTC](https://discourse.julialang.org/t/a-default-representation-for-expr/82956/2 "2022-06-18T08:28:47Z")

</div>

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 `String`s 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.

---

<div class="post-metadata">

**Author:** ![Jollywatt](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jollywatt/32/202198_2.png) [@Jollywatt](https://discourse.julialang.org/u/Jollywatt)\
**Post date:** [June 18, 2022, 11:30am UTC](https://discourse.julialang.org/t/a-default-representation-for-expr/82956/3 "2022-06-18T11:30:06Z")

</div>

Perhaps not naive enough, but an appropriate tool for expression rewriting and equality testing is [Metatheory.jl](https://juliasymbolics.github.io/Metatheory.jl/stable/).

```julia
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

```

---

<div class="post-metadata">

**Author:** ![yakir12](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yakir12/32/297_2.png) [@yakir12](https://discourse.julialang.org/u/yakir12)\
**Post date:** [June 18, 2022, 3:15pm UTC](https://discourse.julialang.org/t/a-default-representation-for-expr/82956/4 "2022-06-18T15:15:21Z")

</div>

Wow, `Metatheory` looks amazing! OK, but I realize this would work well for very simple examples, or not at all. Thanks a bunch to both answers!