Planning for v4

[AayushSabharwal]

SU is overdue for a breaking release, if only to move from Unityper to Moshi. This issue is to track other structural changes we might want to make. I've listed out my ideas below, but would greatly appreciate input.

@data BasicSymbolicImpl{T} begin  # hash2, isequal_with_metadata
  struct Const{T}
    val::T
  end
  struct Sym{T}
    name::Symbol
    metadata::M
    hash2::Ref{UInt}
    shape::Tuple{Vararg{UIntRange{Int}}}
  end
  struct Term{T}
    f::Any
    args::SmallVec{Symbolic}
    metadata::M
    hash::Ref{UInt}
    hash2::Ref{UInt}
    shape::Tuple{Vararg{UIntRange{Int}}}
  end
  struct ACTerm{T}
    f1::Any # + for Add, * for Mul
    f2::Any # * for Add, ^ for Mul
    coeff::T
    dict::ReadOnlyDict{Symbolic{T}, T}
    args::SmallVec{Symbolic{T}}
    metadata::M
    hash::Ref{UInt}
    hash2::Ref{UInt}
    shape::Tuple{Vararg{UIntRange{Int}}}
  end
  struct Div{T}
    num::Symbolic{T}
    den::Symbolic{T}
    simplified::Bool
    metadata::M
    hash2::Ref{UInt}
  end
  struct Pow{T}
    base::Symbolic{T}
    exp::Symbolic{T}
    metadata::M
    hash2::Ref{UInt}
  end
  struct ArrayOp{T}
    # indices of the einstein notation. We can use `BasicSymbolicImpl`
    # here because we know _exactly_ what these will be.
    output_idxs::SmallVec{BasicSymbolicImpl{Int}}
    # the operation in einstein notation, also body of the for loop
    expr::Symbolic{T}
    # reduction function for contracted dimensions
    reduce::Any
    # the "public" version that we show to people
    term::Symbolic{T}
    shape::Tuple{Vararg{UnitRange{Int}}}
    # TODO: Figure out what `ranges` in the original struct is
    metadata::M
    hash::Ref{UInt}
    hash2::Ref{UInt}
  end
end

mutable struct BasicSymbolic{T} <: Symbolic{T} # hash, isequal
  impl::BasicSymbolicImpl{T}
end

• Const allows representing and hashconsing constants, and prevents Vector{Any}
  • printed in a different color to avoid confusion.
• Sym, Term, ACTerm have shape, to enable first-class array support.
  • shape is not used for scalar types. Not even part of the hash.
  • shape of Const can be calculated from the value.
  • Div and Pow shouldn't be applicable for arrays anyway?.
• ACTerm generalizes Add and Mul. Not sure if it's worth yet. Depends on how
  well Julia handles large unions (since BasicSymbolicImpl is a struct containing a Union
  of all variants).
• ArrayOp allows first class array support and validates T <: AbstractArray
• Since ..Impl uses hash2 and isequal_with_metadata, we hashcons it. This allows using
  it in a weakset instead of keying with hash2. BasicSymbolic still has the old
  behavior.
• Return ReadOnlyArray from arguments.
• ArrayMaker might be nice here, but still feels a little unnecessary.
• Along with scalar algebra, implement vector algebra.

There's also an argument to be made for using Mul instead of Div, with negative exponents. Cancellation might get a bit tricky, but not impossible.

hash(x, ::UInt)
isequal(x, y)
hash_with_metadata(x, ::UInt)
isequal_with_metadata(x, y)
supports_hashconsing(::Type)
set_global_id!(x, y)
hasmetadata
getmetadata
setmetadata
metadata
iscall
operation
arguments
sorted_arguments = arguments
maketerm

The above functions are part of the Symbolic interface.

• *_with_metadata enable correctness during hashconsing
• supports_hashconsing enables hashconsing
  • requires set_global_id! for feat: use a global atomic UInt64 to give each BasicSymbolic a unique ID #716.
  • Maybe export SymbolicIDType to allow changing without breaking.
  • Export hashcons(x::Symbolic, y::HashconsingContainer) where HashconsingContainer
    is exported, allowing us to change it whenever we want.
• maketerm is very necessary.

as_expr(x::Vector) = term(vcat, x)
as_expr(x::Array) = term(hvncat, #= ... =#)

Non-symbolic array arguments to an expression are wrapped in Const if non-symbolic
or turned into Terms if symbolic. The conversion to Terms happens via as_expr, which
allows adding methods to handle different types of arrays.

unwrap(x) = x
unwrap(x::BasicSymbolic) = isconst(x) ? x.val : x

unwrap moves here and Symbolics implements it. Also allows better polyadic +/*. Should
also probably move iswrapped. Still a little on the fence about the unwrapping of const
symbolics.

---

One unsolved problem is being able to differentiate betweendependent variables and symbolic function calls. @variables t x(t) (from Symbolics) creates a time-dependent variable x using an FnType and calling it. @variables x(..) creates a CallWithMetadata representing a function, which can be called with any variable or expression. Symbolics differentiates between the two using metadata, but I'd like to explore the idea of supporting this better.

It might be the case that this is considered out-of-scope for SymbolicUtils, in the interest of keeping the package lean. But I'd like to avoid having to reimplement stuff like substitute in Symbolics to account for these nuances.