macro

`@syms <lhs_expr>[::T1] <lhs_expr>[::T2]...`

For instance:

`@syms foo::Real bar baz(x, y::Real)::Complex`

Create one or more variables. `<lhs_expr>`

can be just a symbol in which case it will be the name of the variable, or a function call in which case a function-like variable which has the same name as the function being called. The Sym type, or in the case of a function-like Sym, the output type of calling the function can be set using the `::T`

syntax.

`@syms foo bar::Real baz::Int`

will create

variable `foo`

of symtype `Number`

(the default), `bar`

of symtype `Real`

and `baz`

of symtype `Int`

`@syms f(x) g(y::Real, x)::Int h(a::Int, f(b))`

creates 1-arg`f`

2-arg`g`

and 2 arg `h`

. The second argument to `h`

must be a one argument function-like variable. So, `h(1, g)`

will fail and `h(1, f)`

will work.

type

`Sym{T}(name::Symbol)`

A named variable of type `T`

. Type `T`

can be `FnType{X,Y}`

which means the variable is a function with the type signature X -> Y where `X`

is a tuple type of arguments and `Y`

is any type.

fn

`symtype(x)`

The supposed type of values in the domain of x. Tracing tools can use this type to pick the right method to run or analyse code.

This defaults to `typeof(x)`

if `x`

is numeric, or `Any`

otherwise. For the types defined in this package, namely `T<:Symbolic{S}`

it is `S`

.

Define this for your symbolic types if you want `simplify`

to apply rules specific to numbers (such as commutativity of multiplication). Or such rules that may be implemented in the future.

type

`Term{T}(f, args::AbstractArray)`

or Term(f, args::AbstractArray)

Symbolic expression representing the result of calling `f(args...)`

.

`operation(t::Term)`

returns`f`

`arguments(t::Term)`

returns`args`

`symtype(t::Term)`

returns`T`

If `T`

is not provided during construction, it is queried by calling `SymbolicUtils.promote_symtype(f, map(symtype, args)...)`

.

See promote_symtype

type

`Add(T, coeff, dict::Dict)`

Represents `coeff + (key1 * val1) + (key2 * val2) + ...`

where keys and values come from the dictionary (`dict`

). where `coeff`

and the vals are `<:Number`

and keys are symbolic.

`operation(::Add)`

– returns`+`

.`symtype(::Add)`

– returns`T`

.`arguments(::Add)`

– returns a totally ordered vector of arguments. i.e.`[coeff, keyM*valM, keyN*valN...]`

type

`Mul(T, coeff, dict)`

Represents coeff * (key1 ^ val1) * (key2 ^ val2) * ....

where coeff is a <:Number and keys and values come from the dictionary (`dict`

). where `coeff`

and the vals are `<:Number`

and keys are symbolic.

`symtype(::Mul)`

– returns`T`

.`operation(::Mul)`

– returns`*`

.`arguments(::Mul)`

– returns a totally ordered vector of arguments. i.e.`[coeff, keyM^valM, keyN^valN...]`

type

`Pow(base, exp)`

Represents `base^exp`

, a lighter version of `Mul(1, Dict(base=>exp))`

fn

`promote_symtype(f, Ts...)`

The result of applying `f`

to arguments of `symtype`

`Ts...`

```
julia> promote_symtype(+, Real, Real)
Real
julia> promote_symtype(+, Complex, Real)
Number
julia> @syms f(x)::Complex
(f(::Number)::Complex,)
julia> promote_symtype(f, Number)
Complex
```

When constructing `Term`

s without an explicit symtype, `promote_symtype`

is used to figure out the symtype of the Term.

`promote_symtype(f::Sym{FnType{X,Y}}, arg_symtypes...)`

The output symtype of applying variable `f`

to arugments of symtype `arg_symtypes...`

. if the arguments are of the wrong type then this function will error.

fn

`istree(x::T)`

Check if `x`

represents an expression tree. If returns true, it will be assumed that `operation(::T)`

and `arguments(::T)`

methods are defined. Definining these three should allow use of `simplify`

on custom types. Optionally `symtype(x)`

can be defined to return the expected type of the symbolic expression.

fn

`operation(x::T)`

Returns the operation (a function object) performed by an expression tree. Called only if `istree(::T)`

