Reduce (computer algebra system)

REDUCE

CSL REDUCE on Microsoft Windows
Developer(s)	Anthony C. Hearn et al.
Initial release	1968 (1968)
Stable release	6860 (August 2024 (2024-08)) [±]
Repository	sourceforge.net/projects/reduce-algebra/
Written in	Standard Lisp
Operating system	Cross-platform
Type	Computer algebra system
License	Modified BSD license
Website	reduce-algebra.sourceforge.io

REDUCE is a general-purpose computer algebra system originally geared towards applications in physics.

The development of REDUCE was started in 1963 by Anthony C. Hearn. Since then, many scientists from all over the world have contributed to its development. REDUCE was open-sourced in December 2008 and is available for free under a modified BSD license on SourceForge. Previously it had cost $695.

REDUCE is written entirely in its own Lisp dialect called Standard Lisp, expressed in an ALGOL-like syntax called RLISP that is also used as the basis for REDUCE's user-level language.

Implementations of REDUCE are available on most variants of Unix, Linux, Microsoft Windows, or Apple Macintosh systems by using an underlying Portable Standard Lisp (PSL) or Codemist Standard Lisp (CSL) implementation. CSL REDUCE offers a graphical user interface. REDUCE can also be built on other Lisps, such as Common Lisp. The Julia package Reduce.jl uses REDUCE as a backend and implements its semantics in Julia style.

Features

• arbitrary precision integer, rational, complex and floating-point arithmetic
• expressions and functions involving one or more variables
• algorithms for polynomials, rational and transcendental functions
• facilities for the solution of a variety of algebraic equations
• automatic and user-controlled simplification of expressions
• substitutions and pattern matching in a wide variety of forms
• symbolic differentiation, indefinite and definite integration
• solution of ordinary differential equations
• computations with a wide variety of special functions
• general matrix and non-commutative algebra
• plotting in 2 and 3 dimensions of
  • graphs of functions
  • arbitrary points, lines and curves
• Dirac matrix calculations of interest in high energy physics
• quantifier elimination and decision for interpreted first-order logic
• powerful intuitive user-level programming language

Syntax

The REDUCE language is a high-level structured programming language based on ALGOL 60 (but with Standard Lisp semantics), although it does not support all ALGOL 60 syntax. It is similar to Pascal, which evolved from ALGOL 60, and Modula, which evolved from Pascal.

REDUCE is a free-form language, meaning that spacing and line breaks are not significant, but consequently input statements must be separated from each other and all input must be terminated with either a semi-colon (;) or a dollar sign ($). The difference is that if the input results in a useful (non-nil) value then it will be output if the separator is a semi-colon (;) but hidden if it is a dollar sign ($). The assignment operator is colon-equal (:=), which in its simplest usage assigns to the variable on its left the value of the expression on its right. However, a REDUCE variable can have no value, in which case it is displayed as its name, in order to allow mathematical expressions involving indeterminates to be constructed and manipulated. The simplest way to use REDUCE is interactively: type input after the last input prompt, terminate it with semi-colon and press the Return or Enter key; REDUCE processes the input and displays the result. This is illustrated in the screenshot.

Identifiers and strings

