Usenet 1994 January/usenetsourcesnewsgroupsinfomagicjanuary1994.iso/sources/misc/volume24/gnucalc/part48

Text File | 1991-11-01 | 55.5 KB | 1,349 lines

Newsgroups: comp.sources.misc
From: [e-mail] (David Gillespie)
Subject:  v24i096:  gnucalc - GNU Emacs Calculator, v2.00, Part48/56
Message-ID: <[e-mail]>
X-Md4-Signature: eb45f40d4c9bff375844f727facb0400
Date: Fri, 1 Nov 1991 18:39:26 GMT
Approved: [e-mail]

Submitted-by: [e-mail] (David Gillespie)
Posting-number: Volume 24, Issue 96
Archive-name: gnucalc/part48
Environment: Emacs
Supersedes: gmcalc: Volume 13, Issue 27-45

---- Cut Here and unpack ----
#!/bin/sh
# do not concatenate these parts, unpack them in order with /bin/sh
# file calc.texinfo continued
#
if test ! -r _shar_seq_.tmp; then
    echo 'Please unpack part 1 first!'
    exit 1
fi
(read Scheck
 if test "$Scheck" != 48; then
    echo Please unpack part "$Scheck" next!
    exit 1
 else
    exit 0
 fi
) < _shar_seq_.tmp || exit 1
if test ! -f _shar_wnt_.tmp; then
    echo 'x - still skipping calc.texinfo'
