calc: Rewrites Tutorial
3.5.2 Rewrite Rules
-------------------
No matter how many built-in commands Calc provided for doing algebra,
there would always be something you wanted to do that Calc didn’t have
in its repertoire. So Calc also provides a “rewrite rule” system that
you can use to define your own algebraic manipulations.
Suppose we want to simplify this trigonometric formula:
1: 2 sec(x)^2 / tan(x)^2 - 2 / tan(x)^2
.
' 2sec(x)^2/tan(x)^2 - 2/tan(x)^2 <RET> s 1
If we were simplifying this by hand, we’d probably combine over the
common denominator. The ‘a n’ algebra command will do this, but we’ll
do it with a rewrite rule just for practice.
Rewrite rules are written with the ‘:=’ symbol.
1: (2 sec(x)^2 - 2) / tan(x)^2
.
a r a/x + b/x := (a+b)/x <RET>
(The “assignment operator” ‘:=’ has several uses in Calc. All by itself
the formula ‘a/x + b/x := (a+b)/x’ doesn’t do anything, but when it is
given to the ‘a r’ command, that command interprets it as a rewrite
rule.)
The lefthand side, ‘a/x + b/x’, is called the “pattern” of the
rewrite rule. Calc searches the formula on the stack for parts that
match the pattern. Variables in a rewrite pattern are called
“meta-variables”, and when matching the pattern each meta-variable can
match any sub-formula. Here, the meta-variable ‘a’ matched the
expression ‘2 sec(x)^2’, the meta-variable ‘b’ matched the constant ‘-2’
and the meta-variable ‘x’ matched the expression ‘tan(x)^2’.
This rule points out several interesting features of rewrite
patterns. First, if a meta-variable appears several times in a pattern,
it must match the same thing everywhere. This rule detects common
denominators because the same meta-variable ‘x’ is used in both of the
denominators.
Second, meta-variable names are independent from variables in the
target formula. Notice that the meta-variable ‘x’ here matches the
subformula ‘tan(x)^2’; Calc never confuses the two meanings of ‘x’.
And third, rewrite patterns know a little bit about the algebraic
properties of formulas. The pattern called for a sum of two quotients;
Calc was able to match a difference of two quotients by matching ‘a = 2
sec(x)^2’, ‘b = -2’, and ‘x = tan(x)^2’.
When the pattern part of a rewrite rule matches a part of the
formula, that part is replaced by the righthand side with all the
meta-variables substituted with the things they matched. So the result
is ‘(2 sec(x)^2 - 2) / tan(x)^2’.
We could just as easily have written ‘a/x - b/x := (a-b)/x’ for the
rule. It would have worked just the same in all cases. (If we really
wanted the rule to apply only to ‘+’ or only to ‘-’, we could have used
the ‘plain’ symbol. 
Algebraic Properties of Rewrite Rules, for
some examples of this.)
One more rewrite will complete the job. We want to use the identity
‘tan(x)^2 + 1 = sec(x)^2’, but of course we must first rearrange the
identity in a way that matches our formula. The obvious rule would be
‘2 sec(x)^2 - 2 := 2 tan(x)^2’, but a little thought shows that the rule
‘sec(x)^2 := 1 + tan(x)^2’ will also work. The latter rule has a more
general pattern so it will work in many other situations, too.
1: 2
.
a r sec(x)^2 := 1 + tan(x)^2 <RET>
You may ask, what’s the point of using the most general rule if you
have to type it in every time anyway? The answer is that Calc allows
you to store a rewrite rule in a variable, then give the variable name
in the ‘a r’ command. In fact, this is the preferred way to use
rewrites. For one, if you need a rule once you’ll most likely need it
again later. Also, if the rule doesn’t work quite right you can simply
Undo, edit the variable, and run the rule again without having to retype
it.
' a/x + b/x := (a+b)/x <RET> s t merge <RET>
' sec(x)^2 := 1 + tan(x)^2 <RET> s t secsqr <RET>
1: 2 sec(x)^2 / tan(x)^2 - 2 / tan(x)^2 1: 2
. .
r 1 a r merge <RET> a r secsqr <RET>
To edit a variable, type ‘s e’ and the variable name, use regular
Emacs editing commands as necessary, then type ‘C-c C-c’ to store the
edited value back into the variable. You can also use ‘s e’ to create a
new variable if you wish.
Notice that the first time you use each rule, Calc puts up a
“compiling” message briefly. The pattern matcher converts rules into a
special optimized pattern-matching language rather than using them
directly. This allows ‘a r’ to apply even rather complicated rules very
efficiently. If the rule is stored in a variable, Calc compiles it only
once and stores the compiled form along with the variable. That’s
another good reason to store your rules in variables rather than
entering them on the fly.
(•) *Exercise 1.* Type ‘m s’ to get Symbolic mode, then enter the
formula ‘(2 + sqrt(2)) / (1 + sqrt(2))’. Using a rewrite rule, simplify
this formula by multiplying the top and bottom by the conjugate
‘1 - sqrt(2)’. The result will have to be expanded by the distributive
law; do this with another rewrite. 1 Rewrites Answer 1. (•)
The ‘a r’ command can also accept a vector of rewrite rules, or a
variable containing a vector of rules.
1: [merge, secsqr] 1: [a/x + b/x := (a + b)/x, ... ]
. .
' [merge,sinsqr] <RET> =
1: 2 sec(x)^2 / tan(x)^2 - 2 / tan(x)^2 1: 2
. .
s t trig <RET> r 1 a r trig <RET>
Calc tries all the rules you give against all parts of the formula,
repeating until no further change is possible. (The exact order in
which things are tried is rather complex, but for simple rules like the
ones we’ve used here the order doesn’t really matter. Nested
Formulas with Rewrite Rules.)
Calc actually repeats only up to 100 times, just in case your rule
set has gotten into an infinite loop. You can give a numeric prefix
argument to ‘a r’ to specify any limit. In particular, ‘M-1 a r’ does
only one rewrite at a time.
1: (2 sec(x)^2 - 2) / tan(x)^2 1: 2
. .
r 1 M-1 a r trig <RET> M-1 a r trig <RET>
You can type ‘M-0 a r’ if you want no limit at all on the number of
rewrites that occur.
Rewrite rules can also be “conditional”. Simply follow the rule with
a ‘::’ symbol and the desired condition. For example,
1: sin(x + 2 pi) + sin(x + 3 pi) + sin(x + 4 pi)
.
' sin(x+2pi) + sin(x+3pi) + sin(x+4pi) <RET>
1: sin(x + 3 pi) + 2 sin(x)
.
a r sin(a + k pi) := sin(a) :: k % 2 = 0 <RET>
(Recall, ‘k % 2’ is the remainder from dividing ‘k’ by 2, which will be
zero only when ‘k’ is an even integer.)
An interesting point is that the variable ‘pi’ was matched literally
rather than acting as a meta-variable. This is because it is a
special-constant variable. The special constants ‘e’, ‘i’, ‘phi’, and
so on also match literally. A common error with rewrite rules is to
write, say, ‘f(a,b,c,d,e) := g(a+b+c+d+e)’, expecting to match any ‘f’
with five arguments but in fact matching only when the fifth argument is
literally ‘e’!
Rewrite rules provide an interesting way to define your own
functions. Suppose we want to define ‘fib(n)’ to produce the Nth
Fibonacci number. The first two Fibonacci numbers are each 1; later
numbers are formed by summing the two preceding numbers in the sequence.
This is easy to express in a set of three rules:
' [fib(1) := 1, fib(2) := 1, fib(n) := fib(n-1) + fib(n-2)] <RET> s t fib
1: fib(7) 1: 13
. .
' fib(7) <RET> a r fib <RET>
One thing that is guaranteed about the order that rewrites are tried
is that, for any given subformula, earlier rules in the rule set will be
tried for that subformula before later ones. So even though the first
and third rules both match ‘fib(1)’, we know the first will be used
preferentially.
This rule set has one dangerous bug: Suppose we apply it to the
formula ‘fib(x)’? (Don’t actually try this.) The third rule will match
‘fib(x)’ and replace it with ‘fib(x-1) + fib(x-2)’. Each of these will
then be replaced to get ‘fib(x-2) + 2 fib(x-3) + fib(x-4)’, and so on,
expanding forever. What we really want is to apply the third rule only
when ‘n’ is an integer greater than two. Type ‘s e fib <RET>’, then
edit the third rule to:
fib(n) := fib(n-1) + fib(n-2) :: integer(n) :: n > 2
Now:
1: fib(6) + fib(x) + fib(0) 1: fib(x) + fib(0) + 8
. .
' fib(6)+fib(x)+fib(0) <RET> a r fib <RET>
We’ve created a new function, ‘fib’, and a new command, ‘a r fib <RET>’,
which means “evaluate all ‘fib’ calls in this formula.” To make things
easier still, we can tell Calc to apply these rules automatically by
storing them in the special variable ‘EvalRules’.
1: [fib(1) := ...] . 1: [8, 13]
. .
s r fib <RET> s t EvalRules <RET> ' [fib(6), fib(7)] <RET>
It turns out that this rule set has the problem that it does far more
work than it needs to when ‘n’ is large. Consider the first few steps
of the computation of ‘fib(6)’:
fib(6) =
fib(5) + fib(4) =
fib(4) + fib(3) + fib(3) + fib(2) =
fib(3) + fib(2) + fib(2) + fib(1) + fib(2) + fib(1) + 1 = ...
Note that ‘fib(3)’ appears three times here. Unless Calc’s algebraic
simplifier notices the multiple ‘fib(3)’s and combines them (and, as it
happens, it doesn’t), this rule set does lots of needless recomputation.
To cure the problem, type ‘s e EvalRules’ to edit the rules (or just ‘s
E’, a shorthand command for editing ‘EvalRules’) and add another
condition:
fib(n) := fib(n-1) + fib(n-2) :: integer(n) :: n > 2 :: remember
If a ‘:: remember’ condition appears anywhere in a rule, then if that
rule succeeds Calc will add another rule that describes that match to
the front of the rule set. (Remembering works in any rule set, but for
technical reasons it is most effective in ‘EvalRules’.) For example, if
the rule rewrites ‘fib(7)’ to something that evaluates to 13, then the
rule ‘fib(7) := 13’ will be added to the rule set.
Type ‘' fib(8) <RET>’ to compute the eighth Fibonacci number, then
type ‘s E’ again to see what has happened to the rule set.
With the ‘remember’ feature, our rule set can now compute ‘fib(N)’ in
just N steps. In the process it builds up a table of all Fibonacci
numbers up to N. After we have computed the result for a particular N,
we can get it back (and the results for all smaller N) later in just one
step.
All Calc operations will run somewhat slower whenever ‘EvalRules’
contains any rules. You should type ‘s u EvalRules <RET>’ now to
un-store the variable.
(•) *Exercise 2.* Sometimes it is possible to reformulate a problem
to reduce the amount of recursion necessary to solve it. Create a rule
that, in about N simple steps and without recourse to the ‘remember’
option, replaces ‘fib(N, 1, 1)’ with ‘fib(1, X, Y)’ where X and Y are
the Nth and N+1st Fibonacci numbers, respectively. This rule is rather
clunky to use, so add a couple more rules to make the “user interface”
the same as for our first version: enter ‘fib(N)’, get back a plain
number. 2 Rewrites Answer 2. (•)
There are many more things that rewrites can do. For example, there
are ‘&&&’ and ‘|||’ pattern operators that create “and” and “or”
combinations of rules. As one really simple example, we could combine
our first two Fibonacci rules thusly:
[fib(1 ||| 2) := 1, fib(n) := ... ]
That means “‘fib’ of something matching either 1 or 2 rewrites to 1.”
You can also make meta-variables optional by enclosing them in ‘opt’.
For example, the pattern ‘a + b x’ matches ‘2 + 3 x’ but not ‘2 + x’ or
‘3 x’ or ‘x’. The pattern ‘opt(a) + opt(b) x’ matches all of these
forms, filling in a default of zero for ‘a’ and one for ‘b’.
(•) *Exercise 3.* Your friend Joe had ‘2 + 3 x’ on the stack and
tried to use the rule ‘opt(a) + opt(b) x := f(a, b, x)’. What happened?
3 Rewrites Answer 3. (•)
(•) *Exercise 4.* Starting with a positive integer ‘a’, divide ‘a’
by two if it is even, otherwise compute ‘3 a + 1’. Now repeat this step
over and over. A famous unproved conjecture is that for any starting
‘a’, the sequence always eventually reaches 1. Given the formula
‘seq(A, 0)’, write a set of rules that convert this into ‘seq(1, N)’
where N is the number of steps it took the sequence to reach the value
1. Now enhance the rules to accept ‘seq(A)’ as a starting
configuration, and to stop with just the number N by itself. Now make
the result be a vector of values in the sequence, from A to 1. (The
formula ‘X|Y’ appends the vectors X and Y.) For example, rewriting
‘seq(6)’ should yield the vector ‘[6, 3, 10, 5, 16, 8, 4, 2, 1]’.
4 Rewrites Answer 4. (•)
(•) *Exercise 5.* Define, using rewrite rules, a function
‘nterms(X)’ that returns the number of terms in the sum X, or 1 if X is
not a sum. (A “sum” for our purposes is one or more non-sum terms
separated by ‘+’ or ‘-’ signs, so that ‘2 - 3 (x + y) + x y’ is a sum of
three terms.) 5 Rewrites Answer 5. (•)
(•) *Exercise 6.* A Taylor series for a function is an infinite
series that exactly equals the value of that function at values of ‘x’
near zero.
cos(x) = 1 - x^2 / 2! + x^4 / 4! - x^6 / 6! + ...
The ‘a t’ command produces a “truncated Taylor series” which is
obtained by dropping all the terms higher than, say, ‘x^2’. Calc
represents the truncated Taylor series as a polynomial in ‘x’.
Mathematicians often write a truncated series using a “big-O” notation
that records what was the lowest term that was truncated.
cos(x) = 1 - x^2 / 2! + O(x^3)
The meaning of ‘O(x^3)’ is “a quantity which is negligibly small if
‘x^3’ is considered negligibly small as ‘x’ goes to zero.”
The exercise is to create rewrite rules that simplify sums and
products of power series represented as ‘POLYNOMIAL + O(VAR^N)’. For
example, given ‘1 - x^2 / 2 + O(x^3)’ and ‘x - x^3 / 6 + O(x^4)’ on the
stack, we want to be able to type ‘*’ and get the result ‘x - 2:3 x^3 +
O(x^4)’. Don’t worry if the terms of the sum are rearranged. (This one
is rather tricky; the solution at the end of this chapter uses 6 rewrite
rules. Hint: The ‘constant(x)’ condition tests whether ‘x’ is a
number.) 6 Rewrites Answer 6. (•)
Just for kicks, try adding the rule ‘2+3 := 6’ to ‘EvalRules’. What
happens? (Be sure to remove this rule afterward, or you might get a
nasty surprise when you use Calc to balance your checkbook!)
Rewrite Rules, for the whole story on rewrite rules.
Info Catalog
calc: Basic Algebra Tutorial
calc: Algebra Tutorial