perm filename REDUCE.XER[CSP,DOC] blob sn#002724 filedate 1972-10-09 generic text, type T, neo UTF8

			 R E D U C E   2 

		    U S E R ' S   M A N U A L*


		       Anthony  C.  Hearn

		       University of Utah

*This research was sponsored by the Advanced Research Projects Agency
of  the  Department of Defense under Contract No. F30602-70-C-0300 at
the University of Utah, and under Contract No.   SD-183  at  Stanford


	This manual provides the  user  with  a  description  of  the

algebraic  programming  system  REDUCE  2.   The capabilities of this

system include:

   1)	Expansion and ordering of rational functions of polynomials,

   2)	symbolic differentiation of rational functions of polynomials

	and general functions,

   3)	substitutions and pattern matching in a wide variety of forms,

   4)	calculation of the greatest common divisor of two polynomials,

   5)	automatic and user controlled simplification of expressions,

   6)	calculations with symbolic matrices,

   8)	a complete language for symbolic calculations,  in which  the

	REDUCE program itself is written,

   9)	calculations of interest to high energy physicists including

	spin 1/2 and spin 1 algebra,

  10)	tensor operations.

                          TABLE OF CONTENTS

1.  INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . 1-1

2.  STRUCTURE OF PROGRAMS. . . . . . . . . . . . . . . . . . . . . . 2-1
	2.1  Preliminary . . . . . . . . . . . . . . . . . . . . . . 2-1
	2.2  Numbers . . . . . . . . . . . . . . . . . . . . . . . . 2-1
	2.3  Identifiers . . . . . . . . . . . . . . . . . . . . . . 2-2
	2.4  Variables . . . . . . . . . . . . . . . . . . . . . . . 2-2
	2.4.1  Reserved Variables. . . . . . . . . . . . . . . . . . 2-2
	2.5  Operators . . . . . . . . . . . . . . . . . . . . . . . 2-3
	2.5.1  DF. . . . . . . . . . . . . . . . . . . . . . . . . . 2-6
	2.5.2  COS. LOG. SIN . . . . . . . . . . . . . . . . . . . . 2-7
	2.5.3  SUB . . . . . . . . . . . . . . . . . . . . . . . . . 2-7
	2.6  Strings . . . . . . . . . . . . . . . . . . . . . . . . 2-8	
	2.7  Comments  . . . . . . . . . . . . . . . . . . . . . . . 2-8
	2.8  Expressions . . . . . . . . . . . . . . . . . . . . . . 2-8
	2.8.1  Numerical Expressions . . . . . . . . . . . . . . . . 2-9
	2.8.2 Scalar Expressions . . . . . . . . . . . . . . . . . . 2-9
	2.8.3  Boolean Expressions . . . . . . . . . . . . . . . . . 2-9
	2.8.4  Equations . . . . . . . . . . . . . . . . . . . . . .2-10
	2.9  Reserved Words  . . . . . . . . . . . . . . . . . . . .2-10
	2.10  Statements . . . . . . . . . . . . . . . . . . . . . .2-10
	2.10.1  Assignment Statements. . . . . . . . . . . . . . . .2-11
	2.10.2  Conditional Statements . . . . . . . . . . . . . . .2-12
	2.10.3  FOR Statements . . . . . . . . . . . . . . . . . . .2-12
	2.10.4  GO TO Statements . . . . . . . . . . . . . . . . . .2-14
	2.10.5  Compound Statements. . . . . . . . . . . . . . . . .2-15
	2.10.6  RETURN Statements. . . . . . . . . . . . . . . . . .2-15
	2.11  Declarations . . . . . . . . . . . . . . . . . . . . .2-16
	2.11.1  Variable Type Declarations . . . . . . . . . . . . .2-16
	2.11.2  Array Declarations . . . . . . . . . . . . . . . . .2-17
	2.11.3  Mode Handling Declarations . . . . . . . . . . . . .2-17
	2.12  Commands . . . . . . . . . . . . . . . . . . . . . . .2-17
	2.13  File Handling Commands . . . . . . . . . . . . . . . .2-18
	2.13.1  IN . . . . . . . . . . . . . . . . . . . . . . . . .2-18
	2.13.2  OUT. . . . . . . . . . . . . . . . . . . . . . . . .2-18
	2.13.3  SHUT . . . . . . . . . . . . . . . . . . . . . . . .2-19
	2.14  Substitution Commands. . . . . . . . . . . . . . . . .2-19
	2.15  Removing Assignments and Substitution Rules from
		Expressions. . . . . . . . . . . . . . . . . . . . .2-22
	2.16  Adding Rules for Differentiation of User-defined
		Operators. . . . . . . . . . . . . . . . . . . . . .2-22
	2.17  Procedures . . . . . . . . . . . . . . . . . . . . . .2-23
	2.18 Commands Used in Interactive Systems  . . . . . . . .  2-25
	2.19  END. . . . . . . . . . . . . . . . . . . . . . . . .  2-26

3.  MANIPULATION OF ALGEBRAIC EXPRESSIONS. . . . . . . . . . . . . . 3-1
	3.1  The Expression Workspace  . . . . . . . . . . . . . . . 3-1
	3.2  Output of Expressions . . . . . . . . . . . . . . . . . 3-2
	3.2.1  ORDER . . . . . . . . . . . . . . . . . . . . . . . . 3-3
	3.2.2  FACTOR  . . . . . . . . . . . . . . . . . . . . . . . 3-3
	3.2.3  Output Control Flags  . . . . . . . . . . . . . . . . 3-4
	3.2.4  Output of Strings . . . . . . . . . . . . . . . . . . 3-7
	3.2.5  Suppression of Zeros  . . . . . . . . . . . . . . . . 3-8
	3.3  User Control of the Evaluation Process. . . . . . . . . 3-8
	3.4  Cancellation of Common Factors. . . . . . . . . . . . . 3-9
	3.5  Numerical Evaluation of Expressions . . . . . . . . . . 3-9
	3.6  Saving Expressions for Later Use as Input . . . . . . .3-12
	3.7  Partitioning Expressions  . . . . . . . . . . . . . . .3-12

4.  MATRIX CALCULATIONS. . . . . . . . . . . . . . . . . . . . . . . 4-1
	4.1  Preliminary . . . . . . . . . . . . . . . . . . . . . . 4-1
	4.2  MAT . . . . . . . . . . . . . . . . . . . . . . . . . . 4-1	
	4.3  Matrix Variables. . . . . . . . . . . . . . . . . . . . 4-1
	4.4  Matrix Expressions. . . . . . . . . . . . . . . . . . . 4-2
	4.5  Operators with Matrix Arguments . . . . . . . . . . . . 4-3
	4.5.1  DET . . . . . . . . . . . . . . . . . . . . . . . . . 4-3
	4.5.2  TRACE . . . . . . . . . . . . . . . . . . . . . . . . 4-3
	4.6  Matrix Assignments. . . . . . . . . . . . . . . . . . . 4-4
	4.7  Evaluating Matrix Elements. . . . . . . . . . . . . . . 4-4

5.  ADVANCED COMMANDS. . . . . . . . . . . . . . . . . . . . . . . . 5-1
	5.1  Kernels . . . . . . . . . . . . . . . . . . . . . . . . 5-1
	5.2  Substitutions for General Expressions . . . . . . . . . 5-2
	5.3  Asymptotic Commands . . . . . . . . . . . . . . . . . . 5-5

6.  SYMBOLIC MODE  . . . . . . . . . . . . . . . . . . . . . . . . . 6-1
	6.1  Preliminary . . . . . . . . . . . . . . . . . . . . . . 6-1
	6.2  General Identifiers . . . . . . . . . . . . . . . . . . 6-2
	6.3  Symbolic Infix Operators. . . . . . . . . . . . . . . . 6-2
	6.4  Symbolic Expressions. . . . . . . . . . . . . . . . . . 6-3
	6.5  Quoted Expressions. . . . . . . . . . . . . . . . . . . 6-3
        6.6  LAMBDA Expressions. . . . . . . . . . . . . . . . . . . 6-4
	6.7  Symbolic Assignment Statements. . . . . . . . . . . . . 6-4
	6.8 Communication with Algebraic Mode. . . . . . . . . . . . 6-6

APPENDIX A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A-1
	A.1  Reserved Identifiers. . . . . . . . . . . . . . . . . . A-1
	A.2  Commands Normally Available in REDUCE . . . . . . . . . A-2
	A.3  Mode Flags in REDUCE. . . . . . . . . . . . . . . . . . A-5
	A.4  Diagnostic and Error Messages in REDUCE . . . . . . . . A-6
	A.4.1  Error Messages. . . . . . . . . . . . . . . . . . . . A-6
	A.4.2  Diagnostic Messages . . . . . . . . . . . . . . . . . A-8

APPENDIX B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B-1
	B.1  Running REDUCE on the Stanford PDP-10 . . . . . . . . . B-1
	B.2  Running REDUCE on the Stanford IBM 360/67 . . . . . . . B-5

APPENDIX C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C-1
     Calculations in High Energy Physics . . . . . . . . . . . . . . C-1
	C.1  Preliminary . . . . . . . . . . . . . . . . . . . . . . C-1
	C.2  Operators Used in High Energy Physics Calculations. . . C-1
	C.2.1  .    .  . . . . . . . . . . . . . . . . . . . . . . . C-1
	C.2.2  G . . . . . . . . . . . . . . . . . . . . . . . . . . C-2
	C.2.3  EPS . . . . . . . . . . . . . . . . . . . . . . . . . C-3
	C.3  Vector Variables. . . . . . . . . . . . . . . . . . . . C-4
	C.4  Additional Expression Types . . . . . . . . . . . . . . C-4
	C.4.1  Vector Expressions. . . . . . . . . . . . . . . . . . C-4
	C.4.2  Dirac Expressions . . . . . . . . . . . . . . . . . . C-5
	C.5  Trace Calculations  . . . . . . . . . . . . . . . . . . C-5
	C.6  Mass Declarations . . . . . . . . . . . . . . . . . . . C-7
	C.7  Example . . . . . . . . . . . . . . . . . . . . . . . . C-7

REFERENCES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . R-1


	REDUCE  is  a  program   designed   for   general   algebraic

computations of interest to mathematicians, physicists and engineers.

Its capabilities include:

   1)	Expansion and ordering of rational functions of polynomials,

   2)	symbolic differentiation of rational functions of polynomials

	and general functions,

   3)	substitutions and pattern matching in a wide variety of forms,

   4)	calculation of the greatest common divisor of two polynomials,

   5)	automatic and user controlled simplification of expressions,

   6)	calculations with symbolic matrices,

   8)	a complete language for symbolic calculations,  in which  the

	REDUCE program itself is written,

   9)	calculations of interest to high energy physicists  including

	spin 1/2 and spin 1 algebra,

  10)	tensor operations.

	There are several levels at which  REDUCE  may  be  used  and

understood.  The beginning user can acquire an operating knowledge of

the system by studying Section  2  of  this  manual,  which  contains

details of the basic structure of programs.  Having mastered this, he

should then study Section 3, which describes the facilities available

for  manipulating  algebraic  expressions.  A more advanced user must

