Previous: Basic Algebra Tutorial, Up: Algebra Tutorial

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. See 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. See 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. See 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 `n`th
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

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
‘

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?
See 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 ‘

(•) **Exercise 5.** Define, using rewrite rules, a function
‘`nterms( x)`’ that returns the number of terms in the sum

(•) **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 ‘

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

See Rewrite Rules, for the whole story on rewrite rules.