Matchers · RewriteTools.jl

Rule-based rewriting

Rewrite rules match and transform an expression. A rule is written using the @rule macro and creates a callable Rule object.

Basics of Rule-based Term Rewriting in RewriteTools

Here is a simple rewrite rule, that uses the formula for the double angle of the sine function:

julia> using RewriteTools

julia> r1 = @rule :call(:sin, :call(:*, 2, ~x)) => :(2 * sin($x) * cos($x))
(:call)(:sin, (:call)(:*, 2, ~x)) => Core._expr(:call, :*, 2, Core._expr(:call, :sin, x), Core._expr(:call, :cos, x))

julia> r1(:(sin(2 * z)))
:(2 * sin(z) * cos(z))

The @rule macro pairs a matcher pattern with its consequent (@rule matcher => consequent). When an expression matches the matcher, it's rewritten to the consequent pattern. This rule signifies: if an expression fits the sin(2x) pattern, it's transformed to 2sin(x)cos(x).

Applying the rule to a non-matching expression results in nothing, indicating a mismatch:

julia> r1(:(sin(3 * z))) === nothing
true

Slot variables can match complex expressions:

julia> r1(:(sin(2 * (w - z))))
:(2 * sin(w - z) * cos(w - z))

But they must represent a single, unified expression:

julia> r1(:(sin(2 * (w + z) * (α + β)))) === nothing
true

Rules can incorporate multiple slot variables:

julia> r2 = @rule :call(:sin, :call(:+, ~x, ~y)) => :(sin($x) * cos($y) + cos($x) * sin($y))
(:call)(:sin, (:call)(:+, ~x, ~y)) => Core._expr(:call, :+, Core._expr(:call, :*, Core._expr(:call, :sin, x), Core._expr(:call, :cos, y)), Core._expr(:call, :*, Core._expr(:call, :cos, x), Core._expr(:call, :sin, y)))

julia> r2(:(sin(α + β)))
:(sin(α) * cos(β) + cos(α) * sin(β))

For matching a variable number of subexpressions, segment variables like ~~xs are used:

julia> r3 = @rule :call(:+, ~~xs) => :(sum($xs))
(:call)(:+, ~(~xs)) => Core._expr(:call, :sum, xs)

julia> r3(:(x + y + z))
:(sum(Any[:x, :y, :z]))

Segment variables match vectors of subexpressions, useful for constructing complex transformations:

julia> r4 = @rule :call(:*, ~x, :call(:+, ~~ys)) => :(+($(map(y -> :($x * $y), ys)...)))
(:call)(:*, ~x, (:call)(:+, ~(~ys))) => Core._expr(:call, :+, map((y->begin
                    #= none:1 =#
                    Core._expr(:call, :*, x, y)
                end), ys)...)

julia> r4(:(2 * +(w, w, α, β)))
:(2w + 2w + 2α + 2β)

Predicates for Matching

Matcher patterns may include slot variables with predicates (~x::f), where f is a function that evaluates the matched expression. Similarly, ~~x::g attaches a predicate g to a segment variable.

Example with predicates:

julia> r5 = @rule :call(:+, ~x, ~~y::(ys -> iseven(length(ys)))) => "odd number of terms"
(:call)(:+, ~x, ~(~(y::(ys->begin
                            #= none:1 =#
                            iseven(length(ys))
                        end)))) => "odd number of terms"

julia> @show r5(:(a + b + c + d))
r5($(Expr(:quote, :(a + b + c + d)))) = nothing

julia> @show r5(:(b + c + d))
r5($(Expr(:quote, :(b + c + d)))) = "odd number of terms"
"odd number of terms"

julia> @show r5(:(b + c + b))
r5($(Expr(:quote, :(b + c + b)))) = "odd number of terms"
"odd number of terms"

julia> @show r5(:(b + c))
r5($(Expr(:quote, :(b + c)))) = nothing

Simplifying Expressions with Rules

To simplify expressions like (sin(x) + cos(x))^2, rules are applied:

julia> sqexpand = @rule :call(:^, :call(:+, ~x, ~y), 2) => :((($x)^2 + ($y)^2 + 2 * $x * $y))
(:call)(:^, (:call)(:+, ~x, ~y), 2) => Core._expr(:call, :+, Core._expr(:call, :^, x, 2), Core._expr(:call, :^, y, 2), Core._expr(:call, :*, 2, x, y))

julia> sqexpand(:((sin(x) + cos(x))^2))
:(sin(x) ^ 2 + cos(x) ^ 2 + 2 * sin(x) * cos(x))

Docs

RewriteTools.@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 expression, returns nothing otherwise. The rule language is described below.

LHS can be any possibly nested function call expression where any of the arguments can optionally be a Slot (~x) or a Segment (~x...) (described below).

If an expression matches LHS entirely, then it is rewritten to the result of the expression RHS, whose local scope includes the slot matches as variables.

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

Segment:

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

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:

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

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

julia> @syms a b;

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