calc: Other Features of Rewrite Rules
11.11.5 Other Features of Rewrite Rules
---------------------------------------
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.
One kind of marker, ‘import(x)’, takes the place of a whole rule.
Here ‘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 ‘[f(a+b) := f(a) + f(b), f(a b) := a f(b) :: real(a)]’ is stored in
variable ‘linearF’, then the rule set ‘[f(0) := 0, import(linearF)]’
will apply all three rules. It is possible to modify the imported rules
slightly: ‘import(x, v1, x1, v2, x2, ...)’ imports the rule set ‘x’ with
all occurrences of ‘v1’, as either a variable name or a function name,
replaced with ‘x1’ and so on. (If ‘v1’ is used as a function name, then
‘x1’ must be either a function name itself or a ‘< >’ nameless function;
Specifying Operators.) For example, ‘[g(0) := 0,
import(linearF, f, g)]’ applies the linearity rules to the function ‘g’
instead of ‘f’. Imports can be nested, but the import-with-renaming
feature may fail to rename sub-imports properly.
The special functions allowed in patterns are:
‘quote(x)’
This pattern matches exactly ‘x’; variable names in ‘x’ are not
interpreted as meta-variables. The only flexibility is that
numbers are compared for numeric equality, so that the pattern
‘f(quote(12))’ will match both ‘f(12)’ and ‘f(12.0)’. (Numbers are
always treated this way by the rewrite mechanism: The rule ‘f(x,x)
:= g(x)’ will match ‘f(12, 12.0)’. The rewrite may produce either
‘g(12)’ or ‘g(12.0)’ as a result in this case.)
‘plain(x)’
Here ‘x’ must be a function call ‘f(x1,x2,...)’. This pattern
matches a call to function ‘f’ with the specified argument
patterns. No special knowledge of the properties of the function
‘f’ is used in this case; ‘+’ is not commutative or associative.
Unlike ‘quote’, the arguments ‘x1,x2,...’ are treated as patterns.
If you wish them to be treated “plainly” as well, you must enclose
them with more ‘plain’ markers: ‘plain(plain(-a) + plain(b c))’.
‘opt(x,def)’
Here ‘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 ‘+’, ‘-’, ‘*’,
‘&&’, or ‘||’, or as the second argument to ‘/’ or ‘^’, the value
DEF may be omitted. The pattern ‘x + opt(y)’ matches a sum by
binding one summand to ‘x’ and the other to ‘y’, and it matches
anything else by binding the whole expression to ‘x’ and zero to
‘y’. The other operators above work similarly.
For general miscellaneous functions, the default value ‘def’ must
be specified. Optional arguments are dropped starting with the
rightmost one during matching. For example, the pattern
‘f(opt(a,0), b, opt(c,b))’ will match ‘f(b)’, ‘f(a,b)’, or
‘f(a,b,c)’. Default values of zero and ‘b’ are supplied in this
example for the omitted arguments. Note that the literal variable
‘b’ will be the default in the latter case, _not_ the value that
matched the meta-variable ‘b’. In other words, the default DEF is
effectively quoted.
‘condition(x,c)’
This matches the pattern ‘x’, with the attached condition ‘c’. It
is the same as ‘x :: c’.
‘pand(x,y)’
This matches anything that matches both pattern ‘x’ and pattern
‘y’. It is the same as ‘x &&& y’. Composing Patterns in
Rewrite Rules.
‘por(x,y)’
This matches anything that matches either pattern ‘x’ or pattern
‘y’. It is the same as ‘x ||| y’.
‘pnot(x)’
This matches anything that does not match pattern ‘x’. It is the
same as ‘!!! x’.
‘cons(h,t)’
This matches any vector of one or more elements. The first element
is matched to ‘h’; a vector of the remaining elements is matched to
‘t’. Note that vectors of fixed length can also be matched as
actual vectors: The rule ‘cons(a,cons(b,[])) := cons(a+b,[])’ is
equivalent to the rule ‘[a,b] := [a+b]’.
‘rcons(t,h)’
This is like ‘cons’, except that the _last_ element is matched to
‘h’, with the remaining elements matched to ‘t’.
‘apply(f,args)’
This matches any function call. The name of the function, in the
form of a variable, is matched to ‘f’. The arguments of the
function, as a vector of zero or more objects, are matched to
‘args’. Constants, variables, and vectors do _not_ match an
‘apply’ pattern. For example, ‘apply(f,x)’ matches any function
call, ‘apply(quote(f),x)’ matches any call to the function ‘f’,
‘apply(f,[a,b])’ matches any function call with exactly two
arguments, and ‘apply(quote(f), cons(a,cons(b,x)))’ matches any
call to the function ‘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 ‘f’ by name, would be
‘apply(quote(f), x :: vlen(x) >= 2)’. Here’s a more interesting
sample use of ‘apply’:
apply(f,[x+n]) := n + apply(f,[x])
:: in(f, [floor,ceil,round,trunc]) :: integer(n)
Note, however, that this will be slower to match than a rule set
with four 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 ‘apply’, Calc must try the rule for every
single formula and sub-formula. If the top-level function in the
pattern is, say, ‘floor’, then Calc invokes the rule only for
sub-formulas which are calls to ‘floor’.
Formulas normally written with operators like ‘+’ are still
considered function calls: ‘apply(f,x)’ matches ‘a+b’ with ‘f =
add’, ‘x = [a,b]’.
You must use ‘apply’ for meta-variables with function names on both
sides of a rewrite rule: ‘apply(f, [x]) := f(x+1)’ is _not_
correct, because it rewrites ‘spam(6)’ into ‘f(7)’. The righthand
side should be ‘apply(f, [x+1])’. Also note that you will have to
use No-Simplify mode (‘m O’) when entering this rule so that the
‘apply’ isn’t evaluated immediately to get the new rule ‘f(x) :=
f(x+1)’. Or, use ‘s e’ to enter the rule without going through the
stack, or enter the rule as ‘apply(f, [x]) := apply(f, [x+1])
:: 1’. Conditional Rewrite Rules.
‘select(x)’
This is used for applying rules to formulas with selections;
Selections with Rewrite Rules.
Special functions for the righthand sides of rules are:
‘quote(x)’
The notation ‘quote(x)’ is changed to ‘x’ when the righthand side
is used. As far as the rewrite rule is concerned, ‘quote’ is
invisible. However, ‘quote’ has the special property in Calc that
its argument is not evaluated. Thus, while it will not work to put
the rule ‘t(a) := typeof(a)’ on the stack because ‘typeof(a)’ is
evaluated immediately to produce ‘t(a) := 100’, you can use ‘quote’
to protect the righthand side: ‘t(a) := quote(typeof(a))’. (
Conditional Rewrite Rules, for another trick for protecting rules
from evaluation.)
‘plain(x)’
Special properties of and simplifications for the function call ‘x’
are not used. One interesting case where ‘plain’ is useful is the
rule, ‘q(x) := quote(x)’, trying to expand a shorthand notation for
the ‘quote’ function. This rule will not work as shown; instead of
replacing ‘q(foo)’ with ‘quote(foo)’, it will replace it with
‘foo’! The correct rule would be ‘q(x) := plain(quote(x))’.
‘cons(h,t)’
Where ‘t’ is a vector, this is converted into an expanded vector
during rewrite processing. Note that ‘cons’ is a regular Calc
function which normally does this anyway; the only way ‘cons’ is
treated specially by rewrites is that ‘cons’ on the righthand side
of a rule will be evaluated even if default simplifications have
been turned off.
‘rcons(t,h)’
Analogous to ‘cons’ except putting ‘h’ at the _end_ of the vector
‘t’.
‘apply(f,args)’
Where ‘f’ is a variable and ARGS is a vector, this is converted to
a function call. Once again, note that ‘apply’ is also a regular
Calc function.
‘eval(x)’
The formula ‘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 ‘cons’ and ‘apply’ are always treated. However, there is a
slight difference: ‘cons(2+3, [])’ with default simplifications off
will be converted to ‘[2+3]’, whereas ‘eval(cons(2+3, []))’ will be
converted to ‘[5]’.
‘evalsimp(x)’
The formula ‘x’ has meta-variables substituted in the usual way,
then algebraically simplified.
‘evalextsimp(x)’
The formula ‘x’ has meta-variables substituted in the normal way,
then “extendedly” simplified as if by the ‘a e’ command.
‘select(x)’
Selections with Rewrite Rules.
There are also some special functions you can use in conditions.
‘let(v := x)’
The expression ‘x’ is evaluated with meta-variables substituted.
The algebraic simplifications are _not_ applied by default, but ‘x’
can include calls to ‘evalsimp’ or ‘evalextsimp’ as described above
to invoke higher levels of simplification. The result of ‘x’ is
then bound to the meta-variable ‘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,
‘v’ may be any pattern in which case the result of evaluating ‘x’
is matched to that pattern, binding any meta-variables that appear
in that pattern. Note that ‘let’ can only appear by itself as a
condition, or as one term of an ‘&&’ which is a whole condition: It
cannot be inside an ‘||’ term or otherwise buried.
The alternate, equivalent form ‘let(v, x)’ is also recognized.
Note that the use of ‘:=’ by ‘let’, while still being
assignment-like in character, is unrelated to the use of ‘:=’ in
the main part of a rewrite rule.
As an example, ‘f(a) := g(ia) :: let(ia := 1/a) :: constant(ia)’
replaces ‘f(a)’ with ‘g’ of the inverse of ‘a’, if that inverse
exists and is constant. For example, if ‘a’ is a singular matrix
the operation ‘1/a’ is left unsimplified and ‘constant(ia)’ fails,
but if ‘a’ is an invertible matrix then the rule succeeds. Without
‘let’ there would be no way to express this rule that didn’t have
to invert the matrix twice. Note that, because the meta-variable
‘ia’ is otherwise unbound in this rule, the ‘let’ condition itself
always “succeeds” because no matter what ‘1/a’ evaluates to, it can
successfully be bound to ‘ia’.
Here’s another example, for integrating cosines of linear terms:
‘myint(cos(y),x) := sin(y)/b :: let([a,b,x] := lin(y,x))’. The
‘lin’ function returns a 3-vector if its argument is linear, or
leaves itself unevaluated if not. But an unevaluated ‘lin’ call
will not match the 3-vector on the lefthand side of the ‘let’, so
this ‘let’ both verifies that ‘y’ is linear, and binds the
coefficients ‘a’ and ‘b’ for use elsewhere in the rule. (It would
have been possible to use ‘sin(a x + b)/b’ for the righthand side
instead, but using ‘sin(y)/b’ avoids gratuitous rearrangement of
the argument of the sine.)
Similarly, here is a rule that implements an inverse-‘erf’
function. It uses ‘root’ to search for a solution. If ‘root’
succeeds, it will return a vector of two numbers where the first
number is the desired solution. If no solution is found, ‘root’
remains in symbolic form. So we use ‘let’ to check that the result
was indeed a vector.
ierf(x) := y :: let([y,z] := root(erf(a) = x, a, .5))
‘matches(v,p)’
The meta-variable V, which must already have been matched to
something elsewhere in the rule, is compared against pattern P.
Since ‘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 ‘&&’, then you get the special extra feature that
meta-variables which are bound to things inside P can be used
elsewhere in the surrounding rewrite rule.
The only real difference between ‘let(p := v)’ and ‘matches(v, p)’
is that the former evaluates ‘v’ using the default simplifications,
while the latter does not.
‘remember’
This is actually a variable, not a function. If ‘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, ‘remember’ is ignored. The lefthand side is
enclosed in ‘quote’ in the added rule if it contains any variables.
For example, the rule ‘f(n) := n f(n-1) :: remember’ applied to
‘f(7)’ will add the rule ‘f(7) := 7 f(6)’ to the front of the rule
set. The rule set ‘EvalRules’ works slightly differently: There,
the evaluation of ‘f(6)’ will complete before the result is added
to the rule set, in this case as ‘f(7) := 5040’. Thus ‘remember’
is most useful inside ‘EvalRules’.
It is up to you to ensure that the optimization performed by
‘remember’ is safe. For example, the rule ‘foo(n) := n ::
evalv(eatfoo) > 0 :: remember’ is a bad idea (‘evalv’ is the
function equivalent of the ‘=’ command); if the variable ‘eatfoo’
ever contains 1, rules like ‘foo(7) := 7’ will be added to the rule
set and will continue to operate even if ‘eatfoo’ is later changed
to 0.
‘remember(c)’
Remember the match as described above, but only if condition ‘c’ is
true. For example, ‘remember(n % 4 = 0)’ in the above factorial
rule remembers only every fourth result. Note that ‘remember(1)’
is equivalent to ‘remember’, and ‘remember(0)’ has no effect.
Info Catalog
calc: Algebraic Properties of Rewrite Rules
calc: Rewrite Rules
calc: Composing Patterns in Rewrite Rules