understand Sections 4 and  5,  which  describe  the  matrix  handling

routines  and  some  advanced commands. Finally, to become a complete

expert, the user will have to learn LISP 1.5 and study  the  material

on the symbolic mode of operation in Section 6.

	Additional  material  of  interest  may  be  found   in   the

Appendices.  Appendix A gives the user a useful summary of the system

commands and other properties  of  the  system.    Appendix  B  gives

instructions for using REDUCE at various computer installations. This

information may  of  course  need  modification  for  your  computer.

Finally,  Appendix  C  contains  details  of  the high energy physics

commands for those interested.

	The author  would  appreciate  hearing  from  any  users  who

experience trouble with the system (please include copies of relevant

input and output).  Acknowledgment  of  the  use  of  REDUCE  in  any

published  calculations  would also be appreciated.  The author would

also be grateful for a copy of any such publication.


2.1 Preliminary

	A REDUCE program consists of a  set  of  functional  commands

which  are evaluated sequentially by the computer. These commands are

composed from declarations, statements and expressions, which in turn

are  sequences  of  numbers,  variables, operators, strings, reserved

words and delimiters (such as commas and parentheses).

2.2 Numbers

	Numbers in REDUCE may be of  two  types;  integer  and  real.

Integers  consist  of a signed or unsigned sequence of decimal digits

written without a decimal point.

	e. g.  -2, 5396, +32

There is no practical limit on the  number  of  digits  permitted  as

arbitrary precision arithmetic is used.

Real numbers may be written in two ways;

i)   as a signed or unsigned sequence of 1-9 decimal digits with

     an embedded decimal point.

ii)  as in 1) followed by a decimal exponent which is written as

     the letter E followed by a signed or unsigned integer.

e. g. 32.  +32.0 0.32E2 and 320.E-1  are all representations of 32.


The unsigned part of any number may NOT begin with a decimal point.

	i. e. NOT ALLOWED  .5  -.23  +.12

2.3 Identifiers

	Identifiers   in   REDUCE   consist  of  one  to  twenty-four

alphanumeric  characters  (i.e.  upper  case  alphabetic  letters  or

decimal digits) the first of which must be alphabetic.


Identifiers are  used  as  variables,  labels  and  to  name  arrays,

operators and procedures.


Reserved words in REDUCE  (see  Section  2.9)  may  not  be  used  as

identifiers.  No  spaces  may  appear  within  an  identifier, and an

identifier may not extend over a line of text.

2.4 Variables

	Variables are  a  particular  type  of  identifier,  and  are

specified   by   name   and  type.    Their  names  must  be  allowed

identifiers.   There are several variable types  allowed,  and  these

are discussed later, beginning in Section 2.11.1.

2.4.1 Reserved Variables

	Several variables in REDUCE have  a  particular  value  which

cannot  easily  be  changed  by  the  user.    These variables are as


	I		square root of -1.   All powers of I  are

			automatically replaced by the appropriate

			combination of -1 and I.

	E		base of natural logarithms

2.5 Operators

	Operators in REDUCE are also  specified  by  name  and  type.

There are two types, infix and prefix.

Infix operators occur between their arguments.

	e. g. A + B - C


The following infix operators are built into the system.

<infix operator> ::= ←|∧|∨|¬|=|≠|>=|>|<=|<|+|-|*|/|↑

	For compatibility with  the  intermediate  language  used  by

REDUCE, each infix operator has an alphanumeric identifier associated

with it.   These identifiers may  be  used  interchangably  with  the

corresponding  infix character(s) on input. This correspondence is as


	←	SETQ

	∧	AND

	∨	OR

	¬	NOT











        ↑       EXPT

	In systems which  do  not  have  all  these  characters,  the

alphanumeric  name  may  be  used instead. In addition, the following

alternative forms are allowed

	operator	alternative

	   ↑                **

	   ←    	    :=

	These operators may be further divided into the following sub


   <logical operator> ::= ∧|∨|¬

   <relational operator> ::= =|≠|>=|>|<=|<

   <arithmetic operator> ::= +|-|*|/|↑

	The  above operators may take any number of arguments, except

- which is unary, and ↑ and / which are binary.  The  expression  A-B

is  interpreted as A+-B on input. Furthermore, A↑B↑C↑D is interpreted

as A↑(B↑(C↑D)) and similarly with /.

Parentheses may be used to specify  the  order  of  combination.   If

parentheses are omitted then this order is by the precedence ordering

given by the above list (from outermost to innermost operations).

The user may add new single character infix operators to  the  system

by the declaration INFIX.

	e. g. INFIX ∀,∃;  adds infix operators ∀ and ∃ to the system.

These new operators will be given a precedence lower than any

existing infix  operator  except  ←  (which  always  has  the  lowest

precedence)  and  will  be ordered among themselves by their order at

definition.   Thus ∀ has a higher precedence than ∃.


	The infix characters λ, !, ε, ≡ and . have reserved  uses  in

REDUCE and cannot be declared as infix operators by the user.

	The precedence of any infix operator except ← may be  changed

by the declaration PRECEDENCE.

	e. g. PRECEDENCE ∀,=;	

gives  ∀  a  new  precedence  immediately  higher  than  the  current

precedence of =.

	Prefix operators occur at the head of their arguments,  which

are  written  as  a  list  enclosed  in  parentheses and separated by

commas, as with normal mathematical functions.

	e. g. COS(U)


	Parentheses may be omitted if the operator is unary.

	e. g.  COS Y and COS (Y) are equivalent.

Such unary operators have a precedence higher than any infix operator.

	Infix operators may also be used in a prefix format on input.

On  output,  however,  they  will always be printed in an infix form.

	Some  prefix operators are also built into the system.  These

are as follows:

2.5.1  DF

	The operator DF is used to represent partial  differentiation

with  respect  to  one  or  more variables. The first argument is the

scalar expression  to  be  differentiated.  The  remaining  arguments

specify  the  differentiation  variables and the number of times they

are applied by the following syntax:


The <number> may be omitted if it is 1.

	e. g.  	DF(Y,X) ≡ ∂Y/∂X

			     2    2
		DF(Y,X,2) ≡ ∂ Y/∂X  

				      5     2      2
		DF(Y,X1,2,X2,X3,2) ≡ ∂ Y/∂X1 ∂X2∂X3  

2.5.2   COS, LOG, SIN

	These elementary functions are included in  the  system  with

the following properties:

	COS (-X) = COS (X)

	SIN (-X) = - SIN (X)

	COS (O)  = 1

	SIN (O)  = 0

	LOG (E)  = 1

	LOG (1)  = 0

	The   user  can  add  further  rules  for  the  reduction  of

expressions involving these operators by  the  methods  described  in

Sections 2.14 and 5.2.

2.5.3  SUB

	This operator is described in Section 2.14.

	The user may add new prefix operators to the  system  by  the

declaration OPERATOR.

	e. g.  OPERATOR  H,  G1,  ARCTAN;

adds  the  prefix operators H, G1 and ARCTAN to the system.

2.6 Strings

	Strings are used only in output statements. A string consists

of any number of characters enclosed in double quotes.

	e. g. "A STRING".


	Comments are useful for  including  explanatory  material  at

various points in a program.  They may be used in the following form:

  	COMMENT <any sequence of characters not including a terminator>


	 <terminator> ::= ;|$


In addition, the sequence of symbols

  END <any sequence of symbols not including a terminator or the

	reserved words END, ELSE or UNTIL>

is equivalent to the reserved word END.

2.8 Expressions

	REDUCE expressions may be of several  types  and  consist  of

syntactically  allowed  sequences  of  numbers, variables, operators,

left and right parentheses and commas.  The most common types are  as


2.8.1  Numerical Expressions

	These  consist  of  syntactically  allowed  combinations   of

integer or real variables, arithmetic operators and parentheses. They

evaluate to numbers.



	I + J - 2 * I↑2

are numerical expressions if I and J are integers.

2.8.2  Scalar Expressions

	These consist of scalar variables  and  arithmetic  operators

and follow the normal rules of scalar algebra.



	X↑3 - 2*Y/(2*Z↑2 - DF(X,Z))

	(P↑2 + M↑2)↑(1/2)*LOG (Y/M)

2.8.3  Boolean Expressions

	These are expressions which return a truth value. In  REDUCE,

the  reserved  word NIL represent the truth value `false'.  Any other

expression represents `true'.  So in a sense,  any  expression  is  a

boolean expression, because all expressions return a value.

However, a proper boolean expression has the syntactical form:

	<expression> <relational operator> <expression>


	<boolean expression> <logical operator> <boolean expression>

They are used mainly in  the  IF  and  FOR  statements  described  in

Sections 2.10.2 and 2.10.3.



	X > 0 ∨ X = -2

2.8.4 Equations

	In the remainder of  this  manual,  we  shall  refer  to  the


	<scalar expression> = <scalar expression>

as an equation.

2.9 Reserved Words

	Certain  words are reserved in REDUCE.  They may only be used

in the manner described in this manual. These words are as follows:



2.10 Statements

	A statement is any allowed combination of reserved words  and

expressions, and has the syntax

<statement> ::= <expression>|<proper statement>

	The following sub-sections describe some proper statements in


2.10.1 Assignment Statements

	These statements have the following syntax

<assignment statement> ::= <expression> ← <statement>

	e. g. A1←B+C


	By analogy with numerical assignments in ALGOL, an assignment

statement  sets  the left hand side of the statement to the algebraic

value  of  the  right  hand  side.   Unfortunately,   the   algebraic

evaluation   of   an   expression   is  not  as  unambiguous  as  the

corresponding numerical evaluation. This algebraic evaluation process

is  generally  referred  to as 'simplification' in the sense that the

evaluation usually but not always produces a simplified form for  the

expression.    In  REDUCE,  the  default  evaluation of an expression

involves expansion of the expression and collection  of  like  terms,

ordering  of the terms, evaluation of derivatives and other functions

and substitution for any expressions which have  values  assigned  or

declared (Sections 2.14 and 5.2). In many cases, this is all that the

user needs.


	However,  the  user can exercise some control over the way in

which the evaluation is performed by various  declarations  available

to him.     These declarations are explained in Section 3.3.

	If a real  (floating  point)  number  is  encountered  during

evaluation,  the  system will normally convert it into a ratio of two

integers, and print a message informing the user of  the  conversion.

If  the  user  wants  to  use  real  arithmetic,  he can inhibit this

conversion  by  the command ON FLOAT;. This use of the ON declaration

is explained in Section 2.11.3.

	The results of the evaluation of an expression are printed if

a semicolon is used as a  delimiter.    Because  it  is  not  usually

possible  to  know  in  advance  how  large an expression will be, no

explicit format statements are  offered  to  the  user.   However,  a

variety  of  output declarations are available so that the output can

be produced in a variety of forms.   These  output  declarations  are

explained in Section 3.4.  

	It is also possible to write an assignment in the form

    <expression> ← <expression> ← ... ← <expression> ← <statement>

In this form, each <expression> is set to the value of the <statement>.

2.10.2 Conditional Statements

	The conditional statement has the following syntax:

<conditional statement> ::= IF <boolean expression> THEN <statement>

				 ELSE <statement>

