tree ← #.exp.reduce tree ⍝ Reduce expression tree.
[reduce] simplifies an expression tree by looking for patterns and replacing
them with simpler equivalents according to a set of _rules_ For example, (x+0)
may be reduced to just (x), for any expression x.
[rules] is a vector of trees, whose principal operator is '=' and whose left and
right subtrees are "find" and "replace" patterns, respectively. For example, the
"factoring" rule: (i*x)+(j*x) = (i+j)*x, produces the tree:
=
┌───┴───┐
+ *
┌─┴─┐ ┌─┴┐
* * + x
┌┴┐ ┌┴┐ ┌┴┐
i x j x i j
For example, the rules from the →#.math← definition vector are:
load math
#.exp.(2 show¨rules)
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
┌─┴─┐ ┌─┴┐ ┌─┴┐ ┌─┴┐ ┌─┴┐ ┌─┴─┐ ┌──┴─┐ ┌───┴─┐ ┌─┴┐ ┌──┴┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴───┐ ┌─┴───┐ ┌───┴───┐ ┌───┴───┐ ┌───┴───┐ ┌─┴───┐ ┌─┴───┐ ┌─┴───┐ ┌─┴───┐ ┌─┴─┐ ┌─┴─┐ ┌───┴───┐ ┌───┴───┐ ┌───┴───┐ ┌───┴───┐ ┌───┴───┐ ┌───┴───┐ ┌─┴─┐ ┌─┴┐ ┌─┴┐ ┌─┴┐ ┌─┴┐ ┌─┴┐ ┌─┴┐ ┌──┴┐ ┌───┴───┐ ┌───┴───┐ ┌───┴───┐ ┌───┴───┐ ┌───┴───┐ ┌───┴───┐ ┌─┴───┐ ┌─┴───┐ ┌─┴─┐ ┌───┴─┐ ┌───┴─┐ ┌───┴───┐ ┌───┴───┐ ┌───┴───┐ ┌───┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴───┐ ┌─┴───┐ ┌─┴┐ ┌─┴┐ ┌─┴─┐ ┌─┴─┐ ┌───┴─┐ ┌───┴─┐ ┌─┴─┐ ┌─┴─┐ ┌───┴─┐ ┌───┴─┐ ┌───┴─┐ ┌─┴─┐ ┌─┴───┐ ┌───┴───┐ ┌─┴───┐ ┌───┴───┐ ┌───┴─┐ ┌───┴───┐ ┌───┴─┐ ┌───┴───┐ ┌───┴───┐ ┌───┴──┐ ┌─┴┐ ┌─┴┐ ┌─┴───┐ ┌─┴───┐ ┌─┴┐ ┌─┴─────┐ ┌─┴─────┐ ┌─┴───────────┐ ┌─┴───┐ ┌─┴───┐ ┌─┴───┐ ┌─┴────┐ ┌─┴─────┐
+ + + x - x - - - 0 + - + - - - - - - x + + - - - + + - + - - - - - - - - + + + - + + - - - + - - - - - - + - - + + + - + + * * * 0 * x / 0 * - / 1 * - * - * * * / / / / * * * / / / / / * / / * * * * / / / / * / / * * * / * * * / / / / * / ∧ 1 ∧ x * ∧ * ∧ * ∧ / ∧ / ∧ ∧ ∧ / ∧ * ∧ / ∧ + * + * + * - * - * + * + * - * - * * * / tan ∆ 0 ∆ 1 ∆ + ∆ - ∆ - ∆ + ∆ - ∆ + ∆ / ∆ * ∆ * ∆ * ∆ /
┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ └┐ ┌┴┐ ┌─┴┐ ┌┴┐ ┌┴┐ ┌┴┐ └─┐ ┌┴┐ ┌─┴┐ └─┐ └┐ ┌─┴┐ ┌┴─┐ ┌─┴┐ ┌┴─┐ ┌─┴┐ ┌┴─┐ ┌─┴┐ ┌┴─┐ ┌─┴┐ ┌─┴┐ ┌─┴┐ ┌─┴┐ ┌┴─┐ ┌─┴┐ ┌┴─┐ ┌─┴┐ ┌┴─┐ ┌─┴┐ ┌─┴┐ ┌─┴┐ ┌─┴┐ ┌─┴┐ ┌─┴┐ ┌─┴┐ ┌─┴┐ ┌─┴┐ ┌─┴┐ ┌┴─┐ ┌─┴┐ ┌┴─┐ ┌┴─┐ ┌─┴┐ ┌┴─┐ ┌─┴┐ ┌┴─┐ ┌─┴┐ ┌┴─┐ ┌─┴┐ ┌┴─┐ ┌─┴┐ ┌┴─┐ ┌─┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌─┴┐ └┐ ┌┴┐ ┌─┴┐ └─┐ ┌┴┐ └─┐ ┌┴─┐ ┌─┴┐ ┌┴─┐ ┌─┴┐ ┌┴─┐ ┌─┴┐ ┌┴─┐ ┌─┴┐ ┌┴─┐ ┌─┴┐ ┌┴─┐ ┌─┴┐ ┌─┴┐ ┌─┴┐ ┌─┴┐ ┌─┴┐ ┌─┴┐ ┌┴─┐ ┌┴─┐ ┌┴─┐ ┌┴─┐ ┌┴─┐ ┌┴─┐ ┌─┴┐ ┌┴─┐ ┌─┴┐ ┌┴─┐ ┌─┴┐ ┌┴─┐ ┌┴─┐ ┌─┴┐ ┌┴─┐ ┌─┴┐ ┌┴─┐ ┌─┴┐ ┌┴─┐ ┌─┴┐ ┌┴─┐ ┌─┴┐ ┌─┴┐ ┌─┴┐ ┌─┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌─┴┐ ┌┴─┐ ┌┴─┐ ┌┴─┐ ┌┴─┐ ┌┴─┐ ┌─┴┐ ┌┴─┐ ┌─┴┐ ┌┴─┐ ┌─┴─┐ ┌┴─┐ ┌─┴─┐ ┌┴─┐ ┌─┴─┐ ┌┴─┐ ┌┴┐ ┌┴┐ ┌─┴┐ ┌─┴┐ ┌┴─┐ ┌─┴┐ ┌─┴┐ ┌─┴┐ ┌┴─┐ ┌─┴┐ ┌─┴─┐ ┌┴─┐ ┌─┴─┐ ┌─┴┐ ┌─┴─┐ ┌┴─┐ ┌─┴─┐ ┌─┴┐ ┌──┴──┐ ┌──┴──┐ ┌──┴──┐ └┐ ┌┴┐ ┌┴┐ ┌─┴┐ ┌─┴─┐ ┌─┴┐ ┌─┴─┐ ┌─┴┐ └─┐ ┌─┴┐ ┌─┴─┐ ┌─┴┐ ┌─┴─────┐ ┌─┴┐ ┌─────┴──────┐ ┌─┴┐ ┌─┴┐ ┌──┴┐ ┌─┴──┐ ┌──┴┐ ┌─┴──┐ ┌──┴┐ ┌───┴──┐ ┌──┴┐ ┌─┴───┐
i x x i x 0 x 0 0 x x x x - y y x x - x y - y x - y + - + j x + - j x + + j x - - j x - - j + x - j - x i + - x i - + x i - - x + y + i + y - i - y + i - y - i - y i - - y i + x + - i x - - i x - + i x + + i x - + i x - - i x i i x 0 x 1 x 0 x ¯1 x x x x - y * x - * i * * x i / * x i * / x i / / x i / / x i / * x / j / x * j / x / j x * x * i * x / i / x * / i x / * i x / * i x / i / * y i * * y i / / y i / / y i * / y / i / y * i x 0 x 1 x x x 2 ∧ x x + x ∧ x + x ∧ x - ∧ x x - ∧ q x * ∧ ∧ x - ∧ ∧ p + ∧ ∧ p - p p 2 p * q + q p * + p * q - q p * - p * * p + * * + r * * p - * * - r cos sin sin cos sin cos x i a a a + a ∆ ∆ - a ∆ ∆ - a ∆ * a * * / a / / ∧ a * * ln a ∆ p exp a ∆ exp sin a ∆ cos cos a - sin tan a * ∧
└┐ └┐ ┌┴┐ └┐ ┌┴┐ └┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ └┐ ┌┴┐ └┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ └┐ └┐ └┐ └┐ └┐ └┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ └┐ ┌┴┐ ┌┴┐ ┌─┴┐ ┌┴─┐ ┌┴┐ ┌─┴┐ ┌───┴─┐ ┌┴┐ ┌─┴─┐ ┌──┴─┐ └┐ ┌┴┐ └┐ ┌┴┐ └┐ └┐ ┌┴┐ └┐ └┐ └─┐ └┐ └┐ ┌─┴┐ ┌──┴┐
x y x y x x y x x i i j x i i j x i i j x i i j i x i j i x i j x j i j x j i j j x i j x i x y x i x y x i x y x i x y i x x y i x x y y i x y y i x y i y x y y i x y y i x y i y x y x x y y x y j x i j j x i j j x i j j x i j x j i j x j i j i x i j i x i j x i i j i y x y i y x y i y x y i y x y y i x y y i x y i x x y i x x y i x y x i x x y x i x y x i x y x p p 1 x p p 1 x p 1 p x p p 1 x p p q x p x q p q p q p r q r p q p r q r p q p 1 q p q 1 p q p 1 q p 1 q p q p r q r p r q r p q p q p r q r q r q r p q q p p q x x p q p a q a p q p a q a p p a p q ∆ q p ∆ p q ∆ q * ∧ p q * ∧ * ∧ p p a p p a p p p a p p ∆ p p ∆ 1 cos 2
┌┴┐ ┌┴┐ ┌┴┐ ┌┴─┐ ┌┴┐ ┌─┴┐ ┌┴─┐ ┌─┴─┐ ┌┴┐ ┌┴┐ ┌┴┐ └┐
p a q a p a p ∆ q 2 ∆ q p - ∆ ln p q p a p a p
┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ └┐
Within the trees, variables i, j, k stand for (and match) literal numbers 0, 2, q a p a q 1 q a p
¯3.4, ···; ¯i, ¯j, ¯k match any _negative_ literal numbers ¯2, ¯4.5, ···; x, y,
z stand for arbitrary expressions, not including literal numbers; and p, q, r, s
and t stand for any values. See →Expression_simplification←.
As an example, the first reduction tree above (i+x=x+i) reverses sums to put a
literal constant on the right. In this way, literals are collected and may be
evaluated: 2+x+3 => x+2+3 => x+5. "Metavariables" a, b, c are used by the deriv-
ative reductions to represent expression variables x, y, z.
Technical note:
The reduction rules in the source vector attempt to bring together constant
terms, so that they may be evaluated. By convention, constant terms are placed
to the left of '*' and to the right of '+'. For example:
5+4*x*3+2
¯¯ ¯¯
→ 4*x*3+5+2
¯¯¯
→ 4*x*3+7
¯¯¯¯¯
→ 4*3*x+7
¯¯¯
→ 12*x+7
[reduce] is an example of a "term rewriting system", a subject on which there is
a large and growing technical literature. See →Differentiation← for an example
of the challenges that such systems face.
Examples:
math script until'→'
1+x+2 ⍝ constants collected to the right.
x+3
(x-y)∧(3-2) ⍝ x∧1 => x
x-y
(2*x)+(x*3) ⍝ * factoring
5*x
x∧2*x∧3 ⍝ ∧ factoring
x∧5
→
See also: →Expression_simplification←
Back to: →Implementation_Details←