Programming Paradigms

For specifying symbolic tasks and algorithms REDUCE offers a set of different programming paradigms:

Using REDUCE as a desk calculator for symbolic and numeric expressions is the simplest approach. Formulas can be entered, combined, stored and processed by a set of powerful operators like differentiation, integration, polynomial GCD, factorization etc. Any formula will be processed immediately with the objective of finding its most complete simplification, and the result will be presented on the screen as soon as available.

Example: Taylor polynomial for x*sin(x)

for i:=0:5 sum 
  sub(x=0,df(x*sin(x),x,i)) * x**i 
            / factorial(i);

    1   4    2
 - ---*X  + X
    6

Evaluation of a single formula with the immediate output of the result is a special case of a statement of the REDUCE programming language, which, from a syntactical standpoint, is part of the ALGOL family. This programming language allows the user to code complicated evaluation sequences such as conditionals, groups, blocks, iterations controlled by counters or list structures, and the definition of complete parameterized procedures with local variables.

Example: definition of a procedure for expanding a function to a Taylor polynomial:

procedure tay(u,x,n);
  begin scalar ser,fac;  
    ser:=sub(x=0,u);fac:=1; 
    for i:=1:n do 
    <<u:=df(u,x); fac:=fac*i;   
      ser:=ser+sub(x=0,u)*x**i/fac >>;
    return(ser);  
  end;

A call to this procedure:

tay(x*sin(x),x,5);

    1   4    2
 - ---*X  + X
    6

Example: a recursive program for collecting a basis of Legendre polynomials from the recurrence relation:

    P{n+1,x) = ((2n+1)*x*P(n,x) - n*P(n-1,x))/(n+1)

The infix operator "." adds a new element to the head of a list.

procedure Legendre_basis(m,x);
  % Start with basis of order 1
   Legendre_basis_aux(m,x,1,{x,1});

procedure Legendre_basis_aux(m,x,n,ls);
    % ls contains polynomials n, n-1, n-2 ...
  if n>=m then ls     % done
  else Legendre_basis_aux(m,x,n+1,
  (((2n+1)*x*first ls - n*second ls)/(n+1))
       . ls);

A call to this procedure

Legendre_basis(3,z);

  5   3    3
{---*Z  - ---*Z,
  2        2

  3   2    1
 ---*Z  - ---,
  2        2

 Z, 1}

Rule Oriented Programming

In REDUCE, global algebraic relations can be formulated with rules. A rule links an algebraic search pattern to a replacement pattern, sometimes controlled by additional conditions. Rules can be activated (and deactivated) globally, or they can be invoked with a limited scope for single evaluations. So the user has an arbitrary precise control over the algebraic simplification.

Example: Expanding trigonometric functions for combined arguments; the tilde symbol represents an implicit for-all.

Sin_Cos_rules:=
{sin(~x+~y)=>sin(x)*cos(y) + cos(x)*sin(y),
 cos(~x+~y)=>cos(x)*cos(y) - sin(x)*sin(y)};

Global activation is achieved by

let Sin_Cos_rules;

Note: REDUCE has no predefined "knowledge" about these relations for trigonometric functions, as they can be used as production rules in either form depending on whether expansion or collection is required; only the user can define which mode is adequate for his problem.

Using rules, a complete calculus can be implemented; the rule syntax here is very close to the mathematical notation for multistep cases.

Example: Definition of Hermite polynomials:

operator Hermite;
Hermite_rules:=
{Hermite(0,~x) => 1,
 Hermite(1,~x) => 2*x,
 Hermite(~n,~x) => 2*x*Hermite(n-1,x)
          -2*(n-1)*Hermite(n-2,x)
              when n>1};

let Hermite_rules;

Generation of a Hermite polynomial:

Hermite(4,z);

    4       2
16*Z  - 48*Z  + 12

The paradigms described so far give access to the REDUCE facilities at the top level. They enable a compact programming close to the application problem. No knowledge about the internal data structures is necessary, since REDUCE converts data automatically to the formats needed locally for each evaluation step. On the other hand, such frequent conversions are time consuming and so for very large problems it might be desirable to keep intermediate results in the internal form in order to avoid the conversion overhead. Here the ``symbolic'' mode of REDUCE can be used, which allows the access to internal data structures and procedures directly with the same syntax as in top level programming.

Of course, this level of programming requires some knowledge about LISP and about internal REDUCE structures. However, it enables the implementation of algorithms with the highest possible efficiency.