is true. Part of the API required for `simplify`

to work. Other required methods are `arguments`

and `istree`

fn

`arguments(x::T)`

Returns the arguments (a `Vector`

) for an expression tree. Called only if `istree(x)`

is `true`

. Part of the API required for `simplify`

to work. Other required methods are `operation`

and `istree`

fn

`similarterm(t, f, args, symtype; metadata=nothing)`

Create a term that is similar in type to `t`

. Extending this function allows packages using their own expression types with SymbolicUtils to define how new terms should be created. Note that `similarterm`

may return an object that has a different type than `t`

, because `f`

also influences the result.

`t`

the reference term to use to create similar terms`f`

is the operation of the term`args`

is the argumentsThe

`symtype`

of the resulting term. Best effort will be made to set the symtype of the resulting similar term to this type.

macro

`@rule LHS => RHS`

Creates a `Rule`

object. A rule object is callable, and takes an expression and rewrites it if it matches the LHS pattern to the RHS pattern, returns `nothing`

otherwise. The rule language is described below.

LHS can be any possibly nested function call expression where any of the arugments can optionally be a Slot (`~x`

) or a Segment (`~~x`

) (described below).

If an expression matches LHS entirely, then it is rewritten to the pattern in the RHS Segment (`~x`

) and slot variables (`~~x`

) on the RHS will substitute the result of the matches found for these variables in the LHS.

**Slot**:

A Slot variable is written as `~x`

and matches a single expression. `x`

is the name of the variable. If a slot appears more than once in an LHS expression then expression matched at every such location must be equal (as shown by `isequal`

).

*Example:*

Simple rule to turn any `sin`

into `cos`

:

```
julia> @syms a b c
(a, b, c)
julia> r = @rule sin(~x) => cos(~x)
sin(~x) => cos(~x)
julia> r(sin(1+a))
cos((1 + a))
```

A rule with 2 segment variables

```
julia> r = @rule sin(~x + ~y) => sin(~x)*cos(~y) + cos(~x)*sin(~y)
sin(~x + ~y) => sin(~x) * cos(~y) + cos(~x) * sin(~y)
julia> r(sin(a + b))
cos(a)*sin(b) + sin(a)*cos(b)
```

A rule that matches two of the same expressions:

```
julia> r = @rule sin(~x)^2 + cos(~x)^2 => 1
sin(~x) ^ 2 + cos(~x) ^ 2 => 1
julia> r(sin(2a)^2 + cos(2a)^2)
1
julia> r(sin(2a)^2 + cos(a)^2)
# nothing
```

**Segment**:

A Segment variable is written as `~~x`

and matches zero or more expressions in the function call.

*Example:*

This implements the distributive property of multiplication: `+(~~ys)`

matches expressions like `a + b`

, `a+b+c`

and so on. On the RHS `~~ys`

presents as any old julia array.

```
julia> r = @rule ~x * +((~~ys)) => sum(map(y-> ~x * y, ~~ys));
julia> r(2 * (a+b+c))
((2 * a) + (2 * b) + (2 * c))
```

**Predicates**:

Predicates can be used on both `~x`

and `~~x`

by using the `~x::f`

or `~~x::f`

. Here `f`

can be any julia function. In the case of a slot the function gets a single matched subexpression, in the case of segment, it gets an array of matched expressions.

The predicate should return `true`

if the current match is acceptable, and `false`

otherwise.

```
julia> two_πs(x::Number) = abs(round(x/(2π)) - x/(2π)) < 10^-9
two_πs (generic function with 1 method)
julia> two_πs(x) = false
two_πs (generic function with 2 methods)
julia> r = @rule sin(~~x + ~y::two_πs + ~~z) => sin(+(~~x..., ~~z...))
sin(~(~x) + ~(y::two_πs) + ~(~z)) => sin(+(~(~x)..., ~(~z)...))
julia> r(sin(a+3π))
julia> r(sin(a+6π))
sin(a)
julia> r(sin(a+6π+c))
sin((a + c))
```

Predicate function gets an array of values if attached to a segment variable (`~~x`

).

**Context**:

*In predicates*: Contextual predicates are functions wrapped in the `Contextual`

type. The function is called with 2 arguments: the expression and a context object passed during a call to the Rule object (maybe done by passing a context to `simplify`

or a `RuleSet`

object).

