calc: Nested Formulas with Rewrite Rules
11.11.7 Nested Formulas with Rewrite Rules
------------------------------------------
When ‘a r’ (‘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 NEW part of the
rule.
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 every 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.
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 ‘ln(a b)
:= ln(a) + ln(b)’ and the reverse ‘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.
To avoid disaster, Calc normally stops after 100 changes have been
made to the formula. This will be enough for most multiple rewrites,
but it will keep an endless loop of rewrites from locking up the
computer forever. (On most systems, you can also type ‘C-g’ to halt any
Emacs command prematurely.)
To change this limit, give a positive numeric prefix argument. In
particular, ‘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).
You can also put a “function call” ‘iterations(N)’ in place of a rule
anywhere in your rules vector (but usually at the top). Then, N will be
used instead of 100 as the default number of iterations for this rule
set. You can use ‘iterations(inf)’ if you want no iteration limit by
default. A prefix argument will override the ‘iterations’ limit in the
rule set.
[ iterations(1),
f(x) := f(x+1) ]
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.
A prefix argument of zero sets the limit to infinity. Use with
caution!
Given a negative numeric prefix argument, ‘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.
In a formula, ‘rewrite(EXPR, RULES, N)’ does a rewriting operation.
Here EXPR is the expression being rewritten, RULES is the rule, vector
of rules, or variable containing the rules, and N is the optional
iteration limit, which may be a positive integer, a negative integer, or
‘inf’ or ‘-inf’. If N is omitted the ‘iterations’ value from the rule
set is used; if both are omitted, 100 is used.
Info Catalog
calc: Composing Patterns in Rewrite Rules
calc: Rewrite Rules
calc: Multi-Phase Rewrite Rules