Composing Rewriters
Rewriters are powerful tools for transforming expressions. They can be composed and chained together to create sophisticated transformations.
Overview of Composing Rewriters
A rewriter is any callable object that takes an expression and returns either a new expression or nothing. Nothing indicates no applicable changes. The RewriteTools.Rewriters module provides several types of rewriters:
Empty(): Always returnsnothing.Chain(itr): Chains an iterator of rewriters into a single rewriter. Each rewriter is applied in sequence.RestartedChain(itr): Similar toChain(itr)but restarts from the first rewriter after a successful application.IfElse(cond, rw1, rw2): Appliesrw1ifcondreturns true, otherwiserw2.If(cond, rw): Equivalent toIfElse(cond, rw, Empty()).Prewalk(rw): Performs a pre-order traversal of an expression, applyingrwat each step.Postwalk(rw): Post-order traversal, applyingrw.Fixpoint(rw): Repeatedly appliesrwuntil no further changes occur.Prestep(rw): Recursively rewrites each node usingrw. Only recurses ifrwis not nothing.Rewrite(rw): Ifrw(x)returnsnothing,Rewritereturnsxinstead.
Chaining Rewriters
Rewriters can be combined into a chain, allowing multiple rules to be applied sequentially:
julia> using RewriteTools
julia> using RewriteTools.Rewriters
julia> powexpand = @rule :call(:^, ~x, ~n) => :($x * $x^$(n - 1))
(:call)(:^, ~x, ~n) => Core._expr(:call, :*, x, Core._expr(:call, :^, x, n - 1))
julia> powid = @rule :call(:^, ~x, 1) => :($x)
(:call)(:^, ~x, 1) => x
julia> cas = Chain([powexpand, powid])
Chain{Vector{RewriteTools.Rule{RewriteTools.Term}}}(RewriteTools.Rule{RewriteTools.Term}[(:call)(:^, ~x, ~n) => Core._expr(:call, :*, x, Core._expr(:call, :^, x, n - 1)), (:call)(:^, ~x, 1) => x])
julia> cas(:((sin(x) + cos(x))^2))
:((sin(x) + cos(x)) * (sin(x) + cos(x)) ^ 1)An important feature of Chain is that it returns nothing if there are no changes:
julia> Chain([powid, powexpand])(:(x + y))
Postwalk allows us to further rewrite subterms of our expressions.
julia> cas2 = Postwalk(Chain([powid, powexpand]))
Postwalk{Chain{Vector{RewriteTools.Rule{RewriteTools.Term}}}}(Chain{Vector{RewriteTools.Rule{RewriteTools.Term}}}(RewriteTools.Rule{RewriteTools.Term}[(:call)(:^, ~x, 1) => x, (:call)(:^, ~x, ~n) => Core._expr(:call, :*, x, Core._expr(:call, :^, x, n - 1))]))
julia> cas2(:((sin(x) + cos(x)) * (sin(x) + cos(x)) ^ 1))
:((sin(x) + cos(x)) * (sin(x) + cos(x)))Fixpoint allows us to rewrite until no changes can be made
julia> cas3 = Fixpoint(Postwalk(Chain([powid, powexpand])))
Fixpoint{Postwalk{Chain{Vector{RewriteTools.Rule{RewriteTools.Term}}}}}(Postwalk{Chain{Vector{RewriteTools.Rule{RewriteTools.Term}}}}(Chain{Vector{RewriteTools.Rule{RewriteTools.Term}}}(RewriteTools.Rule{RewriteTools.Term}[(:call)(:^, ~x, 1) => x, (:call)(:^, ~x, ~n) => Core._expr(:call, :*, x, Core._expr(:call, :^, x, n - 1))])))
julia> cas3(:((sin(x) + cos(x))^4))
:((sin(x) + cos(x)) * ((sin(x) + cos(x)) * ((sin(x) + cos(x)) * (sin(x) + cos(x)))))RewriteTools.Rewriters.IfElse — Type`IfElse(cond, rw1, rw2)`
Returns a function which runs the `cond` function on the input, applies
`rw1` if cond returns true, `rw2` if it retuns false. For example, one
might set `rw2` to `NoRewrite()` or `NoSaturate()`RewriteTools.Rewriters.Rewrite — TypeRewrite(rw)
A rewriter which returns the original argument even if `rw` returns nothingRewriteTools.Rewriters.NoRewrite — TypeNoRewrite()
A rewriter which always returns `nothing`RewriteTools.Rewriters.Fixpoint — Type`Fixpoint(rw)`
An rewriter which repeatedly applies `rw` to `x` until no changes are made. If
the rewriter first returns `nothing`, returns `nothing`.RewriteTools.Rewriters.Prewalk — Type`Prewalk(rw)`
An rewriter which recursively rewrites each node using `rw`, then rewrites
the arguments of the resulting node. If all rewriters return `nothing`,
returns `nothing`.RewriteTools.Rewriters.Postwalk — Type`Postwalk(rw)`
An rewriter which recursively rewrites the arguments of each node using
`rw`, then rewrites the resulting node. If all rewriters return `nothing`,
returns `nothing`.RewriteTools.Rewriters.Chain — Type`Chain(itr)`
An rewriter which rewrites using each rewriter in `itr`. If all rewriters
return `nothing`, return `nothing`.RewriteTools.Rewriters.Prestep — Type`Prestep(rw)`
An rewriter which recursively rewrites each node using `rw`. If `rw` is
nothing, it returns `nothing`, otherwise it recurses to the arguments.