15 Procedures

It is often useful to name a statement for repeated use in calculations with varying parameters, or to define a complete evaluation procedure for an operator. REDUCE offers a procedural declaration for this purpose. Its general syntax is:

[⟨procedural type⟩] PROCEDURE ⟨name⟩[⟨varlist⟩];⟨statement⟩;

where

⟨varlist⟩ ::= (⟨variable⟩,…,⟨variable⟩)

This will be explained more fully in the following sections.

In the algebraic mode of REDUCE the ⟨procedural type⟩ can be omitted, since the default is ALGEBRAIC. Procedures of type INTEGER or REAL may also be used. In the former case, the system checks that the value of the procedure is an integer. At present, such checking is not done for a real procedure, although this will change in the future when a more complete type checking mechanism is installed. Users should therefore only use these types when appropriate. An empty variable list may also be omitted.

All user-defined procedures are automatically declared to be operators.

In order to allow users relatively easy access to the whole REDUCE source program, system procedures are not protected against user redefinition. If a procedure is redefined, a message

        *** <procedure name> REDEFINED

is printed. If this occurs, and the user is not redefining his own procedure, he is well advised to rename it, and possibly start over (because he has already redefined some internal procedure whose correct functioning may be required for his job!)

All required procedures should be defined at the top level, since they have global scope throughout a program. In particular, an attempt to define a procedure within a procedure will cause an error to occur.

15 Procedures

15.1 Procedure Heading
15.2 Procedure Body
15.3 Matrix-valued Procedures
15.4 Using LET Inside Procedures
15.5 LET Rules as Procedures
15.6 REMEMBER Statement

15.1 Procedure Heading

Each procedure has a heading consisting of the word procedure (optionally preceded by the word ALGEBRAIC), followed by the name of the procedure to be defined, and followed by its formal parameters – the symbols that will be used in the body of the definition to illustrate what is to be done. There are three cases:

No parameters. Simply follow the procedure name with a terminator (semicolon or dollar sign).

        procedure abc;

When such a procedure is used in an expression or command, abc(), with empty parentheses, must be written.

One parameter. Enclose it in parentheses or just leave at least one space, then follow with a terminator.

        procedure abc(x);

        procedure abc x;

More than one parameter. Enclose them in parentheses, separated by commas, then follow with a terminator.

        procedure abc(x,y,z);

Referring to the last example, if later in some expression being evaluated the symbols abc(u,p*q,123) appear, the operations of the procedure body will be carried out as if x had the same value as u does, y the same value as p*q does, and z the value 123. The values of x, y, z, after the procedure body operations are completed are unchanged. So, normally, are the values of u, p, q, and (of course) 123. (This is technically referred to as call by value.)

The reader will have noted the word normally a few lines earlier. The call by value protections can be bypassed if necessary, as described elsewhere.

15.2 Procedure Body

Following the delimiter that ends the procedure heading must be a single statement defining the action to be performed or the value to be delivered. A terminator must follow the statement. If it is a semicolon, the name of the procedure just defined is printed. It is not printed if a dollar sign is used.

If the result wanted is given by a formula of some kind, the body is just that formula, using the variables in the procedure heading.

Simple Example: If f(x) is to mean (x+5)*(x+6)/(x+7), the entire procedure definition could read

        procedure f x; (x+5)*(x+6)/(x+7);

Then f(10) would evaluate to 240/17, f(a-6) to a*(a-1)/(a+1), and so on.

More Complicated Example: Suppose we need a function p(n,x) that, for any positive integer n, is the Legendre polynomial of order n. We can define this operator using the textbook formula defining these functions: $p_n(x) = \frac{1}{n!} \frac{d^n}{dy^n} \frac{1}{(y^2-2xy+1)^{\frac{1}{2}}} \bigg|_{y=0}$ Put into words, the Legendre polynomial $p_n(x)$ is the result of substituting $y = 0$ in the $n^{th}$ partial derivative with respect to $y$ of a certain fraction involving $x$ and $y$, then dividing that by $n!$. This verbal formula can easily be written in REDUCE:

        procedure p(n,x);  
           sub(y=0,df(1/(y^2-2*x*y+1)^(1/2),y,n))  
               /(for i:=1:n product i);

Having input this definition, the expression evaluation

        2p(2,w);

would result in the output

           2  
        3*W  - 1 .

If the desired process is best described as a series of steps, then a group or compound statement can be used.

Example: The above Legendre polynomial example can be rewritten as a series of steps instead of a single formula as follows:

        procedure p(n,x);  
          begin scalar seed,deriv,top,fact;  
               seed:=1/(y^2 - 2*x*y +1)^(1/2);  
               deriv:=df(seed,y,n);  
               top:=sub(y=0,deriv);  
               fact:=for i:=1:n product i;  
               return top/fact  
          end;

Procedures may also be defined recursively. In other words, the procedure body can include references to the procedure name itself, or to other procedures that themselves reference the given procedure. As an example, we can define the Legendre polynomial through its standard recurrence relation:

        procedure p(n,x);  
           if n<0 then rederr ~Invalid argument to P(N,X)~  
            else if n=0 then 1  
            else if n=1 then x  
            else ((2*n-1)*x*p(n-1,x)-(n-1)*p(n-2,x))/n;