else
echo 'x - continuing file calc.texinfo'
sed 's/^X//' << 'SHAR_EOF' >> 'calc.texinfo' &&
but @samp{linnt(2,x)} and @samp{linnt(y,x)} are left unevaluated
(in other words, these formulas are considered to be only ``trivially''
linear in @cite{x}).
X
All four linearity-testing functions allow you to omit the second
argument, in which case the input may be linear in any non-constant
formula.  Here, the @cite{a=0}, @cite{b=1} case is also considered
trivial, and only constant values for @cite{a} and @cite{b} are
recognized.  Thus, @samp{lin(2 x y)} returns @cite{[0, 2, x y]},
@samp{lin(2 - x y)} returns @cite{[2, -1, x y]}, and @samp{lin(x y)}
returns@cite{[0, 1, x y]}.  The @code{linnt} function would allow the
first two cases but not the third.  Also, neither @code{lin} nor
@code{linnt} accept plain constants as linear in the one-argument
case: @samp{islin(2,x)} is true, but @samp{islin(2)} is false.
X
@tindex istrue
The @samp{istrue(a)} function returns 1 if @cite{a} is a nonzero
number, or 0 if @cite{a} is anything else.  Calls to @code{istrue}
can only be entered or manipulated if @kbd{m O} mode is used to
make sure they are not evaluated prematurely.
X
@node Rewrite Rules, , Logical Operations, Algebra
@section Rewrite Rules
X
@noindent
@cindex Rewrite rules
@cindex Transformations
@cindex Pattern matching
@kindex a r
@pindex calc-rewrite
@tindex rewrite
The @kbd{a r} (@code{calc-rewrite}) [@code{rewrite}] command makes
substitutions in a formula according to a specified pattern or patterns
known as @dfn{rewrite rules}.  Whereas @kbd{a b} (@code{calc-substitute})
matches literally, so that substituting @samp{sin(x)} with @samp{cos(x)}
matches only the @code{sin} function applied to the variable @code{x},
rewrite rules match general kinds of formulas; rewriting using the rule
@samp{sin(x) := cos(x)} matches @code{sin} of any argument and replaces
it with @code{cos} of that same argument.  The only significance of the
name @code{x} is that the same name is used on both sides of the rule.
X
@menu
* Entering Rewrite Rules::
* Basic Rewrite Rules::
* Conditional Rewrite Rules::
* Algebraic Properties of Rewrite Rules::
* Other Features of Rewrite Rules::
* Composing Patterns in Rewrite Rules::
* Nested Formulas with Rewrite Rules::
* Multi-Phase Rewrite Rules::
* Selections with Rewrite Rules::
* Matching Commands::
* Automatic Rewrites::
* Debugging Rewrites::
* Examples of Rewrite Rules::
@end menu
X
@node Entering Rewrite Rules, Basic Rewrite Rules, Rewrite Rules, Rewrite Rules
@subsection Entering Rewrite Rules
X
@noindent
Rewrite rules normally use the ``assignment'' operator @samp{old := new}.
This operator is equivalent to the function call @samp{assign(old, new)}.
The @code{assign} function is undefined by itself in Calc, so an
assignment formula like a rewrite rule will be left alone by ordinary
Calc commands.  But certain commands, like the rewrite system, interpret
assignments in special ways.
X
For example, the rule @samp{sin(x)^2 := 1-cos(x)^2} says to replace
every occurrence of the sine of something, squared, with one minus the
square of the cosine of that same thing.  All by itself it does nothing,
but when given to the @kbd{a r} command it turns that command into
a sine-squared-to-cosine-squared converter.
X
To specify a set of rules, make a vector of rules.
X
When @kbd{a r} prompts you to enter the rewrite rules, you can answer
in several ways:
X
@enumerate
@item
With a rule:  @kbd{f(x) := g(x) RET}.
@item
With a vector of rules:  @kbd{[f1(x) := g1(x), f2(x) := g2(x)] RET}.
(You can omit the enclosing square brackets if you wish.)
@item
With the name of a variable that contains the rule or rules vector:
@kbd{myrules RET}.
@item
With any formula except a rule, a vector, or a variable name; this
will be interpreted as the @samp{old} half of a rewrite rule,
and you will be prompted a second time for the @samp{new} half:
@kbd{f(x) @key{RET} g(x) @key{RET}}.
@item
With a blank line, in which case the rule, rules vector, or variable
will be taken from the top of the stack (and the formula to be
rewritten will come from the second-to-top position).
@end enumerate
X
If you enter the rules directly (as opposed to using rules stored
in a variable), those rules will be put into the Trail so that you
can retrieve them later.  @xref{Trail Commands}.
X
It is most convenient to store rules you use often in a variable and
invoke them by naming the variable.  The @kbd{s e} (@code{calc-edit-variable})
command is an easy way to create or edit a rule set stored in a variable.
You may also wish to use @kbd{s p} (@code{calc-permanent-variable}) to
save your rules permanently; @pxref{Operations on Variables}.@refill
X
Rewrite rules are compiled into a special internal form for faster
matching.  If you enter a rule set directly it must be recompiled
for every @kbd{a r} command.  If you store the rules in a variable
and refer to them through that variable, they will be compiled
once and saved away along with the variable for later reference.
This is another good reason to store your rules in a variable.
X
Calc also accepts an obsolete notation for rules, as vectors
@samp{[old, new]}.  But because it is easily confused with a vector
of two rules, the use of this notation is no longer recommended.
X
@node Basic Rewrite Rules, Conditional Rewrite Rules, Entering Rewrite Rules, Rewrite Rules
@subsection Basic Rewrite Rules
X
@noindent
To match a particular formula @cite{x} with a particular rewrite rule
@samp{old := new}, Calc compares the structure of @cite{x} with the
structure of @samp{old}.  Variables that appear in @samp{old} are
treated as @dfn{meta-variables}; the corresponding positions in @cite{x}
may contain any sub-formulas.  For example, the pattern @samp{f(x,y)}
would match the expression @samp{f(12, a+1)} with the meta-variable
@samp{x} corresponding to 12 and with @samp{y} corresponding to
@samp{a+1}.  However, this pattern would not match @samp{f(12)} or
@samp{g(12, a+1)}, since there is no assignment of the meta-variables
that will make the pattern match these expressions.  Notice that if
the pattern is a single meta-variable, it will match any expression.
X
If a given meta-variable appears more than once in @samp{old}, the
corresponding sub-formulas of @cite{x} must be identical.  Thus
the pattern @samp{f(x,x)} would match @samp{f(12, 12)} and
@samp{f(a+1, a+1)} but not @samp{f(12, a+1)} or @samp{f(x+y, y+x)}.
X
Things other than variables must match exactly between the pattern
and the target formula.  To match a particular variable exactly, use
the pseudo-function @samp{quote(v)} in the pattern.  For example, the
pattern @samp{x+quote(y)} matches @samp{x+y}, @samp{2+y}, or
@samp{sin(a)+y}.
X
The special variable names @samp{e}, @samp{pi}, @samp{i}, @samp{phi},
@samp{gamma}, @samp{inf}, @samp{uinf}, and @samp{nan} always match
literally.  Thus the pattern @samp{sin(d + e + f)} acts exactly like
@samp{sin(d + quote(e) + f)}.
X
If the @samp{old} pattern is found to match a given formula, that
formula is replaced by @samp{new}, where any occurrences in @samp{new}
of meta-variables from the pattern are replaced with the sub-formulas
that they matched.  Thus, applying the rule @samp{f(x,y) := g(y+x,x)}
to @samp{f(12, a+1)} would produce @samp{g(a+13, 12)}.
X
The normal @kbd{a r} command applies rewrite rules over and over
throughout the target formula until no further changes are possible.
Use @kbd{C-u 1 a r} to make only one change at a time.
X
@node Conditional Rewrite Rules, Algebraic Properties of Rewrite Rules, Basic Rewrite Rules, Rewrite Rules
@subsection Conditional Rewrite Rules
X
@noindent
A rewrite rule can also be @dfn{conditional}, written in the form
@samp{old := new :: cond}.  (There is also the obsolete form
@samp{[old, new, cond]}.)  If a @samp{cond} part is present in the
rule, this is an additional condition that must be satisfied before
the rule is accepted.  Once @samp{old} has been successfully matched
to the target expression, @samp{cond} is evaluated (with all the
meta-variables substituted for the values they matched) and simplified
with @kbd{a s} (@code{calc-simplify}).  If the result is a nonzero
number or any other object known to be nonzero (@pxref{Declarations}),
the rule is accepted.  If the result is zero or if it is a symbolic
formula that is not known to be nonzero, the rule is rejected.
@xref{Logical Operations}, for a number of functions that return
1 or 0 according to the results of various tests.
X
For example, the formula @samp{n > 0} simplifies to 1 or 0 if @cite{n}
is replaced by a positive or nonpositive number, respectively (or if
@cite{n} has been declared to be positive or nonpositive).  Thus,
the rule @samp{f(x,y) := g(y+x,x) :: x+y > 0} would apply to
@samp{f(0, 4)} but not to @samp{f(-3, 2)} or @samp{f(12, a+1)}
(assuming no outstanding declarations for @cite{a}).  In the case of
@samp{f(-3, 2)}, the condition can be shown not to be satisfied; in
the case of @samp{f(12, a+1)}, the condition merely cannot be shown
to be satisfied, but that is enough to reject the rule.
X
While Calc will use declarations to reason about variables in the
formula being rewritten, declarations do not apply to meta-variables.
For example, the rule @samp{[f(a), g(a+1)]} will match for any values
of @samp{a}, such as complex numbers, vectors, or formulas, even if
@samp{a} has been declared to be real or scalar.  If you want the
meta-variable @samp{a} to match only literal real numbers, use
@samp{f(a) := g(a+1) :: real(a)}.  If you want @samp{a} to match only
reals and formulas which are provably real, use @samp{dreal(a)} as
the condition.
X
The @samp{::} operator is a shorthand for the @code{condition}
function; @samp{old := new :: cond} is equivalent to the formula
@samp{condition(assign(old, new), cond)}.
X
If you have several conditions, you can use @samp{... :: c1 :: c2 :: c3}
or @samp{... :: c1 && c2 && c3}.  The two are entirely equivalent.
X
It is also possible to embed conditions inside the pattern:
@samp{f(x :: x>0, y) := g(y+x, x)}.  This is purely a notational
convenience, though; where a condition appears in a rule has no
effect on when it is tested.  The rewrite-rule compiler automatically
decides when it is best to test each condition while a rule is being
matched.
X
Certain conditions are handled as special cases by the rewrite rule
system and are tested very efficiently:  Where @cite{x} is any
meta-variable, these conditions are @samp{integer(x)}, @samp{real(x)},
@samp{constant(x)}, @samp{negative(x)}, @samp{x >= y} where @cite{y}
is either a constant or another meta-variable and @samp{>=} may be
replaced by any of the six relational operators, and @samp{x % a = b}
where @cite{a} and @cite{b} are constants.  Other conditions, like
@samp{x >= y+1} or @samp{dreal(x)}, will be less efficient to check
since Calc must bring the whole evaluator and simplifier into play.
X
An interesting property of @samp{::} is that neither of its arguments
will be touched by Calc's default simplifications.  This is important
because conditions often are expressions that cannot safely be
evaluated early.  For example, the @code{typeof} function never
remains in symbolic form; entering @samp{typeof(a)} will put the
number 100 (the type code for variables like @samp{a}) on the stack.
But putting the condition @samp{... :: typeof(a) = 6} on the stack
is safe since @samp{::} prevents the @code{typeof} from being
evaluated until the condition is actually used by the rewrite system.
X
Since @samp{::} protects its lefthand side, too, you can use a dummy
condition to protect a rule that itself must not evaluate early.
For example, it's not safe to put @samp{a(f,x) := apply(f, [x])} on
the stack because it will immediately evaluate to @samp{a(f,x) := f(x)},
where the meta-variable-ness of @code{f} on the righthand side has been
lost.  But @samp{a(f,x) := apply(f, [x]) :: 1} is safe, and of course
the condition @samp{1} is always true (nonzero) so it has no effect on
the functioning of the rule.  (The rewrite compiler will ensure that
it doesn't even impact the speed of matching the rule.)
X
@node Algebraic Properties of Rewrite Rules, Other Features of Rewrite Rules, Conditional Rewrite Rules, Rewrite Rules
@subsection Algebraic Properties of Rewrite Rules
X
@noindent
The rewrite mechanism understands the algebraic properties of functions
like @samp{+} and @samp{*}.  In particular, pattern matching takes
the associativity and commutativity of the following functions into
account:
X
@smallexample
+ - *  = !=  && ||  and or xor  vint vunion vxor  gcd lcm  max min  beta
@end smallexample
X
For example, the rewrite rule:
X
@example
a x + b x  :=  (a + b) x
@end example
X
@noindent
will match formulas of the form,
X
@example
a x + b x,  x a + x b,  a x + x b,  x a + b x
@end example
X
Rewrites also understand the relationship between the @samp{+} and @samp{-}
operators.  The above rewrite rule will also match the formulas,
X
@example
a x - b x,  x a - x b,  a x - x b,  x a - b x
@end example
X
@noindent
by matching @samp{b} in the pattern to @samp{-b} from the formula.
X
Applied to a sum of many terms like @samp{r + a x + s + b x + t}, this
pattern will check all pairs of terms for possible matches.  The rewrite
will take whichever suitable pair it discovers first.
X
In general, a pattern using an associative operator like @samp{a + b}
will try @i{2 n} different ways to match a sum of @i{n} terms
like @samp{x + y + z - w}.  First, @samp{a} is matched against each
of @samp{x}, @samp{y}, @samp{z}, and @samp{-w} in turn, with @samp{b}
being matched to the remainders @samp{y + z - w}, @samp{x + z - w}, etc.
If none of these succeed, then @samp{b} is matched against each of the
four terms with @samp{a} matching the remainder.  Half-and-half matches,
like @samp{(x + y) + (z - w)}, are not tried.
X
Note that @samp{*} is not commutative when applied to matrices, but
rewrite rules pretend that it is.  If you type @kbd{m v} to enable
matrix mode (@pxref{Matrix Mode}), rewrite rules will match @samp{*}
literally, ignoring its usual commutativity property.  (In the
current implementation, the associativity also vanishes---it is as
if the pattern had been enclosed in a @code{plain} marker; see below.)
If you are applying rewrites to formulas with matrices, it's best to
enable matrix mode first to prevent algebraically incorrect rewrites
from occurring.
X
The pattern @samp{-x} will actually match any expression.  For example,
the rule
X
@example
f(-x)  :=  -f(x)
@end example
X
@noindent
will rewrite @samp{f(a)} to @samp{-f(-a)}.  To avoid this, either use
a @code{plain} marker as described below, or add a @samp{negative(x)}
condition.  The @code{negative} function is true if its argument
``looks'' negative, for example, because it is a negative number or
because it is a formula like @samp{-x}.  The new rule using this
condition is:
X
@example
f(x)  :=  -f(-x)  :: negative(x)    @r{or, equivalently,}
f(-x)  :=  -f(x)  :: negative(-x)
@end example
X
In the same way, the pattern @samp{x - y} will match the sum @samp{a + b}
by matching @samp{y} to @samp{-b}.
X
The pattern @samp{a b} will also match the formula @samp{x/y} if
@samp{y} is a number.  Thus the rule @samp{a x + b x := (a+b) x}
will also convert @samp{a x + x / 2} to @samp{(a + 0.5) x} (or
@samp{(a + 1:2) x}, depending on the current fraction mode).
X
Calc will @emph{not} take other liberties with @samp{*}, @samp{/}, and
@samp{^}.  For example, the pattern @samp{f(a b)} will not match
@samp{f(x^2)}, and @samp{f(a + b)} will not match @samp{f(2 x)}, even
though conceivably these patterns could match with @samp{a = b = x}.
Nor will @samp{f(a b)} match @samp{f(x / y)} if @samp{y} is not a
constant, even though it could be considered to match with @samp{a = x}
and @samp{b = 1/y}.  The reasons are partly for efficiency, and partly
because while few mathematical operations are substantively different
for addition and subtraction, often it is preferable to treat the cases
of multiplication, division, and integer powers separately.
X
Even more subtle is the rule set
X
@example
[ f(a) + f(b) := f(a + b),  -f(a) := f(-a) ]
@end example
X
@noindent
attempting to match @samp{f(x) - f(y)}.  You might think that Calc
will view this subtraction as @samp{f(x) + (-f(y))} and then apply
the above two rules in turn, but actually this will not work because
Calc only does this when considering rules for @samp{+} (like the
first rule in this set).  So it will see first that @samp{f(x) + (-f(y))}
does not match @samp{f(a) + f(b)} for any assignments of the
meta-variables, and then it will see that @samp{f(x) - f(y)} does
not match @samp{-f(a)} for any assignment of @samp{a}.  Because Calc
tries only one rule at a time, it will not be able to rewrite
@samp{f(x) - f(y)} with this rule set.  An explicit @samp{f(a) - f(b)}
rule will have to be added.
X
Another thing patterns will @emph{not} do is break up complex numbers.
The pattern @samp{myconj(a + b i) := a - b i} will work for formulas
involving the special constant @samp{i} (such as @samp{3 - 4 i}), but
it will not match actual complex numbers like @samp{(3, -4)}.  A version
of the above rule for complex numbers would be
X
@example
myconj(a)  :=  re(a) - im(a) (0,1)  :: im(a) != 0
@end example
X
@noindent
(Because the @code{re} and @code{im} functions understand the properties
of the special constant @samp{i}, this rule will also work for
@samp{3 - 4 i}.  In fact, this particular rule would probably be better
without the @samp{im(a) != 0} condition, since if @samp{im(a) = 0} the
righthand side of the rule will still give the correct answer for the
conjugate of a real number.)
X
It is also possible to specify optional arguments in patterns.  The rule
X
@example
opt(a) x + opt(b) (x^opt(c) + opt(d))  :=  f(a, b, c, d)
@end example
X
@noindent
will match the formula
X
@example
5 (x^2 - 4) + 3 x
@end example
X
@noindent
in a fairly straightforward manner, but it will also match reduced
formulas like
X
@example
x + x^2,    2(x + 1) - x,    x + x
@end example
X
@noindent
producing, respectively,
X
@example
f(1, 1, 2, 0),   f(-1, 2, 1, 1),   f(1, 1, 1, 0)
@end example
X
(The latter two formulas can be entered only if default simplifications
have been turned off with @kbd{m O}.)
X
The default value for a term of a sum is zero.  The default value
for a part of a product, for a power, or for the denominator of a
quotient, is one.  Also, @samp{-x} matches the pattern @samp{opt(a) b}
with @samp{a = -1}.
X
In particular, the distributive-law rule can be refined to
X
@example
opt(a) x + opt(b) x  :=  (a + b) x
@end example
X
@noindent
so that it will convert, e.g., @samp{a x - x}, to @samp{(a - 1) x}.
X
The pattern @samp{opt(a) + opt(b) x} matches any formula which is
linear in @samp{x}.  You can also use the @code{lin} and @code{islin}
functions with rewrite conditions to test for this; @pxref{Logical
Operations}.  These functions are not as convenient to use in rewrite
rules, but they recognize more kinds of formulas as linear:
@samp{x/z} is considered linear with @cite{b = 1/z} by @code{lin},
but it will not match the above pattern because that pattern calls
for a multiplication, not a division.
X
As another example, the obvious rule to replace @samp{sin(x)^2 + cos(x)^2}
by 1,
X
@example
sin(x)^2 + cos(x)^2  :=  1
@end example
X
@noindent
misses many cases because the sine and cosine may both be multiplied by
an equal factor.  Here's a more successful rule:
X
@example
opt(a) sin(x)^2 + opt(a) cos(x)^2  :=  a
@end example
X
Note that this rule will @emph{not} match @samp{sin(x)^2 + 6 cos(x)^2}
because one @cite{a} would have ``matched'' 1 while the other matched 6.
X
Calc automatically converts a rule like
X
@example
f(x-1, x)  :=  g(x)
@end example
X
@noindent
into the form
X
@example
f(temp, x)  :=  g(x)  :: temp = x-1
@end example
X
@noindent
(where @code{temp} stands for a new, invented meta-variable that
doesn't actually have a name).  This modified rule will successfully
match @samp{f(6, 7)}, binding @samp{temp} and @samp{x} to 6 and 7,
respectively, then verifying that they differ by one even though
@samp{6} does not superficially look like @samp{x-1}.
X
However, Calc does not solve equations to interpret a rule.  The
following rule,
X
@example
f(x-1, x+1)  :=  g(x)
@end example
X
@noindent
will not work.  That is, it will match @samp{f(a - 1 + b, a + 1 + b)}
but not @samp{f(6, 8)}.  Calc always interprets at least one occurrence
of a variable by literal matching.  If the variable appears ``isolated''
then Calc is smart enough to use it for literal matching.  But in this
last example, Calc is forced to rewrite the rule to @samp{f(x-1, temp)
:= g(x) :: temp = x+1} where the @samp{x-1} term must correspond to an
actual ``something-minus-one'' in the target formula.
X
A successful way to write this would be @samp{f(x, x+2) := g(x+1)}.
You could make this resemble the original form more closely by using
@code{let} notation, which is described in the next section:
X
@example
f(xm1, x+1)  :=  g(x)  :: let(x := xm1+1)
@end example
X
Calc does this rewriting or ``conditionalizing'' for any sub-pattern
which involves only the functions in the following list, operating
only on constants and meta-variables which have already been matched
elsewhere in the pattern.  When matching a function call, Calc is
careful to match arguments which are plain variables before arguments
which are calls to any of the functions below, so that a pattern like
@samp{f(x-1, x)} can be conditionalized even though the isolated
@samp{x} comes after the @samp{x-1}.
X
@smallexample
+ - * / \ % ^  abs sign  round rounde roundu trunc floor ceil
max min  re im conj arg
@end smallexample
X
You can suppress all of the special treatments described in this
section by surrounding a function call with a @code{plain} marker.
This marker causes the function call which is its argument to be
matched literally, without regard to commutativity, associativity,
negation, or conditionalization.  When you use @code{plain}, the
``deep structure'' of the formula being matched can show through.
For example,
X
@example
plain(a - a b)  :=  f(a, b)
@end example
X
@noindent
will match only literal subtractions.  However, the @code{plain}
marker does not affect its arguments' arguments.  In this case,
commutativity and associativity is still considered while matching
the @samp{a b} sub-pattern, so the whole pattern will match
@samp{x - y x} as well as @samp{x - x y}.  We could go still
further and use
X
@example
plain(a - plain(a b))  :=  f(a, b)
@end example
X
@noindent
which would do a completely strict match for the pattern.
X
By contrast, the @code{quote} marker means that not only the
function name but also the arguments must be literally the same.
The above pattern will match @samp{x - x y} but
X
@example
quote(a - a b)  :=  f(a, b)
@end example
X
@noindent
will match only the single formula @samp{a - a b}.  Also,
X
@example
quote(a - quote(a b))  :=  f(a, b)
@end example
X
@noindent
will match only @samp{a - quote(a b)}---probably not the desired
effect!
X
A certain amount of algebra is also done when substituting the
meta-variables on the righthand side of a rule.  For example,
in the rule
X
@example
a + f(b)  :=  f(a + b)
@end example
X
@noindent
matching @samp{f(x) - y} would produce @samp{f((-y) + x)} if
taken literally, but the rewrite mechanism will simplify the
righthand side to @samp{f(x - y)} automatically.  (Of course,
the default simplifications would do this anyway, so this
special simplification is only noticeable if you have turned the
default simplifications off.)  This rewriting is done only when
a meta-variable expands to a ``negative-looking'' expression.
If this simplification is not desirable, you can use a @code{plain}
marker on the righthand side:
X
@example
a + f(b)  :=  f(plain(a + b))
@end example
X
@noindent
In this example, we are still allowing the pattern-matcher to
use all the algebra it can muster, but the righthand side will
always simplify to a literal addition like @samp{f((-y) + x)}.
X
@node Other Features of Rewrite Rules, Composing Patterns in Rewrite Rules, Algebraic Properties of Rewrite Rules, Rewrite Rules
@subsection Other Features of Rewrite Rules
X
@noindent
Certain ``function names'' serve as markers in rewrite rules.
Here is a complete list of these markers.  First are listed the
markers that work inside a pattern; then come the markers that
work in the righthand side of a rule.
X
@tindex import
One kind of marker, @samp{import(x)}, takes the place of a whole
rule.  Here @cite{x} is the name of a variable containing another
rule set; those rules are ``spliced into'' the rule set that
imports them.  For example, if @samp{[f(a+b) := f(a) + f(b),
f(a b) := a f(b) :: real(a)]} is stored in variable @samp{linearF},
then the rule set @samp{[f(0) := 0, import(linearF)]} will apply
all three rules.  It is possible to modify the imported rules
slightly:  @samp{import(x, v1, x1, v2, x2, @dots{})} imports
the rule set @cite{x} with all occurrences of @cite{v1}, as either
a variable name or a function name, replaced with @cite{x1} and
so on.  (If @cite{v1} is used as a function name, then @cite{x1}
must be either a function name itself or a @samp{< >} nameless
function @pxref{Specifying Operators}.)  For example, @samp{[g(0) := 0,
import(linearF, f, g)]} applies the linearity rules to the function
@samp{g} instead of @samp{f}.  Imports can be nested, but the
import-with-renaming feature may not properly rename sub-imports.
X
The special functions allowed in patterns are:
X
@table @samp
@item quote(x)
@tindex quote
This pattern matches exactly @cite{x}; variable names in @cite{x} are
not interpreted as meta-variables.  The only flexibility is that
numbers are compared for numeric equality, so that the pattern
@samp{f(quote(12))} will match both @samp{f(12)} and @samp{f(12.0)}.
(Numbers are always treated this way by the rewrite mechanism:
The rule @samp{f(x,x) := g(x)} will match @samp{f(12, 12.0)}.
The rewrite may produce either @samp{g(12)} or @samp{g(12.0)}
as a result in this case.)
X
@item plain(x)
@tindex plain
Here @cite{x} must be a function call @samp{f(x1,x2,@dots{})}.  This
pattern matches a call to function @cite{f} with the specified
argument patterns.  No special knowledge of the properties of the
function @cite{f} is used in this case; @samp{+} is not commutative or
associative.  Unlike @code{quote}, the arguments @samp{x1,x2,@dots{}}
are treated as patterns.  If you wish them to be treated ``plainly''
as well, you must enclose them with more @code{plain} markers:
@samp{plain(plain(-a) + plain(b c))}.
X
@item opt(x,def)
@tindex opt
Here @cite{x} must be a variable name.  This must appear as an
argument to a function or an element of a vector; it specifies that
the argument or element is optional.
As an argument to @samp{+}, @samp{-}, @samp{*}, @samp{&&}, or @samp{||},
or as the second argument to @samp{/} or @samp{^}, the value @var{def}
may be omitted.  The pattern @samp{x + opt(y)} matches a sum by
binding one summand to @cite{x} and the other to @cite{y}, and it
matches anything else by binding the whole expression to @cite{x} and
zero to @cite{y}.  The other operators above work similarly.@refill
X
For general miscellanous functions, the default value @code{def}
must be specified.  Optional arguments are dropped starting with
the rightmost one during matching.  For example, the pattern
@samp{f(opt(a,0), b, opt(c,b))} will match @samp{f(b)}, @samp{f(a,b)},
or @samp{f(a,b,c)}.  Default values of zero and @cite{b} are
supplied in this example for the omitted arguments.  Note that
the literal variable @cite{b} will be the default in the latter
case, @emph{not} the value that matched the meta-variable @cite{b}.
In other words, the default @var{def} is effectively quoted.
X
@item condition(x,c)
@tindex condition
@tindex ::
This matches the pattern @cite{x}, with the attached condition
@cite{c}.  It is the same as @samp{x :: c}.
X
@item pand(x,y)
@tindex pand
@tindex &&&
This matches anything that matches both pattern @cite{x} and
pattern @cite{y}.  It is the same as @samp{x &&& y}.
@pxref{Composing Patterns in Rewrite Rules}.
X
@item por(x,y)
@tindex por
@tindex |||
This matches anything that matches either pattern @cite{x} or
pattern @cite{y}.  It is the same as @samp{x ||| y}.
X
@item pnot(x)
@tindex pnot
@tindex !!!
This matches anything that does not match pattern @cite{x}.
It is the same as @samp{!!! x}.
X
@item cons(h,t)
@tindex cons (rewrites)
This matches any vector of one or more elements.  The first
element is matched to @cite{h}; a vector of the remaining
elements is matched to @cite{t}.  Note that vectors of fixed
length can also be matched as actual vectors:  The rule
@samp{cons(a,cons(b,[])) := cons(a+b,[])} is equivalent
to the rule @samp{[a,b] := [a+b]}.
X
@item rcons(t,h)
@tindex rcons (rewrites)
This is like @code{cons}, except that the @emph{last} element
is matched to @cite{h}, with the remaining elements matched
to @cite{t}.
X
@item apply(f,args)
@tindex apply (rewrites)
This matches any function call.  The name of the function, in
the form of a variable, is matched to @cite{f}.  The arguments
of the function, as a vector of zero or more objects, are
matched to @samp{args}.  Constants, variables, and vectors
do @emph{not} match an @code{apply} pattern.  For example,
@samp{apply(f,x)} matches any function call, @samp{apply(quote(f),x)}
matches any call to the function @samp{f}, @samp{apply(f,[a,b])}
matches any function call with exactly two arguments, and
@samp{apply(quote(f), cons(a,cons(b,x)))} matches any call
to the function @samp{f} with two or more arguments.  Another
way to implement the latter, if the rest of the rule does not
need to refer to the first two arguments of @samp{f} by name,
would be @samp{apply(quote(f), x :: vlen(x) >= 2)}.
Here's a more interesting sample use of @code{apply}:
X
@example
apply(f,[x+n])  :=  n + apply(f,[x])
X   :: in(f, [floor,ceil]) :: integer(n)
@end example
X
Note, however, that this will be slower to match than a rule
set with two separate rules.  The reason is that Calc sorts
the rules of a rule set according to top-level function name;
if the top-level function is @code{apply}, Calc must try the
rule for every single formula and sub-formula.  If the top-level
function in the pattern is, say, @code{floor}, then Calc invokes
the rule only for sub-formulas which are calls to @code{floor}.
X
You must use @code{apply} for meta-variables with function names
on both sides of a rewrite rule:  @samp{apply(f, [x]) := f(x+1)}
is @emph{not} correct, because it rewrites @samp{spam(6)} into
@samp{f(7)}.  The righthand side should be @samp{apply(f, [x+1])}.
Also note that you will have to use no-simplify (@kbd{m O})
mode when entering this rule so that the @code{apply} isn't
evaluated immediately to get the new rule @samp{f(x) := f(x+1)}.
Or, use @kbd{s e} to enter the rule without going through the stack,
or enter the rule as @samp{apply(f, [x]) := apply(f, [x+1]) :: 1}.
@xref{Conditional Rewrite Rules}.
X
@item select(x)
@tindex select
This is used for applying rules to formulas with selections;
@pxref{Selections with Rewrite Rules}.
@end table
X
Special functions for the righthand sides of rules are:
X
@table @samp
@item quote(x)
The notation @samp{quote(x)} is changed to @samp{x} when the
righthand side is used.  As far as the rewrite rule is concerned,
@code{quote} is invisible.  However, @code{quote} has the special
property in Calc that its argument is not evaluated.  Thus,
while it will not work to put the rule @samp{t(a) := typeof(a)}
on the stack because @samp{typeof(a)} is evaluated immediately
to produce @samp{t(a) := 100}, you can use @code{quote} to
protect the righthand side:  @samp{t(a) := quote(typeof(a))}.
(@xref{Conditional Rewrite Rules}, for another trick for
protecting rules from evaluation.)
X
@item plain(x)
Special properties of and simplifications for the function call
@cite{x} are not used.  One interesting case where @code{plain}
is useful is the rule, @samp{q(x) := quote(x)}, trying to expand a
shorthand notation for the @code{quote} function.  This rule will
not work as shown; instead of replacing @samp{q(foo)} with
@samp{quote(foo)}, it will replace it with @samp{foo}!  The correct
rule would be @samp{q(x) := plain(quote(x))}.
X
@item cons(h,t)
Where @cite{t} is a vector, this is converted into an expanded
vector during rewrite processing.  Note that @code{cons} is a regular
Calc function which normally does this anyway; the only way @code{cons}
is treated specially by rewrites is that @code{cons} on the righthand
side of a rule will be evaluated even if default simplifications
have been turned off.
X
@item rcons(t,h)
Analogous to @code{cons} except putting @cite{h} at the @emph{end} of
the vector @cite{t}.
X
@item apply(f,args)
Where @cite{f} is a variable and @samp{args} is a vector, this
is converted to a function call.  Once again, note that @code{apply}
is also a regular Calc function.
X
@item eval(x)
@tindex eval
The formula @cite{x} is handled in the usual way, then the
default simplifications are applied to it even if they have
been turned off normally.  This allows you to treat any function
similarly to the way @code{cons} and @code{apply} are always
treated.  However, there is a slight difference:  @samp{cons(2+3, [])}
with default simplifications off will be converted to @samp{[2+3]},
whereas @samp{eval(cons(2+3, []))} will be converted to @samp{[5]}.
X
@item evalsimp(x)
@tindex evalsimp
The formula @cite{x} has meta-variables substituted in the usual
way, then algebraically simplified as if by the @kbd{a s} command.
X
@item evalextsimp(x)
@tindex evalextsimp
The formula @cite{x} has meta-variables substituted in the normal
way, then ``extendedly'' simplified as if by the @kbd{a e} command.
X
@item select(x)
@xref{Selections with Rewrite Rules}.
@end table
X
There are also some special functions you can use in conditions.
X
@table @samp
@item let(v := x)
@tindex let
The expression @cite{x} is evaluated with meta-variables substituted.
The @kbd{a s} command's simplifications are @emph{not} applied by
default, but @cite{x} can include calls to @code{evalsimp} or
@code{evalextsimp} as described above to invoke higher levels
of simplification.  The
result of @cite{x} is then bound to the meta-variable @cite{v}.  As
usual, if this meta-variable has already been matched to something
else the two values must be equal; if the meta-variable is new then
it is bound to the result of the expression.  This variable can then
appear in later conditions, and on the righthand side of the rule.
In fact, @cite{v} may be any pattern in which case the result of
evaluating @cite{x} is matched to that pattern, binding any
meta-variables that appear in that pattern.  Note that @code{let}
can only appear by itself as a condition, or as one term of an
@samp{&&} which is a whole condition:  It cannot be inside
an @samp{||} term or otherwise buried.@refill
X
The alternate, equivalent form @samp{let(v, x)} is also recognized.
Note that the use of @samp{:=} by @code{let}, while still being
assignment-like in character, is unrelated to the use of @samp{:=}
in the main part of a rewrite rule.
X
As an example, @samp{f(a) := g(ia) :: let(ia := 1/a) :: constant(ia)}
replaces @samp{f(a)} with @samp{g} of the inverse of @samp{a}, if
that inverse exists and is constant.  For example, if @samp{a} is a
singular matrix the operation @samp{1/a} is left unsimplified and
@samp{constant(ia)} fails, but if @samp{a} is an invertible matrix
then the rule succeeds.  Without @code{let} there would be no way
to implement this rule that didn't have to invert the matrix twice.
Note that, because the meta-variable @samp{ia} is otherwise unbound
in this rule, the @code{let} condition itself always ``succeeds''
because no matter what @samp{1/a} evaluates to, it can successfully
be bound to @code{ia}.@refill
X
As another example, here is a rule for integrating cosines of linear
terms:  @samp{myint(cos(y),x) := sin(y)/b :: let([a,b,x] := lin(y,x))}.
The @code{lin} function returns a 3-vector if its argument is linear,
or leaves itself unevaluated if not.  But an unevaluated @code{lin}
call will not match the 3-vector on the lefthand side of the @code{let},
so this @code{let} both verifies that @code{y} is linear, and binds
the coefficients @code{a} and @code{b} for use elsewhere in the rule.
(It would have been possible to use @samp{sin(a x + b)/b} for the
righthand side instead, but using @samp{sin(y)/b} avoids gratuitous
rearrangement of the argument of the sine.)@refill
X
Similarly, here is a rule that implements an inverse-@code{erf}
function.  It uses @code{root} to search for a solution.  If
@code{root} succeeds, it will return a vector of two numbers
where the first number is the desired solution.  If no solution
is found, @code{root} remains in symbolic form.  So we use
@code{let} to check that the result was indeed a vector.
X
@tindex ierf
@example
ierf(x)  :=  y  :: let([y,z] := root(erf(a) = x, a, .5))
@end example
X
@item matches(v,p)
The meta-variable @var{v}, which must already have been matched
to something elsewhere in the rule, is compared against pattern
@var{p}.  Since @code{matches} is a standard Calc function, it
can appear anywhere in a condition.  But if it appears alone or
as a term of a top-level @samp{&&}, then you get the special
extra feature that meta-variables which are bound to things
inside @var{p} can be used elsewhere in the surrounding rewrite
rule.
X
The only real difference between @samp{let(p := v)} and
@samp{matches(v, p)} is that the former evaluates @samp{v} using
the default simplifications, while the latter does not.
X
@item remember
@vindex remember
This is actually a variable, not a function.  If @code{remember}
appears as a condition in a rule, then when that rule succeeds
the original expression and rewritten expression are added to the
front of the rule set that contained the rule.  If the rule set
was not stored in a variable, @code{remember} is ignored.  The
lefthand side is enclosed in @code{quote} in the added rule if it
contains any variables.
X
For example, the rule @samp{f(n) := n f(n-1) :: remember} applied
to @samp{f(7)} will add the rule @samp{f(7) := 7 f(6)} to the front
of the rule set.  The rule set @code{EvalRules} works slightly
differently:  There, the evaluation of @samp{f(6)} will complete before
the result is added to the rule set, in this case as @samp{f(7) := 5040}.
Thus @code{remember} is most useful inside @code{EvalRules}.
X
It is up to you to ensure that the optimization performed by
@code{remember} is safe.  For example, the rule @samp{foo(n) := n
:: evalv(eatfoo) > 0 :: remember} is a bad idea (@code{evalv} is
the function equivalent of the @kbd{=} command); if the variable
@code{eatfoo} ever contains 1, rules like @samp{foo(7) := 7} will
be added to the rule set and will continue to operate even if
@code{eatfoo} is later changed to 0.
X
@item remember(c)
@tindex remember
Remember the match as described above, but only if condition @cite{c}
is true.  For example, @samp{remember(n % 4 = 0)} in the above factorial
rule remembers only every fourth result.  Note that @samp{remember(1)}
is equivalent to @samp{remember}, and @samp{remember(0)} has no effect.
@end table
X
@node Composing Patterns in Rewrite Rules, Nested Formulas with Rewrite Rules, Other Features of Rewrite Rules, Rewrite Rules
@subsection Composing Patterns in Rewrite Rules
X
@noindent
There are three operators, @samp{&&&}, @samp{|||}, and @samp{!!!},
that combine rewrite patterns to make larger patterns.  The
combinations are ``and,'' ``or,'' and ``not,'' respectively, and
these operators are the pattern equivalents of @samp{&&}, @samp{||}
and @samp{!} (which operate on zero-or-nonzero logical values).
X
Note that @samp{&&&}, @samp{|||}, and @samp{!!!} are left in symbolic
form by all regular Calc features; they have special meaning only in
the context of rewrite rule patterns.
X
The pattern @samp{@var{p1} &&& @var{p2}} matches anything that
matches both @var{p1} and @var{p2}.  One especially useful case is
when one of @var{p1} or @var{p2} is a meta-variable.  For example,
here is a rule that operates on error forms:
X
@example
f(x &&& a +/- b, x)  :=  g(x)
@end example
X
This does the same thing, but is arguably simpler than, the rule
X
@example
f(a +/- b, a +/- b)  :=  g(a +/- b)
@end example
X
Here's another interesting example:
X
@tindex ends
@example
ends(cons(a, x) &&& rcons(y, b))  :=  [a, b]
@end example
X
@noindent
which effectively clips out the middle of a vector leaving just
the first and last elements.  This rule will change a one-element
vector @samp{[a]} to @samp{[a, a]}.  The similar rule
X
@example
ends(cons(a, rcons(y, b)))  :=  [a, b]
@end example
X
@noindent
would do the same thing except that it would fail to match a
one-element vector.
X
@tex
\bigskip
@end tex
X
The pattern @samp{@var{p1} ||| @var{p2}} matches anything that
matches either @var{p1} or @var{p2}.  Calc first tries matching
against @var{p1}; if that fails, it goes on to try @var{p2}.
X
A simple example of @samp{|||} is
X
@tindex curve
@example
curve(inf ||| -inf)  :=  0
@end example
X
@noindent
which converts both @samp{curve(inf)} and @samp{curve(-inf)} to zero.
X
Here is a larger example:
X
@example
log(a, b) ||| (ln(a) :: let(b := e))  :=  mylog(a, b)
@end example
X
This matches both generalized and natural logarithms in a single rule.
Note that the @samp{::} term must be enclosed in parentheses because
that operator has lower precedence than @samp{|||} or @samp{:=}.
X
(In practice this rule would probably include a third alternative,
omitted here for brevity, to take care of @code{log10}.)
X
While Calc generally treats interior conditions exactly the same as
conditions on the outside of a rule, it does guarantee that if all the
variables in the condition are special names like @code{e}, or already
bound in the pattern to which the condition is attached (say, if
@samp{a} had appeared in this condition), then Calc will process this
condition right after matching the pattern to the left of the @samp{::}.
Thus, we know that @samp{b} will be bound to @samp{e} only if the
@code{ln} branch of the @samp{|||} was taken.
X
Note that this rule was careful to bind the same set of meta-variables
on both sides of the @samp{|||}.  Calc does not check this, but if
you bind a certain meta-variable only in one branch and then use that
meta-variable elsewhere in the rule, results are unpredictable:
X
@example
f(a,b) ||| g(b)  :=  h(a,b)
@end example
X
Here if the pattern matches @samp{g(17)}, Calc makes no promises about
the value that will be substituted for @samp{a} on the righthand side.
X
@tex
\bigskip
@end tex
X
The pattern @samp{!!! @var{pat}} matches anything that does not
match @var{pat}.  Any meta-variables that are bound while matching
@var{pat} remain unbound outside of @var{pat}.
X
For example,
X
@example
f(x &&& !!! a +/- b, !!![])  :=  g(x)
@end example
X
@noindent
converts @code{f} whose first argument is anything @emph{except} an
error form, and whose second argument is not the empty vector, into
a similar call to @code{g} (but without the vector).
X
If we know that the second argument will be a vector (empty or not),
then an equivalent rule would be:
X
@example
f(x, y)  :=  g(x)  :: typeof(x) != 7 :: vlen(y) > 0
@end example
X
@noindent
where of course 7 is the @code{typeof} code for error forms.
Another final condition, that works for any kind of @samp{y},
would be @samp{!istrue(y == [])}.  (The @code{istrue} function
returns an explicit 0 if its argument was left in symbolic form;
plain @samp{!(y == [])} or @samp{y != []} would not work to replace
@samp{!!![]} since these would be left unsimplified, and thus cause
the rule to fail, if @samp{y} was something like a variable name.)
X
It is possible for a @samp{!!!} to refer to meta-variables bound
elsewhere in the pattern.  For example,
X
@example
f(a, !!!a)  :=  g(a)
@end example
X
@noindent
matches any call to @code{f} with different arguments, changing
this to @code{g} with only the first argument.
X
If a function call is to be matched and one of the argument patterns
contains a @samp{|||} somewhere inside it, that argument will be
matched last.  Thus
X
@example
f(!!!a, a)  :=  g(a)
@end example
X
@noindent
will be careful to bind @samp{a} to the second argument of @code{f}
before testing the first argument.  If Calc had tried to match the
first argument of @code{f} first, the results would have been
disasterous:  Since @code{a} was unbound so far, the pattern @samp{a}
would have matched anything at all, and the pattern @samp{!!!a}
therefore would @emph{not} have matched anything at all!
X
@node Nested Formulas with Rewrite Rules, Multi-Phase Rewrite Rules, Composing Patterns in Rewrite Rules, Rewrite Rules
@subsection Nested Formulas with Rewrite Rules
X
@noindent
When @kbd{a r} (@code{calc-rewrite}) is used, it takes an expression from
the top of the stack and attempts to match any of the specified rules
to any part of the expression, starting with the whole expression
and then, if that fails, trying deeper and deeper sub-expressions.
For each part of the expression, the rules are tried in the order
they appear in the rules vector.  The first rule to match the first
sub-expression wins; it replaces the matched sub-expression according
to the @samp{new} part of the rule.
X
Often, the rule set will match and change the formula several times.
The top-level formula is first matched and substituted repeatedly until
it no longer matches the pattern; then, sub-formulas are tried, and
so on.  Once each part of the formula has gotten its chance, the
rewrite mechanism starts over again with the top-level formula
(in case a substitution of one of its arguments has caused it again
to match).  This continues until no further matches can be made
anywhere in the formula.
X
It is possible for a rule set to get into an infinite loop.  The
most obvious case, replacing a formula with itself, is not a problem
because a rule is not considered to ``succeed'' unless the righthand
side actually comes out to something different than the original
formula or sub-formula that was matched.  But if you accidentally
had both @samp{ln(a b) := ln(a) + ln(b)} and the reverse
@samp{ln(a) + ln(b) := ln(a b)} in your rule set, Calc would
run forever switching a formula back and forth between the two
forms.
X
To avoid disaster, Calc normally stops after 100 changes have been
made to the formula.  This will be enough for most multiple rewrites,
but will keep an endless loop of rewrites from locking up the
computer forever.  (On most systems, you can also type @kbd{C-g} to
halt any Emacs command prematurely.)
X
To change this limit, give a positive numeric prefix argument.
In particular, @kbd{M-1 a r} applies only one rewrite at a time,
useful when you are first testing your rule (or just if repeated
rewriting is not what is called for by your application).
X
@tindex iterations
You can also put a ``function call'' @samp{iterations(@var{n})}
in place of a rule anywhere in your rules vector (but usually at
the top).  Then, @var{n} will be used instead of 100 as the default
number of iterations for this rule set.  You can use
@samp{iterations(inf)} if you want no iteration limit by default.
A prefix argument will override the @code{iterations} limit in the
rule set.
X
@example
[ iterations(1),
X  f(x) := f(x+1) ]
@end example
X
More precisely, the limit controls the number of ``iterations,''
where each iteration is a successful matching of a rule pattern whose
righthand side, after substituting meta-variables and applying the
default simplifications, is different from the original sub-formula
that was matched.
X
A prefix argument of zero sets the limit to infinity.  Use with caution!
X
Given a negative numeric prefix argument, @kbd{a r} will match and
substitute the top-level expression up to that many times, but
will not attempt to match the rules to any sub-expressions.
X
In a formula, @code{rewrite(@var{expr}, @var{rules}, @var{n})}
does a rewriting operation.  Here @var{expr} is the expression
being rewritten, @var{rules} is the rule, vector of rules, or
variable containing the rules, and @var{n} is the optional
iteration limit, which may be a positive integer, a negative
integer, or @samp{inf} or @samp{-inf}.  If @var{n} is omitted
the @code{iterations} value from the rule set is used; if both
are omitted, 100 is used.
X
@node Multi-Phase Rewrite Rules, Selections with Rewrite Rules, Nested Formulas with Rewrite Rules, Rewrite Rules
@subsection Multi-Phase Rewrite Rules
X
@noindent
It is possible to separate a rewrite rule set into several @dfn{phases}.
During each phase, certain rules will be enabled while certain others
will be disabled.  A @dfn{phase schedule} controls the order in which
phases occur during the rewriting process.
X
@tindex phase
@vindex all
If a call to the marker function @code{phase} appears in the rules
vector in place of a rule, all rules following that point will be
members of the phase(s) identified in the arguments to @code{phase}.
Phases are given integer numbers.  The markers @samp{phase()} and
@samp{phase(all)} both mean the following rules belong to all phases;
this is the default at the start of the rule set.
X
If you do not explicitly schedule the phases, Calc sorts all phase
numbers that appear in the rule set and executes the phases in
ascending order.  For example, the rule set
X
@group
@example
[ f0(x) := g0(x),
X  phase(1),
X  f1(x) := g1(x),
X  phase(2),
X  f2(x) := g2(x),
X  phase(3),
X  f3(x) := g3(x),
X  phase(1,2),
X  f4(x) := g4(x) ]
@end example
@end group
X
@noindent
has three phases, 1 through 3.  Phase 1 consists of the @code{f0},
@code{f1}, and @code{f4} rules (in that order).  Phase 2 consists of
@code{f0}, @code{f2}, and @code{f4}.  Phase 3 consists of @code{f0}
and @code{f3}.
X
When Calc rewrites a formula using this rule set, it first rewrites
the formula using only the phase 1 rules until no further changes are
possible.  Then it switches to the phase 2 rule set and continues
until no further changes occur, then finally rewrites with phase 3.
When no more phase 3 rules apply, rewriting finishes.  (This is
assuming @kbd{a r} with a large enough prefix argument to allow the
rewriting to run to completion; the sequence just described stops
early if the number of iterations specified in the prefix argument,
100 by default, is reached.)
X
During each phase, Calc descends through the nested levels of the
formula as described previously.  (@xref{Nested Formulas with Rewrite
Rules}.)  Rewriting starts at the top of the formula, then works its
way down to the parts, then goes back to the top and works down again.
The phase 2 rules do not begin until no phase 1 rules apply anywhere
in the formula.
X
@tindex schedule
A @code{schedule} marker appearing in the rule set (anywhere, but
conventionally at the top) changes the default schedule of phases.
In the simplest case, @code{schedule} has a sequence of phase numbers
for arguments; each phase number is invoked in turn until the
arguments to @code{schedule} are exhausted.  Thus adding
@samp{schedule(3,2,1)} at the top of the above rule set would
reverse the order of the phases; @samp{schedule(1,2,3)} would have
no effect since this is the default schedule; and @samp{schedule(1,2,1,3)}
would give phase 1 a second chance after phase 2 has completed, before
moving on to phase 3.
X
Any argument to @code{schedule} can instead be a vector of phase
numbers (or even of sub-vectors).  Then the sub-sequence of phases
described by the vector are tried repeatedly until no change occurs
in any phase in the sequence.  For example, @samp{schedule([1, 2], 3)}
tries phase 1, then phase 2, then, if either phase made any changes
to the formula, repeats these two phases until they can make no
further progress.  Finally, it goes on to phase 3 for finishing
touches.
X
Also, items in @code{schedule} can be variable names as well as
numbers.  A variable name is interpreted as the name of a function
to call on the whole formula.  For example, @samp{schedule(1, simplify)}
says to apply the phase-1 rules (presumably, all of them), then to
call @code{simplify} which is the function name equivalent of @kbd{a s}.
Likewise, @samp{schedule([1, simplify])} says to alternate between
phase 1 and @kbd{a s} until no further changes occur.
X
Phases can be used purely to improve efficiency; if it is known that
a certain group of rules will apply only at the beginning of rewriting,
and a certain other group will apply only at the end, then rewriting
will be faster if these groups are identified as separate phases.
Once the phase 1 rules are done, Calc can put them aside and no longer
spend any time on them while it works on phase 2.
X
There are also some problems that can only be solved with several
rewrite phases.  For a real-world example of a multi-phase rule set,
examine the set @code{FitRules}, which is used by the curve-fitting
command to convert a model expression to linear form.
@xref{Curve Fitting Details}.  This set is divided into four phases.
The first phase rewrites certain kinds of expressions to be more
easily linearizable, but less computationally efficient.  After the
linear components have been picked out, the final phase includes the
opposite rewrites to put each component back into an efficient form.
If both sets of rules were included in one big phase, Calc could get
into an infinite loop going back and forth between the two forms.
X
Elsewhere in @code{FitRules}, the components are first isolated,
then recombined where possible to reduce the complexity of the linear
fit, then finally packaged one component at a time into vectors.
If the packaging rules were allowed to begin before the recombining
rules were finished, some components might be put away into vectors
before they had a chance to recombine.  By putting these rules in
two separate phases, this problem is neatly avoided.
X
@node Selections with Rewrite Rules, Matching Commands, Multi-Phase Rewrite Rules, Rewrite Rules
@subsection Selections with Rewrite Rules
X
@noindent
If a sub-formula of the current formula is selected (as by @kbd{j s};
@pxref{Selecting Subformulas}), the @kbd{a r} (@code{calc-rewrite})
command applies only to that sub-formula.  Together with a negative
prefix argument, you can use this fact to apply a rewrite to one
specific part of a formula without affecting any other parts.
X
@kindex j r
@pindex calc-rewrite-selection
The @kbd{j r} (@code{calc-rewrite-selection}) command allows more
sophisticated operations on selections.  This command prompts for
the rules in the same way as @kbd{a r}, but it then applies those
rules to the whole formula in question even though a sub-formula
of it has been selected.  However, the selected sub-formula will
first have been surrounded by a @samp{select( )} function call.
(Calc's evaluator does not understand the function name @code{select};
this is only a tag used by the @kbd{j r} command.)
X
For example, suppose the formula on the stack is @samp{2 (a + b)^2}
and the sub-formula @samp{a + b} is selected.  This formula will
be rewritten to @samp{2 select(a + b)^2} and then the rewrite
rules will be applied in the usual way.  The rewrite rules can
SHAR_EOF
true || echo 'restore of calc.texinfo failed'
fi
echo 'End of  part 48'
echo 'File calc.texinfo is continued in part 49'
echo 49 > _shar_seq_.tmp
exit 0
exit 0 # Just in case...
--
Kent Landfield                   INTERNET: [e-mail]
Sterling Software, IMD           UUCP:     uunet!sparky!kent
Phone:    [phone]         FAX:      [phone]
Please send comp.sources.misc-related mail to [e-mail].