UCP-19 March 1973 R E D U C E 2 U S E R ' S M A N U A L* by Anthony C. Hearn University of Utah Salt Lake City, Utah 84112 USA Second Edition *Work supported in part by the National Science Foundation under Grant No. GJ-32181. Computer time supported by the Advanced Research Projects Agency of the Office of the Department of Defense under Contract No. F30602-70-C-0300 at the University of Utah. i ABSTRACT 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 polynomials and rational functions, 2) symbolic differentiation, 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, 7) a complete language for symbolic calculations, in which the REDUCE program itself is written, 8) calculations of interest to high energy physicists including spin 1/2 and spin 1 algebra, 9) tensor operations. ii UPDATES TO MANUAL This copy of the REDUCE 2 User's Manual includes all updates through March 15, 1973. iii TABLE OF CONTENTS 1. INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . 1-1 2. STRUCTURE OF PROGRAMS. . . . . . . . . . . . . . . . . . . . . . 2-1 2.1 Preliminary . . . . . . . . . . . . . . . . . . . . . . 2-1 2.2 The REDUCE Standard Character Set . . . . . . . . . . . 2-1 2.3 Numbers . . . . . . . . . . . . . . . . . . . . . . . . 2-1 2.4 Identifiers . . . . . . . . . . . . . . . . . . . . . . 2-2 2.5 Variables . . . . . . . . . . . . . . . . . . . . . . . 2-2 2.5.1 Reserved Variables. . . . . . . . . . . . . . . . . . 2-2 2.6 Operators . . . . . . . . . . . . . . . . . . . . . . . 2-2 2.6.1 DF. . . . . . . . . . . . . . . . . . . . . . . . . . 2-4 2.6.2 COS. LOG. SIN . . . . . . . . . . . . . . . . . . . . 2-4 2.6.3 SUB . . . . . . . . . . . . . . . . . . . . . . . . . 2-5 2.7 Strings . . . . . . . . . . . . . . . . . . . . . . . . 2-5 2.8 Comments . . . . . . . . . . . . . . . . . . . . . . . 2-5 2.9 Expressions . . . . . . . . . . . . . . . . . . . . . . 2-5 2.9.1 Numerical Expressions . . . . . . . . . . . . . . . . 2-6 2.9.2 Scalar Expressions. . . . . . . . . . . . . . . . . . 2-6 2.9.3 Boolean Expressions . . . . . . . . . . . . . . . . . 2-6 2.9.4 Equations . . . . . . . . . . . . . . . . . . . . . . 2-6 2.10 Reserved Words . . . . . . . . . . . . . . . . . . . . 2-7 2.11 Statements . . . . . . . . . . . . . . . . . . . . . . 2-7 2.11.1 Assignment Statements. . . . . . . . . . . . . . . . 2-7 2.11.2 Conditional Statements . . . . . . . . . . . . . . . 2-8 2.11.3 FOR Statements . . . . . . . . . . . . . . . . . . . 2-8 2.11.4 GO TO Statements . . . . . . . . . . . . . . . . . . 2-9 2.11.5 Compound Statements. . . . . . . . . . . . . . . . .2-10 2.11.6 RETURN Statements. . . . . . . . . . . . . . . . . .2-10 2.12 Declarations . . . . . . . . . . . . . . . . . . . . .2-10 2.12.1 Variable Type Declarations . . . . . . . . . . . . .2-11 2.12.2 Array Declarations . . . . . . . . . . . . . . . . .2-11 2.12.3 Mode Handling Declarations . . . . . . . . . . . . .2-11 2.13 Commands . . . . . . . . . . . . . . . . . . . . . . .2-11 2.14 File Handling Commands . . . . . . . . . . . . . . . .2-12 2.14.1 IN . . . . . . . . . . . . . . . . . . . . . . . . .2-12 2.14.2 OUT. . . . . . . . . . . . . . . . . . . . . . . . .2-12 2.14.3 SHUT . . . . . . . . . . . . . . . . . . . . . . . .2-12 2.15 Substitution Commands. . . . . . . . . . . . . . . . .2-13 2.16 Removing Assignments and Substitution Rules from Expressions. . . . . . . . . . . . . . . . . . . . .2-14 2.17 Adding Rules for Differentiation of User-defined Operators. . . . . . . . . . . . . . . . . . . . . .2-14 2.18 Procedures . . . . . . . . . . . . . . . . . . . . . .2-15 2.19 Commands Used in Interactive Systems . . . . . . . . .2-16 2.20 DEFINE . . . . . . . . . . . . . . . . . . . . . . . .2-17 2.21 END. . . . . . . . . . . . . . . . . . . . . . . . . .2-17 iv 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-2 3.2.2 FACTOR . . . . . . . . . . . . . . . . . . . . . . . 3-2 3.2.3 Output Control Flags . . . . . . . . . . . . . . . . 3-3 3.2.4 WRITE Command . . . . . . . . . . . . . . . . . . . . 3-4 3.2.5 Suppression of Zeros . . . . . . . . . . . . . . . . 3-5 3.3 User Control of the Evaluation Process. . . . . . . . . 3-6 3.4 Cancellation of Common Factors. . . . . . . . . . . . . 3-6 3.5 Numerical Evaluation of Expressions . . . . . . . . . . 3-6 3.6 Saving Expressions for Later Use as Input . . . . . . . 3-8 3.7 Partitioning Expressions . . . . . . . . . . . . . . . 3-8 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-1 4.5 Operators with Matrix Arguments . . . . . . . . . . . . 4-2 4.5.1 DET . . . . . . . . . . . . . . . . . . . . . . . . . 4-2 4.5.3 TP. . . . . . . . . . . . . . . . . . . . . . . . . . 4-2 4.5.3 TRACE . . . . . . . . . . . . . . . . . . . . . . . . 4-2 4.6 Matrix Assignments. . . . . . . . . . . . . . . . . . . 4-3 4.7 Evaluating Matrix Elements. . . . . . . . . . . . . . . 4-3 5. ADVANCED COMMANDS. . . . . . . . . . . . . . . . . . . . . . . . 5-1 5.1 Kernels . . . . . . . . . . . . . . . . . . . . . . . . 5-1 5.2 Substitutions for General Expressions . . . . . . . . . 5-2 5.3 Asymptotic Commands . . . . . . . . . . . . . . . . . . 5-4 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-2 6.5 Quoted Expressions. . . . . . . . . . . . . . . . . . . 6-2 6.6 LAMBDA Expressions. . . . . . . . . . . . . . . . . . . 6-3 6.7 Symbolic Assignment Statements. . . . . . . . . . . . . 6-3 6.8 Communication with Algebraic Mode . . . . . . . . . . . 6-4 6.9 Obtaining the LISP Equivalent of REDUCE Input . . . . . 6-4 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 v 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-3 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-2 C.3 Vector Variables. . . . . . . . . . . . . . . . . . . . C-3 C.4 Additional Expression Types . . . . . . . . . . . . . . C-3 C.4.1 Vector Expressions. . . . . . . . . . . . . . . . . . C-3 C.4.2 Dirac Expressions . . . . . . . . . . . . . . . . . . C-4 C.5 Trace Calculations . . . . . . . . . . . . . . . . . . C-4 C.6 Mass Declarations . . . . . . . . . . . . . . . . . . . C-5 C.7 Example . . . . . . . . . . . . . . . . . . . . . . . . C-5 REFERENCES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . R-1 1-1 1. INTRODUCTION REDUCE is a program designed for general algebraic computations of interest to mathematicians, physicists and engineers. Its capabilities include: 1) expansion and ordering of polynomials and rational functions, 2) symbolic differentiation, 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, 7) a complete language for symbolic calculations, in which the REDUCE program itself is written, 8) calculations of interest to high energy physicists including spin 1/2 and spin 1 algebra, 9) 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 2. STRUCTURE OF PROGRAMS 2.1 Preliminary A REDUCE program consists of a set of functional commands which are evaluated sequentially by the computer. These commands are built up from declarations, statements and expressions. Such entities are composed of sequences of numbers, variables, operators, strings, reserved words and delimiters (such as commas and parentheses), which in turn are sequences of basic characters. 2.2 The REDUCE Standard Character Set The basic characters which are used to build up REDUCE symbols are the following: i) The 26 upper case letters A through Z ii) The 10 decimal digits 0 through 9 iii) The special characters ! " $ % ' ( ) * + , - . / : ; < > Programs composed from this standard set of characters will run in any available REDUCE system. In addition, several implementations of REDUCE (for example, on the PDP-10) use additional characters to represent some of the operators in the system. The local operating instructions for the given computer such as those in Section B of this manual should be consulted for the meaning of these special characters. However, for generality in exposition we shall limit ourselves to the standard character set in the body of this manual. 2.3 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 i) 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. 2-2 Restriction: The unsigned part of any number may NOT begin with a decimal point. i. e. NOT ALLOWED .5 -.23 +.12 2.4 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. e. g. A AZ P1 Q23P AVERYLONGVARIABLE Identifiers are used as variables, labels and to name arrays, operators and procedures. Restrictions: Reserved words in REDUCE (see Section 2.10) 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.5 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.12.1. 2.5.1 Reserved Variables Several variables in REDUCE have a particular value which cannot easily be changed by the user. These variables are as follows: 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.6 Operators Operators in REDUCE are also specified by name and type. There are two types, infix and prefix. Infix operators occur between their arguments. 2-3 e. g. A + B - C X = Y AND W MEMBER Z The following infix operators are built into the system. <INFIX OPERATOR> ::= |OR|AND|NOT|MEMBER|=|NEQ|EQ|>=|>|<=|<|+|-|*|/|**|. The use of the EQ operator is explained in Section 6 and the . operator in Section 6 and Appendix C. These operators may be further divided into the following sub classes <logical operator> ::= |OR|AND|NOT|MEMBER <relational operator> ::= =|EQ|NEQ|>=|>|<=|< <arithmetic operator> ::= +|-|*|/|** <symbolic operator> ::= . For compatibility with the intermediate language used by REDUCE, each special character infix operator has an additional alphanumeric identifier associated with it. These identifiers may be used interchangably with the corresponding infix character(s) on input. This correspondence is as follows: := SETQ = EQUAL >= GEQ > GREATERP <= LEQ < LESSP + PLUS - DIFFERENCE (unary MINUS) * TIMES / QUOTIENT (unary RECIP) ** EXPT . CONS The above operators are assumed to be binary,, except NOT which is unary and + and * which are nary. In addition, - and / may be used in a unary position. Any other operator is parsed as a binary operator using a left procedure grouping. Thus A/B/C is interpreted as (A/B)/C. There are two exceptions to this latter rule, namely ** and . which have a right precedence grouping. Thus A**B**C is interpreted as A**(B**C). 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). 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. 2-4 e. g. COS(U) DF(X**2,X) Parentheses may be omitted if the operator is unary. e. g. COS Y and COS(Y) are equivalent. Such unary prefix 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 infix form. Some prefix operators are also built into the system. These are as follows: 2.6.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: DF(<expression>,<variable>,<number>,...,<variable>,<number>) The <number> may be omitted if it is 1. e. g. DF(Y,X) = dY/dX 2 2 DF(Y,X,2) = d Y/dX 5 2 2 DF(Y,X1,2,X2,X3,2)= d Y/dX dX dX 1 2 3 2.6.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 (0) = 1 SIN (0) = 0 LOG (E) = 1 LOG (1) = 0 Their derivatives are also known to the system. The user can also add further rules for the reduction of expressions involving these operators by the methods described in Sections 2.15 and 5.2. 2-5 2.6.3 SUB This operator is described in Section 2.15. 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.7 Strings Strings are used only in output statements. A string consists of any number of characters enclosed in double quotes. e. g. "A STRING". 2.8 Comments 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> where <terminator> ::= ;|$ e. g. COMMENT THIS IS A COMMENT; Such comments are equivalent on input to an space. In addition, the sequence of symbols END <any sequence of symbols not including a terminator or the reserved words END, or ELSE or UNTIL> is equivalent to the reserved word END. 2.9 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 follows: 2-6 2.9.1 Numerical Expressions These consist of syntactically allowed combinations of integer or real variables, arithmetic operators and parentheses. They evaluate to numbers. Examples: 2 I + J - 2 * I**2 are numerical expressions if I and J are integers. 2.9.2 Scalar Expressions These consist of scalar variables and arithmetic operators and follow the normal rules of scalar algebra. Examples: X X**3 - 2*Y/(2*Z**2 - DF(X,Z)) (P**2 + M**2)**(1/2)*LOG (Y/M) 2.9.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> or <boolean expression> <logical operator> <boolean expression> They are used mainly in the IF and FOR statements described in Sections 2.11.2 and 2.11.3. Examples: J<1 X>0 or X=-2 2.9.4 Equations In the remainder of this manual, we shall refer to the expression <expression> = <expression> 2-7 as an equation. 2.10 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: <reserved word> ::= BEGIN|DO|ELSE|END|FOR|FUNCTION|GO|GOTO|IF|LAMBDA| NIL|PRODUCT|RETURN|STEP|SUM|TO|UNTIL|WHILE| 2.11 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 REDUCE. 2.11.1 Assignment Statements These statements have the following syntax <assignment statement> ::= <expression> := <statement> e. g. A1:=B+C H(X,Y):=X-2*Y 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.15 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. 2-8 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.12.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.11.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.11.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 usage, and is similar to the FORTRAN DO statement. Its value is 0. 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. 2-9 The <variable> within the FOR statement is assumed INTEGER. 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 -1. Examples: We assume that the declaration ARRAY A(10); has been made in the following examples. This declaration is explained in Section 2.12.2. (i) To set each element A(I) of the array to X**I we could write FOR I:=0 STEP 1 UNTIL 10 DO A(I):=X**I$ As a further convenience, the common construction STEP 1 UNTIL may be abbreviated by a colon. Thus we could write instead of the above FOR I:=0:10 DO A(I):=X**I$ Since the assignments in this calculation are not made at the top level, they are not printed. If the user desires this, he can use the WRITE statement for this purpose as in FOR I:=0:10 DO WRITE A(I):=X**I; Further uses of WRITE are described in Section 3.2.4. (ii) To sum the squares of the even positive integers through 50, we could write FOR I:=2 STEP 2 UNTIL 50 SUM I**2; (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 statements A(0):= 1$ FOR I:=1:10 DO A(I):=I*A(I-1)$ 2.11.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.11.5). They have the syntax: <go to statement> ::= GO TO <label> <label> ::= <variable> 2-10 Restrictions: GO TO statements may only occur within a compound statement. They may NOT occur at the top level of your program. Furthermore, they can only reference labels within the local block in which they are defined. 2.11.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; M:=1$ L1: IF N=0 THEN RETURN M; M:=M*N$ N:=N-1$ GO TO L1 END OF BLOCK; will assign the factorial of a preassigned INTEGER N to X. 2.11.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 0. e. g., RETURN (X+Y); RETURN M; RETURN; Restriction: RETURN statements may only occur within a compound statement.They may NOT occur at the top level of your program. 2.12 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.18. Some other REDUCE declarations are described in the following sub-sections. 2-11 2.12.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; SCALAR X,Y; 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 type. All such variables are given the initial value of 0. 2.12.2 Array declarations Arrays in REDUCE are defined similar to FORTRAN dimension statements. 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) All array elements are initialized to 0 at declaration time. Array elements may appear in the left side of assignment statements as in the examples in Section 2.11.3. 2.12.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 respectively. e. g. ON FLOAT,GCD; OFF LIST; The use of these flags and others available to the user is explained later in this manual. 2.13 Commands A command is an order to the system to do something. It has the syntax <command> ::= <statement><terminator>|<proper command> 2-12 <proper command> ::= <command name><space> <statement>,...,<statement><terminator> A variety of commands are discussed in the sections which follow. 2.14 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.14.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 identifier. 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.14.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.14.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-13 2.15 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; FOR ALL X LET K(X,Y) = X**Y; 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 2-14 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 X**2+2*X+2 2.16 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.12.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.17 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>) 2-15 and <var1>,...,<vari>,...,<varn> are the dummy variable arguments of <operator>. An analogous form applies to infix operators. We illustrate this with some examples: FOR ALL X LET DF(TAN X,X)= SEC(X)**2; FOR ALL X,Y LET DF(F(X,Y),X)=2*F(X,Y), DF(F(X,Y),Y)=X*F(X,Y); 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.18 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>; and <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. Examples: (1) The example in Section 2.11.5 could be made into an integer procedure FAC by the declaration: INTEGER PROCEDURE FAC (N); BEGIN INTEGER M; M:=1$ L1: IF N=0 THEN RETURN M; M:=M*N$ N:=N-1$ 2-16 GO TO L1 END; 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 formula n | 1 d 1 | p (x) = --- --- ---------------| n n! n 2 1/2| dy (y -2*x*y+1) | y=0 A REDUCE version of this is ALGEBRAIC PROCEDURE P(N,X); 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 2*P(2,W) would result in the output 2 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.19 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 2-17 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.20 DEFINE The command DEFINE allows a user to rename permanently any identifier in the system. Its argument is a list of expressions of the form <identifier> = <number>|<identifier>|<operator>| <reserved word>|<expression> For example, DEFINE BE==,X=Y+Z; means that 'BE' will be interpreted as an equal sign, and 'X' as the expression Y+Z from then on. This renaming is done at the input level and therefore takes precedence over any other replacement declared for the same identifier. 2.21 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 omitted. If an END command is used in the main program, control is then transferred to LISP. 3-1 3. MANIPULATION OF ALGEBRAIC EXPRESSIONS 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, (i.e., not inside a compound statement or procedure) 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. Example: If we evaluate the expression (X+Y)**2 at the top level and next wish to differentiate it with respect to Y, we can simply say DF(!*ANS,Y); to get the desired answer. If the user gets tired of typing !*ANS, he can use the DEFINE command to introduce another name for the workspace. For example, the statement DEFINE WS=!*ANS; would mean that from then on WS will be 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 syntax 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 SAVEAS Z; 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. 3-2 e. g. FOR ALL X SAVEAS H(X); 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. It should be noted, however, that the transformation of large expressions to produce these varied output formats can take a lot of computing time and space. If a user wishes to speed up the printing of his output in such cases, he can turn off the flag PRI using the OFF command. If this is done, then output is produced in one fixed format, which basically reflects the internal form of the expression, and none of the options below apply. PRI is normally on. With PRI on, the output declarations available are as follows: 3.2.1 ORDER The declaration ORDER may be used to order variables on output. Thus ORDER X,Y,Z; 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; ORDER Y,X; would order Z ahead of Y and X. 3-3 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 identifiers. e. g. FACTOR X,COS,SIN(X); causes all powers of X and SIN(X) and all functions of COS to be factored. 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 X**2*(Y**2+2*Y)+X*(Y**2+Z)/(2*A). 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. 3-4 (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 2 X*(2*X*Y *A + 4*X*Y*A 2 + Y + Z)/(2*A) 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 3-5 2 2 2 X *(Y + 2*Y) + X*(Y + Z)/(2*A) 3.2.4 WRITE Command 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.7). 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 value of WRITE is the value of its last argument. The print line is closed at the end of the WRITE command evaluation. Example: The following program calculates the famous f and g series [1]: X1:= -SIG*(MU+2*EPS)$ X2:= EPS-2*SIG**2$ X3:= -3*MU*SIG$ F:= 1$ G:= 0$ FOR I:= 1 STEP 1 UNTIL 10 DO BEGIN 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; F:=F1$ G:=G1$ END; A portion of the output, to illustrate the printout from the WRITE command, is as follows: ... <prior output> ... 2 F(4) := MU*(3*EPS - 15*SIG + MU) G(4) := 6*SIG*MU 2 F(5) := 15*SIG*MU*( - 3*EPS + 7*SIG - MU) 2 G(5) := MU*(9*EPS - 45*SIG + MU) 3-6 ... <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 printing 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. The latter flag is particularly useful if no greatest common divisor calculations are desired, or excessive differentiation of rational functions is required. 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 will perform this greatest common divisor check if the flag GCD is on. A check is automatically made, however, for common variable and numerical 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.11.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. 3-7 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. Example: The following REDUCE statements ON FORT; OUT FORFIL; WRITE "C THIS IS A FORTRAN PROGRAM"; WRITE " 1 FORMAT(E13.5)"; WRITE " U=1.23"; WRITE " V=2.17"; WRITE " W=5.2"; X:=(U+V+W)**11; WRITE "C OF COURSE IT WAS FOOLISH TO EXPAND THIS EXPRESSION"; WRITE " PRINT 1,X"; WRITE " END"; SHUT FORFIL; OFF FORT; will generate a file FORFIL which contains: C THIS IS A FORTRAN PROGRAM 1 FORMAT(E13.5) U=1.23 V=2.17 W=5.2 X=U**11+11*U**10*V+11*U**10*W+55*U**9*V**2+110*U**9 X*V*W+55*U**9*W**2+165*U**8*V**3+495*U**8*V**2*W+495 X*U**8*V*W**2+165*U**8*W**3+330*U**7*V**4+1320*U**7* XV**3*W+1980*U**7*V**2*W**2+1320*U**7*V*W**3+330*U** X7*W**4+462*U**6*V**5+2310*U**6*V**4*W+4620*U**6*V** X3*W**2+4620*U**6*V**2*W**3+2310*U**6*V*W**4+462*U** X6*W**5+462*U**5*V**6+2772*U**5*V**5*W+6930*U**5*V** X4*W**2+9240*U**5*V**3*W**3+6930*U**5*V**2*W**4+2772 X*U**5*V*W**5+462*U**5*W**6+330*U**4*V**7+2310*U**4* XV**6*W+6930*U**4*V**5*W**2+11550*U**4*V**4*W**3+ X11550*U**4*V**3*W**4+6930*U**4*V**2*W**5+2310*U**4* XV*W**6+330*U**4*W**7+165*U**3*V**8+1320*U**3*V**7*W 3-8 X+4620*U**3*V**6*W**2+9240*U**3*V**5*W**3+11550*U**3 X*V**4*W**4+9240*U**3*V**3*W**5+4620*U**3*V**2*W**6+ X1320*U**3*V*W**7+165*U**3*W**8+55*U**2*V**9+495*U** X2*V**8*W+1980*U**2*V**7*W**2+4620*U**2*V**6*W**3+ X6930*U**2*V**5*W**4+6930*U**2*V**4*W**5+4620*U**2*V X**3*W**6+1980*U**2*V**2*W**7+495*U**2*V*W**8+55*U** X2*W**9+11*U*V**10+110*U*V**9*W+495*U*V**8*W**2+1320 X*U*V**7*W**3 X=X+2310*U*V**6*W**4+2772*U*V**5*W**5+2310*U*V**4*W X**6+1320*U*V**3*W**7+495*U*V**2*W**8+110*U*V*W**9+ X11*U*W**10+V**11+11*V**10*W+55*V**9*W**2+165*V**8*W X**3+330*V**7*W**4+462*V**6*W**5+462*V**5*W**6+330*V X**4*W**7+165*V**3*W**8+55*V**2*W**9+11*V*W**10+W** X11 C OF COURSE IT WAS FOOLISH TO EXPAND THIS EXPRESSION PRINT 1,X END The number of continuation cards per statement can be modified by the assignment !*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.14. 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 expression. Example: The following program OFF NAT; OUT OUT; X := (Y+Z)**2; WRITE "END"; SHUT OUT; ON NAT; will generate a file OUT which contains X := Y**2 + 2*Y*Z + Z**2$ 3-9 END$ 3.7 Partitioning Expressions It is often necessary to get at parts of an expression during a calculation. REDUCE provides three operators for this purpose. These have proved adequate for all calculations brought to the author's attention, but other commands could be added if there is sufficient demand. (1) COEFF is an operator which assigns coefficients of the various powers of a kernel. It takes three arguments and has the syntax: COEFF(<expression>,<kernel>,<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 <kernel> in <expression>, up to the maximum dimension of the array. 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. Example: ARRAY X(7); COEFF((Y**2+Z)**3,Y,X); will cause X(7) to be set to 0, X(6) to 1, X(5) to 0, X(4) to 3*Z and so on until X(0), which would be set to Z**3. On the other hand, if we said COEFF((Y**2+Z)**3,Y,W); we would get a message W6 W4 W2 W0 are non zero and W6 would be set to 1, W4 to 3*Z and so on. It is also possible to place the various coefficients generated by COEFF in a particular column of a multi-dimensional array. To do this, the <identifier> in the above symbols should be replaced by an array expression in which the relevant array column is indicated by an asterisk. For example, 3-10 ARRAY XX(7,7,7); COEFF((Y**2+Z)**3,Y,XX(5,*,7)); will cause XX(5,7,7) to be set to 0, XX(5,6,7) to 1, XX(5,5,7) to 0 and so on. The value of COEFF is the highest non-zero power encountered in the expression. Thus in the above examples it would be 6. (2) NUM and DEN are operators which take a single expression as argument and which return the numerator and denominator of this expression respectively. E.g., NUM(X/Y**2) has the value X and DEN(X/Y**2) the value Y**2. 4-1 4. MATRIX CALCULATIONS 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. The size of the matrix may be declared explicitly in the matrix declaration, or by default in assigning such a variable to a matrix expression. e. g. MATRIX X(2,1),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. All elements of a matrix whose size is declared are initialized to 0. 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> 4-2 Sums and products of matrix expressions must be of compatible 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 A*B**(-1). Examples: Assuming X and Y have been declared as matrices, the following are matrix expressions Y Y**2*X-3*Y**(-2)*X Y+ MAT((1,A),(B,C))/2 4.5 Operators With Matrix Arguments Three additional operators are useful in matrix calculations, namely DET,TP 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, and DET MAT((A,B,C),(D,E,F),(G,H,J)); is a scalar expression whose value is the determinant of the matrix ( A B C ) ( ) ( D E F ) ( ) ( G H J ). 4.5.2 TP This operator takes a single matrix argument and returns its transpose. Its use is obvious. 4.5.3 TRACE The operator TRACE is used to represent the trace of a square matrix. Its use is also obvious. 4-3 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. 5-1 5. ADVANCED COMMANDS 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 [2]. 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 evaluation. Examples of kernel forms are: A COS (X*Y) LOG (SIN (X)) 5-2 whereas A*B (A+B)**4 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 [3] and [4], REDUCE does not attempt to implement a general pattern matching algorithm. However, the present system uses more sophisticated techniques than those discussed in reference [4]. 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. 5-3 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 e. g. FOR ALL X,Y LET COS(X+Y)=COS(X)*COS(Y)-SIN(X)*SIN(Y); 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 arbitrary variables in this syntax, we prefix such variables by the operator ARB rather than combine the IF construction with a FOR ALL clause. e. g. IF ARB X<0 LET F(X)=2*X**2; 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, 5-4 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. e.g. FOR ALL X CLEAR LOG(E**X),E**LOG(X),COS(W*T+THETA(X)); 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 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>; 5-5 which sets <number> as the new weight level of the system. Again, <number> must be a positive integer. 6-1 6. SYMBOLIC MODE 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 SYMBOLIC; (or LISP;) 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 !*MODE; 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 SYMBOLIC <command> (or LISP <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 SYMBOLIC CAR '(A); X+Y; 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 [5] or Clark Weissman's LISP 1.5 Primer[6]. Persons unfamiliar with this material will have some difficulty understanding this Section! Except where explicit limitations have been made, most REDUCE algebraic constructions carry over into symbolic mode. However, there are some differences. First, expression evaluation now becomes LISP evaluation. Secondly, assignment statements are handled differently, as we discuss in Section 6.7. Thirdly, local variables and array elements are initialized to NIL rather than 0. (In fact, such variables and elements are also initialized to NIL in algebraic mode, but the algebraic evaluator recognizes NIL as 0). Fourthly, the delimiters SUM and PRODUCT in the FOR statement (Section 2.11.3) are not defined in symbolic mode. Finally, function definitions follow the conventions of Standard LISP [7]. 6-2 To begin with, we mention a few extensions to our basic syntax which are designed primarily if not exclusively for symbolic mode. 6.2 General Identifiers In Section 2.4, 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 two binary infix operators in REDUCE intended for use in symbolic mode, namely EQ and . (CONS). The precedence of these operators was given in Section 2.6. 6.4 Symbolic Expressions These consist of scalar variables and operators and follow the normal rules of the LISP meta language. Examples: X CAR U . REVERSE V SIMP (U+V**2) 6.5 Quoted Expressions Because LISP evaluation requires that each variable or expression has 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 PRINC "A STRING"; Within a quoted expression, identifier syntax rules are those of REDUCE. Thus ( A !. B) is the list consisting of the three elements A, . and B, whereas (A . B) is the dotted pair of A and B. 6-3 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. Syntax: <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 (LAMBDA (X Y) (CONS (CAR X) (CDR Y))) The parentheses may be omitted in specifying the variable list if desired. LAMBDA expressions may be used in symbolic mode in place of prefix operators, or as an argument of the reserved word FUNCTION. 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 assumed. e. g. X:=Y translates into (SETQ X Y) whereas ASSOC(U,V) := IF NULL V THEN NIL ELSE IF U EQ CAAR V THEN CAR V 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 MACRO CONSCONS L := EXPAND(CDR L, 'CONS); Function definitions may also be input in the procedural form discussed in Section 2.18. The procedural type in this case is SYMBOLIC (or LISP). For example, the above definition of ASSOC could be written as 6-4 SYMBOLIC PROCEDURE ASSOC(U,V); IF NULL V THEN NIL ELSE IF U EQ CAAR V THEN CAR V ELSE ASSOC (U, CDR V); 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 OPERATOR FUN1,FUN2; 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. 6.9 Obtaining the LISP Equivalent of REDUCE Input A user can obtain the LISP equivalent of his REDUCE input by turning on the flag DEFN (for definition). The system then prints the LISP translation of his input but does not evaluate it. Normal operation is resumed when DEFN is turned off. Users should note that the LISP obtained is implementation dependent and so will vary from machine to machine. A-1 APPENDIX A SUMMARY OF THE REDUCE SYSTEM 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 Words BEGIN DO ELSE END FOR FUNCTION GO GOTO LAMBDA NIL PRODUCT RETURN STEP SUM TO WHILE Reserved Scalar E I Variables Infix Operators := = >= > <= < + - * / ** . SETQ AND NOT OR MEMBER EQUAL UNEQ EQ GREATEQ GREATERP LESSEQ LESSP PLUS MINUS TIMES QUOTIENT EXPT CONS Prefix Operators ARB COEFF COS DEN DET DF EPS G LOG MAT NUM SIN SUB TRACE Commands ALGEBRAIC ARRAY CLEAR COMMENT END FACTOR FOR FORALL GO GOTO IF IN INTEGER LET LISP MASS MATCH MATRIX MSHELL NOSPUR OFF ON OPERATOR ORDER OUT PROCEDURE REAL RETURN SAVEAS SCALAR SHUT SPUR SYMBOLIC VECTOR WEIGHT WRITE WTLEVEL A-2 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 (2.12.2) CLEAR E1,...En; Removes any substitutions declared for E1 through En from system (2.16) COMMENT <any>; Used for including comments in text. <any> is any sequence of characters not including a terminator (2.8) 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.19) 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.20) FACTOR E1,...En; Declares expressions as factors in output (3.2.2) FOR Command used to define a variety of program loops (2.11.3) FORALL V1,...,Vn Declares variables V1 through Vn as arbitrary <command> in the substitution rules given by <command> (2.15, 2.17, 3.1 and 5.2) GOTO V; Performs an unconditional transfer to label V. Can only be used in compound statements (2.11.4) IF Used to define conditional statements (2.11.2 and 5.2) IN V1,...,Vn; Inputs the external REDUCE files V1 through Vn (2.14.1) A-3 INTEGER V1,...,Vn; Declares V1 through Vn as integer variables (2.12.1) LET E1,...,En; Declares substitutions for the left hand sides of expressions E1 through En. (2.15 and 5.2). In addition, LET can be used to input differentiation rules (2.17) 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) OFF V1,...,Vn; Turns off the flags V1 through Vn (2.12.3) ON V1,...,Vn; Turns on the flags V1 through Vn (2.12.3) OPERATOR V1,...,Vn; Declares V1 through Vn as algebraic operators (2.6 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.14.2) PAUSE; An interactive command for use in an input file. When it is evaluated, control is transferred to the user's terminal (2.19) PROCEDURE Names a statement for repeated use in calculations. Type specification of procedure precedes the command name (2.18 and 6.7) REAL V1,...,Vn; Declares variables V1 through Vn as real (2.12.1) 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.11.6) SAVEAS E; Assigns E to the current expression in the workspace (3.1) SCALAR V1,...,Vn; Declares variables V1 through Vn as scalar (2.12.1) A-4 SHUT V; Closes the output file V (2.14.3) SYMBOLIC E; Same as LISP E; 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-5 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) DEFN Causes the system to output the LISP equivalent of REDUCE input without evaluation (6.9) 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.14.1) EXP Causes expressions to be expanded during evaluation (3.3) FLOAT Prevents conversion of floating point numbers into the ratio of two integers during evaluation (2.11.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.19) 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.15) NAT Specifies 'natural' style of output (3.6) NERO Inhibits printing of zero assignments (3.2.5) PRI Specifies fancy printing for output (3.2) 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-6 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 A REPRESENTS ONLY A can only be used as gamma 5 in vector GAMMA5 IN VECTOR expressions EXPRESSIONS ARRAY TOO SMALL An array used in COEFF is too small to store all powers of the expression being partitioned CATASTROPHIC ERROR If this error occurs, please send a listing of the input and a copy of the output to the author DIFFERENTIATION WRT Differentation with respect to anything but a <expression> NOT ALLOWED variable is not permitted DOT CONTEXT ERROR A quoted expression in symbolic mode has an incorrect LISP syntax ELEMENT OUT OF BOUNDS A reference to an array element outside the declared range has been made INCORRECT ARRAY Non-numerical index has been used with array ARGUMENTS FOR <name> or matrix <name> LARGER SYSTEM NEEDED This means that your problem requires REDUCE facilities not present in your system LOCAL VARIABLE USED A local variable has been illegally used in AS OPERATOR an operator context A-7 MATRIX MISMATCH Two matrix expressions are not correctly matched for addition or multiplication MATRIX <name> NOT SET A matrix has been referenced whose elements are not known MISMATCH OF ARGUMENTS Indicates that an operator for which an evaluation procedure has been defined is called with the wrong number of arguments MISSING ARGUMENTS FOR A line symbol is missing in a gamma matrix G OPERATOR expression MISSING OPERATOR Input error MISSING VECTOR An expression encountered in a vector context does not contain a vector NON-NUMERICAL ARGUMENT An array or matrix element has been referenced IN <expression> by an non-numerical expression NON SQUARE MATRIX An invalid operation on a non square matrix has been requested (e. g., a trace) NOT YET IMPLEMENTED Please write to the author if you get this message, enclosing a copy of your input OPERATOR <name> CANNOT An arbitrary operator cannot be used in a BE ARBITRARY substitution rule REDUNDANT OPERATOR Input error REDUNDANT VECTOR A redundant vector has been found in a vector expression SINGULAR MATRIX System has been asked to invert a singular matrix SUBSTITUTION FOR An invalid expression has occurred in a <expression> NOT substitution statement ALLOWED SYNTAX ERROR Incorrect syntax in input. This error occurs only if the system is unable to determine what causes the error SYNTAX <expression> A syntax error has been found during the INCORRECT evaluation of <expression> TOO FEW RIGHT Input error PARENTHESES TOO MANY RIGHT Input error PARENTHESES A-8 TYPE CONFLICT FOR An expression has been found in the wrong type <expression> context UNMATCHED INDEX Unmatched indices have been encountered during ERROR <list> the evaluation of a vector expression ZERO DENOMINATOR An expression with a zero denominator has been encountered 0/0 FORMED The system cannot handle 0/0 <expression> CANNOT BE An operator has been given an invalid name AN OPERATOR <expression> INVALID A procedure has been given an illegal name PROCEDURE NAME <expression> NOT FOUND An expression expected by the system (e.g., in a CLEAR statement) was not found <filename> NOT OPEN SHUT has been given the name of a file which has not been opened or which is already shut <identifier> UNDEFINED An unrecognized command name has been found <number> TOO LONG FOR A large integer has been found while FORTRAN preparing FORTRAN output <type> <variable> A variable with type <type> has been used in a USED AS SCALAR scalar context <variable> ALREADY A declaration for a previously declared DEFINED AS <type> variable has been made <variable> INVALID or Incorrect statement syntax <variable> INVALID IN <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 COEFF GIVEN EXPRESSION COEFF has been given an expression WITH DENOMINATOR <exp> with a denominator which may be a function of the kernel whose powers are being separated MISSING END IN FILE <name> The file <name> is not terminated with an END statement A-9 <expression> REPRESENTED The system has represented the first BY <expression> expression by the second <name> REDEFINED An operator or procedure has been redefined <variable> DECLARED <type> <variable> has been declared <type> B-1 APPENDIX B B.1 RUNNING REDUCE ON THE STANFORD PDP-10 B.1.1 Preliminary REDUCE is stored as a 38K system with filename REDUCE.DMP. It may be loaded by typing R REDUCE. When the system is loaded, it prints a version date and returns an asterisk indicating that it is ready for input. If you require more core for your job, you can get it by typing ↑C .CORE <size required><cr> ST<cr> You will then be back in REDUCE. 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 (i.e., device LPT:). Input from other devices may be specified by preceding the file name by the device name with the proviso that project-programmer numbers must be quoted. For example, to input a file ANDY from disk area [S,JAM] followed by FOO from DTA2:, you would type IN '(S,JAM),ANDY,DTA2!:,FOO; 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. B-2 B.1.3 A SAMPLE PROGRAM .R REDUCE load the program *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; * A: IF N=0 THEN RETURN M; * M:=M*N; * N:=N-1; * GO TO A * END; *2**FAC 3; we can omit the parentheses 64 *FAC (120); or put them in with unary operators <yes. big numbers do work!> *COMMENT THE FOLLOWING IS USEFUL ONLY IF YOU ARE INTERESTED IN SYMBOLIC MODE; *SYMBOLIC; enter symbolic mode NIL value returned in symbolic mode *CAR ('(A)); compute the CAR of (A) A here's its value *ASSOC(U,V):=IF NULL V THEN NIL now define ASSOC * ELSE IF U CAAR V THEN CAR V * ELSE ASSOC(U,CDR V); *** 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 * B-3 B.2 RUNNING REDUCE ON THE STANFORD CAMPUS FACILITY IBM 360/67 B.2.1 Preliminary REDUCE for the Stanford IBM 360/67 computer is stored in symbolic form on a 2314 disk file, and is called into core by a LISP program. However, because of the relatively large size of the program, it is necessary to run REDUCE jobs in the LARGE partition, or overnight. A minimum REDUCE job with the necessary JCL is as follows: <job card> /* SERVICE CLASS=L // EXEC PGM=LISP //REDUCE DD DSN=SYS3.REDUCE2,DISP=OLD //LISPOUT DD SYSOUT=A //LISPIN DD * RESTORE(REDUCE) BEGIN NIL <REDUCE command> ... <REDUCE command> END; /* Filenames which appear in IN and OUT statements are the ddnames of the relevant files. The description of such files must be specified as part of the JCL for the job. For example //TRAC DD DSN=A123.TR,VOL=SER=SYS15,UNIT=2314,DISP=OLD specifies a file named TRAC for input. It would be referenced in REDUCE by the command IN TRAC; Similarly, to output results onto a file OUT using the OUT command, the JCL for OUT might be: //OUT DD DSN=A123.OUT,VOL=SER=SYS07,DISP=(NEW,KEEP),UNIT=2314, // SPACE=(TRK,(5,5),RLSE), // DCB=(RECFM=FB,LRECL=80,BLKSIZE=80) The default BLKSIZE specification in REDUCE is 80, so that the files TRAC and OUT discussed above would have that form. However, the user can change that parameter by changing the value of the identifier BLKSIZE*. This change must of course be made before referencing the file. For example, to input a file INP in WYLBUR CARD format one would say, in REDUCE, BLKSIZE!* := 3520; IN INP; B-4 B.2.2 ERROR RECOVERY If an error occurs in a REDUCE calculation, the program immediately returns control to the OS supervisor after printing some diagnostic information. It is unfortunately not possible at present to continue a REDUCE job step after such an error has occurred. B.2.3 Additional Error Messages Possible in REDUCE/360 In addition to the error messages listed in Appendix A it is possible for users to get error messages direct from LISP. The following LISP messages can be expected from time to time: STORAGE FULL This means that your problem is too large as stated for your current core partition. The only possible solutions are to run the job in a larger core partition or restate your problem so that less intermediate storage is required. PUSH DOWN OVERF This means either that you have defined a recursive substitution (see Section 2.15) or that your problem is so complicated that it exceeds the stack capacity of your system. If you are sure that you haven't done anything wrong, see a system expert about building a system with more stack capacity. The following messages should NOT occur under normal circumstances. If they or any other strange errors occur, PLEASE SEND A COPY OF THE OUTPUT AND A LISTING OF THE INPUT PROGRAM TO THE AUTHOR. PSW TRAP OVER OR UNDERFLOW FUNCTION NOT DEFINED C-1 APPENDIX C CALCULATIONS IN HIGH ENERGY PHYSICS NOTATION: In order to allow for the printing of this Manual on printers with limited character sets, we represent Greek characters in this Appendix by their (upper case) English names. 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 calculations. C.2.1 . The . operator is a binary operator used in algebraic mode to denote the scalar product of two Lorentz 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[8]. 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. Thus INDEX U; declares U as an index, and the simplification of (P.U) * (Q.U) would result in (P.Q) C-2 The metric tensor g may be represented by (U.V). If uv 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. Thus 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. Thus 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 GAMMA5. Thus G(L,A) = GAMMA5 associated with line L. G(L,P,A) = GAMMA.P*GAMMA5 associated with line L. GAMMA (associated with line L) may be written as G(L,U), with U U flagged as an index if contraction over u is required. The notation of Bjorken and Drell [8] is assumed in all operations involving gamma matrices. C-3 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. Thus EPS = ( +1 if I,J,K,L is an even permutation of 0,1,2,3 IJKL ( -1 if an odd permutation ( 0 otherwise A contraction of the form EPS p q may be written as EPS(I,J,P,Q), IJuv u v with I and J 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 C.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 declarations. 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. Examples: Assuming P and Q have been declared vectors, the following are vector expressions C-4 P P-2*Q/3 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 [9] for contracting indices in products of traces, REDUCE uses the elegant algorithm of Kahane [10] 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 gamma matrix terms involving the line numbers L1 and L2. A trace of a gamma matrix expression involving a line identifier which has been declared NOSPUR may be later taken by making the declaration SPUR. C-5 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 [8], Eqs. (7.72) through (7.74). We wish to compute 2 2 PF+m E'EKI EE'KF PI+m KIEE' KFE'E ALPHA /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 e and e' and laboratory energies k and k' respectively) and pi,pf are incident and final electron four-momenta. Upper case momenta in the above formula are used to indicate contractions of the momenta with gamma matrices. For example, PF = GAMMA . pf. Omitting the factor ALPHA**2/(2*m**2)*(k'/k)**2 we need to find C-6 E'EKI EE'KF KIEE' KFE'E 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: ON DIV; COMMENT THIS GIVES US OUTPUT IN SAME FORM AS BJORKEN AND DRELL; MASS KI= 0, KF= 0, PI= M, PF= M; VECTOR E; COMMENT IF E IS USED AS A VECTOR, IT LOSES ITS SCALAR IDENTITY AS THE BASE OF NATURAL LOGARITHMS; MSHELL KI,KF,PI,PF; 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=-1; FOR ALL P LET GP(P)= G(L,P)+M; COMMENT THIS IS JUST TO SAVE US A LOT OF WRITING; 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)) $ WRITE "THE COMPTON CROSS-SECTION IS ",!*ANS; 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 R-1 REFERENCES [1] Sconzo, P., LeSchack, A. R., and Tobey, R., Symbolic Computation of f and g Series by Computer. Astronomical Journal 70 (May 1965). [2] 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) [3] 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. [4] 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) [5] 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 [6] Weissman, Clark, LISP 1.5 Primer, Dickenson, 1967 [7] Hearn, A. C., Standard LISP, Stanford Artificial Intelligence Project Memo AI-90 (May 1969) [8] Bjorken, J. D. and Drell, S. D., Relativistic Quantum Mechanics (McGraw-Hill, New York, 1965). [9] Chisholm, J. S. R., Il Nuovo Cimento X, 3