SymbolicUtils.jl

API Reference

Symbols and Terms

@syms
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.

Examples:

  • @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 f. 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.

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

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

Term
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

promote_symtype
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 Terms 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.

Interfacing

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

operation
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

arguments
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

similarterm
fn

similarterm(t, f, args)

Create a term that is similar in type to t. If t is a Term will create a Term with the same symtype Otherwise simply calls f(args...) by default.

Rewriters

@rule
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 ~x - ~y => ~x + (-(~y))
~x - ~y => ~x + -(~y)

julia> r(a-2b)
(a + (-(2 * 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.

module

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

Simplify

simplify
fn

simplify(x; rewriter=defaultsimplifier(), threaded=false, polynorm=true, threadsubtree_cutoff=100)

Simplify an expression (x) by applying rewriter until there are no changes. polynorm=true applies polynormalize in the beginning of each fixpoint iteration.

substitute
fn

substitute(expr, dict)

substitute any subexpression that matches a key in dict with the corresponding value.

Utilities

@timerewrite
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.

Example:

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)