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

Returns the symbolic type of `x`

. By default this is just `typeof(x)`

. Define this for your symbolic types if you want `SymbolicUtils.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)`

Returns `true`

if `x`

is a term. If true, `operation`

, `arguments`

must also be defined for `x`

appropriately.

fn

`operation(x)`

If `x`

is a term as defined by `istree(x)`

, `operation(x)`

returns the head of the term if `x`

represents a function call, for example, the head is the function being called.

fn

`arguments(x)`

Get the arguments of `x`

, must be defined if `istree(x)`

is `true`

.

fn

`similarterm(x, head, args, symtype=nothing; metadata=nothing, exprhead=:call)`

Returns a term that is in the same closure of types as `typeof(x)`

, with `head`

as the head and `args`

as the arguments, `type`

as the symtype and `metadata`

as the metadata. By default this will execute `head(args...)`

. `x`

parameter can also be a `Type`

. The `exprhead`

keyword argument is useful when manipulating `Expr`

s.

`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 [SLOTS...] LHS operator RHS`

Creates an `AbstractRule`

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).

SLOTS is an optional list of symbols to be interpeted as slots or segments directly (without using `~`

). To declare slots for several rules at once, see the `@slots`

macro.

If an expression matches LHS entirely, then it is rewritten to the pattern in the RHS , whose local scope includes the slot matches as variables. Segment (`~x`

) and slot variables (`~~x`

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

**Rule operators**:

`LHS => RHS`

: create a`DynamicRule`

. The RHS is*evaluated*on rewrite.`LHS --> RHS`

: create a`RewriteRule`

. The RHS is**not**evaluated but*symbolically substituted*on rewrite.`LHS == RHS`

: create a`EqualityRule`

. In e-graph rewriting, this rule behaves like`RewriteRule`

but can go in both directions. Doesn't work in classical rewriting`LHS ≠ RHS`

: create a`UnequalRule`

. Can only be used in e-graphs, and is used to eagerly stop the process of rewriting if LHS is found to be equal to RHS.

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

A rule without `~`

```
julia> r = @slots x y z @rule x(y + z) --> x*y + x*z
x(y + z) --> x*y + x*z
```

**Segment**: A Segment variable matches zero or more expressions in the function call. Segments may be written by splatting slot variables (`~x...`

).

*Example:*

```
julia> r = @rule f(~xs...) --> g(~xs...);
julia> r(:(f(1, 2, 3)))
:(g(1,2,3))
```

**Predicates**:

There are two kinds of predicates, namely over slot variables and over the whole rule. For the former, 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($(Expr(:call, :+, ~~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...`

).

For the predicate over the whole rule, use `@rule <LHS> => <RHS> where <predicate>`

:

```
julia> predicate(x) = x === a;
julia> r = @rule ~x => ~x where f(~x);
julia> r(a)
a
julia> r(b) === nothing
true
```

Note that this is syntactic sugar and that it is the same as `@rule ~x => f(~x) ? ~x : nothing`

.

**Compatibility**: Segment variables may still be written as (`~~x`

), and slot (`~x`

) and segment (`~x...`

or `~~x`

) syntaxes on the RHS will still substitute the result of the matches. See also: `@capture`

, `@slots`

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

behaves like`Fixpoint`

but instead it applies`rw`

repeatedly only while it is returning new results.`PassThrough(rw)`

returns a rewriter which if`rw(x)`

returns`nothing`

will instead return`x`

otherwise will return`rw(x)`

.

`Base`

`Base.Threads`

`Core`

`TermInterface`

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, e.g., `a*(b+c)`

becomes `ab+ac`

.

`expand`

uses replace symbols and non-algebraic expressions by variables of type `variable_type`

to compute the distribution using a specialized sparse multivariate polynomials implementation. `variable_type`

can be any subtype of `MultivariatePolynomials.AbstractVariable`

.

fn

`substitute(expr, dict; fold=true)`

substitute any subexpression that matches a key in `dict`

with the corresponding value. If `fold=false`

, expressions which can be evaluated won't be evaluated.

```
julia> substitute(1+sqrt(y), Dict(y => 2), fold=true)
2.414213562373095
julia> substitute(1+sqrt(y), Dict(y => 2), fold=false)
1 + sqrt(2)
```

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
────────────────────────────────────────────────────────────────────────────────────────────────
Rule((~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
Rule((~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: October 18, 2021. Website built with Franklin.jl and PkgPage.jl.