11.3 Rule Lists

Rule lists offer an alternative approach to defining substitutions that is different from either sub or let. In fact, they provide the best features of both, since they have all the capabilities of let, but the rules can also be applied locally as is possible with sub. In time, they will be used more and more in REDUCE. However, since they are relatively new, much of the REDUCE code you see uses the older constructs.

A rule list is a list of rules that have the syntax

For example,

    {cos(~x)*cos(~y) => (cos(x+y)+cos(x-y))/2,
     cos(~n*pi)      => (-1)^n when remainder(n,2)=0}

The tilde preceding a variable marks that variable as free for that rule, much as a variable in a for all clause in a let statement. The first occurrence of that variable in each relevant rule must be so marked on input, otherwise inconsistent results can occur. For example, the rule list

        {cos(~x)*cos(~y) => (cos(x+y)+cos(x-y))/2,
         cos(x)^2        => (1+cos(2x))/2}

designed to replace products of cosines, would not be correct, since the second rule would only apply to the explicit argument x. Later occurrences in the same rule may also be marked, but this is optional (internally, all such rules are stored with each relevant variable explicitly marked). The optional when clause allows constraints to be placed on the application of the rule, much as the such that clause in a let statement.

A rule list may be named, for example

    trig1 := {cos(~x)*cos(~y) => (cos(x+y)+cos(x-y))/2,
              cos(~x)*sin(~y) => (sin(x+y)-sin(x-y))/2,
              sin(~x)*sin(~y) => (cos(x-y)-cos(x+y))/2,
              cos(~x)^2       => (1+cos(2*x))/2,
              sin(~x)^2       => (1-cos(2*x))/2};

Such named rule lists may be inspected as needed. E.g., the command trig1; would cause the above list to be printed.

Rule lists may be used in two ways. They can be globally instantiated by means of the command let. For example,

        let trig1;

would cause the above list of rules to be globally active from then on until cancelled by the command clearrules, as in

        clearrules trig1;

clearrules has the syntax

The second way to use rule lists is to invoke them locally by means of a where clause. For example

    cos(a)*cos(b+c)
       where {cos(~x)*cos(~y) => (cos(x+y)+cos(x-y))/2};

or

        cos(a)*sin(b) where trigrules;

The syntax of an expression with a where clause is:

so the first example above could also be written

    cos(a)*cos(b+c)
       where cos(~x)*cos(~y) => (cos(x+y)+cos(x-y))/2;

The effect of this construct is that the rule list(s) in the where clause only apply to the expression on the left of where. They have no effect outside the expression. In particular, they do not affect previously defined where clauses or let statements. For example, the sequence

     let a=>2;
     a where a=>4;
     a;

would result in the output

     4

     2

Although where has a precedence less than any other infix operator, it still binds higher than keywords such as else, then, do, repeat and so on. Thus the expression

        if a=2 then 3 else a+2 where a=>3

will parse as

        if a=2 then 3 else (a+2 where a=>3)

where may be used to introduce auxiliary variables in symbolic mode expressions, as described in Section 21.4. However, the symbolic mode use has different semantics, so expressions do not carry from one mode to the other.

Compatibility Note: In order to provide compatibility with older versions of rule lists released through the Network Library, it is currently possible to use an equal sign interchangeably with the replacement sign => in rules and let statements. However, since this will change in future versions, the replacement sign is preferable in rules and the equal sign in non-rule-based let statements. When an equal sign is used in rules a warning

** Please use => instead of = in rules

will be printed.

Advanced Use of Rule Lists

Some advanced features of the rule list mechanism make it possible to write more complicated rules than those discussed so far, and in many cases to write more compact rule lists. These features are:

• Free operators

• Double slash operator

• Double tilde variables.

A free operator in the left hand side of a pattern will match any operator with the same number of arguments. The free operator is written in the same style as a variable. For example, the implementation of the product rule of differentiation can be written as:

operator diff, !~f, !~g;

prule := {diff(~f(~x) * ~g(~x),x) =>
             diff(f(x),x) * g(x) + diff(g(x),x) * f(x)};

