`NCMul`, `@assocrule` for non-commutative multiplication

[MasonProtter]

This is currently incomplete, but it's in at least a somewhat working state. It still requires at the very least

• [ ] Docs
• [ ] Tests

and maybe also

• [ ] Make this work with Add

The idea here is that I've added a special term struct NCMul which is meant to represent non-commutative multiplication (kinda like Mul, but order preserving). I've also added a new type of rule, AssocRule where the idea is that it is meant to represent associative replacement rules (but not commutative).

For example, we could write

r = @assocrule f(a, b) => c
t = f(x, y, a, b, z) # assume this is an istree object
r()

and this would traverse the arguments list doing something like

r(f(x, y)) # no-match
r(f(y, a)) # no-match
r(f(a, b)) # match! now return similarterm(t, f, [[x, y]; c; [z]])
r(f(b, z)) # this does not get hit

Now, here is an example case where someone might want to use this machinery to implement a 2D geometric algebra:

using SymbolicUtils
using SymbolicUtils.Rewriters
using SymbolicUtils: Symbolic, commutes, NCMul, @assocrule

SymbolicUtils.show_simplified[] = false

struct Clifford end

@syms σ1::Clifford σ2::Clifford

SymbolicUtils.promote_symtype(::typeof(*), ::Type{Clifford}, ::Type{Clifford}) = Clifford
SymbolicUtils.promote_symtype(::typeof(*), ::Type{<:Number}, ::Type{Clifford}) = Clifford
SymbolicUtils.promote_symtype(::typeof(*), ::Type{Clifford}, ::Type{<:Number}) = Clifford

SymbolicUtils.promote_symtype(::typeof(+), ::Type{<:Number}, ::Type{Clifford}) = Clifford
SymbolicUtils.promote_symtype(::typeof(+), ::Type{Clifford}, ::Type{<:Number}) = Clifford

SymbolicUtils.commutes(::typeof(*), ::Type{<:Clifford}) = false

Base.:(*)(x::Symbolic{Clifford}, y::Symbolic{Clifford}) = NCMul(Clifford, 1, [x, y])
Base.:(*)(x, y::Symbolic{Clifford}) = NCMul(Clifford, x, [y,])
Base.:(*)(x::Symbolic{Clifford}, y) = NCMul(Clifford, y, [x,])

Base.:(*)(x::Number, y::Symbolic{Clifford}) = NCMul(Clifford, x, [y,])
Base.:(*)(x::Symbolic{Clifford}, y::Number) = NCMul(Clifford, y, [x,])

Base.:(*)(x::NCMul, y::Symbolic{Clifford}) = NCMul(Clifford, x.coeff, [x.vec; y])
Base.:(*)(x::Symbolic{Clifford}, y::NCMul) = NCMul(Clifford, y.coeff, [x; y.vec])

Base.:(-)(x::Symbolic{Clifford}) = -1 * x
Base.:(-)(x::Symbolic{Clifford}, y::Symbolic{Clifford}) = x + -y
Base.:(-)(x, y::Symbolic{Clifford}) = x + -y
Base.:(-)(x::Symbolic{Clifford}, y) = x + -y

## This won't currently work since Add can only store symtypes which are <:Number
# using SymbolicUtils: Add
# Base.:(+)(x::Symbolic{Clifford}, y::Symbolic{Clifford}) = Add(Clifford, 0, Dict(x => 1, y => 1))
# Base.:(+)(x::Symbolic, y::Symbolic{Clifford}) = Add(Clifford, 0, Dict(x => 1, y => 1))
# Base.:(+)(x::Symbolic{Clifford}, y::Symbolic) = Add(Clifford, 0, Dict(x => 1, y => 1))
# Base.:(+)(x::Number, y::Symbolic{Clifford}) = Add(Clifford, x, Dict(y => 1))
# Base.:(+)(x::Symbolic{Clifford}, y::Number) = Add(Clifford, y, Dict(x => 1))

for op ∈ (:+, :^, :/)
    @eval begin
        Base.$op(x::Symbolic{Clifford}, y::Symbolic{Clifford}) = Term{Clifford}($op, [x, y])
        Base.$op(x, y::Symbolic{Clifford}) = Term{Clifford}($op, [x, y])
        Base.$op(x::Symbolic{Clifford}, y) = Term{Clifford}($op, [x, y])

        Base.$op(x::Number, y::Symbolic{Clifford}) = Term{Clifford}($op, [x, y])
        Base.$op(x::Symbolic{Clifford}, y::Number) = Term{Clifford}($op, [x, y])
    end
end

GArules = [
    simplify
    @assocrule σ1 * σ1 => 1
    @assocrule σ2 * σ2 => 1
    @assocrule σ2 * σ1 => -1 * (σ1 * σ2)

] |> Chain |> Postwalk |> Fixpoint

Now we can do all sorts of stuff:

(-1 * (σ2 * σ1 * 3)) * σ2 
#+RESULTS:
: -3σ2*σ1*σ2

(-1 * (σ2 * σ1 * 3)) * σ2  |> GArules
#+RESULTS:
: 3σ1

[JeffreySarnoff]

Perhaps include NCAdd to widen available Algebraizations.

[JeffreySarnoff]

It is helpful to have anti-commutative operations available and visually distinct from their subsumptive non-commutative operations. a ⨱ b == -(b x a)

Or, allow one to declare a type or to declare some arithmetic ops for a type to be commutative or anticommutative or noncommutative, associative or nonassociative

[shashi]

We now have LiteralReal which just does not reorder anything! It can be used as a type annotation and is a subtype of Real:

julia> @syms a::LiteralReal b::LiteralReal
(a, b)

julia> a * b * a
(a * b) * a