10.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 from 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.