let prule;

diff(sin(z)*cos(z),z);

         cos(z)*diff(sin(z),z) + diff(cos(z),z)*sin(z)

The double slash operator may be used as an alternative to a single slash (quotient) in order to match quotients properly. E.g., in the example of the Gamma function above, one can use:

gammarule :=
  {gamma(~z)//(~c*gamma(~zz)) =>
        gamma(z)/(c*gamma(zz-1)*zz)
                  when fixp(zz -z) and (zz -z) >0,
   gamma(~z)//gamma(~zz) =>
        gamma(z)/(gamma(zz-1)*zz)
                  when fixp(zz -z) and (zz -z) >0};

let gammarule;

gamma(z)/gamma(z+3);

          1
----------------------
  3      2
 z  + 6*z  + 11*z + 6

The above example suffers from the fact that two rules had to be written in order to perform the required operation. This can be simplified by the use of double tilde variables. E.g. the rule list

 GGrule :=  {
    gamma(~z)//(~~c*gamma(~zz)) =>
         gamma(z)/(c*gamma(zz-1)*zz)
             when fixp(zz -z) and (zz -z) >0};

will implement the same operation in a much more compact way. In general, double tilde variables are bound to the neutral element with respect to the operation in which they are used.

Remarks: A double tilde variable as the numerator of a pattern is not allowed. Also, using double tilde variables may lead to recursion errors when the zero case is not handled properly.

let f(~~a * ~x,x)  => a * f(x,x) when freeof (a,x);

f(z,z);

***** f(z,z) improperly defined in terms of itself

% BUT:

let ff(~~a * ~x,x)
       => a * ff(x,x) when freeof (a,x) and a neq 1;

ff(z,z);
                 ff(z,z)

ff(3*z,z);
                 3*ff(z,z)

Displaying Rules Associated with an Operator

The operator showrules takes a single identifier as argument, and returns in rule-list form the operator rules associated with that argument. For example:

showrules log;

                    1
{df(log(~x),~x) => ---,
                    x

         ~x
 df(log(----),~z) => df(log(x),z) - df(log(y),z)}
         ~y

Such rules can then be manipulated further as with any list. For example rhs first ws; has the value 1. Note that an operator may have other properties that cannot be displayed in such a form, such as the fact it is an odd function, or has a definition defined as a procedure.

Order of Application of Rules

If rules have overlapping domains, their order of application is important. In general, it is very difficult to specify this order precisely, so that it is best to assume that the order is arbitrary. However, if only one operator is involved, the order of application of the rules for this operator can be determined from the following:

1.

Rules containing at least one free variable apply before all rules without free variables.

2.

Rules activated in the most recent let command are applied first.

3.

let with several entries generate the same order of application as a corresponding sequence of commands with one rule or rule set each.

4.

Within a rule set, the rules containing at least one free variable are applied in their given order. In other words, the first member of the list is applied first.

5.

Consistent with the first item, any rule in a rule list that contains no free variables is applied after all rules containing free variables.

Example: The following rule set enables the computation of exact values of the Gamma function:

    operator gamma,gamma_error;
    gamma_rules :=
    {gamma(~x)=>sqrt(pi)/2 when x=1/2,
     gamma(~n)=>factorial(n-1) when fixp n and n>0,
     gamma(~n)=>gamma_error(n) when fixp n,
     gamma(~x)=>(x-1)*gamma(x-1) when fixp(2*x) and x>1,
     gamma(~x)=>gamma(x+1)/x when fixp(2*x)};

Here, rule by rule, cases of known or definitely uncomputable values are sorted out; e.g. the rule leading to the error expression will be applied for negative integers only, since the positive integers are caught by the preceding rule, and the last rule will apply for negative odd multiples of \(1/2\) only. Alternatively the first rule could have been written as

        gamma(1/2) => sqrt(pi)/2,

but then the case \(x=1/2\) should be excluded in the when part of the last rule explicitly because a rule without free variables cannot take precedence over the other rules.

Hosted by