The function can use the inputs however it wants, and must return a boolean indicating whether the predicate holds or not.

*In the consequent pattern*: Use `(@ctx)`

to access the context object on the right hand side of an expression.

A rewriter is any function which takes an expression and returns an expression or `nothing`

. If `nothing`

is returned that means there was no changes applicable to the input expression.

The `SymbolicUtils.Rewriters`

module contains some types which create and transform rewriters.

`Empty()`

is a rewriter which always returns`nothing`

`Chain(itr)`

chain an iterator of rewriters into a single rewriter which applies each chained rewriter in the given order. If a rewriter returns`nothing`

this is treated as a no-change.`RestartedChain(itr)`

like`Chain(itr)`

but restarts from the first rewriter once on the first successful application of one of the chained rewriters.`IfElse(cond, rw1, rw2)`

runs the`cond`

function on the input, applies`rw1`

if cond returns true,`rw2`

if it retuns false`If(cond, rw)`

is the same as`IfElse(cond, rw, Empty())`

`Prewalk(rw; threaded=false, thread_cutoff=100)`

returns a rewriter which does a pre-order traversal of a given expression and applies the rewriter`rw`

. Note that if`rw`

returns`nothing`

when a match is not found, then`Prewalk(rw)`

will also return nothing unless a match is found at every level of the walk.`threaded=true`

will use multi threading for traversal.`thread_cutoff`

is the minimum number of nodes in a subtree which should be walked in a threaded spawn.`Postwalk(rw; threaded=false, thread_cutoff=100)`

similarly does post-order traversal.`Fixpoint(rw)`

returns a rewriter which applies`rw`

repeatedly until there are no changes to be made.`PassThrough(rw)`

returns a rewriter which if`rw(x)`

returns`nothing`

will instead return`x`

otherwise will return`rw(x)`

.

fn

```
simplify(x; expand=false,
threaded=false,
thread_subtree_cutoff=100,
rewriter=nothing)
```

Simplify an expression (`x`

) by applying `rewriter`

until there are no changes. `expand=true`

applies `expand`

in the beginning of each fixpoint iteration.

fn

`expand(expr)`

Expand expressions by distributing multiplication over addition.

`a*(b+c)`

becomes `ab+ac`

. `expand`

uses AbstractAlgebra.jl to construct dense Multi-variate polynomial to do this very fast.

fn

`substitute(expr, dict)`

substitute any subexpression that matches a key in `dict`

with the corresponding value.

macro

`@timerewrite expr`

If `expr`

calls `simplify`

or a `RuleSet`

object, track the amount of time it spent on applying each rule and pretty print the timing.

This uses TimerOutputs.jl.

```
julia> expr = foldr(*, rand([a,b,c,d], 100))
(a ^ 26) * (b ^ 30) * (c ^ 16) * (d ^ 28)
julia> @timerewrite simplify(expr)
────────────────────────────────────────────────────────────────────────────────────────────────
Time Allocations
────────────────────── ───────────────────────
Tot / % measured: 340ms / 15.3% 92.2MiB / 10.8%
Section ncalls time %tot avg alloc %tot avg
────────────────────────────────────────────────────────────────────────────────────────────────
ACRule((~y) ^ ~n * ~y => (~y) ^ (~n ... 667 11.1ms 21.3% 16.7μs 2.66MiB 26.8% 4.08KiB
RHS 92 277μs 0.53% 3.01μs 14.4KiB 0.14% 160B
ACRule((~x) ^ ~n * (~x) ^ ~m => (~x)... 575 7.63ms 14.6% 13.3μs 1.83MiB 18.4% 3.26KiB
(*)(~(~(x::!issortedₑ))) => sort_arg... 831 6.31ms 12.1% 7.59μs 738KiB 7.26% 910B
RHS 164 3.03ms 5.81% 18.5μs 250KiB 2.46% 1.52KiB
...
...
────────────────────────────────────────────────────────────────────────────────────────────────
(a ^ 26) * (b ^ 30) * (c ^ 16) * (d ^ 28)
```

© Shashi Gowda, Yingbo Ma, Mason Protter. Last modified: June 11, 2021. Website built with Franklin.jl and PkgPage.jl.