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

STANFORD ARTIFICIAL INTELLIGENCE PROJECT October 1970 MEMO AIM-133 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 *This research was sponsored by the Advanced Research Projects Agency of the Department of Defense under Contract No. F30602-70-C-0300 at the University of Utah, and under Contract No. SD-183 at Stanford University. 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 rational functions of polynomials, 2) symbolic differentiation of rational functions of polynomials and general functions, 3) substitutions and pattern matching in a wide variety of forms, 4) calculation of the greatest common divisor of two polynomials, 5) automatic and user controlled simplification of expressions, 6) calculations with symbolic matrices, 8) a complete language for symbolic calculations, in which the REDUCE program itself is written, 9) calculations of interest to high energy physicists including spin 1/2 and spin 1 algebra, 10) tensor operations. %TOP,,,,i TABLE OF CONTENTS 1. INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . 1-1 2. STRUCTURE OF PROGRAMS. . . . . . . . . . . . . . . . . . . . . . 2-1 2.1 Preliminary . . . . . . . . . . . . . . . . . . . . . . 2-1 2.2 Numbers . . . . . . . . . . . . . . . . . . . . . . . . 2-1 2.3 Identifiers . . . . . . . . . . . . . . . . . . . . . . 2-2 2.4 Variables . . . . . . . . . . . . . . . . . . . . . . . 2-2 2.4.1 Reserved Variables. . . . . . . . . . . . . . . . . . 2-2 2.5 Operators . . . . . . . . . . . . . . . . . . . . . . . 2-3 2.5.1 DF. . . . . . . . . . . . . . . . . . . . . . . . . . 2-6 2.5.2 COS. LOG. SIN . . . . . . . . . . . . . . . . . . . . 2-7 2.5.3 SUB . . . . . . . . . . . . . . . . . . . . . . . . . 2-7 2.6 Strings . . . . . . . . . . . . . . . . . . . . . . . . 2-8 2.7 Comments . . . . . . . . . . . . . . . . . . . . . . . 2-8 2.8 Expressions . . . . . . . . . . . . . . . . . . . . . . 2-8 2.8.1 Numerical Expressions . . . . . . . . . . . . . . . . 2-9 2.8.2 Scalar Expressions . . . . . . . . . . . . . . . . . . 2-9 2.8.3 Boolean Expressions . . . . . . . . . . . . . . . . . 2-9 2.8.4 Equations . . . . . . . . . . . . . . . . . . . . . .2-10 2.9 Reserved Words . . . . . . . . . . . . . . . . . . . .2-10 2.10 Statements . . . . . . . . . . . . . . . . . . . . . .2-10 2.10.1 Assignment Statements. . . . . . . . . . . . . . . .2-11 2.10.2 Conditional Statements . . . . . . . . . . . . . . .2-12 2.10.3 FOR Statements . . . . . . . . . . . . . . . . . . .2-12 2.10.4 GO TO Statements . . . . . . . . . . . . . . . . . .2-14 2.10.5 Compound Statements. . . . . . . . . . . . . . . . .2-15 2.10.6 RETURN Statements. . . . . . . . . . . . . . . . . .2-15 2.11 Declarations . . . . . . . . . . . . . . . . . . . . .2-16 2.11.1 Variable Type Declarations . . . . . . . . . . . . .2-16 2.11.2 Array Declarations . . . . . . . . . . . . . . . . .2-17 2.11.3 Mode Handling Declarations . . . . . . . . . . . . .2-17 2.12 Commands . . . . . . . . . . . . . . . . . . . . . . .2-17 2.13 File Handling Commands . . . . . . . . . . . . . . . .2-18 2.13.1 IN . . . . . . . . . . . . . . . . . . . . . . . . .2-18 2.13.2 OUT. . . . . . . . . . . . . . . . . . . . . . . . .2-18 2.13.3 SHUT . . . . . . . . . . . . . . . . . . . . . . . .2-19 2.14 Substitution Commands. . . . . . . . . . . . . . . . .2-19 2.15 Removing Assignments and Substitution Rules from Expressions. . . . . . . . . . . . . . . . . . . . .2-22 2.16 Adding Rules for Differentiation of User-defined Operators. . . . . . . . . . . . . . . . . . . . . .2-22 2.17 Procedures . . . . . . . . . . . . . . . . . . . . . .2-23 2.18 Commands Used in Interactive Systems . . . . . . . . 2-25 2.19 END. . . . . . . . . . . . . . . . . . . . . . . . . 2-26 3. MANIPULATION OF ALGEBRAIC EXPRESSIONS. . . . . . . . . . . . . . 3-1 3.1 The Expression Workspace . . . . . . . . . . . . . . . 3-1 3.2 Output of Expressions . . . . . . . . . . . . . . . . . 3-2 3.2.1 ORDER . . . . . . . . . . . . . . . . . . . . . . . . 3-3 3.2.2 FACTOR . . . . . . . . . . . . . . . . . . . . . . . 3-3 3.2.3 Output Control Flags . . . . . . . . . . . . . . . . 3-4 3.2.4 Output of Strings . . . . . . . . . . . . . . . . . . 3-7 3.2.5 Suppression of Zeros . . . . . . . . . . . . . . . . 3-8 3.3 User Control of the Evaluation Process. . . . . . . . . 3-8 3.4 Cancellation of Common Factors. . . . . . . . . . . . . 3-9 3.5 Numerical Evaluation of Expressions . . . . . . . . . . 3-9 3.6 Saving Expressions for Later Use as Input . . . . . . .3-12 3.7 Partitioning Expressions . . . . . . . . . . . . . . .3-12 4. MATRIX CALCULATIONS. . . . . . . . . . . . . . . . . . . . . . . 4-1 4.1 Preliminary . . . . . . . . . . . . . . . . . . . . . . 4-1 4.2 MAT . . . . . . . . . . . . . . . . . . . . . . . . . . 4-1 4.3 Matrix Variables. . . . . . . . . . . . . . . . . . . . 4-1 4.4 Matrix Expressions. . . . . . . . . . . . . . . . . . . 4-2 4.5 Operators with Matrix Arguments . . . . . . . . . . . . 4-3 4.5.1 DET . . . . . . . . . . . . . . . . . . . . . . . . . 4-3 4.5.2 TRACE . . . . . . . . . . . . . . . . . . . . . . . . 4-3 4.6 Matrix Assignments. . . . . . . . . . . . . . . . . . . 4-4 4.7 Evaluating Matrix Elements. . . . . . . . . . . . . . . 4-4 5. ADVANCED COMMANDS. . . . . . . . . . . . . . . . . . . . . . . . 5-1 5.1 Kernels . . . . . . . . . . . . . . . . . . . . . . . . 5-1 5.2 Substitutions for General Expressions . . . . . . . . . 5-2 5.3 Asymptotic Commands . . . . . . . . . . . . . . . . . . 5-5 6. SYMBOLIC MODE . . . . . . . . . . . . . . . . . . . . . . . . . 6-1 6.1 Preliminary . . . . . . . . . . . . . . . . . . . . . . 6-1 6.2 General Identifiers . . . . . . . . . . . . . . . . . . 6-2 6.3 Symbolic Infix Operators. . . . . . . . . . . . . . . . 6-2 6.4 Symbolic Expressions. . . . . . . . . . . . . . . . . . 6-3 6.5 Quoted Expressions. . . . . . . . . . . . . . . . . . . 6-3 6.6 LAMBDA Expressions. . . . . . . . . . . . . . . . . . . 6-4 6.7 Symbolic Assignment Statements. . . . . . . . . . . . . 6-4 6.8 Communication with Algebraic Mode. . . . . . . . . . . . 6-6 APPENDIX A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A-1 A.1 Reserved Identifiers. . . . . . . . . . . . . . . . . . A-1 A.2 Commands Normally Available in REDUCE . . . . . . . . . A-2 A.3 Mode Flags in REDUCE. . . . . . . . . . . . . . . . . . A-5 A.4 Diagnostic and Error Messages in REDUCE . . . . . . . . A-6 A.4.1 Error Messages. . . . . . . . . . . . . . . . . . . . A-6 A.4.2 Diagnostic Messages . . . . . . . . . . . . . . . . . A-8 APPENDIX B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B-1 B.1 Running REDUCE on the Stanford PDP-10 . . . . . . . . . B-1 B.2 Running REDUCE on the Stanford IBM 360/67 . . . . . . . B-5 APPENDIX C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C-1 Calculations in High Energy Physics . . . . . . . . . . . . . . C-1 C.1 Preliminary . . . . . . . . . . . . . . . . . . . . . . C-1 C.2 Operators Used in High Energy Physics Calculations. . . C-1 C.2.1 . . . . . . . . . . . . . . . . . . . . . . . . . C-1 C.2.2 G . . . . . . . . . . . . . . . . . . . . . . . . . . C-2 C.2.3 EPS . . . . . . . . . . . . . . . . . . . . . . . . . C-3 C.3 Vector Variables. . . . . . . . . . . . . . . . . . . . C-4 C.4 Additional Expression Types . . . . . . . . . . . . . . C-4 C.4.1 Vector Expressions. . . . . . . . . . . . . . . . . . C-4 C.4.2 Dirac Expressions . . . . . . . . . . . . . . . . . . C-5 C.5 Trace Calculations . . . . . . . . . . . . . . . . . . C-5 C.6 Mass Declarations . . . . . . . . . . . . . . . . . . . C-7 C.7 Example . . . . . . . . . . . . . . . . . . . . . . . . C-7 REFERENCES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . R-1 %TOP,,,,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 rational functions of polynomials, 2) symbolic differentiation of rational functions of polynomials and general functions, 3) substitutions and pattern matching in a wide variety of forms, 4) calculation of the greatest common divisor of two polynomials, 5) automatic and user controlled simplification of expressions, 6) calculations with symbolic matrices, 8) a complete language for symbolic calculations, in which the REDUCE program itself is written, 9) calculations of interest to high energy physicists including spin 1/2 and spin 1 algebra, 10) tensor operations. There are several levels at which REDUCE may be used and understood. The beginning user can acquire an operating knowledge of the system by studying Section 2 of this manual, which contains details of the basic structure of programs. Having mastered this, he should then study Section 3, which describes the facilities available for manipulating algebraic expressions. A more advanced user must understand Sections 4 and 5, which describe the matrix handling routines and some advanced commands. Finally, to become a complete expert, the user will have to learn LISP 1.5 and study the material on the symbolic mode of operation in Section 6. Additional material of interest may be found in the Appendices. Appendix A gives the user a useful summary of the system commands and other properties of the system. Appendix B gives instructions for using REDUCE at various computer installations. This information may of course need modification for your computer. Finally, Appendix C contains details of the high energy physics commands for those interested. The author would appreciate hearing from any users who experience trouble with the system (please include copies of relevant input and output). Acknowledgment of the use of REDUCE in any published calculations would also be appreciated. The author would also be grateful for a copy of any such publication. %TOP,,,,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 composed from declarations, statements and expressions, which in turn are sequences of numbers, variables, operators, strings, reserved words and delimiters (such as commas and parentheses). 2.2 Numbers Numbers in REDUCE may be of two types; integer and real. Integers consist of a signed or unsigned sequence of decimal digits written without a decimal point. e. g. -2, 5396, +32 There is no practical limit on the number of digits permitted as arbitrary precision arithmetic is used. Real numbers may be written in two ways; i) as a signed or unsigned sequence of 1-9 decimal digits with an embedded decimal point. ii) as in 1) followed by a decimal exponent which is written as the letter E followed by a signed or unsigned integer. e. g. 32. +32.0 0.32E2 and 320.E-1 are all representations of 32. Restriction: The unsigned part of any number may NOT begin with a decimal point. i. e. NOT ALLOWED .5 -.23 +.12 2.3 Identifiers Identifiers in REDUCE consist of one to twenty-four alphanumeric characters (i.e. upper case alphabetic letters or decimal digits) the first of which must be alphabetic. 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.9) may not be used as identifiers. No spaces may appear within an identifier, and an identifier may not extend over a line of text. 2.4 Variables Variables are a particular type of identifier, and are specified by name and type. Their names must be allowed identifiers. There are several variable types allowed, and these are discussed later, beginning in Section 2.11.1. 2.4.1 Reserved Variables Several variables in REDUCE have a particular value which cannot easily be changed by the user. These variables are as 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.5 Operators Operators in REDUCE are also specified by name and type. There are two types, infix and prefix. Infix operators occur between their arguments. e. g. A + B - C B↑2/3-U The following infix operators are built into the system. <infix operator> ::= ←|∧|∨|¬|=|≠|>=|>|<=|<|+|-|*|/|↑ For compatibility with the intermediate language used by REDUCE, each infix operator has an alphanumeric identifier associated with it. These identifiers may be used interchangably with the corresponding infix character(s) on input. This correspondence is as follows: ← SETQ ∧ AND ∨ OR ¬ NOT = EQUAL ≠ UNEQ >= GREATEQ > GREATERP <= LESSEQ < LESSP + PLUS - MINUS * TIMES / QUOTIENT ↑ EXPT In systems which do not have all these characters, the alphanumeric name may be used instead. In addition, the following alternative forms are allowed operator alternative ↑ ** ← := These operators may be further divided into the following sub classes <logical operator> ::= ∧|∨|¬ <relational operator> ::= =|≠|>=|>|<=|< <arithmetic operator> ::= +|-|*|/|↑ The above operators may take any number of arguments, except - which is unary, and ↑ and / which are binary. The expression A-B is interpreted as A+-B on input. Furthermore, A↑B↑C↑D is interpreted as A↑(B↑(C↑D)) and similarly with /. Parentheses may be used to specify the order of combination. If parentheses are omitted then this order is by the precedence ordering given by the above list (from outermost to innermost operations). The user may add new single character infix operators to the system by the declaration INFIX. e. g. INFIX ∀,∃; adds infix operators ∀ and ∃ to the system. These new operators will be given a precedence lower than any existing infix operator except ← (which always has the lowest precedence) and will be ordered among themselves by their order at definition. Thus ∀ has a higher precedence than ∃. Restriction: The infix characters λ, !, ε, ≡ and . have reserved uses in REDUCE and cannot be declared as infix operators by the user. The precedence of any infix operator except ← may be changed by the declaration PRECEDENCE. e. g. PRECEDENCE ∀,=; gives ∀ a new precedence immediately higher than the current precedence of =. Prefix operators occur at the head of their arguments, which are written as a list enclosed in parentheses and separated by commas, as with normal mathematical functions. e. g. COS(U) DF(X↑2,X) Parentheses may be omitted if the operator is unary. e. g. COS Y and COS (Y) are equivalent. Such unary operators have a precedence higher than any infix operator. Infix operators may also be used in a prefix format on input. On output, however, they will always be printed in an infix form. Some prefix operators are also built into the system. These are as follows: 2.5.1 DF The operator DF is used to represent partial differentiation with respect to one or more variables. The first argument is the scalar expression to be differentiated. The remaining arguments specify the differentiation variables and the number of times they are applied by the following syntax: DF(<expression>,<variable>,<number>,...,<variable>,<number>) The <number> may be omitted if it is 1. e. g. DF(Y,X) ≡ ∂Y/∂X 2 2 DF(Y,X,2) ≡ ∂ Y/∂X 5 2 2 DF(Y,X1,2,X2,X3,2) ≡ ∂ Y/∂X1 ∂X2∂X3 2.5.2 COS, LOG, SIN These elementary functions are included in the system with the following properties: COS (-X) = COS (X) SIN (-X) = - SIN (X) COS (O) = 1 SIN (O) = 0 LOG (E) = 1 LOG (1) = 0 The user can add further rules for the reduction of expressions involving these operators by the methods described in Sections 2.14 and 5.2. 2.5.3 SUB This operator is described in Section 2.14. The user may add new prefix operators to the system by the declaration OPERATOR. e. g. OPERATOR H, G1, ARCTAN; adds the prefix operators H, G1 and ARCTAN to the system. 2.6 Strings Strings are used only in output statements. A string consists of any number of characters enclosed in double quotes. e. g. "A STRING". 2.7 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; In addition, the sequence of symbols END <any sequence of symbols not including a terminator or the reserved words END, ELSE or UNTIL> is equivalent to the reserved word END. 2.8 Expressions REDUCE expressions may be of several types and consist of syntactically allowed sequences of numbers, variables, operators, left and right parentheses and commas. The most common types are as follows: 2.8.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.8.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.8.3 Boolean Expressions These are expressions which return a truth value. In REDUCE, the reserved word NIL represent the truth value `false'. Any other expression represents `true'. So in a sense, any expression is a boolean expression, because all expressions return a value. However, a proper boolean expression has the syntactical form: <expression> <relational operator> <expression> or <boolean expression> <logical operator> <boolean expression> They are used mainly in the IF and FOR statements described in Sections 2.10.2 and 2.10.3. Examples: J<1 X > 0 ∨ X = -2 2.8.4 Equations In the remainder of this manual, we shall refer to the expression <scalar expression> = <scalar expression> as an equation. 2.9 Reserved Words Certain words are reserved in REDUCE. They may only be used in the manner described in this manual. These words are as follows: <reserved word> ::= BEGIN|DO|ELSE|END|FOR|FUNCTION|IF|LAMBDA|NIL| PRODUCT|RETURN|STEP|SUM|UNTIL|WHILE 2.10 Statements A statement is any allowed combination of reserved words and expressions, and has the syntax <statement> ::= <expression>|<proper statement> The following sub-sections describe some proper statements in REDUCE. 2.10.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.14 and 5.2). In many cases, this is all that the user needs. needs. However, the user can exercise some control over the way in which the evaluation is performed by various declarations available to him. These declarations are explained in Section 3.3. If a real (floating point) number is encountered during evaluation, the system will normally convert it into a ratio of two integers, and print a message informing the user of the conversion. If the user wants to use real arithmetic, he can inhibit this conversion by the command ON FLOAT;. This use of the ON declaration is explained in Section 2.11.3. The results of the evaluation of an expression are printed if a semicolon is used as a delimiter. Because it is not usually possible to know in advance how large an expression will be, no explicit format statements are offered to the user. However, a variety of output declarations are available so that the output can be produced in a variety of forms. These output declarations are explained in Section 3.4. It is also possible to write an assignment in the form <expression> ← <expression> ← ... ← <expression> ← <statement> In this form, each <expression> is set to the value of the <statement>. 2.10.2 Conditional Statements The conditional statement has the following syntax: <conditional statement> ::= IF <boolean expression> THEN <statement> ELSE <statement> Its use is obvious. The ELSE clause is optional. 2.10.3 FOR Statements The FOR statement is used to define a variety of program loops. Its general syntax is as follows: FOR <variable>←<arithmetic expression> STEP <arithmetic expression> {DO <statement> {UNTIL <arithmetic expression>} { { } {SUM <algebraic expression> {WHILE <boolean expression> } { {PRODUCT <algebraic expression> The DO version of the FOR statement is the normal ALGOL useage, and is similar to the FORTRAN DO statement. It does not return an algebraic value. The SUM and PRODUCT versions respectively form the sum and product of the relevant algebraic expression over the defined range. They return the value of the computed sum or product. Note, however, that this value is NOT printed. It will be printed, however, if the statement is assigned as the value of an expression and a semicolon used as a terminator. The <variable> within the FOR statement is declared INTEGER if it is not already. Its value during the calculation of the statement is independent of its value outside, so that I can be used in this context, even though I normally stands for the square root of -1. Examples: We assume that the declaration ARRAY A(10); has been made in the following examples. This declaration is explained in Section 2.11.2. (i) To set each element A(I) of the array to X↑I we could write 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$ (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; As explained above, the result is not printed in this case. However, it is held in the expression workspace (see Section 3.1) and can be retrieved from there if required. (iii) To set X to the factorial of 10 we could write X ← FOR I←1:10 PRODUCT I; Alternatively, we could set the element A(I) to I! by the statements A(0)← 1$ FOR I←1:10 DO A(I)←I*A(I-1)$ 2.10.4 GO TO Statements GO TO (or GOTO) statements are used to perform an unconditional transfer to a label in a compound statement (Section 2.10.5). They have the syntax: <go to statement> ::= GO TO <label> <label> ::= <variable> Restriction: GO TO statements may only occur within a compound statement. They may NOT occur at the top level of your program. 2.10.5 Compound Statements A compound statement is defined by the following syntax <compound statement> ::= BEGIN <compound tail> <compound tail> ::= <unlabeled compound tail> |<label>:<compound tail> <unlabeled compound tail> ::= <statement> END | <statement> <terminator> <compound tail> <label> ::= <identifier> <terminator> ::= ;|$ e. g. X ← BEGIN INTEGER M; 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.10.6 RETURN Statements The RETURN statement allows for a transfer out of a compound statement to the next highest program level. It may be used alone, in which case the statement returns NIL. e. g., RETURN (X+Y); RETURN M; RETURN; Restriction: RETURN statements may only occur within a compound statement.They may NOT occur at the top level of your program. 2.11 Declarations Declarations are a particular type of statement used to set flags, make type declarations and define procedures. PROCEDURE declarations are discussed in Section 2.17. Some other REDUCE declarations are described in the following sub-sections. 2.11.1 Variable Type Declarations These declarations tell the system how various identifiers are to be processed. Types allowed include INTEGER, REAL and SCALAR. e. g. INTEGER M,N; REAL M1; 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. 2.11.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) Array elements may appear in the left side of assignment statements as in the examples in Section 2.10.3. 2.11.3 Mode Handling Declarations Two declarations are offered to the user for turning on or off a variety of flags in the system. The declarations ON and OFF take a list of flag names as argument and turn them on and off 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.12 Commands A command is an order to the system to do something. It has the syntax <command> ::= <statement><terminator>|<proper command> <proper command> ::= <command name><space> <statement>,...,<statement><terminator> A variety of commands are discussed in the sections which follow. 2.13 File Handling Commands In many applications, it is desirable to load previously prepared REDUCE files into the system, or to write output on varying devices. REDUCE offers three commands for this purpose, namely, IN, OUT, and SHUT. 2.13.1 IN This command takes a list of file names as argument and directs the system to input each file (which should contain REDUCE commands) into the system. A file name will have a varying syntax from implementation to implementation, but in many cases will be an 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.13.2 OUT This command takes a single file name as argument, and directs output to that file from then on. If the file has previously been used for output during the current job, the output is appended to the end of the file. An existing file is erased before its first use for output in a job. To output on the terminal without closing the output file, the reserved file name T (for terminal) may be used. e. g. OUT OFILE; will direct output to the file OFILE and OUT T; will direct output the user's terminal. 2.13.3 SHUT This command is used to close an output file at completion. Most systems require this action by the user, otherwise output may be lost. If a file is shut and a further OUT command issued for the same file, the file is erased before the new output is written. 2.14 Substitution Commands An important class of commands in REDUCE is that class which defines substitutions for variables and expressions to be made during the evaluation of expressions. Such substitutions may be declared globally by the command LET and locally by use of the operator SUB. LET is used in the form LET <substitution list>; where <substitution list> is a list of equations of the form: <variable> = <expression> or <prefix operator> (<argument>,...,<argument>) = <expression> or <argument> <infix operator>,..., <argument> = <expression> e. g. LET X = Y↑2 + 2, H(X,Y) = X - Y, COS(60) = 1/2, Y↑3 = 2*Z - 3; These substitutions will now be made for all such variables and expressions appearing in evaluations. Any operators occuring in such equations will be automatically declared OPERATOR by the system. In each of these examples, substitutions are only made for the explicit expressions given; i.e., none of the variables may be considered arbitrary in any sense. For example, the command LET H(X,Y) = X - Y; will replace H(X,Y) by X - Y, but not H(X,Z) or any other function of H. If a substitution for all possible values of a given argument of an operator is required, the declaration FOR ALL (or FORALL) may be used. The syntax of such a command is FOR ALL <variable>,...,<variable> <LET command><terminator> e. g. FOR ALL X,Y LET H(X,Y) = X-Y; FOR ALL X LET K(X,Y) = X↑Y; If the left hand side of an equation is redefined by a later call of LET, the previous expression is replaced by the new one, and a diagnostic message printed to inform the user. Such messages may be inhibited by turning off the flag MSG. In applying any substitutions set up by LET, the system searches the substitution expression itself for any expressions which may themselves have substitutions declared for them. Thus LET sets up an equivalence between the left hand side of the substitution and the right hand side rather than an assignment as made by an assignment statement. In other words, a substitution such as LET X = X + 1; is not allowed, since in substituting for X, the system will find that the variable X in the substitution expression itself has a substitution and a push-down-list overflow error will ultimately result. Similarly, a pair of substitutions LET L = M + N, N = L + R; are not allowed. On the other hand, if the user wishes simply to replace every occurrence of a variable by any expression without checking that expression again for further substitutions, the operator SUB may be used. Its general form is SUB (<substitution list>,<expression>) as in SUB(X=X+1, Y=1, X**2+Y**2) This substitution is made by first simplifying the <expression>, then replacing any variables occurring on the substitution list, and finally resimplifying the result. Thus, in the above example, the result would be X**2+2*X+2 2.15 Removing Assignments and Substitution Rules from Expressions The user may remove all assignments and substitution rules from any expression by the command CLEAR, in the form CLEAR <expression>,...,<expression><terminator> e. g. CLEAR X, H(X,Y); A whole array, such as A in Section 2.11.2, can be cleared by the command CLEAR A; An individual element of A can also be cleared by a command such as CLEAR A(3); 2.16 Adding Rules for Differentiation of User-defined Operators An extension of the syntax of LET arguments allows for the introduction of rules for differentiation of user-defined operators. Its general form is FOR ALL <var1>,...,<varn> LET DF(<operator><varlist>,<vari>)=<expression> where <varlist> ::= (<var1>,...,<varn>) and <var1>,...,<vari>,...,<varn> are the dummy variable arguments of <operator>. An analogous form is allowed for 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.17 Procedures It is often useful to name a statement for repeated use in calculations with varying parameters, or to define a complete evaluation procedure for an operator. REDUCE offers a procedural declaration for this purpose. Its general syntax is: <procedural type> PROCEDURE <name><varlist>;<statement>; 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.10.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$ 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 ∂ 1 | p (x) = --- --- ------------- | n n! n 2 | ∂y 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.18 Commands Used in Interactive Systems REDUCE is designed primarily for interactive use with a time- shared computer, but naturally it can also operate in a batch processing environment. There is a basic difference, however, between interactive and batch use of the system. In the former case, whenever the system discovers an ambiguity at some point in a calculation, such as a forgotten type assignment for instance, it asks the user for the correct interpretation. In batch operation, it is not practical to terminate the calculation at such points and require resubmission of the job, so the system makes the most obvious guess of the user's intentions and continues the calculation. If input is coming from an external file, the system treats it as a batch processed calculation. If the user desires interactive response in this case, he can turn on the flag INT in the file. Likewise, he can turn off INT in the main program if he does not desire continual questioning from the system. Two commands are available in REDUCE for use in interactive computing. The command PAUSE; may be inserted at any point in an input file. When this command is encountered on input, the system prints the message CONT? on the user's terminal and halts. If the user responds Y (for yes), the calculation continues from that point in the file. On the other hand, if the user responds N (for no), control is returned to the terminal, and the user can input further commands. However, later on he can use the command CONT; and control is then transferred back to the point in the file after the last pause was encountered. 2.19 END The command END; is used to end external files which are used as input to REDUCE. One of its purposes is to turn off the command echo, which is annoying to a user typing at a terminal. However, it also does some file control book-keeping, and should therefore not be omitted. If an END command is used in the main program, control is then transferred to LISP. %TOP,,,,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, 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 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, or wishes to rename ANY identifier in the system EXCEPT reserved words, he can simply say: LET <new name> = <old name>; e. g. LET WS=!*ANS; From now on, WS is recognized as !*ANS in all input. If the user wishes to assign the workspace to a variable or expression for later use, the command SAVEAS can be used. It has the 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. 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. These 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.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. (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 2 2 2 X *(Y + 2*Y) + X*(Y + Z)/(2*A) 3.2.4 Output of Strings It is often useful to write a title or comment on output, or name output expressions in a particular way. This is possible in REDUCE by means of the command WRITE. The form of this command is WRITE <expression>,...,<expression>; where <expression> may be either an algebraic expression or a string (Section 2.6). Strings are printed on output exactly as given except for any characters which are ignored by the input scanner. Other expressions are evaluated and their value printed. The print line is closed at the end of the WRITE command 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) ... <more output> ... 3.2.5 Suppression of Zeros It is sometimes annoying to have zero assignments (i.e. assignments of the form <expression> ← 0) printed, especially in setting large arrays with many zero elements. The output from such assignments can be suppressed by turning on the flag NERO. 3.3 User Control of the Evaluation Process In addition to the wide range of output options available to the user, there are two additional flags which control the internal evaluation of expressions. The flag EXP controls expansion of expressions. If it is off no expansion of powers or products of expressions occurs. When two rational functions are added, REDUCE normally produces an expression over a common denominator. However, if the user does not want denominators combined, he can turn off the flag MCD which controls this process. EXP and MCD are normally on. 3.4 Cancellation of Common Factors Facilities are available in REDUCE for cancelling common factors in the numerators and denominators of expressions, at the option of the user. The system computes the required greatest common divisor using an algorithm due to G.E. Collins [2] and cancels this divisor from the relevant terms. This facility should only be used on small expressions as the computational time quickly becomes prohibitive for moderately large expressions in several variables. The system will perform this greatest common divisor check if the flag GCD is on. A check is automatically made, however, for common variable products in the numerators and denominators of expressions, and the appropriate cancellations made. 3.5 Numerical Evaluation of Expressions It is naturally possible to evaluate expressions numerically in REDUCE by giving all variables and sub-expressions numerical values. However, as we pointed out in Section 2.10.1 the user must declare real arithmetical operation by turning on the flag FLOAT. Furthermore, there are no routines for evaluation of the elementary functions COS,SIN etc for arbitrary numerical argument. Finally, arithmetic in REDUCE is not particularly fast. The user with a large amount of numerical computation after all necessary algebraic manipulations have been performed is therefore well advised to perform these calculations in a FORTRAN or similar system. For this purpose, REDUCE offers facilities for users to produce FORTRAN compatible files for numerical processing. First, when the flag FORT is on, the system will print expressions in a FORTRAN notation. Expressions begin in column 7. If an expression extends over one line, a continuation mark (X) appears on subsequent cards. After 19 continuation lines are produced, a new expression is started. If the expression printed arises from an assignment to a variable, the variable is printed as the name of the expression. Otherwise the expression is named ANS. Secondly, the WRITE command can be used to produce other programs. 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 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.13. However, we see in the examples in Section 3.2 that the standard `natural' method of printing expressions in not compatible with the input syntax. So to print the expression in an input compatible form we must inhibit this natural style by turning off the flag NAT. If this is done, a dollar sign will also be printed at the end of the 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 $ END; 3.7 Partitioning Expressions It is often necessary to get at parts of an expression during a calculation. REDUCE provides four commands for this purpose, each of which apply to the current expression in the work space. These have proved adequate for all calculations brought to the author's attention, but other commands could be added if there is sufficient demand. (1) MKCOEFF is a command which assigns coefficients of the various powers of a variable. It has the syntax: MKCOEFF <variable>,<identifier>; If the <identifier> has been previously declared a single dimensioned array, the Ith array element is assigned to the coefficient (zero or non zero) of the Ith power of <variable> in the expression. This assignment begins at the maximum power of the variable, and a message is printed to inform the user of that power. If the <identifier> is not an array name, a variable with name <identifier><power> is assigned to the coefficient of that power. Only NON ZERO powers are set in this manner, and a message is printed to inform the user of the variables set. Example: Suppose we evaluate the expression (Y↑2+Z)↑3, so that the workspace holds the expression Y↑6 + 3*Y↑4*Z + 3*Y↑2*Z↑2 + Z↑3 If we now say ARRAY X(7); MKCOEFF Y,X; then a message HIGHEST POWER IS 6 will be printed and X(6) set to 1, X(5) to 0, X(4) to 3*Z and so on until X(0), which is set to Z↑3. X(7) will not be set. On the other hand, if we said MKCOEFF Y,W; we would get a message W6 W4 W2 W0 ARE NON ZERO and W6 set to 1, W4 to 3*Z and so on. (2) NUMER and DENOM are commands which have a single variable argument and which respectively assign the numerator and denominator of the workspace to their argument. e. g., with X/Y↑2 in the workspace, NUMER V; will set V to X, and DENOM W; will set W to Y↑2. (3) ND, finally, takes two variables as argument, and assigns the numerator of the workspace to the first, and the denominator to the second. e. g., we could achieve the assignments in (2) with the single command ND V,W; %TOP,,,,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. Matrices are stored as arrays in REDUCE. The size of the matrix may be declared explicitly in the matrix declaration, or by default in assigning such a variable to a matrix expression. e. g. MATRIX X(2),Y(3,4),Z; declares X to be a 2 x 1 (column) matrix, Y to be a 3 x 4 matrix and Z a matrix whose size is declared later by default. 4.4 Matrix Expressions These follow the normal rules of matrix algebra as defined by the following syntax: <matrix expression> ::= MAT<matrix description>|<matrix variable>| <scalar expression>*<matrix expression>| <matrix expression>*<matrix expression> <matrix expression>+<matrix expression>| <matrix expression>↑<integer>| <matrix expression>/<matrix expression> Sums and products of matrix expressions must have the same size otherwise an error will result during their evaluation. Similarly, only square matrices may be raised to a power. A negative power is computed as the inverse of the matrix raised to the corresponding positive power. A/B is interpreted as AxB↑(-1). The inverse of a matrix is computed by an algorithm due to John Lipson [3]. I am indebted to Dr. Jim Griesmer for allowing me to include in REDUCE his programmed version of this algorithm. 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 Two additional operators are useful in matrix calculations, namely DET and TRACE defined as follows 4.5.1 DET The operator DET is used to represent the determinant of a square matrix expression. e.g. DET(Y↑2) is a scalar expression whose value is the determinant of the square of the matrix Y. The particular construction DET(MAT <matrix description>) max be abbreviated to DET<matrix description> For example, the determinant | A B C | | | | D E F | | | | G H J | could be written DET((A,B,C),(D,E,F),(G,H,J)); 4.5.2 TRACE The operator TRACE is used to represent the trace of a square matrix. Its use is obvious. 4.6 Matrix Assignments Matrix expressions may appear in the right hand side of assignment statements. If the left hand side of the assignment, which must be a variable, has not already been declared a matrix, it is declared by default to the size of the right hand side. The variable is then set to the value of the right hand side. Such an assignment may be used very conveniently to find the solution of a set of linear equations. For example, to find the solution of the following set of equations A11*X(1) + A12*X(2) = Y1 A21*X(1) + A22*X(2) = Y2 we simply write X ← 1/MAT((A11,A12),(A21,A22))*MAT((Y1),(Y2)); 4.7 Evaluating Matrix Elements Once an element of a matrix has been assigned, it may be referred to in standard array element notation. Thus Y(2,1) refers to the element in the second row and first column of the matrix Y. %TOP,,,,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 [4]. The evaluation function may transform its arguments in one of two alternative ways. First, it may convert the expression into other operators in the system, leaving no functions of the original operator for further manipulation. This is in a sense true of the evaluation functions associated with the operators +, * and / , for example, because the canonical form does not include these operators explicitly. It is also true of an operator such as the determinant operator DET discussed in Section 4.5.1, because the relevant evaluation function calculates the appropriate determinant, and the operator DET no longer appears. On the other hand, the evaluation process may leave some residual functions of the relevant operator. For example, with the operator COS, a residual expression like COS(X) may remain after evaluation unless a rule for the reduction of cosines into exponentials, for example, were introduced. These residual functions of an operator are termed kernels and are stored uniquely like variables. Subsequently, the kernel is carried through the calculation as a variable unless transformations are introduced for the operator at a later stage. In cases where the arguments of the kernel operators may be reordered, the system puts them in a canonical order, based on an internal intrinsic ordering of the variables. However, some commands allow arguments in the form of kernels, and the user has no way of telling what internal order the system will assign to these arguments. To resolve this difficulty, we introduce the notion of a kernel form as an expression which transforms to a kernel on evaluation. Examples of kernel forms are: A COS (X*Y) LOG (SIN (X)) 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 [5] and [6], REDUCE does not attempt to implement a general pattern matching algorithm. However, the present system uses more sophisticated techniques than those discussed in reference [6]. It is now possible for the equations appearing in arguments of LET to have the form <substitution expression> = <expression> where <substitution expression> is ANY expression, subject to the following restrictions: (i) The operators +, - and / cannot appear at the top level in a substitution expression. This restriction is currently under study to see if it can be removed. e. g. LET COS(X)↑2 + SIN(X)↑2 = 1; is NOT allowed. (ii) The operators + and * can only be used in binary form within substitution expressions. e. g. LET SIN (X + Y) = SIN(X)*COS(Y) + COS(X)*SIN(Y); is allowed but a substitution for FN(X+Y+Z) would not be. The system will of course substitute for any expression containing + or * as an n-ary operator by making the appropriate expansion of the binary rule. (iii) The operator - can only be specified as a unary operator within substitution expressions. e. g. LET COS(-X)= COS(X) is allowed but LET COS(X-Y) = <expression> is not. It should be noted, however, that a rule for COS(X+Y) and one for COS(-X) is sufficient to specify the expansion of COS(X-Y). Any variables appearing in substitution expressions may be declared arbitrary by the FOR ALL construction 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 completely arbitrary variables in this syntax, we use the boolean operator ARB rather than combine the IF construction with a FOR ALL clause. e. g. IF X ≠ 0 ∧ NUMBERP N ∧ ARB Y LET F(X,Y,N)= 2*Y↑N; As before, after a substitution has been made, the expression being evaluated is reexamined in case a new allowed substitution has been generated. This process is continued until no more substitutions can be made. However, this is sometimes undesirable. For example, if one wishes to integrate a polynomial with respect to X by a rule of the form FOR ALL N LET X↑N = X↑(N+1)/(N+1); one only wants the substitution to be made once. (Otherwise X↑2 would become X↑3/3 which would then become X↑4/12 and so on). This resubstitution can be inhibited by turning off the flag RESUBS (which is normally on). When a substitution expression appears in a product, the substitution is made if that expression divides the product. For example, the rule LET A↑2*C = 3*Z; would cause A↑2*C*X to be replaced by 3*Z*X and A↑2*C↑2 by 3*Z*C. If the substitution is desired only when the substitution expression appears in a product with the explicit powers supplied in the rule, the command MATCH should be used instead. For example, MATCH A↑2*C = 3*Z; would cause A↑2*C*X to be replaced by 3*Z*X, but A↑2*C↑2 would not be replaced. MATCH can also be used with the FOR ALL or IF constructions described above. To remove substitution rules of the type discussed in this Section, the CLEAR command can be used, combined, if necessary, with a FOR ALL or IF clause. 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 equal to or greater than the weight level assigned to the calculation. If it is, the term is deleted. To compute the total weight of a product, the individual weights of each kernel form are multiplied by their corresponding powers and then added. The weight level of the system is initially set to 2. The user may change this setting, however, by the command WTLEVEL <number>; which sets <number> as the new weight level of the system. Again, <number> must be a positive integer. Restrictions: In the present system, it is not possible to differentiate with respect to a variable for which a weight has been assigned, or for such a variable to appear in a substitution expression. These restrictions could be removed if they prove too inconvenient for users. %TOP,,,,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 LISP; (or SYMBOLIC;) and to return to algebraic mode he types ALGEBRAIC;. Evaluations proceed differently in each mode so the user is advised to check what mode he is in if a puzzling error arises. He can find his mode by typing !*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 LISP <command> (or SYMBOLIC <command>) or ALGEBRAIC <command> At the end of the evaluation, you will be back in the previous mode. For example, if the current mode is ALGEBRAIC, then the commands LISP 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 [7] or Clark Weissman's LISP 1.5 Primer[8]. 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 two major differences. First, expression evaluation now becomes LISP evaluation. Secondly, assignment statements are handled differently. We shall describe this difference later. In addition, function definitions follow the conventions of Standard LISP [9]. To begin with, we mention a few extensions to our basic syntax which are designed primarily if not exclusively for symbolic mode. 6.2 General Identifiers In Section 2.3, we limited identifiers to sequences of letters and numbers. However, it is possible to input any sequence of characters in REDUCE as a name by prefixing non alphanumeric characters by the 'escape character' ! . e.g. A!(B is an allowed identifier. It will print as A(B. 6.3 Symbolic Infix Operators There are three binary infix operators in REDUCE intended for use in symbolic mode. These operators and their alphanumeric equivalents are as follows: ε MEMBER ≡ EQ . CONS The precedence of these operators is as given by the following list, from outermost to innermost operations: <infix operator> ::= ←|∧|∨|¬|ε|=|≠|≡|>=|>|<=|<|+|-|*|/|↑|. 6.4 Symbolic Expressions These consist of scalar variables and operators and follow the normal rules of the LISP meta language. Examples: X CAR U . REVERSE V SIMP (U+V↑2) 6.5 Quoted Expressions Because LISP evaluation requires that each variable or expression have a value, it is necessary to add to REDUCE the concept of a quoted expression by analogy with the LISP QUOTE function. This is provided by the single quote mark '. e. g. 'A represents the LISP S-expression (QUOTE A) '(A B C) represents the LISP S-expression (QUOTE (A B C)) Note, however, that strings are automatically quoted in symbolic mode. Thus, to print the string "A STRING", one would write PRINC "A STRING"; BEWARE!!! Within a quoted expression, normal LISP S-expression syntax rules apply. Thus the escape character ! is just another LISP character, as are the terminators ; and $. For example, 'A; represents the S-expression (QUOTE A;), so you must put a space before the semicolon if it is to act as a terminator. 6.6 LAMBDA Expressions LAMBDA expressions provide the means for constructing LISP LAMBDA expressions in symbolic mode. They may not be used in algebraic mode. 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, and λ may be used in place of the reserved word LAMBDA. LAMBDA expressions may be used in symbolic mode in place of prefix operators, or as an argument of the reserved word FUNCTION, which is used in the same way as FUNCTION in Standard LISP. 6.7 Symbolic Assignment Statements In symbolic mode, if the left side of an assignment statement is a variable, a SETQ of the right hand side to that variable occurs. If the left hand side is an expression, a function definition is assumed. e. g. X←Y translates into (SETQ X Y) whereas ASSOC(U,V) ← IF NULL V THEN NIL ELSE IF U≡ 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.17. The procedural type in this case is LISP (or SYMBOLIC). For example, the above definition of ASSOC could be written as LISP PROCEDURE ASSOC(U,V); IF NULL V THEN NIL ELSE IF U≡ 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. %TOP,,,,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 IF LAMBDA NIL PRODUCT RETURN STEP SUM UNTIL WHILE Reserved Scalar E I Variables Infix Operators ← := ∧ ∨ ¬ ε = ≠ ≡ >= > <= < + - * / ↑ ** . SETQ AND OR NOT MEMBER EQUAL UNEQ EQ GREATEQ GREATERP LESSEQ LESSP PLUS MINUS TIMES QUOTIENT EXPT CONS Prefix Operators DET DF COS EPS G LOG MAT SIN SUB TRACE Commands ALGEBRAIC ARRAY CLEAR COMMENT DENOM END FACTOR FOR FORALL GOTO IF IN INFIX INTEGER LET LISP MASS MATCH MATRIX MKCOEFF MSHELL ND NOSPUR NUMER OFF ON OPERATOR ORDER OUT PRECEDENCE PROCEDURE REAL REDUCE RETURN SAVEAS SCALAR SHUT SPUR SYMBOLIC VECTOR WEIGHT WRITE WTLEVEL A.2 Commands Normally Available In REDUCE Notation: E, E1,...,En denote expressions V,V1,...,Vn denote variables The number after the description refers to the Section in which the command is described. ALGEBRAIC E; If E is empty, the system mode is set to algebraic. Otherwise, E is evaluated in algebraic mode and the system mode is not changed (6.1) ARRAY V1<size>, Declares V1 through Vn as array names. <size> ,...,Vn<size>; describes the maximum size of the array (2.11.2) CLEAR E1,...En; Removes any substitutions declared for E1 through En from system (2.15) COMMENT <any>; Used for including comments in text. <any> is any sequence of characters not including a terminator (2.7) CONT; An interactive command which causes the system to continue the calculation from the point in the input file where the last PAUSE was encountered (2.18) DENOM V; Assigns V to denominator of the workspace (3.7) END <any>; Terminates files used for input to REDUCE. <any> is any sequence of symbols not including a terminator or the reserved words END, ELSE or UNTIL (2.19) FACTOR E1,...En; Declares expressions as factors in output (3.2.2) FOR Command used to define a variety of program loops (2.10.3) FORALL V1,...,Vn Declares variables V1 through Vn as arbitrary <command> in the substitution rules given by <command> (2.14, 2.16, 3.1 and 5.2) GOTO V; Performs an unconditional transfer to label V. Can only be used in compound statements (2.10.4) IF Used to define conditional statements (2.10.2 and 5.2) IN V1,...,Vn; Inputs the external REDUCE files V1 through Vn (2.13.1) INFIX V1,...,Vn; Declares the non-alphanumeric characters V1 through Vn as infix operators (2.5) INTEGER V1,...,Vn; Declares V1 through Vn as integer variables (2.11.1) LET E1,...,En; Declares substitutions for the left hand sides of expressions E1 through En. (2.14 and 5.2). In addition, LET can be used to input differentiation rules (2.16) LISP E; If E is empty, the system evaluation mode is set to symbolic. Otherwise, E is evaluated in symbolic mode and the system mode not changed (6.1) MATCH E1,...,En; Declares substitutions for the left hand sides of E1 through En when matching of explicit powers is required (5.2) MATRIX E1,...,En; Declares matrix variables to the system. The Ei may be matrix variable names, or include details of the size of the matrix (4.3) MKCOEFF V1,V2; Used to partition expression in the workspace. The various powers of V1 in this expression are stored in V2 (3.7) ND V1,V2; Assigns V1 to numerator of the workspace and V2 to its denominator (3.7) NUMER V; Assigns V to numerator of the workspace (3.7) OFF V1,...,Vn; Turns off the flags V1 through Vn (2.11.3) ON V1,...,Vn; Turns on the flags V1 through Vn (2.11.3) OPERATOR V1,...,Vn; Declares V1 through Vn as algebraic operators (2.5 and 6.8) ORDER V1,...,Vn; Declares an ordering for variables V1 through Vn on output (3.2.1) OUT V; Declares V as output file (2.13.2) PAUSE; An interactive command for use in an input file. When it is evaluated, control is transferred to the user's terminal (2.18) PRECEDENCE V1,V2; Gives infix operator V1 a new precedence immediately higher than the current precedence of V2 (2.5) PROCEDURE Names a statement for repeated use in calculations. Type specification of procedure precedes the command name (2.17 and 6.7) REAL V1,...,Vn; Declares variables V1 through Vn as real (2.11.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.10.6) SAVEAS E; Assigns E to the current expression in the workspace (3.1) SCALAR V1,...,Vn; Declares variables V1 through Vn as scalar (2.11.1) SHUT V; Closes the output file V (2.13.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.3 Mode Flags in REDUCE This Section lists the flags which may appear as arguments of ON and OFF. The action of the flag when it is ON is described here, unless stated otherwise. The numbers, as previously, refer to the Section in which the flag is described. ALLFAC Causes the system to factor out common products on output of expressions (3.2.3) DIV Causes the system to divide out simple factors on output, so that negative powers or rational fractions can be produced (3.2.3) ECHO Causes echoing of input (2.13.1) EXP Causes expressions to be expanded during evaluation (3.3) FLOAT Prevents conversion of floating point numbers into the ratio of two integers during evaluation (2.10.1) FORT Declares output in a FORTRAN notation (3.5) GCD Causes the system to cancel greatest common divisors in rational expressions (3.4) INT Specifies an interactive mode of operation (2.18) LIST Causes output to be listed one term to a line (3.2.3) MCD Causes denominators to be combined when expressions are added (3.3) MSG Causes diagnostic messages to be printed (2.14) NAT Specifies 'natural' style of output (3.6) NERO Inhibits printing of zero assignments (3.2.5) RAT An output flag used in conjunction with FACTOR. It causes the overall denominator in an expression to be printed with each factored sub-expression (3.2.3) RESUBS When RESUBS is OFF, the system does not reexamine an expression for further substitutions after one has been made (5.2) A.4 Diagnostic and Error Messages in REDUCE Diagnostic messages in the REDUCE system are of two types; error messages and warning messages. The former usually cause the termination of the current calculation whereas the latter warn the user of an ambiguity encountered or some action taken which may indicate an error. If the system is in an interactive state, it can ask the user when it encounters an ambiguity for the correct interpretation. Otherwise it will make the most plausible guess, print a message informing the user of the choice made, and continue. If an error is found during the parsing of the input, the current phrase is reprinted with the place marked where the error was encountered. In some systems, it is then possible to edit the line and correct the error. For completeness, again, we include messages which can occur in High Energy Physics calculations (Appendix C). A.4.1 Error Messages ARRAY TOO SMALL An array used in MKCOEFF is too small to store all powers of the expression being partitioned ASSIGNMENT <expression> An invalid assignment has been input to the NOT ALLOWED system FORMAT <expression> The format of the argument of a command is INCORRECT incorrect INCORRECT ARRAY Non-numeric index has been used with matrix ARGUMENTS FOR <name> <name> INVALID CHARACTER Invalid character found on input MATRIX MISMATCH Two matrix expressions are not correctly matched for addition or multiplication MATRIX SYNTAX A syntax error has been encountered in a matrix expression MISMATCH OF ARGUMENTS Indicates that an operator for which an evaluation procedure has been defined is called with the wrong number of arguments MISSING OPERATOR Input error MISSING VECTOR An expression encountered in a vector context does not contain a vector NON SQUARE MATRIX An invalid operation on a non square matrix has been requested (e. g., a trace) REDUNDANT OPERATOR Input error SINGULAR MATRIX System has been asked to invert a singular matrix SUB FORMAT The arguments of the operator SUB have the wrong format SYNTAX ERROR Incorrect syntax in input. This error occurs only if the system is unable to determine what causes the error TOO FEW RIGHT Input error PARENTHESES TOO MANY RIGHT Input error PARENTHESES UNMATCHED INDEX Unmatched indices have been encountered during ERROR <list> the evaluation of a vector expression VECTOR <variable> A vector variable has been used in a scalar USED AS SCALAR context ZERO DENOMINATOR An expression with a zero denominator has been encountered <operator> NOT FOUND An unknown operator appears in a PRECEDENCE declaration <variable> INVALID IN Incorrect statement syntax <statement name> STATEMENT <variable> HAS NO MASS A variable encountered in an MSHELL declaration has no mass assigned to it A.4.2 Diagnostic Messages ASSIGNMENT FOR <expression> <expression> has been reassigned to a REDEFINED new value <expression> REPRESENTED The system has represented the first BY <expression> expression by the second <expression> NOT FACTORABLE An invalid expression has been given <variable> DECLARED <type> <variable> has been declared <type> %TOP,,,,B-1 APPENDIX B B.1 RUNNING REDUCE ON THE STANFORD PDP-10 B.1.1 REDUCE is stored as a 38K system with filename REDUCE.DMP. The complete source program, written in REDUCE, is stored in the user area [1,ACH] with filename REDUCE.RED if anyone is interested in studying it. REDUCE may be loaded by typing R REDUCE. When the system returns an asterisk, you are in LISP. You can then enter REDUCE by typing (BEGIN). The system then expects REDUCE commands from you. You can return to LISP by the command END; If you require more core for your job, you can get it by typing ↑C .CORE <size required><cr> .REE<cr> You will then be back in LISP. B.1.2 Special Features B.1.2.1 If you give IN and OUT a variable or dotted pair as argument, the output goes to your disk area. In addition, the reserved identifier L is used to represent the line printer on output. i. e. OUT L; sends output to the line printer. Input from other devices may be specified by preceding the file name by the device name. For example, to input a file ANDY from disk area [S,JAM] followed by FOO from DTA2:, you would type 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.1.3 A SAMPLE PROGRAM .R REDUCE load the program *(BEGIN) enter REDUCE *COMMENT A SAMPLE PROGRAM; comments are allowed *X←(Y+Z)↑2; set X to (Y+Z)↑2 2 2 here's the result printed X := Y + 2*Y*Z + Z because we used a semicolon as a terminator *DF(X,Z,2); now differentiate X wrt Z twice 2 here's that result *PROCEDURE FAC N; now define the factorial * BEGIN INTEGER M,N; function * M←1; * 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; *LISP; 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.2 RUNNING REDUCE ON THE STANFORD CAMPUS FACILITY IBM 360/67 Instructions for running REDUCE on this machine are obtainable from the AIDS Office in Pine Hall. %TOP,,,,C-1 APPENDIX C CALCULATIONS IN HIGH ENERGY PHYSICS 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 Loretz four-vectors. In the present system, the index handling routines all assume that Lorentz four-vectors are used, but these routines could be rewritten to handle other cases. Components of vectors can be represented by including representations of unit vectors in the system. Thus if EO represents the unit vector (1,0,0,0), (P.EO) represents the zeroth component of the four-vector P. Our metric and notation follows Bjorken and Drell[10]. Similarly, an arbitrary component P may be represented by (P.U). If contraction over components of vectors is required, then the declaration INDEX must be used. Thus INDEX U; declares U as an index, and the simplification of (P.U) * (Q.U) would result in (P.Q) The metric tensor g may be represented by (U.V). If contraction over u and v is required, then U and V should be declared as indices. The declaration REMIND V1...VN $ removes the index flags from the variables V1 through VN. However, these variables remain vectors in the system. C.2.2 G G is an n-ary operator used to denote a product of gamma matrices contracted with Lorentz four-vectors. Gamma matrices are associated with fermion lines in a Feynman diagram. If more than one such line occurs, then a different set of gamma matrices (operating in independent spin spaces) is required to represent each line. To facilitate this, the first argument of G is a line identification identifier (not a number) used to distinguish different lines. 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 . Thus G(L,A) ≡ associated with line L. G(L,P,A) ≡ associated with line L. (associated with line L) may be written as G(L,U), with U flagged as an index if contraction over u is required. The notation of Bjorken and Drell [10] is assumed in all operations involving gamma matrices. C.2.3 EPS The operator EPS has four arguments, and is used only to denote the completely antisymmetric tensor of order 4 and its contraction with Lorentz four-vectors. Thus ε = { +1 if α,β,u,v is an even permutation of 0,1,2,3 αβuv { -1 if an odd permutation { 0 otherwise A contraction of the form ε p q may be written as EPS(AL,BE,P,Q), αβuv u v with AL and BE flagged as indices, and so on. C.3 Vector variables. Apart from the line identification identifier in the G operator, all other arguments of the operators in Section B.2 are vectors. Variables used as such must be declared so by the type declaration VECTOR. e. g. VECTOR P1,P2; declares P1 and P2 to be vectors. Variables declared as indices or given a mass (Section C.6) are automatically declared vector by these 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 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 [11] for contracting indices in products of traces, REDUCE uses the elegant algorithm of Kahane [12] for contracting indices in gamma matrix products. It is possible to prevent the trace calculation over any line identifier by the declaration NOSPUR. e. g. NOSPUR L1,L2; will mean that no traces are taken of of gamma matrix terms involving the line numbers L1 and L2. Furthermore, any product of gamma matrices may be reduced to combinations of the sixteen fundamental gamma matrices by the declaration REDUCE. e. g. REDUCE L1,L2; will mean that products of gamma matrices with line numbers L1 and L2 will be reduced to the sixteen fundamental forms. The declaration REDUCE naturally includes NOSPUR. This command should be used with extreme caution. For example, the reduction of a product of six different 'slashed' vectors generates 66 terms! A trace of a gamma matrix expression involving a line identifier which has been declared NOSPUR or REDUCE may be later taken by making the declaration SPUR. SPUR cancels both NOSPUR and REDUCE. C.6 Mass Declarations It is often necessary to put a particle 'on the mass shell' in a calculation. This can, of course, be accomplished with a LET command such as LET P.P= M↑2; but an alternative method is provided by two commands MASS and MSHELL. MASS takes a list of equations of the form: <vector variable> = <scalar variable> e. g. MASS P1=M, Q1=MU; The only effect of this command is to associate the relevant scalar variable as a mass with the corresponding vector. If we now say MSHELL <vector variable>,...,<vector variable>; and a mass has been associated with these arguments, a substitution of the form <vector variable>.<vector variable> = <mass>↑2 is set up. An example of this is given in the following. C.7 Example We give here as an example of a simple calculation in high energy physics the computation of the Compton scattering cross-section as given in Bjorken and Drell[10], Eqs. (7.72) through(7.74). We wish to compute 2 2 pf+m ε'εki + εε'kf pi+m kiεε' + kfε'ε α /2 (k'/k) trace {(----)(----- ------)(----)(----- ------)} 2m 2k.pi 2k'.pi 2m 2k.pi 2k'.pi where ki and kf are the four-momenta of incoming and outgoing photons (with polarization vectors ε and ε' and laboratory energies k and k' respectively) and pi,pf are incident and final electron four-momenta. Omitting the factor α↑2/(2*m↑2)*(k'/k)↑2 we need to find ε'εki + εε'kf kiεε' + kfε'ε 1/4 trace {(pf+m)(----- ------)(pi+m)(----- ------)} 2k.pi 2k'.pi 2k.pi 2k'.pi A straightforward REDUCE program for this, with appropriate substitutions would be: 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 %TOP,,,,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] Collins, G. E., Journal of the A.C.M. 14, 128 (1967). [3] Lipson, J. D., Symbolic Methods for the Computer Solution of Linear Equations with Applications to Flowgraphs, Proceedings of the 1968 Summer Institute on Symbolic Mathematical Computation, IBM Programming Laboratory Report FSC 69-0312 (1969) [4] Hearn, A. C., REDUCE 2, A System and Language for Algebraic Manipulation, Proceedings of the Second Symposium on Symbolic and Algebraic Manipulation (to be published) [5] Hearn, A. C., REDUCE, A User-Oriented Interactive System for Algebraic Simplification, Proceedings of the ACM Symposium on Interactive Systems for Experimental Applied Mathematics, held in Washington, D.C., August 1967. [6] Hearn, A. C., The Problem of Substitution, Proceedings of the 1968 Summer Institute on Symbolic Mathematical Computation, IBM Programming Laboratory Report FSC 69-0312 (1969) [7] McCarthy, J., Abrahams, P. W., Edwards, D. J., Hart, T. P. and Levin, M. I., LISP 1.5 Programmer's Manual, M.I.T. Press, 1965 [8] Weissman, Clark, LISP 1.5 Primer, Dickenson, 1967 [9] Hearn, A. C., Standard LISP, Stanford Artificial Intelligence Project Memo AI-90 (May 1969) [10] Bjorken, J. D. and Drell, S. D., Relativistic Quantum Mechanics (McGraw-Hill, New York, 1965). [11] Chisholm, J. S. R., Il Nuovo Cimento X, 30, 426 (1963) [12] Kahane, J., Journal Math. Phys. 9, 1732 (1968)