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

No documentation found.

Summary

struct SymbolicUtils.Sym{T}

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.

No documentation found.

Summary

struct SymbolicUtils.Term{T}

No documentation found.

Summary

struct SymbolicUtils.Add{T}

No documentation found.

Summary

struct SymbolicUtils.Mul{T}

No documentation found.

Summary

struct SymbolicUtils.Pow{T}

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

istree(x)

Returns true if x is a term. If true, operation, arguments must also be defined for x appropriately.

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.

arguments(x)

Get the arguments of x, must be defined if istree(x) is true.

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

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.

Arguments

• t the reference term to use to create similar terms

• f is the operation of the term

• args is the arguments

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

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

Imports

• Base

• Base.Threads

• Core

• TermInterface

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.

By default, simplify will assume denominators are not zero and allow cancellation in fractions. Pass simplify_fractions=false to prevent this.

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.

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)

@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
 ────────────────────────────────────────────────────────────────────────────────────────────────
 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)

Signatures

Methods