Programming languages use identifiers to name constructs such as variables and functions, and strings to store text. A REDUCE identifier must begin with a letter and can be followed by letters, digits and underscore characters (_). A REDUCE identifier can also include any character anywhere if it is input preceded by an exclamation mark (!). A REDUCE string is any sequence of characters delimited when input by double quote characters ("). A double quote can be included in a string by entering two double quotes; no other escape mechanism is implemented within strings. An identifier can be used instead of a string in most situations in REDUCE, such as to represent a file name.

REDUCE source code was originally written in all upper-case letters, as were all programming languages in the 1960s. (Hence, the name REDUCE is normally written in all upper-case.) However, modern REDUCE is case-insensitive (by default), which means that it ignores the case of letters, and it is normally written in lower-case. (The REDUCE source code has been converted to lower case.) The exceptions to this rule are that case is preserved within strings and when letters in identifiers are preceded by an exclamation mark (!). Hence, it is conventional to use snake-case (e.g. long_name) rather than camel-case (e.g. longName) for REDUCE identifiers, because camel-case gets lost without also using exclamation marks.

Hello World programs

Below is a REDUCE "Hello, World!" program, which is almost as short as such a program could possibly be!

"Hello, World!";

REDUCE displays the output

Hello, World!

Another REDUCE "Hello, World!" program, which is slightly longer than the version above, uses an identifier as follows

!Hello!,! !World!!;

CSL REDUCE displays the same output as shown above. (Other REDUCE GUIs may italicise this output on the grounds that it is an identifier rather than a string.)

Statements and expressions

Because REDUCE inherits Lisp semantics, all programming constructs have values. Therefore, the only distinction between statements and expressions is that the value of an expression is used but the value of a statement is not. The terms statement and expression are interchangeable, although a few constructs always return the Lisp value nil and so are always used as statements.

Structured programming

REDUCE supports conditional and repetition statements, some of which are controlled by a boolean expression, which is any expression whose value can be either true or false, such as $x>0$. (The REDUCE user-level language does not explicitly support constants representing true or false although, as in C and related languages, 0 has the boolean value false, whereas 1 and many other non-zero values have the boolean value true.)

Conditional statements: if ... then ... else

The conditional statement has the form

if boolean expression then statement

which can optionally be followed by

else statement

For example, the following conditional statement ensures that the value of $n$, assumed to be numerical, is positive. (It effectively implements the absolute value function.)

if n < 0 then n := -n

The following conditional statement, used as an expression, avoids an error that would be caused by dividing by 0.

recip_x := if x = 0 then infinity else 1/x

Repetition statements: for ...

The for statement is a flexible loop construct that executes statement repeatedly a number of times that must be known in advance. One version has the form

for variable := initial step increment until final do statement

where variable names a variable whose value can be used within statement, and initial, increment and final are numbers (preferably integers). The value of variable is initialized to initial and statement is executed, then the value of variable is repeatedly increased by increment and the statement executed again, provided the value of variable is not greater than final. The common special case "initial step 1 until final" can be abbreviated as "initial : final".

The following for statement computes the value of $n!$ as the value of the variable fac.

n := 5;
fac := 1$ for r := 2 : n do fac := fac*r; fac;

Another version of the for statement iterates over a list, and the keyword do can be replaced by product, sum, collect or join, in which case the for statement becomes an expression and the controlled statement is treated as an expression. With product, the value is the product of the values of the controlled statement; with sum, the value is the sum of the values of the controlled statement; with collect, the value is the values of the controlled statement collected into a list; with join, the value is the values of the controlled statement, which must be lists, joined into one list.

The following for statement computes the value of $n!$ much more succinctly and elegantly than the previous example.

n := 5;
for r := 2 : n product r;

Repetition statements: while ... do; repeat ... until

The two loop statements

while boolean expression do statement
repeat statement until boolean expression

are closely related to the conditional statement and execute statement repeatedly a number of times that need not be known in advance. Their difference is that while repetition stops when boolean expression becomes false whereas repeat repetition stops when boolean expression becomes true. Also, repeat always executes statement at least once and it can be used to initialize boolean expression, whereas when using while boolean expression must be initialized before entering the loop.

The following while statement computes the value of $n!$ as the value of the variable fac. Note that this code treats the assignment n := n - 1 as an expression and uses its value.

n := 5;
fac := n$ while n > 1 do fac := fac*(n := n - 1); fac;

Programming paradigms

REDUCE's user-level language supports several programming paradigms, as illustrated in the algebraic programming examples below.

Since it is based on Lisp, which is a functional programming language, REDUCE supports functional programming and all statements have values (although they are not always useful). REDUCE also supports procedural programming by ignoring statement values. Algebraic computation usually proceeds by transforming a mathematical expression into an equivalent but different form. This is called simplification, even though the result might be much longer. (The name REDUCE is a pun on this problem of intermediate expression swell!) In REDUCE, simplification occurs automatically when an expression is entered or computed, controlled by simplification rules and switches. In this way, REDUCE supports rule-based programming, which is the classic REDUCE programming paradigm. In early versions of REDUCE, rules and switches could only be set globally, but modern REDUCE also supports local setting of rules and switches, meaning that they control the simplification of only one expression. REDUCE programs often contain a mix of programming paradigms.

Algebraic programming examples

The screenshot shows simple interactive use.

As a simple programming example, consider the problem of computing the $n$^th Taylor polynomial of the function $f(x)$ about the point $x=a$, which is given by the formula $\sum _{r=0}^{n}{\frac {f^{(r)}(a)}{r!}}(x-a)^{r}$. Here, $f^{(r)}$ denotes the $r$^th derivative of $f$ evaluated at the point $a$ and $r!$ denotes the factorial of $r$. (However, note that REDUCE includes sophisticated facilities for power-series expansion.)

As an example of functional programming in REDUCE, here is an easy way to compute the 5^th Taylor polynomial of $\sin x$ about 0. In the following code, the control variable r takes values from 0 through 5 in steps of 1, df is the REDUCE differentiation operator and the operator sub performs substitution of its first argument into its second. Note that this code is very similar to the mathematical formula above (with $n=5$ and $a=0$).

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

produces by default the output

${\frac {x\left(x^{4}-20x^{2}+120\right)}{120}}$

This is correct, but it doesn't look much like a Taylor series. That can be fixed by changing a few output-control switches and then evaluating the special variable ws, which stands for workspace and holds the last non-empty output expression:

off allfac; on revpri, div; ws;

$x-{\frac {1}{6}}x^{3}+{\frac {1}{120}}x^{5}$

As an example of procedural programming in REDUCE, here is a procedure to compute the general Taylor polynomial, which works for functions that are well-behaved at the expansion point $a$.

procedure my_taylor(f, x, x0, n);
   % Return the nth Taylor polynomial of f
   % as a function of x about x0.
   begin scalar result := sub(x = x0, f), mul := 1;
      for r := 1:n do <<
         f := df(f, x);
         mul := mul*(x - x0)/r;
         result := result + sub(x = x0, f)*mul
      >>;
      return result
   end;

The procedure is called my_taylor because REDUCE already includes an operator called taylor. All the text following a % sign up to the end of the line is a comment. The keyword scalar introduces and initializes two local variables, result and mul. The keywords begin and end delimit a block of code that may include local variables and may return a value, whereas the symbols << and >> delimit a group of statements without introducing local variables.

The procedure may be called as follows to compute the same Taylor polynomial as above.

my_taylor(sin x, x, 0, 5);

File handling

In order to develop non-trivial computations, it is convenient to store source code in a file and have REDUCE read it instead of interactive input. REDUCE input should be plain text (not rich text as produced by word-processing applications). REDUCE filenames are arbitrary. The REDUCE source code uses the filename extension .red for the main source code and .tst for the test files, and for that reason REDUCE GUIs such as CSL REDUCE normally offer to input files with those extensions by default, but on platforms such as Microsoft Windows the extension .txt may be more convenient. It is recommended to end a REDUCE input file with the line

;end;

as an end-of-file marker. This is something of a historical quirk but it avoids potential warning messages. Apart from that, an input file can contain whatever might be entered interactively into REDUCE. The command

in file1, file2, ...

inputs each of the named files in succession into REDUCE, essentially as if their contents had been entered interactively, after which REDUCE waits for further interactive input. If the separator used to terminate this command is a semi-colon (;) then the file content is echoed as output; if the separator is a dollar sign ($) then the file content is not echoed.

REDUCE filenames can be either absolute or relative to the current directory; when using a REDUCE GUI absolute filenames are safer because it is not obvious what the current directory is! Filenames can be specified as either strings or identifiers; strings (in double quotes) are usually more convenient because otherwise filename elements such as directory separators and dots must be escaped with an exclamation mark (!). Note that the Microsoft Windows directory or folder separator, backslash (\), does not need to be doubled in REDUCE strings because backslash is not an escape character in REDUCE, but REDUCE on Microsoft Windows also accepts forward slash (/) as the directory separator.

REDUCE output can be directed to a file instead of the interactive display by executing the command

out file;

Output redirection can be terminated permanenty by executing the command

shut file;

or temporarily by executing the command

out t;

There are similar mechanisms for directing a compiled version of the REDUCE input to a file and loading compiled code, which is the basis for building REDUCE and can be used to extend it. REDUCE GUIs provide menu support for some or all of the file handling described above.

Types and variable scope

REDUCE inherits dynamic scoping from Lisp, which means that data have types but variables themselves do not: the type of a variable is the type of the data assigned to it. The simplest REDUCE data types are Standard Lisp atomic types such as identifiers, machine numbers (i.e. "small" integers and floating-point numbers supported directly by the computer hardware), and strings. Most other REDUCE data types are represented internally as Lisp lists whose first element (car) indicates the data type. For example, the REDUCE input

mat((1, 2), (3, 4));

produces the display

$\left({\begin{matrix}1&2\\3&4\end{matrix}}\right)$

and the internal representation of this matrix is the Lisp list

(mat (1 2) (3 4))

The main algebraic objects used in REDUCE are quotients of two possibly-multivariate polynomials, the indeterminates of which, called kernels, may in fact be functions of one or more variables, e.g. the input

z := (x + y^2)/f(x,y);

produces the display

$z\ \mathrm {:=} \ {\frac {x+y^{2}}{f\left(x,y\right)}}$

REDUCE uses two representations for such algebraic objects. One is called prefix form, which is just the Standard Lisp code for the expression and is convenient for operations such as input and output; e.g. for $z$ it is

(quotient (plus x (expt y 2)) (f x y))

The other is called standard quotient form, which is better for performing algebraic manipulations such as addition; e.g. for $z$ it is

(!*sq ((((x . 1) . 1) ((y . 2) . 1)) (((f x y) . 1) . 1)) t)

REDUCE converts between these two representations as necessary, but tries to retain standard quotient form as much as possible to avoid the conversion overhead.

Because variables have no types there are no variable type declarations in REDUCE, but there are variable scope declarations. The scope of a variable refers to the range of a program throughout which it has the same significance. By default, REDUCE variables are automatically global in scope, meaning that they have the same significance everywhere, i.e. once a variable has been assigned a value, it will evaluate to that same value everywhere. Variables can be declared to have scope limited to a particular block of code by delimiting that block of code by the keywords begin and end, and declaring the variables scalar at the start of the block, using the following syntax (as illustrated in the algebraic programming examples above):

begin scalar variable1, variable2, ...;
   statements
end

Each variable so declared can optionally be followed by an assignment operator (:=) and an initial value. The keyword scalar should be read as meaning local. (The reason for the name scalar is buried in the history of REDUCE, but it was probably chosen to distinguish local variables from the relativistic 4-vectors and Dirac gamma matrices defined in the high-energy physics package, which was the original core of REDUCE.)

The scalar keyword can be replaced by integer or real. The difference is that integer variables are initialized by default to 0, whereas scalar and real variables are initialized by default to the Lisp value nil (which has the algebraic value 0 anyway). This distinction is more significant in the REDUCE implementation language, RLISP, also known as symbolic or lisp mode. Otherwise, it is useful as documentation of the intended use of local variables.

There are two other variable declarations that are used only in the implementation of REDUCE, i.e. in symbolic mode. The REDUCE begin...end block described above is translated into a Standard Lisp prog form by the REDUCE parser, and all Standard Lisp variables should either be bound in prog forms, or declared global or fluid. In RLISP, these declarations look like this:

fluid '(variable1, variable2, ...)
global '(variable1, variable2, ...)

A global variable cannot be rebound in a prog form, whereas a fluid variable can. This distinction is normally only significant to a Lisp compiler and is used to maximize efficiency; in interpreted code these declarations can be skipped and undeclared variables are effectively fluid.

See also

• List of computer algebra systems
• ALTRAN
• REDUCE Meets CAMAL - J. P. Fitch [1]

External links

• REDUCE on SourceForge
• Anthony C. Hearn at al., REDUCE User's Manual [ HTML | PDF ].
• Anthony C. Hearn, "REDUCE: The First Forty Years". Invited paper presented at the A3L Conference in Honor of the 60th Birthday of Volker Weispfenning, April 2005.
• Andrey Grozin, "TeXmacs-Reduce interface", April 2012.