Its use is obvious.  The ELSE clause is optional.

2.10.3 FOR Statements

	The FOR statement is used to  define  a  variety  of  program

loops. Its general syntax is as follows:

    FOR <variable>←<arithmetic expression> STEP <arithmetic expression>

					{DO <statement>
       {UNTIL <arithmetic expression>}  {
       {			     }	{SUM <algebraic expression>
       {WHILE <boolean expression>   }  {
			      		{PRODUCT <algebraic expression>

	The  DO  version  of  the  FOR  statement is the normal ALGOL

useage, and is similar to the  FORTRAN  DO  statement.  It  does  not

return   an   algebraic  value.      The  SUM  and  PRODUCT  versions

respectively form the sum  and  product  of  the  relevant  algebraic

expression  over  the  defined  range.   They return the value of the

computed sum or product.  Note,  however,  that  this  value  is  NOT

printed. It will be printed, however, if the statement is assigned as

the value of an expression and a semicolon used as a terminator.

	The <variable> within the FOR statement is  declared  INTEGER

if  it  is  not  already.    Its  value during the calculation of the

statement is independent of its value outside, so that I can be  used

in this context, even though I normally stands for the square root of



We assume that the declaration ARRAY A(10);  has  been  made  in  the

following examples.  This declaration is explained in Section 2.11.2.

(i)  To set each element A(I) of the array to X↑I we could write


As a further convenience, the common construction


may be abbreviated by a colon.  Thus we could write  instead  of  the


	FOR I←0:10 DO A(I)←X↑I$

(ii) To sum the squares of the even positive integers through 50,  we

could write


As  explained above, the result is not printed in this case. However,

it is held in the expression workspace (see Section 3.1) and  can  be

retrieved from there if required.

(iii) To set X to  the factorial of 10 we could write

	X ← FOR I←1:10 PRODUCT I;

Alternatively, we could set the element A(I) to I! by the


	A(0)← 1$ FOR I←1:10 DO A(I)←I*A(I-1)$

2.10.4 GO TO Statements

	GO  TO  (or  GOTO)  statements  are  used   to   perform   an

unconditional  transfer  to  a label in a compound statement (Section

2.10.5).  They have the syntax:

<go to statement> ::= GO TO <label>

<label> ::= <variable>


GO TO statements may only occur within a compound statement. They may

NOT occur at the top level of your program.

2.10.5 Compound Statements

	A compound statement is defined by the following syntax

<compound statement> ::= BEGIN <compound tail>

<compound tail> ::= <unlabeled compound tail>

		    |<label>:<compound tail>

<unlabeled compound tail> ::= <statement> END 

		    | <statement> <terminator> <compound tail>

<label> ::= <identifier>

<terminator> ::= ;|$

	e. g. X ←  BEGIN INTEGER M;
		    L1: IF N=0 THEN RETURN M;
			GO TO L1 

will assign the factorial of a preassigned INTEGER N to X.

2.10.6 RETURN Statements

	The RETURN statement allows for a transfer out of a  compound

statement  to  the next highest program level.  It may be used alone,

in which case the statement returns NIL.

	e. g.,	RETURN (X+Y);




RETURN statements may only occur within a compound statement.They may

NOT occur at the top level of your program.

2.11 Declarations

	Declarations are a particular type of statement used  to  set

flags,  make  type  declarations  and  define  procedures.  PROCEDURE

declarations are  discussed  in  Section  2.17.   Some  other  REDUCE

declarations are described in the following sub-sections.

2.11.1 Variable Type Declarations

	These declarations tell the system  how  various  identifiers

are to be processed.  Types allowed include INTEGER, REAL and SCALAR.

	e. g.	INTEGER  M,N;

		REAL M1;


Type declarations may be made at any level in a  program,  and  apply

only  to the particular program block in which they occur.  Variables

not declared are assumed SCALAR. This is the basic symbolic  variable


2.11.2 Array declarations

	Arrays in REDUCE are defined  similar  to  FORTRAN  dimension


	e. g. ARRAY  A(10),B(2,3,4);

Their  indices each range from 0 to the value declared. An element of

an array is referred to in standard FORTRAN notation,

	e. g. A(2)

Array  elements  may appear in the left side of assignment statements

as in the examples in Section 2.10.3.

2.11.3  Mode Handling Declarations

	Two  declarations  are  offered to the user for turning on or

off a variety of flags in the system.  The declarations  ON  and  OFF

take  a  list  of  flag  names  as  argument and turn them on and off


	e. g.	ON FLOAT,GCD;


	The  use  of  these flags and others available to the user is

explained later in this manual.

2.12 Commands

	A command is an order to the system to do something.  It  has

the syntax

<command> ::= <statement><terminator>|<proper command>

<proper command> ::= <command name><space>


A variety of commands are discussed in the sections which follow.

2.13 File Handling Commands

	In  many  applications,  it  is  desirable to load previously

prepared REDUCE files into the system, or to write output on  varying

devices.   REDUCE offers three commands for this purpose, namely, IN,

OUT, and SHUT.

2.13.1 IN

	This command takes a list  of  file  names  as  argument  and

directs  the  system  to input each file (which should contain REDUCE

commands) into the system.   A file name will have a  varying  syntax

from  implementation  to implementation, but in many cases will be an


	e. g.	IN F1,GGG; will load the files F1 and GGG.

	When input comes from an external file, statements are echoed

on the output device as they are  read.   If  this  facility  is  not

required, the echoing can be prevented by turning off the  flag  ECHO

in the relevant file.

2.13.2 OUT

	This  command  takes  a  single  file  name  as argument, and

directs output to that file from then on.  If the file has previously

been  used  for output during the current job, the output is appended

to the end of the file.  An existing file is erased before its  first

use for output in a job.

	To  output  on  the terminal without closing the output file,

the reserved file name T (for terminal) may be used.

	e. g. 	OUT OFILE; will direct output to the file OFILE and

		OUT T; will direct output the user's terminal.

2.13.3 SHUT

	This  command  is used to close an output file at completion.

Most systems require this action by the user, otherwise output may be

lost.    If  a  file is shut and a further OUT command issued for the

same file, the file is erased before the new output is written.

2.14  Substitution Commands

	An  important class of commands in REDUCE is that class which

defines substitutions for variables and expressions to be made during

the  evaluation  of  expressions.  Such substitutions may be declared

globally by the command LET and locally by use of the operator SUB.

	LET is used in the form

	  LET <substitution list>;

where <substitution list> is a list of equations of the form:

	<variable> = <expression>

or	<prefix operator> (<argument>,...,<argument>) = <expression>

or	<argument> <infix operator>,..., <argument> = <expression>

	e. g. LET X = Y↑2 + 2,

		 H(X,Y) = X - Y,

		 COS(60) = 1/2,

		 Y↑3 = 2*Z - 3;

These  substitutions  will  now  be  made  for all such variables and

expressions appearing in evaluations.  Any operators occuring in such

equations will be automatically declared OPERATOR by the system.

	In  each  of  these examples, substitutions are only made for

the explicit expressions given; i.e., none of the  variables  may  be

considered arbitrary in any sense.

	For example, the command

	LET H(X,Y) = X - Y;

will replace H(X,Y) by X - Y, but not H(X,Z) or any other function of

H.   If a substitution for all possible values of a given argument of

an operator is required, the declaration FOR ALL (or FORALL)  may  be

used.  The syntax of such a command is

	FOR ALL <variable>,...,<variable> <LET command><terminator>

	e. g. 	FOR ALL X,Y LET H(X,Y) = X-Y;


	If the left hand side of an equation is redefined by a  later

call  of LET, the previous expression is replaced by the new one, and

a diagnostic message printed to inform the user.  Such  messages  may

be inhibited by turning off the flag MSG.

	In applying any substitutions  set  up  by  LET,  the  system

searches the substitution expression itself for any expressions which

may themselves have substitutions declared for them.  Thus  LET  sets

up  an equivalence between the left hand side of the substitution and

the right  hand  side  rather  than  an  assignment  as  made  by  an

assignment statement.  In other words, a substitution such as

		LET X = X + 1;

is not allowed, since in substituting for X,  the  system  will  find

that  the  variable  X  in  the  substitution expression itself has a

substitution and a  push-down-list  overflow  error  will  ultimately

result.  Similarly, a pair of substitutions

		LET L = M + N, N = L + R;

are not allowed.

	On the other hand, if the user wishes simply to replace every

occurrence  of  a  variable  by  any expression without checking that

expression again for further substitutions, the operator SUB  may  be

used.  Its general form is

		SUB (<substitution list>,<expression>)

as in

		SUB(X=X+1, Y=1, X**2+Y**2)

This substitution is made by first simplifying the <expression>, then

replacing  any  variables  occurring  on  the  substitution list, and

finally resimplifying the result.  Thus, in the  above  example,  the

result would be


2.15  Removing Assignments and Substitution Rules from Expressions

	The user may remove all assignments  and  substitution  rules

from any expression by the command CLEAR, in the form

		CLEAR <expression>,...,<expression><terminator>

	e. g.	CLEAR  X, H(X,Y);

	A whole array, such as A in Section 2.11.2, can be cleared by

the  command  CLEAR A; An individual element of A can also be cleared

by a command such as CLEAR A(3);

2.16 Adding Rules for Differentiation of User-defined Operators

	An extension of the syntax of LET arguments  allows  for  the

introduction  of rules for differentiation of user-defined operators.

Its general form is

	FOR ALL <var1>,...,<varn>

	     LET DF(<operator><varlist>,<vari>)=<expression>

where	<varlist> ::= (<var1>,...,<varn>)

and  <var1>,...,<vari>,...,<varn> are the dummy variable arguments of


An analogous form is allowed for infix operators.

 We illustrate this with some examples:




	We notice that all dummy arguments of the  relevant  operator

must be declared arbitrary by the FOR ALL command, and that rules may

be supplied for operators with  any  number  of  arguments.    If  no

differentiation  rule  appears  for  any argument in an operator, the

differentiation routines will return an expression in terms of DF  as

the  result.  For example, if the rule for the differentiation of the

second argument of F is not supplied, the evaluation of  DF(F(X,Z),Z)

would leave this expression unchanged.

2.17 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>;


	<varlist> ::= (<variable>,...,<variable>)

The types permitted in REDUCE are REAL, INTEGER and ALGEBRAIC.    The

default  type  is  ALGEBRAIC.  All these procedures are automatically

declared to be operators on definition.

	In the present system, no distinction is made in the handling

of these three types, although this may not be true in later versions.


(1) The example in Section 2.10.5  could  be  made  into  an  integer

procedure FAC by the declaration:

		    L1: IF N=0 THEN RETURN M;
			GO TO L1 

If we now evaluate FAC (3) we get the result 6.

(2)  As  an  example of an algebraic procedure, we define an operator

LEG of two arguments which evaluates to the Legendre polynomial.   We

define  this  operator  as  a  procedure from the generating function


		                 n		   |
	                 1	∂ 	   1	   |
          p (x)   = 	---	---  ------------- |
           n          	 n!	  n	2          |
		                ∂y     y -2*x*y+1  | y=0

A REDUCE version of this is


	  SUB(Y=0,DF((Y↑2-2*X*Y+1)↑(-1/2),Y,N))/(FOR I←1:N PRODUCT I)$

With this definition, the evaluation of


would result in the output

	3*W  - 1

	We can of course omit the word ALGEBRAIC  in  this  procedure

definition as this is the default type.

	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!

2.18  Commands Used in Interactive Systems

	REDUCE is designed primarily for interactive use with a time-

shared computer, but  naturally  it  can  also  operate  in  a  batch

processing  environment.   There  is  a  basic  difference,  however,

between interactive and batch use of the system.  In the former case,

whenever  the  system  discovers  an  ambiguity  at  some  point in a

calculation, such as a forgotten type  assignment  for  instance,  it

asks  the user for the correct interpretation. In batch operation, it

is not practical to terminate the  calculation  at  such  points  and

require resubmission of the job, so the system makes the most obvious

guess of the user's intentions and continues the calculation.

	If  input  is coming from an external file, the system treats

it as a batch processed calculation.  If the user desires interactive

response  in  this  case,  he  can  turn on the flag INT in the file.

Likewise, he can turn off INT in the main  program  if  he  does  not

desire continual questioning from the system.

	Two commands are available in REDUCE for use  in  interactive

computing.   The  command  PAUSE;  may be inserted at any point in an

input file.  When this command is encountered on  input,  the  system

prints  the  message  CONT? on the user's terminal and halts.  If the

user responds Y (for yes), the calculation continues from that  point

in  the  file.   On  the other hand, if the user responds N (for no),

control  is  returned to the terminal, and the user can input further

commands. However, later on he can use the command CONT; and  control

is  then  transferred  back  to  the point in the file after the last

pause was encountered.

2.19 END

	The command END; is used to end external files which are used

as  input  to REDUCE.  One of its purposes is to turn off the command

echo, which is annoying to a user typing at a terminal.  However,  it

also does some file control book-keeping, and should therefore not be


	If  an  END  command  is used in the main program, control is

then transferred to LISP.


	In this Section, we consider some further  system  facilities

for the processing of algebraic expressions.

3.1 The Expression Workspace

	When an assignment of an algebraic expression is made, or  an

expression  is  evaluated  at  the  top  level,  the  results  of the

evaluation are automatically saved in an environment which  we  shall

refer  to  as  the  workspace.   In  actual  fact,  the expression is

assigned  to  a  variable  *ANS  which  is  available   for   further

manipulation.  In order to input the asterisk as part of the variable

name, however, it must be prefixed by an exclamation mark.


	If  we  evaluate  the  expression  (X+Y)↑2  and  next wish to

differentiate it with respect to Y, we can simply say


to get the desired answer.

	If the user gets tired of typing !*ANS, or wishes  to  rename

ANY  identifier  in  the  system EXCEPT reserved words, he can simply


	LET <new name> = <old name>;

	 e. g. LET WS=!*ANS;

From now on, WS is recognized as !*ANS in all input.

	If  the  user wishes to assign the workspace to a variable or

expression for later use, the command SAVEAS can be used.  It has the


	SAVEAS <expression><terminator>

	e.  g.  after  the  differentiation  in the last example, the

workspace holds the expression 2*X+2*Y.  If we wish to assign this to

the variable Z we can now say


	If  the  user  wishes  to  save the expression in a form that

allows him to use some of its variables as arbitrary parameters,  the

FOR ALL command can be used.


with the above expression would mean that H(Z) evaluates to 2*Y+2*Z.

3.2 Output of Expressions

	A considerable degree of flexibility is available  in  REDUCE

in  the printing of expressions generated during calculations.  As we

mentioned earlier, no explicit format  statements  are  supplied,  as

these  prove to be of little use in algebraic calculations, where the

size of output or its composition is not generally known in  advance.

Instead,  REDUCE  provides a series of mode options to the user which

should enable him to produce  his  output  in  a  comprehensible  and

possibly pleasing form.

	As we mentioned earlier, an algebraic expression is  normally

printed  in  an  expanded  form,  filling  the whole output line with

terms.  Certain output declarations, however, can be used  to  affect

this format.  These are as follows:

3.2.1  ORDER

	The  declaration  ORDER  may  be  used  to order variables on

output. Thus


orders X ahead of Y, Y ahead of Z  and  X,Y  and  Z  ahead  of  other

variables  in  expressions  which  follow, and all ahead of variables

appearing in further ORDER assignments, or those not given an  order.

The order of variables may be changed by a further call of ORDER, but

then the reordered variables would have an order lower than those  in

earlier ORDER calls.

	Thus,	ORDER X,Y,Z;


 would order Z ahead of Y and X.

3.2.2  FACTOR

	This  declaration  takes  a list of identifiers or functional

expressions as argument.  FACTOR is not really a  factoring  command,

but  rather a separation command. All terms involving fixed powers of

the declared expressions are printed as a product of the fixed powers

and a sum of the rest of the terms.

	All expressions involving a given prefix operator may also be

factored  by  putting  the  operator  name  in  the  list of factored



causes all powers of X and SIN(X) and all  functions  of  COS  to  be


The declaration REMFAC V1,...,VN; removes the factoring flag from the

expressions V1 through VN.

3.2.3  Output Control Flags

	In addition to these declarations, the form of the output can

be modified by switching  various  output  control  flags  using  the

declarations  ON  and OFF. We shall illustrate the use of these flags

by   an   example,   namely   the   printing   of   the    expression


The relevant flags are as follows:

(1) ALLFAC.  This flag will cause  the  system  to  search  the

     whole   expression,  or  any  sub-expression  enclosed  in

     parentheses, for simple multiplicative factors  and  print

     them  outside  the  parentheses.  Thus our expression with

     ALLFAC off will print as

	    2  2        2          2
	(2*X *Y *A + 4*X *Y*A + X*Y  + X*Z)/(2*A)

	and with ALLFAC on as

	        2                2
	X*(2*X*Y *A + 4*X*Y*A + Y  + Z)/(2*A)

	ALLFAC is normally on, and is on in the  following  examples,

except where otherwise stated.

(2) DIV.   This flag makes the system search the denominator of

     an expression for simple factors which it divides into the

     numerator,  so that rational fractions and negative powers

     appear in the output. With DIV on,  our  expression  would

     print as

	      2                2  (-1)        (-1)
	X*(X*Y  + 2*X*Y + 1/2*Y *A     + 1/2*A    *Z)

	DIV is normally off.

(3) LIST.  This flag causes the system to print  each  term  in

     any  sum on a separate line.  With LIST on, our expression

     prints as

	X*(2*X*Y *A

	    + 4*X*Y*A

	    + Y

	    + Z)


	LIST is normally off.

(4)  RAT.   This  flag is only useful with expressions in which

     variables are factored with FACTOR.  With this  mode,  the

     overall denominator of the expression is printed with each

     factored sub-expression. We  assume  a  prior  declaration

     FACTOR  X;  in  the  following output . We first print the

     expression with RAT off:

	    2                   2
	(2*X *Y*A*(Y + 2) + X*(Y  + Z))/(2*A)

	With RAT on the output becomes:

	 2                 2
	X *Y*(Y + 2) + X*(Y  + Z)/(2*A)

	RAT is normally off.

	Next, if we leave X factored, and turn on both DIV  and

     RAT, the result becomes

	 2                    (-1)   2
	X *Y*(Y + 2) + 1/2*X*A    *(Y  + Z)

	Finally, with X factored, RAT  on  and  ALLFAC  off  we

     retrieve the original structure

	 2   2              2
	X *(Y  + 2*Y) + X*(Y  + Z)/(2*A)

3.2.4  Output of Strings

	It is often useful to write a title or comment on output,  or

name  output  expressions  in  a particular way.  This is possible in

REDUCE by means of the command WRITE.  The form of this command is

	WRITE <expression>,...,<expression>;

where  <expression> may be either an algebraic expression or a string

(Section 2.6). Strings are printed on output exactly as given  except

for  any  characters  which  are  ignored by the input scanner. Other

expressions are evaluated and their value printed.

	The  print  line  is  closed  at the end of the WRITE command



	The  following  program  calculates the famous f and g series


X1:= -SIG*(MU+2*EPS)$
X2:= EPS-2*SIG**2$
X3:= -3*MU*SIG$
F:= 1$
G:= 0$
     F1:= -MU*G + X1*DF(F,EPS) + X2*DF(F,SIG) + X3*DF(F,MU)$
     WRITE "F(",I,") ← ",F1;
     G1:= F + X1*DF(G,EPS) + X2*DF(G,SIG) + X3*DF(G,MU)$
     WRITE "G(",I,") ← ",G1;

A  portion  of  the output, to illustrate the printout from the WRITE

command, is as follows:

		... <prior output> ...

F(4) ← MU*(3*EPS - 15*SIG  + MU)

G(4) ← 6*SIG*MU

F(5) ← 15*SIG*MU*( - 3*EPS + 7*SIG  - MU)

G(5) ← MU*(9*EPS - 45*SIG  + MU)

		... <more output> ...

3.2.5 Suppression of Zeros

	It  is  sometimes  annoying  to  have  zero assignments (i.e.

assignments of the form <expression>  ←  0)  printed,  especially  in

setting  large  arrays  with many zero elements. The output from such

assignments can be suppressed by turning on the flag NERO.

3.3 User Control of the Evaluation Process

	In addition to the wide range of output options available  to

the  user,  there are two additional flags which control the internal

evaluation  of  expressions.  The  flag  EXP  controls  expansion  of

expressions.   If  it  is  off  no expansion of powers or products of

expressions occurs.

	When  two  rational  functions  are  added,  REDUCE  normally

produces an expression over a common denominator.   However,  if  the

user  does  not  want denominators combined, he can turn off the flag

MCD which controls this process.

	EXP and MCD are normally on.

3.4 Cancellation of Common Factors

	Facilities are available  in  REDUCE  for  cancelling  common

factors  in  the  numerators  and denominators of expressions, at the

option of the user. The system computes the required greatest  common

divisor  using  an algorithm due to G.E. Collins [2] and cancels this

divisor from the relevant terms.  This facility should only  be  used

on  small  expressions  as  the  computational  time  quickly becomes

prohibitive for moderately large expressions  in  several  variables.

The  system  will  perform  this greatest common divisor check if the

flag GCD is on.

	A check is automatically made, however, for common variable

products in the numerators and denominators of expressions, and the 

appropriate cancellations made.

3.5 Numerical Evaluation of Expressions

	It  is naturally possible to evaluate expressions numerically

in REDUCE by  giving  all  variables  and  sub-expressions  numerical

values.   However,  as we pointed out in Section 2.10.1 the user must

declare real arithmetical operation by turning  on  the  flag  FLOAT.

Furthermore,  there  are no routines for evaluation of the elementary

functions COS,SIN etc for arbitrary  numerical  argument.    Finally,

arithmetic in REDUCE is not particularly fast.

	The  user  with a large amount of numerical computation after

all  necessary  algebraic  manipulations  have  been   performed   is

therefore  well advised to perform these calculations in a FORTRAN or

similar system. For this purpose, REDUCE offers facilities for  users

to produce FORTRAN compatible files for numerical processing.

	First,  when  the  flag  FORT  is  on,  the system will print

expressions in a FORTRAN notation.  Expressions begin in column 7. If

an  expression extends over one line, a continuation mark (X) appears

on subsequent cards.   After 19 continuation lines  are  produced,  a

new  expression  is started.   If the expression printed arises  from

an assignment to a variable, the variable is printed as the  name  of

the  expression.   Otherwise the expression is named ANS.   Secondly,

the WRITE command can be used to produce other programs.


	The following REDUCE statements

WRITE " 1    FORMAT(E13.5)";
WRITE "      U=1.23";
WRITE "      V=2.17";
WRITE "      W=5.2";
WRITE "      PRINT 1,X";
WRITE "      END";

	will generate a file FORFIL which contains:

 1    FORMAT(E13.5)
      PRINT 1,X

The number of continuation cards per statement can be modified by the


	!*CARDNO ← <number>;

where <number> is the TOTAL number of cards allowed in  a  statement.

*CARDNO is thus initially set to 20.

3.6  Saving Expressions for Later Use as Input

	It is often useful to save an expression on an external  file

for  use  later  as  input in further calculations.  The commands for

opening and closing output files  were  explained  in  Section  2.13.

However,  we  see  in  the  examples in Section 3.2 that the standard

`natural'  method  of printing expressions in not compatible with the

input syntax.    So to print the expression in  an  input  compatible

form  we must inhibit this natural style by turning off the flag NAT.

If this is done, a dollar sign will also be printed at the end of the



	The following program


	will generate a file OUT which contains

X := Y**2 + 2*Y*Z + Z**2

3.7 Partitioning Expressions

	It is often necessary to get at parts of an expression during

a  calculation.  REDUCE provides four commands for this purpose, each

of which apply to the current expression in the  work space.   These

have  proved  adequate  for  all calculations brought to the author's

attention, but other commands could be added if there  is  sufficient


	(1) MKCOEFF is a command which assigns  coefficients  of  the

various powers of a variable.  It has the syntax:

	MKCOEFF <variable>,<identifier>;

	If  the  <identifier>  has  been previously declared a single

dimensioned  array,  the  Ith  array  element  is  assigned  to   the

coefficient  (zero or non zero) of the Ith power of <variable> in the

expression.  This assignment begins  at  the  maximum  power  of  the

variable, and a message is printed to inform the user of that power.

	If the <identifier> is not an array  name,  a  variable  with

name  <identifier><power>  is  assigned  to  the  coefficient of that

power. Only NON ZERO powers are set in this manner, and a message  is

printed to inform the user of the variables set.


	Suppose we evaluate the expression  (Y↑2+Z)↑3,  so  that  the

workspace holds the expression

	Y↑6 + 3*Y↑4*Z + 3*Y↑2*Z↑2 + Z↑3

If we now say ARRAY X(7); MKCOEFF Y,X;

then a message


will be printed and X(6) set to 1, X(5) to 0, X(4) to 3*Z and  so  on

until X(0), which is set to Z↑3. X(7) will not be set.

	On the other hand, if we said  MKCOEFF Y,W;

we would get a message


and W6 set to 1, W4 to 3*Z and so on.

(2) NUMER and  DENOM  are  commands  which  have  a  single  variable

argument  and which respectively assign the numerator and denominator

of the workspace to their argument.

	e. g., with X/Y↑2 in the workspace,

	NUMER V; will set V to X, and DENOM W; will set W to Y↑2.

(3)  ND,  finally,  takes  two variables as argument, and assigns the

numerator of the workspace to the first, and the denominator  to  the


	e. g., we could achieve  the  assignments  in  (2)  with  the

single command ND V,W;


4.1 Preliminary

	A very powerful feature of the REDUCE system is the ease with

which  matrix  calculations can be performed. To extend our syntax to

this class of calculations we need to add  another  prefix  operator,

MAT, and a further variable and expression type as follows:

4.2 MAT

	This prefix operator is used to represent n x m matrices. MAT

has n arguments interpreted as rows of the matrix, each of which is a

list of m expressions representing elements in that row. For example,

the matrix

			| A B C |
			|       |
			| D E F |

would be written as

	MAT ((A,B,C),(D,E,F))

4.3 Matrix variables.

	An identifier may  be  declared  a  matrix  variable  by  the

declaration  MATRIX.  Matrices  are stored as arrays in REDUCE.   The

size  of  the  matrix  may  be  declared  explicitly  in  the  matrix

declaration,  or  by default in assigning such a variable to a matrix


	e. g. MATRIX X(2),Y(3,4),Z;

declares X to be a 2 x 1 (column) matrix, Y to be a 3 x 4 matrix  and

Z a matrix whose size is declared later by default.

4.4 Matrix Expressions

	These follow the normal rules of matrix algebra as defined by

the following syntax:

  <matrix expression> ::= MAT<matrix description>|<matrix variable>|

			  <scalar expression>*<matrix expression>|

			  <matrix expression>*<matrix expression>

			  <matrix expression>+<matrix expression>|

			  <matrix expression>↑<integer>|

			  <matrix expression>/<matrix expression>

	Sums and products of matrix expressions must  have  the  same

size   otherwise  an  error  will  result  during  their  evaluation.

Similarly, only square matrices may be raised to a power.  A negative

power  is  computed  as  the  inverse  of  the  matrix  raised to the

corresponding positive power.  A/B is interpreted as AxB↑(-1).

	The inverse of a matrix is computed by an  algorithm  due  to

John Lipson [3]. I am indebted to Dr. Jim Griesmer for allowing me to

include in REDUCE his programmed version of this algorithm.


	Assuming  X  and  Y  have  been  declared  as  matrices,  the

following are matrix expressions



	Y+ MAT((1,A),(B,C))/2


4.5  Operators With Matrix Arguments

	Two additional operators are useful in  matrix  calculations,

namely DET and TRACE defined as follows

4.5.1 DET

	The operator DET is used to represent the  determinant  of  a

square matrix expression.

	e.g. DET(Y↑2)

is a scalar expression whose value is the determinant of  the  square

of the matrix Y. The particular construction

	DET(MAT <matrix description>) max be abbreviated to 

	DET<matrix description>

For example, the determinant

		| A B C |
		|       |
		| D E F |
		|       |
		| G H J |

could be written


4.5.2  TRACE

	The operator TRACE is used to represent the trace of a square

matrix. Its use is obvious.

4.6 Matrix Assignments

	Matrix  expressions  may  appear  in  the  right hand side of

assignment statements. If the left hand side of the assignment, which

must  be  a  variable,  has not already been declared a matrix, it is

declared by default to the size of the right hand side. The  variable

is then set to the value of the right hand side.

	Such  an assignment may be used very conveniently to find the

solution of a set of linear equations.   For  example,  to  find  the

solution of the following set of equations

	A11*X(1) + A12*X(2) = Y1

	A21*X(1) + A22*X(2) = Y2

we simply write

	X ← 1/MAT((A11,A12),(A21,A22))*MAT((Y1),(Y2));

4.7  Evaluating Matrix Elements

	Once an element of a matrix has  been  assigned,  it  may  be

referred  to  in standard array element notation.  Thus Y(2,1) refers

to the element in the second row and first column of the matrix Y.


	In this Section, we consider several extensions of the basic

REDUCE system which add to its power as a problem solving tool.  

	We begin by introducing a new data type which  is  needed  to

extend our syntax, namely the kernel.

5.1 Kernels

	REDUCE is designed so that each operator in the system has  a

evaluation  (or  simplification)  function  associated  with it which

transforms the expression into an internal canonical form. This form,

which  bears  little  resemblance  to  the  original  expression,  is

described in detail in Reference [4]. 

	The  evaluation  function  may transform its arguments in one

of two alternative ways.  First, it may convert  the  expression into

other operators in the system, leaving no functions of  the  original

operator  for further manipulation.    This is in a sense true of the

evaluation functions associated with the operators +, * and /  ,  for

example,  because the canonical form does not include these operators

explicitly.  It is also true of an operator such as  the  determinant

operator  DET  discussed  in  Section  4.5.1,  because  the  relevant

evaluation function calculates the appropriate determinant,  and  the

operator  DET  no longer appears.   On the other hand, the evaluation

process may leave some residual functions of the  relevant  operator.

For example, with the operator COS, a residual expression like COS(X)

may remain after evaluation  unless  a  rule  for  the  reduction  of

cosines  into  exponentials,  for  example,  were introduced.   These

residual functions of an operator are termed kernels and  are  stored

uniquely like variables.  Subsequently, the kernel is carried through

the calculation as a variable unless transformations  are  introduced

for the operator at a later stage.

	In cases where the arguments of the kernel operators  may  be

reordered,  the  system  puts  them in a canonical order, based on an

internal  intrinsic  ordering  of  the  variables.    However,   some

commands  allow arguments in the form of kernels, and the user has no

way of telling what internal order the system will  assign  to  these

arguments.     To resolve this difficulty, we introduce the notion of

a kernel form as an  expression  which  transforms  to  a  kernel  on


Examples of kernel forms are:


	COS (X*Y)

	LOG (SIN (X))




are not.   

We  see  that  kernel  forms are in fact the 'functional expressions'

previously allowed in LET and FACTOR statements.

5.2  Substitutions for General Expressions

	All substitutions discussed so far have been very limited  in

scope,  because  they  involve  only  replacements  for variables and

kernels.  These substitutions are very efficient to implement because

variables  and  kernels are stored uniquely in the system.   However,

there are  many  situations  where  more  general  substitutions  are

required, most of which require extensive pattern matching within the

expression being evaluated .  Consequently, such substitutions cannot

be as efficiently implemented as those discussed so far.

	For  the reasons given in References [5] and [6], REDUCE does

not attempt  to  implement  a  general  pattern  matching  algorithm.

However,  the  present system uses more sophisticated techniques than

those discussed in  reference  [6].   It  is  now  possible  for  the

equations appearing in arguments of LET to have the form

	<substitution expression> = <expression>

where <substitution expression> is  ANY  expression, subject  to  the

following restrictions:

(i) The operators +, - and / cannot appear at  the  top  level  in  a

     substitution  expression.    This restriction is currently under

     study to see if it can be removed.

	e.  g.  LET COS(X)↑2 + SIN(X)↑2 = 1; is NOT allowed.

(ii) The operators + and * can only be used  in  binary  form  within

     substitution expressions.

	e.  g.    LET SIN (X + Y) = SIN(X)*COS(Y) + COS(X)*SIN(Y); 

     is  allowed  but a substitution for FN(X+Y+Z) would not be.  The

     system will of course substitute for any expression containing +

     or * as an n-ary operator by making the appropriate expansion of

     the binary rule.

(iii) The operator - can only be specified as a unary operator within

     substitution expressions.

	e. g.    LET  COS(-X)= COS(X) is allowed

	 but     LET COS(X-Y)  = <expression> is not.

     It should be noted, however, that a rule for  COS(X+Y)  and  one

     for COS(-X) is sufficient to specify the expansion of COS(X-Y).

	Any  variables  appearing  in substitution expressions may be

declared arbitrary by the FOR ALL construction


	       FOR ALL X LET LOG(E↑X) = X, E↑LOG(X)= X,

			     COS(W*T+THETA(X)) = TAU(X);

	It  is  also  possible  to  limit  the  range of an arbitrary

variable by an extension of the syntax  of  the  IF  statement.   The

relevant form is

     IF <boolean expression> LET <substitution list>

To include completely arbitrary variables in this syntax, we use  the

boolean  operator  ARB rather than combine the IF construction with a

FOR ALL clause.

	e. g. IF X ≠ 0 ∧ NUMBERP N ∧ ARB Y LET F(X,Y,N)= 2*Y↑N;

	As before, after a substitution has been made, the expression

being  evaluated is reexamined in case a new allowed substitution has

been generated. This process is continued until no more substitutions

can  be  made.  However, this is sometimes undesirable.  For example,

if one wishes to integrate a polynomial with respect to X by  a  rule

of the form

	FOR ALL N LET X↑N = X↑(N+1)/(N+1);

one only wants the substitution to be made once. (Otherwise X↑2 would

become  X↑3/3  which  would  then  become  X↑4/12  and  so on).  This

resubstitution can be inhibited by turning off the flag RESUBS (which

is normally on).

	When a substitution expression  appears  in  a  product,  the

substitution  is  made  if  that expression divides the product.  For

example, the rule

	LET A↑2*C = 3*Z;

would  cause A↑2*C*X to be replaced by 3*Z*X and A↑2*C↑2 by 3*Z*C. If

the  substitution  is  desired  only when the substitution expression

appears in a product with the explicit powers supplied in  the  rule,

the command MATCH should be used instead.

For example,

	MATCH A↑2*C = 3*Z;

would cause A↑2*C*X to be replaced by 3*Z*X, but A↑2*C↑2 would not be

replaced. MATCH can also be used with the FOR ALL or IF constructions

described above.

	To  remove  substitution  rules of the type discussed in this

Section, the CLEAR command can be used, combined, if necessary,  with

a FOR ALL or IF clause.


Note, however, that the arbitrary variable names in this case MUST be

the same as those used in defining the substitution.

5.3 Asymptotic Commands

	In expansions of polynomials involving  variables  which  are

known  to be small, it is often desirable to throw away all powers of

these  variables  beyond  a  certain  point  to   avoid   unnecessary

computation.    The  command LET may be used to do this. For example,

if only powers of X up to X↑7 are needed, the command

	LET X↑8 = 0;

will cause the system to delete all powers of X higher than 7.

	This  method  is  not  adequate,  however,  when  expressions

involve  several  variables  having  different  degrees of smallness.

In this case, it is necessary to supply an asymptotic weight to  each

variable and count up the total weight of each product in an expanded

expression before deciding whether to keep the term  or  not.   There

are  two  associated  commands  in  the system to permit this type of

asymptotic constraint.  The command WEIGHT takes a list of  equations

of the form

	<kernel form> = <number>,

where <number> must be a positive integer.  This command assigns  the

weight  <number> to the relevant kernel form. A check is then made in

all algebraic evaluations to see if the total weight of the  term  is

equal   to   or  greater  than  the  weight  level  assigned  to  the

calculation.  If it is, the term is deleted.    To compute the  total

weight  of  a product, the individual weights of each kernel form are

multiplied by their corresponding powers and then added.

	The  weight  level of the system is initially set to 2.   The

user may change this setting, however, by the command

	WTLEVEL <number>;

which sets <number> as the new weight level of  the  system.   Again,

<number> must be a positive integer.


	In the present system, it is not  possible  to  differentiate

with  respect  to  a  variable  for which a weight has been assigned,

or  for such a variable to appear in a substitution expression. These

restrictions  could  be  removed  if  they prove too inconvenient for



6.1  Preliminary

	Although   REDUCE   is   designed   primarily  for  algebraic

calculations, its source language is general enough to  allow  for  a

full  range  of  LISP-like  symbolic  calculations.   To achieve this

generality, however, it is necessary to provide  the  user  with  two

modes of evaluation, namely an algebraic mode and a symbolic mode. To

enter symbolic mode, the user  types  LISP;  (or  SYMBOLIC;)  and  to

return  to  algebraic  mode he types ALGEBRAIC;.  Evaluations proceed

differently in each mode so the user is advised to check what mode he

is in if a puzzling error arises.  He can find his mode by typing


The current mode will then be printed as ALGEBRAIC or SYMBOLIC.

	If you wish to enter the other mode for a limited time, it is

possible to say

	LISP <command>		(or SYMBOLIC <command>)

or	ALGEBRAIC <command>

At the end of the evaluation, you will be back in the previous mode. 

For example, if the current mode is ALGEBRAIC, then the commands



will be evaluated in symbolic mode and algebraic mode respectively.

	This  section  assumes  that  the  reader  has  a  reasonable

acquaintance  with LISP 1.5 at the level of the LISP 1.5 Programmer's

Manual [7] or Clark Weissman's LISP 1.5 Primer[8]. Persons unfamiliar

with this material  will  have  some  difficulty  understanding  this


	Except where explicit limitations have been made, most REDUCE

algebraic constructions carry over  into  symbolic  mode.    However,

there  are  two  major differences.  First, expression evaluation now

becomes LISP evaluation. Secondly, assignment statements are  handled

differently.   We shall describe this difference later.  In addition,

function definitions follow the conventions of Standard LISP [9].

	To begin with, we mention  a  few  extensions  to  our  basic

syntax  which  are designed primarily if not exclusively for symbolic


6.2 General Identifiers

	In Section  2.3,  we  limited  identifiers  to  sequences  of

letters  and  numbers.  However, it is possible to input any sequence

of characters in REDUCE as  a  name  by  prefixing  non  alphanumeric

characters by the 'escape character' ! .

	e.g. A!(B is an allowed identifier.  It will print as A(B.

6.3 Symbolic Infix Operators

	There are three binary infix operators in REDUCE intended for

use  in  symbolic  mode.   These operators  and   their  alphanumeric

equivalents are as follows:


	≡	EQ


The  precedence of these operators is as given by the following list,

from outermost to innermost operations:

<infix operator> ::= ←|∧|∨|¬|ε|=|≠|≡|>=|>|<=|<|+|-|*|/|↑|.

6.4  Symbolic Expressions

	These consist of scalar variables and  operators  and  follow

the normal rules of the LISP meta language.




	SIMP (U+V↑2)

6.5 Quoted Expressions

	Because  LISP  evaluation  requires  that  each  variable  or

expression have a value, it is necessary to add to REDUCE the concept

of a quoted expression by analogy with the LISP QUOTE function.  This

is provided by the single quote mark '.

	e. g. 'A    represents the LISP S-expression (QUOTE A)

	     '(A B C) represents the LISP S-expression (QUOTE (A B C))

	Note, however,  that  strings  are  automatically  quoted  in

symbolic mode. Thus, to print the string "A STRING", one would write


BEWARE!!!  Within  a  quoted  expression,  normal  LISP  S-expression

syntax rules apply.  Thus the escape character ! is just another LISP

character,  as  are  the  terminators  ;  and  $.  For  example,  'A;

represents  the  S-expression  (QUOTE  A;),  so  you must put a space

before the semicolon if it is to act as a terminator.

6.6 LAMBDA Expressions

	LAMBDA  expressions  provide  the means for constructing LISP

LAMBDA expressions in symbolic mode.     They  may  not  be  used  in

algebraic mode.


<LAMBDA expression> ::= LAMBDA <varlist><terminator><statement>

<varlist> ::= (<variable>,...,<variable>)

	e. g. LAMBDA (X,Y); CAR X . CDR Y

	is equivalent to the LISP LAMBDA expression


	The  parentheses  may  be  omitted in specifying the variable

list if desired, and λ may be used in  place  of  the  reserved  word


	LAMBDA expressions may be used in symbolic mode in  place  of

prefix  operators,  or  as an argument of the reserved word FUNCTION,

which is used in the same way as FUNCTION in Standard LISP.

6.7 Symbolic Assignment Statements

	In symbolic mode, if the left side of an assignment statement

is a variable, a SETQ of the right hand side to that variable occurs.

If the left hand side is an  expression,  a  function  definition  is


	e. g.  X←Y  translates into  (SETQ X Y)




		      ELSE ASSOC (U,CDR V)

defines the LISP function ASSOC.

	MACROs  and FEXPRs may be defined by prefixing the assignment

by the word MACRO or FEXPR.

e. g. we could define a MACRO CONSCONS by


	Function definitions may also be input in the procedural form

discussed  in Section 2.17.  The procedural type in this case is LISP

(or SYMBOLIC).  For example, the above definition of ASSOC  could  be

written as





	FEXPRs and MACROS may also be input in this manner  with  the

procedural types FEXPR and MACRO respectively.

6.8  Communication with Algebraic Mode

	If a function is defined in  symbolic  mode  for  use  as  an

operator  in an algebraic calculation, it is necessary to communicate

this  to  the  algebraic  processor.   This  can be done by using the

command OPERATOR. Thus


would  declare  the  functions  FUN1 and FUN2 as algebraic operators.

This declaration MUST be made in symbolic  mode,  as  the  effect  in

algebraic mode is different.

	Furthermore, if you wish to use the algebraic evaluator on an

argument  in  a  symbolic  mode definition, the function REVAL can be

used.   The one argument of REVAL must be the LISP prefix  equivalent

of  a  scalar expression, e. g., (COS (PLUS X Y)).  REVAL returns the

evaluated expression in a similar form.

			     APPENDIX A


A.1 Reserved Identifiers

	We list here all identifiers which are normally  reserved  in

REDUCE.  We  include  in  this list all reserved identifiers given in

Section 2 plus all command  names  and  operators  initially  in  the

system.   The  reserved  identifiers  used  in  high  energy  physics

calculations (Appendix C) are also included for completeness.



Reserved Scalar  	E I

Infix Operators		← := ∧ ∨ ¬ ε = ≠ ≡ >= > <= < + - * / ↑  **  .


                        GREATERP  LESSEQ  LESSP  PLUS   MINUS   TIMES

                        QUOTIENT EXPT CONS





                        NOSPUR   NUMER  OFF  ON  OPERATOR  ORDER  OUT


                        SAVEAS   SCALAR  SHUT  SPUR  SYMBOLIC  VECTOR

                        WEIGHT WRITE WTLEVEL

A.2 Commands Normally Available In REDUCE

Notation:	E, E1,...,En	denote expressions

		V,V1,...,Vn	denote variables

The number after the description refers to the Section in  which  the

command is described.

ALGEBRAIC E;		If E is empty, the  system  mode  is  set  to
                        algebraic.    Otherwise,  E  is  evaluated in
                        algebraic mode and the  system  mode  is  not
                        changed (6.1)

ARRAY V1<size>,		Declares V1 through Vn as array names. <size>
	,...,Vn<size>;	describes  the  maximum  size  of  the  array 

CLEAR E1,...En;		Removes  any  substitutions  declared  for E1
                        through En from system (2.15)

COMMENT <any>;		Used for including comments in text. <any> is
                        any sequence of characters  not  including  a
                        terminator (2.7)

CONT;			An  interactive  command  which  causes   the
                        system  to  continue the calculation from the
                        point in the input file where the last  PAUSE
                        was encountered (2.18)

DENOM V;		Assigns V to  denominator  of  the  workspace

END <any>;		Terminates files used for  input  to  REDUCE.
                        <any>   is   any   sequence  of  symbols  not
                        including a terminator or the reserved  words
                        END, ELSE or UNTIL (2.19)
FACTOR E1,...En;	Declares expressions  as  factors  in  output

FOR			Command used to define a variety  of  program
                        loops (2.10.3)

FORALL V1,...,Vn	Declares variables V1 through Vn as arbitrary 
       <command>	in the substitution rules given by <command>
			(2.14, 2.16, 3.1 and 5.2)

GOTO V;			Performs an unconditional transfer  to  label
                        V.  Can  only  be used in compound statements

IF			Used to define conditional statements (2.10.2
                        and 5.2)

IN V1,...,Vn;		Inputs  the  external REDUCE files V1 through
                        Vn (2.13.1)

INFIX V1,...,Vn;	Declares  the  non-alphanumeric characters V1
                        through Vn as infix operators (2.5)

INTEGER V1,...,Vn;	Declares  V1  through Vn as integer variables

LET E1,...,En;		Declares  substitutions  for  the  left  hand
                        sides of expressions E1 through En. (2.14 and
                        5.2).  In  addition, LET can be used to input
                        differentiation rules (2.16)

LISP E;			If  E is empty, the system evaluation mode is
                        set to symbolic.  Otherwise, E  is  evaluated
                        in  symbolic  mode  and  the  system mode not
                        changed (6.1)

MATCH E1,...,En;	Declares  substitutions  for  the  left  hand
                        sides of  E1  through  En  when  matching  of
                        explicit powers is required (5.2)

MATRIX E1,...,En;	Declares matrix variables to the system.  The
                        Ei  may be matrix variable  names, or include
                        details of the size of the matrix (4.3)

MKCOEFF V1,V2;		Used   to   partition   expression   in   the
                        workspace. The various powers of V1  in  this
                        expression are stored in V2 (3.7)

ND V1,V2;		Assigns V1 to numerator of the workspace  and
                        V2 to its denominator (3.7)

NUMER V;		Assigns V to numerator of the workspace (3.7)

OFF V1,...,Vn;		Turns off the flags V1 through Vn (2.11.3)

ON V1,...,Vn;		Turns on the flags V1 through Vn (2.11.3)

OPERATOR V1,...,Vn;	Declares V1 through Vn as algebraic operators
                        (2.5 and 6.8)

ORDER V1,...,Vn;	Declares an ordering for variables V1 through
                        Vn on output (3.2.1)

OUT V;			Declares V as output file (2.13.2)

PAUSE;			An  interactive  command  for use in an input
                        file.   When  it  is  evaluated,  control  is
                        transferred to the user's terminal (2.18)

PRECEDENCE V1,V2;	Gives infix  operator  V1  a  new  precedence
                        immediately    higher    than   the   current
                        precedence of V2 (2.5)

PROCEDURE		Names   a   statement  for  repeated  use  in
                        calculations. Type specification of procedure
                        precedes the command name (2.17 and 6.7)

REAL V1,...,Vn;		Declares variables  V1  through  Vn  as  real

RETURN E;		Causes a transfer out of a compound statement
                        to the next highest program level. Value of E
                        is returned from compound statement. E may be
                        empty (2.10.6)

SAVEAS E;		Assigns E to the current  expression  in  the
                        workspace (3.1)

SCALAR V1,...,Vn;	Declares variables V1 through  Vn  as  scalar

SHUT V;			Closes the output file V (2.13.3)


WEIGHT E1,...En;	Assigns an asymptotic weight to the left hand
                        sides of E1 through En (5.3)

WRITE E1,...,En;	Causes the values of  E1  through  En  to  be
                        written on the current output file (3.2.4)

WTLEVEL V;		Sets  the  asymptotic  weight  level  of  the
                        system to V (5.3)

A.3  Mode Flags in REDUCE

	This Section lists the flags which may appear as arguments of

ON  and OFF.  The action of the flag when it is ON is described here,

unless stated otherwise. The numbers, as  previously,  refer  to  the

Section in which the flag is described.

ALLFAC		Causes  the  system  to factor out common products on
                output of expressions (3.2.3)

DIV		Causes the system to divide  out  simple  factors  on
		output, so that negative powers or rational fractions
		can be produced (3.2.3)

ECHO		Causes echoing of input (2.13.1)

EXP		Causes expressions to be expanded  during  evaluation

FLOAT		Prevents  conversion  of  floating point numbers into
                the ratio of two integers during evaluation (2.10.1)

FORT		Declares output in a FORTRAN notation (3.5)

GCD		Causes  the system to cancel greatest common divisors
                in rational expressions (3.4)

INT		Specifies an interactive mode of operation  (2.18)

LIST		Causes output to be listed one term to a line (3.2.3)

MCD		Causes  denominators  to be combined when expressions
                are added (3.3)

MSG		Causes diagnostic messages to be printed (2.14)

NAT		Specifies 'natural' style of output (3.6)

NERO		Inhibits printing of zero assignments (3.2.5)

RAT		An output flag used in conjunction with  FACTOR.   It
		causes the overall denominator in  an  expression  to
		be printed with each factored sub-expression (3.2.3)

RESUBS		When  RESUBS is OFF, the system does not reexamine an
                expression for further substitutions  after  one  has
                been made (5.2)

A.4  Diagnostic and Error Messages in REDUCE

	Diagnostic messages in the REDUCE system are  of  two  types;

error  messages  and warning messages.   The former usually cause the

termination of the current calculation whereas the  latter  warn  the

user  of  an  ambiguity  encountered  or  some action taken which may

indicate an error. If the system is in an interactive state,  it  can

ask  the  user  when  it  encounters  an  ambiguity  for  the correct

interpretation.  Otherwise it will make  the  most  plausible  guess,

print a message informing the user of the choice made, and continue.

	If an error is found during the parsing  of  the  input,  the

current phrase is reprinted with the place marked where the error was

encountered.   In some systems, it is then possible to edit the  line

and correct the error.

	For completeness, again, we include messages which can  occur

in High Energy Physics calculations (Appendix C).

A.4.1 Error Messages

ARRAY TOO SMALL		An  array  used  in  MKCOEFF  is too small to
                        store all  powers  of  the  expression  being

ASSIGNMENT <expression> An invalid assignment has been input  to  the 

FORMAT <expression>	The format  of  the argument of a command  is
INCORRECT		incorrect

INCORRECT ARRAY		Non-numeric index  has  been used with matrix 
ARGUMENTS FOR <name>	<name>

INVALID CHARACTER	Invalid character found on input

MATRIX MISMATCH		Two  matrix  expressions  are  not  correctly
                        matched for addition or multiplication

MATRIX SYNTAX		A syntax error  has  been  encountered  in  a
                        matrix expression

MISMATCH OF ARGUMENTS	Indicates  that  an  operator  for  which  an
                        evaluation  procedure  has  been  defined  is
                        called with the wrong number of arguments


MISSING VECTOR		An expression encountered in a vector context
                        does not contain a vector

NON SQUARE MATRIX	An  invalid  operation on a non square matrix
                        has been requested (e. g., a trace)


SINGULAR MATRIX		System  has  been  asked to invert a singular

SUB FORMAT		The  arguments  of  the operator SUB have the
                        wrong format

SYNTAX ERROR		Incorrect syntax in input. This error  occurs
                        only  if  the  system  is unable to determine
                        what causes  the  error

TOO FEW RIGHT		Input error

TOO MANY RIGHT		Input error

UNMATCHED INDEX		Unmatched indices have been encountered during
ERROR <list>		the evaluation of a vector expression

VECTOR <variable>	A vector variable has been  used  in  a scalar

ZERO DENOMINATOR	An expression with  a  zero  denominator  has
                        been encountered

<operator> NOT FOUND	An unknown operator appears in  a  PRECEDENCE

<variable> INVALID IN	Incorrect statement syntax
<statement name> STATEMENT

<variable> HAS NO MASS	A   variable   encountered   in   an   MSHELL
                        declaration has no mass assigned to it

A.4.2  Diagnostic Messages

ASSIGNMENT FOR <expression>	<expression> has been reassigned to a 
    REDEFINED			new value

<expression> REPRESENTED	The system has represented the  first
BY <expression>			expression by the second

<expression> NOT FACTORABLE	An invalid expression has been  given

<variable> DECLARED <type>	<variable> has been declared <type>

			     APPENDIX B


B.1.1	REDUCE is stored as a 38K system  with  filename  REDUCE.DMP.

The complete source program, written in REDUCE, is stored in the user

area [1,ACH] with filename REDUCE.RED  if  anyone  is  interested  in

studying it.

	REDUCE may be loaded by typing R  REDUCE.   When  the  system

returns  an  asterisk, you are in LISP.  You can then enter REDUCE by

typing (BEGIN).  The system then expects REDUCE  commands  from  you.

You can return to LISP by the command END;

	If you require more core for your job,  you  can  get  it  by



.CORE <size required><cr>


	You will then be back in LISP.

B.1.2 Special Features

B.1.2.1 If you give IN and OUT a variable or dotted pair as argument,

the  output  goes  to  your  disk  area.    In addition, the reserved

identifier L is used to represent the line printer on output.

	i. e. OUT L;

sends output to the line printer.

	Input from other devices may be specified  by  preceding  the

file name by the device name.  For example, to input a file ANDY from

disk area [S,JAM] followed by FOO from DTA2:, you would type


B.1.2.2  The altmode character may be used as a terminator. However,

if it is used, no results are printed when expressions are evaluated;

the semicolon must be used in this case.


.R REDUCE				load the program

*(BEGIN)				enter REDUCE

*COMMENT A SAMPLE PROGRAM;		comments are allowed

*X←(Y+Z)↑2;				set X to (Y+Z)↑2

      2            2			here's the result printed
X := Y  + 2*Y*Z + Z			because we used a semicolon
					as a terminator	

*DF(X,Z,2);				now differentiate X wrt Z twice

2					here's that result

*PROCEDURE FAC N;			now define the factorial 

*	BEGIN INTEGER M,N;		function

*		M←1;


*		M←M*N;

*		N←N-1;

*		GO TO A

*	 END;

*2↑FAC 3;				we can omit the parentheses


*FAC (120);				or put them in with unary


<yes. big numbers do work!>



*LISP;					enter symbolic mode


NIL					value returned in symbolic mode

*CAR ('(A));				compute the CAR of (A)

A					here's its value




*** ASSOC REDEFINED 			REDUCE diagnostic message

ASSOC 					value from ASSOC definition

*ASSOC ('A,'((B . C) (A . D)));		test ASSOC

(A . D)					it works!

*END;					return to LISP

***					value of END routine

"ENTERING LISP..."			so that you know



	Instructions   for   running   REDUCE  on  this  machine  are

obtainable from the AIDS Office in Pine Hall.

                             APPENDIX C


C.1  Preliminary.

	A set of REDUCE commands is provided for users interested  in

symbolic  calculations in high energy physics.  Several extensions to

our basic syntax are  necessary,  however,  to  allow  for  the  more

complicated data structures encountered.

C.2 Operators used in High Energy Physics Calculations.

	We begin by introducing three new operators required in these


C.2.1   . 

	The  .   operator is a binary operator used in algebraic mode

to denote the scalar product of  two  Loretz  four-vectors.   In  the

present  system,  the index handling routines all assume that Lorentz

four-vectors are used, but  these  routines  could  be  rewritten  to

handle other cases.

	Components   of  vectors  can  be  represented  by  including

representations of unit vectors in the system.  Thus if EO represents

the  unit vector (1,0,0,0), (P.EO) represents the zeroth component of

the four-vector P.  Our  metric  and  notation  follows  Bjorken  and

Drell[10].   Similarly,  an arbitrary component P  may be represented

by (P.U).  If contraction over components  of  vectors  is  required,

then the declaration INDEX must be used.



declares U as an index, and the simplification of

		(P.U) * (Q.U)

would result in


	The metric tensor g    may  be  represented  by  (U.V).    If

contraction over u and v is required, then U and V should be declared

as indices.

	The declaration REMIND V1...VN $ removes the index flags from

the variables V1 through VN.  However, these variables remain vectors

in the system.

C.2.2  G

	G  is  an  n-ary  operator  used to denote a product of gamma

matrices contracted with Lorentz four-vectors.   Gamma  matrices  are

associated with fermion lines in a Feynman diagram.  If more than one

such line occurs, then a different set of gamma  matrices  (operating

in  independent  spin spaces) is required to represent each line.  To

facilitate this, the first argument of G  is  a  line  identification

identifier (not a number) used to distinguish different lines.


		G(L1,P) * G(L2,Q)

denotes the product of P associated with a fermion line identified as

L1,  and  Q associated with another line identified as L2 and where P

and Q  are  Lorentz  four-vectors.    A  product  of  gamma  matrices

associated with the same line may be written in a contracted form.


		G(L1,P1,P2,...,P3) ≡ G(L1,P1)*G(L1,P2)*,...,*G(L1,P3)

The vector A is reserved in arguments of  G  to  denote  the  special

gamma matrix   .


		G(L,A)   ≡      associated with line L.

		G(L,P,A) ≡      associated with line L.

   (associated with line L) may be written as G(L,U), with U  flagged

as an index if contraction over u is required.

	The  notation  of  Bjorken  and  Drell [10] is assumed in all

operations involving gamma matrices.

C.2.3 EPS

	The operator EPS has four arguments,  and  is  used  only  to

denote  the  completely  antisymmetric  tensor  of  order  4  and its

contraction with Lorentz four-vectors.


	ε	= { +1 if α,β,u,v is an even permutation of 0,1,2,3
	 αβuv     { -1 if an odd permutation
		  { 0 otherwise

A contraction of the form ε    p q  may be written as EPS(AL,BE,P,Q),
			   αβuv u v

with AL and BE flagged as indices, and so on.

C.3 Vector variables.

	Apart   from  the  line  identification identifier in  the  G

operator, all other arguments of the operators  in  Section  B.2  are

vectors.  Variables  used  as  such  must  be declared so by the type

declaration VECTOR.

	e. g. 	VECTOR  P1,P2;

declares  P1  and  P2 to be vectors. Variables declared as indices or

given a mass (Section C.6) are automatically declared vector by these


C.4 Additional Expression Types.

	Two additional expression types are necessary for high energy

calculations, namely

C.4.1 Vector Expressions.

	These follow the normal rules of  vector  combination.   Thus

the  product  of  a  scalar  or  numerical  expression  and  a vector

expression is a vector, as are  the  sum  and  difference  of  vector

expressions.   If  these  rules  are not followed, error messages are

printed.   Furthermore,  if  the  system finds an undeclared variable

where it  expects  a  vector  variable,  it  will  ask  the  user  in

interactive  mode  whether to make that variable a vector or not.  In

batch mode, the declaration will be made automatically and  the  user

informed of this by a message.


	Assuming P and Q have been declared  vectors,  the  following

are vector expressions



	2*X*Y*P - P.Q*Q/(3*Q.Q)

whereas P*Q and P/Q are not.

C.4.2 Dirac Expressions

	These  denote those expressions which involve gamma matrices.

A gamma matrix is implicitly a 4 x 4 matrix, and so the product,  sum

and  difference  of  such expressions, or the product of a scalar and

Dirac expression is again a Dirac expression.   There  are  no  Dirac

variables  in  the system, so whenever a scalar variable appears in a

Dirac expression without an associated gamma  matrix  expression,  an

implicit unit 4 x 4 matrix is assumed.

	e. g. G(L,P) + M denotes G(L,P) + M*<unit 4 x 4 matrix>

	Multiplication  of   Dirac   expressions,   as   for   matrix

expressions, is of course non-commutative.

C.5  Trace Calculations.

	When a Dirac expression is evaluated, the system computes one

quarter of the trace of each gamma matrix product in the expansion of

the expression.  One quarter of each trace is taken in order to avoid

confusion  between the trace of the scalar M, say, and M representing

M * <unit 4 x 4 matrix>.

	The algorithms used  for  trace  calculations  are  the  best

available  at  the  time  this  system was produced.  For example, in

addition to the algorithm developed by Chisholm [11] for  contracting

indices  in  products of traces, REDUCE uses the elegant algorithm of

Kahane [12] for contracting indices in gamma matrix products.

	It is possible to prevent the trace calculation over any line

identifier by the declaration NOSPUR.

	e. g. NOSPUR L1,L2;

will mean that no traces are taken of of gamma matrix terms involving

the  line  numbers  L1  and  L2.  Furthermore,  any  product of gamma

matrices may be reduced to combinations of  the  sixteen  fundamental

gamma matrices by the declaration REDUCE.

	e. g. REDUCE L1,L2;

will mean that products of gamma matrices with line numbers L1 and L2

will  be  reduced  to the sixteen fundamental forms.  The declaration

REDUCE naturally includes NOSPUR.  This command should be  used  with

extreme  caution.   For  example,  the  reduction of a product of six

different 'slashed' vectors generates 66 terms!

	A  trace  of  a  gamma  matrix  expression  involving  a line

identifier which has been declared NOSPUR  or  REDUCE  may  be  later

taken  by making the declaration SPUR.   SPUR cancels both NOSPUR and


C.6 Mass Declarations

	It  is  often necessary to put a particle 'on the mass shell'

in a calculation.  This can, of course, be accomplished  with  a  LET

command such as

	LET P.P= M↑2;

but an alternative method  is  provided  by  two  commands  MASS  and

MSHELL. MASS takes a list of equations of the form:

	<vector variable> = <scalar variable>

	e. g. MASS P1=M, Q1=MU;

The only effect of this command is to associate the  relevant  scalar

variable as a mass with the corresponding vector.  If we now say

	MSHELL <vector variable>,...,<vector variable>;

and a mass has been associated with these arguments,  a  substitution

of the form

     <vector variable>.<vector variable> = <mass>↑2

is set up.  An example of this is given in the following.

C.7 Example

	We give here as an example of a simple  calculation  in  high

energy   physics   the   computation   of   the   Compton  scattering

cross-section  as  given  in  Bjorken  and  Drell[10],  Eqs.   (7.72)


	We wish to compute

     2         2        pf+m  ε'εki + εε'kf   pi+m  kiεε' + kfε'ε 
    α /2 (k'/k) trace {(----)(-----   ------)(----)(-----   ------)}
			 2m   2k.pi   2k'.pi   2m   2k.pi   2k'.pi

where ki and kf are the four-momenta of incoming and outgoing photons

(with  polarization vectors ε and ε' and laboratory energies k and k'

respectively) and pi,pf are incident and final electron four-momenta.

	Omitting the factor α↑2/(2*m↑2)*(k'/k)↑2 we need to find

	                  ε'εki + εε'kf         kiεε' + kfε'ε 
	1/4 trace {(pf+m)(-----   ------)(pi+m)(-----   ------)}
			  2k.pi   2k'.pi        2k.pi   2k'.pi

A   straightforward   REDUCE   program  for  this,  with  appropriate

substitutions would be:

MASS KI= 0, KF= 0, PI= M, PF= M; VECTOR E;
LET PI.E= 0, PI.EP= 0, PI.PF= M↑2+KI.KF, PI.KI= M*K,PI.KF= 
    M*KP, PF.E= -KF.E, PF.EP= KI.EP, PF.KI= M*KP, PF.KF=    
    M*K, KI.E= 0, KI.KF= M*(K-KP), KF.EP= 0, E.E= -1, EP.EP=
GP(PF)*(G(L,EP,E,KI)/(2*KI.PI) + G(L,E,EP,KF)/(2*KF.PI)) 
  * GP(PI)*(G(L,KI,E,EP)/(2*KI.PI) + G(L,KF,EP,E)/(2*KF.PI)) $    

This program will print the following result

                           (-1)        (-1)            2
THE COMPTON CXN IS 1/2*K*KP     + 1/2*K    *KP + 2*E.EP  - 1


[1]  Sconzo, P., LeSchack, A. R., and Tobey, R., Symbolic Computation
     of  f  and  g  Series  by Computer. Astronomical Journal 70 (May

[2]  Collins, G. E., Journal of the A.C.M. 14, 128 (1967).

[3]  Lipson,  J.  D.,  Symbolic  Methods for the Computer Solution of
     Linear Equations with Applications to Flowgraphs, Proceedings of
     the  1968 Summer Institute on Symbolic Mathematical Computation,
     IBM Programming Laboratory Report FSC 69-0312 (1969)

[4]  Hearn, A. C.,   REDUCE 2,  A System and  Language for  Algebraic
     Manipulation,  Proceedings of the Second Symposium  on  Symbolic
     and Algebraic Manipulation (to be published)

[5]  Hearn, A. C., REDUCE, A  User-Oriented  Interactive  System  for
     Algebraic  Simplification,  Proceedings  of the ACM Symposium on
     Interactive Systems for Experimental Applied  Mathematics,  held
     in Washington, D.C., August 1967.

[6]  Hearn,  A.  C.,  The Problem of Substitution, Proceedings of the
     1968 Summer Institute on Symbolic Mathematical Computation,  IBM
     Programming Laboratory Report FSC 69-0312 (1969)

[7]  McCarthy, J., Abrahams, P. W., Edwards, D. J., Hart, T.  P.  and
     Levin, M. I., LISP 1.5 Programmer's Manual, M.I.T. Press, 1965

[8]  Weissman, Clark, LISP 1.5 Primer, Dickenson, 1967

[9]  Hearn, A. C., Standard  LISP, Stanford  Artificial  Intelligence
     Project Memo AI-90 (May 1969)

[10] Bjorken, J. D.  and Drell, S. D., Relativistic Quantum Mechanics
     (McGraw-Hill, New York, 1965).

[11] Chisholm, J. S. R., Il Nuovo Cimento X, 30, 426 (1963)

[12] Kahane, J., Journal Math. Phys. 9, 1732 (1968)