The operator rederr in the above example provides for a simple error exit from an algebraic procedure (and also a block). It can take a string as argument.

It should be noted however that all the above definitions of p(n,x) are quite inefficient if extensive use is to be made of such polynomials, since each call effectively recomputes all lower order polynomials. It would be better to store these expressions in an array, and then use say the recurrence relation to compute only those polynomials that have not already been derived. We leave it as an exercise for the reader to write such a definition.

15.3 Matrix-valued Procedures

Normally, procedures can only return scalar values. In order for a procedure to return a matrix, it has to be declared of type matrixproc:

        matrixproc SkewSym1 (w);  
           mat((0,-w(3,1),w(2,1)),  
               (w(3,1),0,-w(1,1)),  
               (-w(2,1), w(1,1), 0));

Following this declaration, the call to SkewSym1 can be used as a matrix, e.g.

        X := SkewSym1(mat((qx),(qy),(qz)));  
 
 
             [  0     - qz   qy  ]  
             [                   ]  
        x := [ qz      0     - qx]  
             [                   ]  
             [ - qy   qx      0  ]  
 
        X * mat((rx),(ry),(rz));  
 
 
        [ qy*rz - qz*ry  ]  
        [                ]  
        [ - qx*rz + qz*rx]  
        [                ]  
        [ qx*ry - qy*rx  ]

15.4 Using LET Inside Procedures

By using let instead of an assignment in the procedure body it is possible to bypass the call-by-value protection. If x is a formal parameter or local variable of the procedure (i.e. is in the heading or in a local declaration), and let is used instead of := to make an assignment to x, e.g.

        let x = 123;

then it is the variable that is the value of x that is changed. This effect also occurs with local variables defined in a block. If the value of x is not a variable, but a more general expression, then it is that expression that is used on the left-hand side of the let statement. For example, if x had the value p*q, it is as if let p*q = 123 had been executed.

15.5 LET Rules as Procedures

The let statement offers an alternative syntax and semantics for procedure definition.

In place of

        procedure abc(x,y,z); <procedure body>;

one can write

        for all x,y,z let abc(x,y,z) = <procedure body>;

There are several differences to note.

If the procedure body contains an assignment to one of the formal parameters, e.g.

        x := 123;

in the procedure case it is a variable holding a copy of the first actual argument that is changed. The actual argument is not changed.

In the let case, the actual argument is changed. Thus, if abc is defined using let, and abc(u,v,w) is evaluated, the value of u changes to 123. That is, the let form of definition allows the user to bypass the protections that are enforced by the call by value conventions of standard procedure definitions.

Example: We take our earlier factorial procedure and write it as a let statement.

        for all n let factorial n =  
                    begin scalar m,s;  
                    m:=1; s:=n;  
                l1: if s=0 then return m;  
                    m:=m*s;  
                    s:=s-1;  
                    go to l1  
                end;

The reader will notice that we introduced a new local variable, s, and set it equal to n. The original form of the procedure contained the statement n:=n-1;. If the user asked for the value of factorial(5) then n would correspond to, not just have the value of, 5, and REDUCE would object to trying to execute the statement 5 := 5 - 1.

If pqr is a procedure with no parameters,

        procedure pqr;  
           <procedure body>;

it can be written as a let statement quite simply:

        let pqr = <procedure body>;

To call procedure pqr, if defined in the latter form, the empty parentheses would not be used: use pqr not pqr() where a call on the procedure is needed.

The two notations for a procedure with no arguments can be combined. pqr can be defined in the standard procedure form. Then a let statement

        let pqr = pqr();

would allow a user to use pqr instead of pqr() in calling the procedure.

A feature available with let-defined procedures and not with procedures defined in the standard way is the possibility of defining partial functions.

    for all x such that numberp x let uvw(x)=<procedure body>;

Now uvw of an integer would be calculated as prescribed by the procedure body, while uvw of a general argument, such as z or p+q (assuming these evaluate to themselves) would simply stay uvw(z) or uvw(p+q) as the case may be.

15.6 REMEMBER Statement

Setting the remember option for an algebraic procedure by

     REMEMBER (PROCNAME:procedure);

saves all intermediate results of such procedure evaluations, including recursive calls. Subsequent calls to the procedure can then be determined from the saved results, and thus the number of evaluations (or the complexity) can be reduced. This mode of evalation costs extra memory, of course. In addition, the procedure must be free of side–effects.

The following examples show the effect of the remember statement on two well–known examples.

procedure H(n);      % Hofstadter’s function  
 if numberp n then  
 << cnn := cnn +1;   % counts the calls  
 if n < 3 then 1 else H(n-H(n-1))+H(n-H(n-2))>>;  
 
remember h;  
 
<< cnn := 0; H(100); cnn>>;  
 
100  
 
% H has been called 100 times only.  
 
procedure A(m,n);    % Ackermann function  
 
 if m=0 then n+1 else  
  if n=0 then A(m-1,1) else  
  A(m-1,A(m,n-1));  
 
remember a;  
 
A(3,3);