perm filename RLISP.XER[CSP,DOC] blob sn#002720 filedate 1972-10-09 generic text, type T, neo UTF8
```STANFORD ARTIFICIAL INTELLIGENCE LABORATORY          October 1970
OPERATING NOTE 62

R E D U C E   2

S Y M B O L I C   M O D E

P R I M E R*

by

Anthony  C.  Hearn

University of Utah

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.

%TOP
1. INTRODUCTION

REDUCE  is a program designed primarily for general algebraic
computations of interest to mathematicians, physicists and engineers.
However,  its  source  language is general enough to allow for a full
range of LISP-like symbolic calculations.  This  primer  is  a  brief
guide  to  this  source language.  It does not describe the algebraic
capabilities of the system, so  anyone  interested  in  these  should
consult  the  REDUCE  2 User's Manual [1], of which this primer is an
extract.

This  primer  assumes  that  the  reader  has  a   reasonable
acquaintance  with LISP 1.5 at the level of the LISP 1.5 Programmer's
Manual [2] or Clark Weissman's LISP 1.5 Primer[3]. Anyone  unfamiliar
with this material is advised to study it before proceeding further.

In  Section  2  of  this primer, we give details of the basic
structure of REDUCE programs.  Finally,  in  Section  3,  details  of
running REDUCE symbolic programs on the Stanford PDP-10 is given.

The  author  would  appreciate  hearing  from  any  users who
experience trouble with the system (please include copies of relevant
input and output).

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

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

It is also possible to include non-alphanumeric characters in
identifiers by prefixing the character by an exclamation mark.

e. g., DSK!: GET!*!* A!+B

Identifiers are used as variables,  labels  and  to  name  operators,
arrays 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 in Section 2.11.1.

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
U . V

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
ε	MEMBER
=	EQUAL
≠	UNEQ
≡	EQ
>=	GREATEQ
>	GREATERP
<=	LESSEQ
<	LESSP
+	PLUS
-	MINUS
*	TIMES
/	QUOTIENT
↑       EXPT
.	CONS

In systems which  do  not  have  all  these  characters,  the
alternative forms are allowed

operator	alternative
↑                **
←    	    :=

These operators may be further divided into the following sub
classes

<logical operator> ::= ∧|∨
<relational operator> ::= ε|=|≠|≡|>=|>|<=|<
<arithmetic operator> ::= +|-|*|/|↑
<symbolic 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 ↑ and /.

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 the lowest precedence and  will  be
ordered  among themselves by their order at definition.  Thus ∀ has a
higher precedence than ∃.

Restriction:
Because  of  their  particular  uses  in  the   system,   the
characters !, λ and ¬ cannot be used as infix operators.

The precedence of any infix operator 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. CAR(U)
CDR (REVERSE (U))

Parentheses may be omitted if the operator is unary.

e. g.  CAR Y and CAR(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.

2.6 Strings

Strings are used only in output statements. A string consists
of any number of characters enclosed in double quotes.

e. g. "A STRING"

Comments are useful for  including  explanatory  material  at
various points in a program.  They may be used in the following form:

COMMENT <any sequence of characters not including a terminator>
<terminator>
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, and
evaluate to numbers.

Examples:
2
I + J - 2 * I↑2

are numerical expressions if I and J are integers.

2.8.2  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
3*X-1 >2
X > 0 ∨ X = -2

2.8.3  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)

2.8.4 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))

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.

2.8.5 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.

2.9 Reserved Words

Certain  words are reserved in REDUCE.  They may only be used
for the purpose intended as  explained  in  the  following  sections.
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 are some proper statements in REDUCE:

2.10.1 Assignment Statements

These statements have the following syntax

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

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

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>
{UNTIL <arithmetic expression>}  {
{			     }	{DO <statement>
{WHILE <boolean expression>   }  {

The FOR statement follows the normal ALGOL useage. It returns
the value NIL.

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.16.   Some  other  REDUCE
declarations are as follows:

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 algebraic 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.

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 ECHO;
OFF INT;

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 Procedures

It  is  often  useful to name a statement for repeated use in
calculations  with  varying  parameters,  or  to  define   operators.
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 are REAL, INTEGER, LISP (or SYMBOLIC), FEXPR  and
MACRO.  There is no default type in symbolic mode, i. e., a type must
always be included.

E. g., the example in Section 2.10.5  could  be  made  into  a 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.

Function definitions may also be input in a  procedural  form
The procedural type in this case is LISP (or SYMBOLIC).  For example,
the definition of ASSOC in Section 2.10.1 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.

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.15  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 a symbolic 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.

2.16  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.

Facilities are present  in  REDUCE  to  allow  users  editing
access  to  program  source  files during calculations.  To use these
facilities, all function definitions should be input from SOS  files,
and  global changes to these files, such as renumbering and insertion
of page marks, should be avoided.

There are two ways in which this link may be used.  These are
as follows:

2.17.1 Correction of Input Errors

If an error is encountered on input  while  an  SOS  file  is
being  loaded,  the system will print the error diagnostics, and then
print the message EDIT?.  If the user types Y (for  yes), the  system
will  then  load  SOS and print the line which marks the beginning of
the command in which  the  error  occurred.  The  error  can  now  be
corrected.  After  editing  is complete, typing G (for go) in SOS has
rereading  the input file from the beginning of the command where the
error occurred.

2.17.2 Editing Function Definitions

Any functions which were input to RLISP from an SOS file have
information  saved  with them which tells the system where they occur
in the file (this is why global changes to tthe source  files  should
be  avoided).   If the user desires to change the function definition
during an RLISP calculation, he can access the source  definition  in
the file by typing

EDIT <function name>;

This  command  causes  SOS  to  be  loaded  and the first line of the
function printed.   The user can now edit  the  function  definition.
Typing  G will cause the user's RLISP program to be reloaded, and the
altered function definition to be read from the file.  Note, however,
that only one function may be redefined at a time by this method.

2.18 Debugging Facilities in REDUCE

A few simple debugging facilities are available in REDUCE for
the more experienced programmer.  These are as follows:

2.18.1 Tracing Functions

A command TR is available in RLISP for tracing LISP  function
calls.  This  command,  and  the  associated  commands UNTR, TRST and
UNTRST, are used in the form:

TR <function name>,<function name>,...,<function name>;

TR  calls  the  LISP function TRACE, and its output is in exactly the
same form. The trace may be turned off by  the  function  UNTR  which
uses the LISP function UNTRACE.

WARNING:
Because  LISP establishes fast links to functions in compiled
code once that code has been referenced, it is necessary  to  inhibit
this  when  tracing  is  required.   TR  does  this  as  part  of its
evaluation sequence, but if tracing is not required until late  in  a
trace.  To prevent this, TR should be called with no arguments as the
first command in the program.

2.18.2 Tracing Assignments in Compound Statements

Useful  diagnostic  information  can  often  be  obtained  by
observing  the  values  which variables acquire during assignments in
particular functions.  To do this in  RLISP,  one  uses  the  command
TRST.  There are some restrictions on the function names which appear
in the arguments of this function, however. First, the functions must
obviously  be  in  the system in symbolic form; compiled functions no
longer  contain  information  on  the  assignment   variable   names.
Secondly,  the  functions must have a compound statement at their top
level.

This particular trace  may  be  turned  off  by  the  command
UNTRST.

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 (for example, any files
still open are automatically closed), and  should  therefore  not  be
omitted.

If  an  END  command  is used in the main program, control is
then transferred to LISP.

3.  RUNNING REDUCE SYMBOLIC MODE ON THE STANFORD PDP-10

3.1	A  symbolic  mode version of REDUCE is stored as a 24K system
with filename RLISP.DMP.

REDUCE may be loaded by typing R RLISP.  A message will  then
inform you when the program is loaded. 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>
.ST<cr>

You will then be back in REDUCE.

Alternatively,  you can load the program initially with a larger core
size by typing

.R RLISP <core size><cr>

3.2 Special Features

3.2.1 If you give IN a variable  or  dotted  pair  as  argument,  the
system expects to find the file in your disk area, and similarly with
OUT. 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;

3.2.2 The altmode character may be used as a terminator. This is very
convenient,  as  it  is not then necessary to follow it by a carriage
return as is required with the other terminators. However, the  value
of the symbolic evaluation is not printed in this case.

3.2.3 NOT

The  character  ¬  may  be used interchangably with the unary
function NOT on input.  On output, however, NOT is printed.

3.3 A SAMPLE PROGRAM

REDUCE 2 <system date>...		system loaded

*COMMENT A SAMPLE PROGRAM;		comments are allowed

*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 			diagnostic message from REDUCE

ASSOC 					value from definition of ASSOC

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

(A . D)					it works!

***					value of END routine

ENTERING LISP...			so that you know
*

REFERENCES

[1]  Hearn,  A.  C.,  REDUCE  2  User's  Manual,  Stanford Artificial
Intelligence Project Memo No. AIM-133 , October 1970.

[2]  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

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

```