# User Manual

SymbolicUtils is an practical symbolic programming utility written in Julia. It lets you create, rewrite and simplify symbolic expressions.

The main features are:

• Fast expressions

• A combinator library for making rewriters.

• Type promotion:

• Symbols (`Sym`s) carry type information. (read more)

• Compound expressions composed of `Sym`s propagate type information. (read more)

• Set of simplification rules. These can be remixed and extended for special purposes.

## `Sym`s

First, let's use the `@syms` macro to create a few symbols.

``````using SymbolicUtils

@syms w z α::Real β::Real``````
``(w, z, α, β)``

Type annotations are optional when creating symbols. Here `α`, `β` behave like Real numbers. `w` and `z` behave like `Number`, which is the default. You can use the `symtype` function to find the type of a symbol.

``````using SymbolicUtils: symtype

symtype(w), symtype(z),  symtype(α), symtype(β)``````
``(Number, Number, Real, Real)``

Note however that they are not subtypes of these types!

``````@show w isa Number
@show α isa Real``````
``````w isa Number = false
α isa Real = false
``````

(see this post for why they are all not just subtypes of `Number`)

You can do basic arithmetic on symbols to get symbolic expressions:

``````expr1 = α*sin(w)^2 +  β*cos(z)^2
expr2 = α*cos(z)^2 +  β*sin(w)^2

expr1 + expr2``````
``α*(sin(w)^2) + α*(cos(z)^2) + β*(sin(w)^2) + β*(cos(z)^2)``

Function-like symbols

Symbols can be defined to behave like functions. Both the input and output types for the function can be specified. Any application to that function will only admit either values of those types or symbols of the same `symtype`.

``````using SymbolicUtils
@syms f(x) g(x::Real, y::Real)::Real

f(z) + g(1, α) + sin(w)``````
``sin(w) + f(z) + g(1, α)``
``g(1, z)``
``````Argument to g(::Real, ::Real)::Real at position 2 must be of symbolic type Real
``````

This does not work since `z` is a `Number`, not a `Real`.

``g(2//5, g(1, β))``
``g(2//5, g(1, β))``

This works because `g` "returns" a `Real`.

## Expression interface

Symbolic expressions are of type `Term{T}`, `Add{T}`, `Mul{T}` or `Pow{T}` and denote some function call where one or more arguments are themselves such expressions or `Sym`s.

All the expression types support the following:

• `istree(x)` – always returns `true` denoting, `x` is not a leaf node like Sym or a literal.

• `operation(x)` – the function being called

• `arguments(x)` – a vector of arguments

• `symtype(x)` – the "inferred" type (`T`)

See more on the interface here

## Rule-based rewriting

Rewrite rules match and transform an expression. A rule is written using either the `@rule` macro or the `@acrule` macro.

Here is a simple rewrite rule:

``````r1 = @rule ~x + ~x => 2 * (~x)

showraw(r1(sin(1+z) + sin(1+z)))``````
``nothing``

The `@rule` macro takes a pair of patterns – the matcher and the consequent (`@rule matcher => consequent`). If an expression matches the matcher pattern, it is rewritten to the consequent pattern. `@rule` returns a callable object that applies the rule to an expression.

`~x` in the example is what is a slot variable named `x`. In a matcher pattern, slot variables are placeholders that match exactly one expression. When used on the consequent side, they stand in for the matched expression. If a slot variable appears twice in a matcher pattern, all corresponding matches must be equal (as tested by `Base.isequal` function). Hence this rule says: if you see something added to itself, make it twice of that thing, and works as such.

If you try to apply this rule to an expression where the two summands are not equal, it will return `nothing` – this is the way a rule signifies failure to match.

``r1(sin(1+z) + sin(1+w)) === nothing``
``true``

If you want to match a variable number of subexpressions at once, you will need a segment variable. `~~xs` in the following example is a segment variable:

``````@syms x y z
@rule(+(~~xs) => ~~xs)(x + y + z)``````
``````3-element view(::Array{SymbolicUtils.Sym{Number},1}, 1:3) with eltype SymbolicUtils.Sym{Number}:
x
y
z``````

`~~xs` is a vector of subexpressions matched. You can use it to construct something more useful:

``````r2 = @rule ~x * +(~~ys) => sum(map(y-> ~x * y, ~~ys));

showraw(r2(2 * (w+w+α+β)))``````
``4w + 2α + 2β``

Notice that there is a subexpression `(2 * w) + (2 * w)` that could be simplified by the previous rule `r1`. Can we chain `r2` and `r1`?

### Predicates for matching

Matcher pattern may contain slot variables with attached predicates, written as `~x::f` where `f` is a function that takes a matched expression and returns a boolean value. Such a slot will be considered a match only if `f` returns true.

Similarly `~~x::g` is a way of attaching a predicate `g` to a segment variable. In the case of segment variables `g` gets a vector of 0 or more expressions and must return a boolean value. If the same slot or segment variable appears twice in the matcher pattern, then at most one of the occurance should have a predicate.

For example,

``````r = @rule ~x + ~~y::(ys->iseven(length(ys))) => "odd terms"

@show r(w + z + z + w)
@show r(w + z + z)
@show r(w + z)``````
``````r(w + z + z + w) = nothing
r(w + z + z) = nothing
r(w + z) = nothing
``````

### Associative-Commutative Rules

Given an expression `f(x, f(y, z, u), v, w)`, a `f` is said to be associative if the expression is equivalent to `f(x, y, z, u, v, w)` and commutative if the order of arguments does not matter. SymbolicUtils has a special `@acrule` macro meant for rules on functions which are associate and commutative such as addition and multiplication of real and complex numbers.

``````@syms x y

acr = @acrule((~y)^(~n) * ~y => (~y)^(~n+1))

acr(x^2 * y * x)``````

## Composing rewriters

A rewriter is any callable object 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 Rules we created above are rewriters.

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

Example using Postwalk, and Chain

``````using SymbolicUtils
using SymbolicUtils.Rewriters

r1 = @rule ~x + ~x => 2 * (~x)
r2 = @rule ~x * +(~~ys) => sum(map(y-> ~x * y, ~~ys));

rset = Postwalk(Chain([r1, r2]))
rset_result = rset(2 * (w+w+α+β))

showraw(rset_result)``````
``4w + 2α + 2β``

It applied `r1`, but didn't get the opportunity to apply `r2`. So we need to apply the ruleset again on the result.

``showraw(rset(rset_result))``
``4w + 2α + 2β``

You can also use `Fixpoint` to apply the rules until there are no changes.

``showraw(Fixpoint(rset)(2 * (w+w+α+β)))``
``4w + 2α + 2β``

## Simplification

The `simplify` function applies a built-in set of rules to rewrite expressions in order to simplify it.

``showraw(simplify(2 * (w+w+α+β + sin(z)^2 + cos(z)^2 - 1)))``
``2(α + β + 2w)``

The rules in the default simplify applies simple constant elemination, trigonometric identities.

If you read the previous section on the rules DSL, you should be able to read and understand the rules that are used by `simplify`.