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:  1 / cos(x) - sin(x) tan(x)
         .

         ' 1/cos(x) - sin(x) tan(x) RET   s 1

If we were simplifying this by hand, we'd probably replace the `tan'
with a `sin/cos' first, then combine over a common denominator.  There
is no Calc command to do the former; the `a n' algebra command will do
the latter but we'll do both with rewrite rules just for practice.

Rewrite rules are written with the `:=' symbol.

     1:  1 / cos(x) - sin(x)^2 / cos(x)
         .

         a r tan(a) := sin(a)/cos(a) RET

(The "assignment operator" `:=' has several uses in Calc.  All by
itself the formula `tan(a) := sin(a)/cos(a)' 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, `tan(a)', 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 actual variable
`x'.

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 `sin(x) / cos(x)'.  Calc's normal algebraic simplifications
then mix this in with the rest of the original formula.

To merge over a common denominator, we can use another simple rule:

     1:  (1 - sin(x)^2) / cos(x)
         .

         a r a/x + b/x := (a+b)/x RET

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 `cos(x)'; 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 = 1', `b = -sin(x)^2', and `x = cos(x)'.

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.  *Note Algebraic Properties of Rewrite
Rules::, for some examples of this.)

One more rewrite will complete the job.  We want to use the identity
`sin(x)^2 + cos(x)^2 = 1', but of course we must first rearrange
the identity in a way that matches our formula.  The obvious rule
would be `1 - sin(x)^2 := cos(x)^2', but a little thought shows
that the rule `sin(x)^2 := 1 - cos(x)^2' will also work.  The
latter rule has a more general pattern so it will work in many other
situations, too.

     1:  (1 + cos(x)^2 - 1) / cos(x)           1:  cos(x)
         .                                         .

         a r sin(x)^2 := 1 - cos(x)^2 RET          a s

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.

     ' tan(x) := sin(x)/cos(x) RET      s t tsc RET
     ' a/x + b/x := (a+b)/x RET         s t merge RET
     ' sin(x)^2 := 1 - cos(x)^2 RET     s t sinsqr RET

     1:  1 / cos(x) - sin(x) tan(x)     1:  cos(x)
         .                                  .

         r 1                a r tsc RET  a r merge RET  a r sinsqr RET  a s

To edit a variable, type `s e' and the variable name, use regular
Emacs editing commands as necessary, then type `M-# M-#' or
`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 both
sides by the conjugate `1 - sqrt(2)'.  The result will have
to be expanded by the distributive law; do this with another
rewrite.  See 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:  [tsc, merge, sinsqr]          1:  [tan(x) := sin(x) / cos(x), ... ]
         .                                 .

         ' [tsc,merge,sinsqr] RET          =

     1:  1 / cos(x) - sin(x) tan(x)    1:  cos(x)
         .                                 .

         s t trig RET  r 1                 a r trig RET  a s

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:  1 / cos(x) - sin(x)^2 / cos(x)    1:  (1 - sin(x)^2) / cos(x)
         .                                     .

         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:  exp(2 pi i) + exp(3 pi i) + exp(4 pi i)
         .

         ' exp(2 pi i) + exp(3 pi i) + exp(4 pi i) RET

     1:  1 + exp(3 pi i) + 1
         .

         a r exp(k pi i) := 1 :: 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 variables `pi' and `i' were matched
literally rather than acting as meta-variables.  This is because they
are special-constant variables.  The special constants `e', `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:  8 + fib(x) + fib(0)
         .                                 .

         ' 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.  See 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?
See 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]'.
See 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.)
See 5: Rewrites Answer 5. (*)

(*) *Exercise 6.* Calc considers the form `0^0' to be "indeterminate,"
and leaves it unevaluated (assuming infinite mode is not enabled).
Some people prefer to define `0^0 = 1', so that the identity `x^0 = 1'
can safely be used for all `x'.  Find a way to make Calc follow this
convention.  What happens if you now type `m i' to turn on infinite
mode?  See 6: Rewrites Answer 6. (*)

(*) *Exercise 7.* 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 or
if `a s' needs to be typed after rewriting.  (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.)
See 7: Rewrites Answer 7. (*)

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