LISP 1.5

ji

i

i

LISP 1.5

GEORGE G. ROBERTSON

VANDERBILT UNIVERSITY
COMPUTER CENTER

AUGUST, 1969

VANDERBILT UNIVERSITY
NASHVILLE, TENNESSEE

Report No. 1004

George G. Robertson

Vanderbilt University-
Computer Center
Nashville, Tennessee

TABLE OF CONTENTS

Page

TABLE OF CONTENTS. i

I. INTRODUCTION. I - 1

II. THE LISP LANGUAGE. II - 1

2.1 Symbolic Expressions. II - 2

2.2 Elementary Functions. II - 2

2.3 List Notation. II - 4

2.4 Meta-Language Expressions. II - 4

2.5 Syntax. II - 7

III. ADAPTING LISP AS A PROGRAMMING SYSTEM.1.. Ill - 1

3.1 The Universal Function. Ill - 1

3.2 Variables, Constants, Functions,

and Special Forms. Ill - 2

3.3 Extentions. Ill - 4

3.4 Arithmetic. HI - 5

3.5 Program Feature. IU - 6

IV. IMPLEMENTATION OF LISP ON THE SDS SIGMA 7. IV - 1

4.1 Internal Structures. IV - 2

4.2 Functions. IV - 8

V. USER OPERATING PROCEDURES. V- 1

5.1 The LISP Program. V - 1

5.2 Tape Operations... V - 1

5.3 System Messages. V - 1

5.4 Control Card Options. V - 6

VI. CONCLUSIONS AND FUTURE CONSIDERATION. VI - 1

APPENDIX I: LISP 1.5 FUNCTIONS

1. INTRODUCTION

This publication is intended as a reference manual in the use of
Vanderbilt SDS SIGMA 7 LISP 1.5, based on MIT 7090 LISP 1.5 (see LISP
1.5 Programmer's Manual , MIT Press, January 1966). The manual is divided
into five sections. The first three sections offer an introduction to
the LISP language. The final two offer a description of the SIGMA 7
implementation and user operating procedures.

LISP is a mathematical language designed primarily for meaningful
manipulation of list structures. When certain important features are
added to the mathematical language, it can be extended to a programming
language suitable for list processing. The mathematical language is
complete without these extensions, but without them, it is not very useful
as a programming language. With the extensions added, the language is
referred to as the programming language LISP 1.5.

Once the mathematical language has been extended to a programming
language, the task becomes one of developing a programming system capable
of translating the programming language into meaningful computer operations.
With some languages, this task is best accomplished with a compiler. A
compiler is a program which translates the source language into machine
language. With LISP 1.5, however, this task is best accomplished with an
interpretive system. An interpretive system is a programming system which
executes a source language program by examining the source language and
performing specified algorithms. These algorithms may be specified by the

user in the LISP language, or they may be one of many primitive routines
included in the system. A primitive is a machine language routine designed
to perform one specific algorithm. These primitives along with the inter¬
preter make up the interpretive system. The task of translating the
programming language LISP 1.5 is accomplished with such an interpretive
system.

Thus, the problem of implementing the mathematical language LISP on
the SDS SIGMA 7 is reduced to a two step process. First, extend the
mathematical language to a programming language. Second, develop an
interpretive system capable of translating the programming language. These
processes, as well as a mathematical description of the language, are
discussed in this manual.

II. THE LISP LANGUAGE

LISP is a formal system and, as such, has the elements of
any formal system. The elements of LISP include a set of symbols
which are called symbolic expressions, abbreviated S-expressions.

Also included is a functional notation over the set of symbols.

These functions are referred to as Meta-language expressions,
abbreviated M-expressions. A formal mapping of M-expressions into
S-expressions is developed as a part of the system. Finally, a
universal function, written as an M-exprossion, is defined. This
function is used for interpreting the S-expression images of the
M-expressions. This interpretation is actually the application of
any function to its arguments. These elements form a complete
mathematical system.

As a mathematical system, LISP can be thought of as a
mathematical language. A language is a set of sentences over
an alphabet. The alphabet, which is a finite set of symbols, is
the set of upper and lower case Latin letters, the arabic numerals,
and a few special characters such as left and right parentheses, the
comma, the blank, and the period. A sentence over an alphabet is
any string of finite length composed of symbols from the alphabet
which satisfies the rules of some grammar. The sentences in LISP
are the atomic symbols which make up S-expressions. The mathematical
system gives the language its meaning. Given the elements of the
mathematical system, the mathematical language can be recognized and

translated.

2.1 Symbolic Expressions

The smallest whole element of the LISP language is the atomic
symbol. An atomic symbol is a string of numerals and capital letters
with the first character of the string being a letter.

Examples :

ATOM

A

BL1234567890

ALONGSTRINGOFLETTERS

All S-expressions are composed of atomic symbols plus appropriate
delimiters. An S-expression is either an atomic symbol or a left
parenthesis, followed by an S-expression, followed by a period,
followed by an S-expression, followed by a right parenthesis. An
S-expression of the second type is sometimes referred to as a
dotted pair.

Examples:

ATOM

(A1 . A2)

(A . (B . C))

((A . B) . C)

((A . B) . (C . D))

2.2 Elementary Functions

The elementary functions operate on S-expressions. To dif¬
ferentiate functions from S-expressions, the functions will be in
small letters. Arguments to functions will be separated by a semi¬
colon. The five elementary functions are cons , head , tail, eq , and
atom .

The function cons is used to construct new S-expressions from
smaller S-expressions. There are two arguments to cons and its value
is an S-expression with the arguments to the function being the

elements of the dotted pair.

Examples :

cons (A ; B) = (A . B)
cons ((A . B) ; C) = ((A . B) . C)
cons (A ; (B . C)) = (A . (B . C))
cons (cons (A ; B) ; C) = ((A . B) . C)

The functions head and tail are selectors. The function

head selects the first S-expression of the dotted pair which is

the functional argument, while tail selects the second S-expres-
sion of the dotted pair. Either function applied to an atomic symbol
yields an undefined result.

Examples:

head ((A . B)) = A

tail ((A . B)) = B

head (((A . B) . C)) = (A . B)

tail (((A . B) . C)) = C

tail (head (((A . B) . C))) = B

head (A) is undefined

head (cons (A ; B)) = A

tail (cons (A ; B)) = B

cons (head ((A . B)) ; tail ((A . B))) = (A . B)

The functions ec^ and atom are predicates, that is, they are

functions whose value is either true or false. In LISP, the values

true and false are represented by the atomic symbols T and F,

respectively. The predicate ec[ tests for equality of atomic symbols.

It is undefined for non-atomic arguments. The predicate atom is

true if its argument is an atomic symbol and false it its argument

is a dotted pair. ,

Examples :

eq (A ; A) = T
eq (A ; B) = F

eq (A ; (B . C)) is undefined
atom (ATOM) = T
atom ((A . B)) = F
atom (head ((A . B))) = T

II - 4

2.3 List Notation

All non-atomic S-expressions used up to this point have been
written as dotted pairs. Any non-atomic S-expression may be written
in this form, but, for convenience, LISP allows an alternative form
for this type of S-expression. The alternative form, called list
notation, consists of a left parenthesis, followed by an arbitrary
number of S-expressions, each separated from the following by either
a blank or a comma, followed by a right parenthesis. The list
(a^ a 2 ...a^) is equivalent to the list . (a 2 . (...(a n .NIL)...))),
where NIL is the atomic symbol used to terminate lists. Dotted pairs
and list notation may be used in the same S-expression.

Examples ;

(A B C) = (A . (B . (C . NIL)))

((A B) C) = ((A . (B . NIL)) . (C . NIL))

(A) = (A . NIL)

((A)) = ((A . NIL) . NIL)

(A (B . C)) = (A . ((B . C) . NIL))

2.4 Meta-language Expressions

The five elementary functions already discussed are examples
of M-expressions. The M-expressions were distinguished from S-expres-
sions by the use of lower case letters and the use of the semicolon
as a seperator for arguments. Lower case letters are also used to
represent variables in LISP. A variable is a symbol used to repre¬
sent an arbitrary S-expression. There are three other M-expressions
which will be discussed before defining the mapping of M-expressions
into S-expressions. These are the conditional expression, the lambda
notation, and the label notation.

In order to facilitate the definition of recursive functions,

the conditional expression is included in the LISP language. A

conditional expression is of the form (p, -* e, ; p~ e 0 ;...; p -*■ e )

s. L & £. nil

where each p^ is an expression whose value is either true or false,
and each e^ is any expression. The p^ are searched from left to
right until the first true one is found. The value of the corre¬
sponding e^ becomes the value of the conditional expression. If
none of the p^ are true, then the value of the entire expression
is undefined. Each p^ or e^ can be either an S-expression, a function,
a composition of functions, or another conditional function.

Example :

(eq (head (x) ; A) cons (B ; tail (x)) ; T ->■ x)

In this example, x is a variable. If the head of x is A, then the
value of the expression is the list x with A replaced by B. If the
head of x is not A, then the value is x unchanged.

The lambda notation is included in the language to allow the
distinction between functions and forms. The lambda notation of
Alonzo Church (See The Calculi of Lambda-Conversion by A. Church)
is used. A form is an expression of more than one variable where
the correspondence between variable and argument is not specified.

If the correspondence is specified, then the expression is a function.
The lambda notation allows a form to be converted to a function by
specifying the correspondence. If e is a form in the variables
x^^;...;x n , then the expression A((Xj;...jx^); e) represents the
function of n variables obtained by substituting the n arguments in
order for the variables Xjj...;x , respectively.

II - 6

Examples :

MO ; y) ; y 2 + x) (3;4) = 4 2 + 3 = 19

H(y X) ; y 2 + x) (3; 4) = 3 2 + 4 = 13

In order to use a function recursively, the function name
must be bound. The lambda notation is not sufficient for this, so
the label notation is included in the language. If e is a expres¬
sion, and a is its name, we write label (a ; e) .

Example :

label (ff ; A((x) ; (atom (x) ->■ x ; T -»• ff (head (x)))))

In this expression, x is a bound variable, and ff is a bound function

name.

The mapping of M-expressions into S-expressions can now be
defined. If the function is represented by its name, it is translated
by changing all of the letters to upper case, making it an atomic
symbol. If the function uses the lambda notation, then the expres¬
sion X((x 1 ;...;x n ); e) is translated into (LAMBDA (XI ... XN) e*),
where e* is the translation of e. If the function begins with label,
then the translation of label (a ; e) is (LABEL a* e*). A variable,
like a function name, is translated by using upper case letters.

The translation of a constant X is (QUOTE X). This avoids ambiguity
from the translation of x, which is X. The form fnfargjj...;arg n )
is translated into (fn* arg^*...arg n *). Finally, the conditional
expression (p^ -+• e 1 ;...;p n e R ) is translated into (COND (pj* e^*)

• ••(p n * e n *».

Examples :

M-expressions S-expressions

x X

head HEAD

head (x) (HEAD X)

II - 7

M-expressions
T

ff(head(x))

(atom(x)->-x; T+ff(head(x)))

label (ff; X ((x); (atom(x)-*x;
T-*-f f (head (x) ) ) ) )

S-expressions

(QUOTH T)

(FF (HEAD X))

(COND ((ATOM X) X)

((QUOTE T) (FF (HEAD X))))
(LABEL FF (LAMBDA (X) (COND
((ATOM X) X)

((QUOTE T) (FF (HEAD X))))))

2.5 Syntax

The discussion of the formal system is now complete with the
exception of a discussion of the universal function. Discussion of
that function will be deferred to the section on the extension of
the mathematical language to a programming language. The purpose
of the universal function is to allow interpretation of the appli¬
cation of a function to its arguments. The interpretive nature of
this function makes the programming language easily translatable.

It is for that reason that discussion of it is found in the next

section.

For completeness, the syntax of the LISP language, described
in Backus notation (see J. W. Backus, The Syntax and Semantics of
the Proposed International Algebraic Language of the Zurich ACM-
Gamm Conference. ICIP Paris, June 1959), is included.

The Data Language

<letter>::= a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z

<digit>::= 0|l|2|3|4|5|6|7|8|9

<atomic-symbol>::= <LETTER>|<atomic-symbol><LETTER>|<atomic-symbol><digit>

<S-expression>::= <atomic-symbol>|

(<S- expression>.<S-expression>)|

(<S-exp part>)

<S-exp part>::= <empty>|<S-expression>|<S-exp part><S-expression>

The Meta-Language

<l$tter>::= a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z
<identifier>::= <letter>|<identifier><letter>|<identi£ier><digit>
<form>::= <constant>|

<variable>|

<function>(<argument list>)|

<constant>: := <S-expression
<variable>::= <identifier>

<argument>:: = <form>

<argument list>::= <empty>|<argument>|<qrgument list>;<argument>
<conditional list>::= <empty> | <form>-*<form> |

<form>-*-<form>; conditional list>

<function>::= <identi£ier>|

A(<var list>;<£orm>)|

label (<identifier>;<£unction>)

<var list>::= (<variable list>)

<variable list>::= <empty>|<variable>|<variable list>;<variable>

III. ADAPTING LISP AS A PROGRAMMING SYSTEM

To make the mathematical language LISP useful in a programming
environment, it must be extended to a programming language. First,
in a programming system it is difficult to differentiate a data language
and a meta-language. The solution to this problem is that the LISP formal
system provides a universal function which can make that distinction, and
which can interpret the meta-language expressed in the data language. Next,
in a programming environment, there must be means of allowing the programmer
to define his own functions and initialize his own variables to constants.

Also, there should be provisions for logical operations on certain types
of data and arithmetic operations on other types. To make the system useful,
a large number of functions should be available to the programmer to accom¬
plish these types of tasks. Finally, there should be some method of
controlled looping available to the programmer. With all of these extensions,
the mathematical language becomes very useful in a programming environment,
and the extended language can rightfully be called a programming language.

3.1 The Universal Function

An interpreter or universal function is one that can compute the value
of any given function applied to its arguments when given a description of that
function. The LISP universal function is evalquote (fn, args). All LISP
functions have S-expressions as arguments, and therefore, the argument fn of
evalquote must be an S-expression. In particular, fn is the S-expression image
of some M-expression function. The universal function obeys the following
identity. Let f be a function written as an M-expression, and let fn be its

translation, an S-expression. Let f be a function of n arguments and let
args=(argj...arg n ), a list of n S-expressions being used as arguments. Then
evalquote (fn, args)=f(argp...;arg n ) if either side of the equation is
defined at all.

Example ;

f: A((x;y) ; cons( head (x) ; y))

fn: (LAMBDA (X Y) (CONS (HEAD X) Y))

argp (A B)

arg 2 : (C D)

args: ((A B) (C D))

evalquote ((LAMBDA (X Y) (CONS (HEAD X) Y)j ; ((A B) (C D)))=

X ((x;y) ; cons(head (x) ; y)) ((A B) ; (C D))=

(A C D)

During the execution of evalquote , an association list is maintained.

This list has the current values of bound variables and function names. Two
main functions are used by evalquote . They are eval and apply . The
function apply handies a function and its arguments, while eval handles
forms. Both auxiliary functions have the current association list as an argument.
The maintenance of an association list in this manner allows dynamic binding
of both variables and function names.

3.2 Variables, Constants, Functions, and Special Forms

A variable is a symbol used to represent an argument of a function. A
variable becomes bound to a value in one of two ways. It may become bound
by the lambda notation. The part of the interpreter that binds variables
is called apply . When apply encounters a function beginning with LAMBDA,
the association list is altered by adding the paired list of variables and
arguments. During evaluation of the functions, when variables are
encountered, they are evaluated by looking them up on the association list.

If a variable has several bindings, the most recent is used. The part of
the interpreter that finds the value of a variable is called eval . A variable

remains bound within the scope of the lambda that binds it.

The second way a variable may become bound is for the programmer to
set the variable to a constant. A constant is simply a variable bound on
the highest level. In other words, a constant is a variable which has the
same value regardless of the current association list. This is accomplished
by means of the property list, abbreviated p-list (see section 4.1 for
detailed discussion of p-lists), associated with the variable symbol. Every
atomic symbol has a p-list. If the p-list contains the indicator APVAL, then
the next item on the p-list is the constant value of the variable. P-lists
are searched by eval before the association list is searched, thus making it
possible to set variables to constant values. This task is accomplished with
the cset function. cset(X ; (ABC D)) makes the variable X always stand
for (A B C D).

Similarly, there are two ways to bind function names. One way is to
use the label notation to alter the current association list by adding the
function name bound to its function definition. A more desirable method
involves the changing of the p-list of the atomic symbol representing the
function name. The indicator EXPR on a p-list informs apply that the
function is bound on the highest level of the S-expression which follows on
the p-list. The function apply searches the p-list before searching the
current association list, so that this method will override the label
notation. The alteration of the p-list is accomplished by the function
define .

There is another class of functions in the LISP system. These are bound
on their respective p-lists by the indicator SUBR followed by linkage to a
machine language subroutine. All of the functions which are a part of the
LISP system are of this type.

A special form is a type of function with an indefinite number of
arguments. The arguments of a special form are not evaluated before the
special form receives them, unlike all other functional arguments. Special
forms have indicators on their p-lists called FEXPR and FSUBR for LISP-
defined forms and machine language forms, respectively. Special forms are
included in the language to give it flexibility.

3.3 Extensions

There are several extensions to the language which are very useful
in a programming environment. A full complement of input and output
functions should be added, as well as functions which are designed for
character manipulation. These functions are referred to as pseudo-functions
because it is their side effects, not their values, which are important. For
example, the print function has a side effect the physical printing of its
S-expression argument on the line printer. The value of the print function
is trivial and may be ignored. In addition to this type of pseudo-function,
it would be useful to introduce functionals, that is, functions which have
functions as arguments. Finally, it would be useful to include propositional
connectives. These extensions extend the scope and usefulness of the
language.

The syntax of the meta-language does not allow functions as arguments.

It expects an argument to be a form. To allow functionals, we must modify
the syntatic definition of an argument to include functional arguments:

<argument>::= form>|<function>

Also, a rule for translating functional arguments must be set forth. If fn
is a function used as an argument, then it is translated into (FUNCTION fn*).

Now, functionals will be considered a part of the programming language.

To allow logical connectives, three predicates are introduced.

These are and , or , and not , The predicate not has only one argument, and
its value is true if the argument has a value of false, false otherwise.

The predicates and and or have an indefinite number of arguments, and
are, therefore, special forms. If any of the arguments to and are false,
then the value of and is false. Otherwise, its value is true. If any of
the arguments to or~ are true, then the value of or is true. Otherwise, its
value is false. With these predicates, any Boolean operations may be performed.
3.4 Arithmetic

Any useful programming language must have means of performing arithmetic
and logical operations and making basic tests. For this reason, the
programming language LISP 1.5 has provisions for handling fixed-point and
floating-point numbers and logical words. In discussing arithmetic in LISP,
two things must be considered; the form of numbers for reading and printing,
and the arithmetic functions and predicates.

Numbers are stored internally as a special type of atomic symbol. They
may occur in S-expressions as though they were atomic symbols. Numbers are
constants that evaluate to themselves. They do not need to be quoted.

Numbers should not be used as variables or function names.

A floating-point number must include a decimal point, but not as the
first or last character. An optional plus or minus sign may precede the
number. An optional exponent may be written directly after the number with
the letter E, followed by an optional sign, followed by one or two digits of
exponent. A fixed-point number _».s written as an integer with an optional sign.

A logical word is written as a hexadecimal constant. It begins with
the letter X, followed by the character ', followed by up to eight hex¬
adecimal digits, that is, the digits and the letters A, B, C, D, E, F,
followed by the character ’.

The arithmetic functions and predicates will be described in detail
in section 4.2. These functions must be given numbers as arguments;
otherwise an error condition will result. Types of numbers may be mixed
in a list of numeric arguments. If all arguments are fixed-point numbers,
then the value of the function will be fixed-point number. If at least
one argument is a floating-point number, then the value of the function
will be a floating-point number. These arithmetic functions may be used
recursively, just as other functions available to the interpreter.

3.5 Program Feature

The addition of the program feature to LISP 1.5 allows the programmer
to write an Algol-like program containing LISP statements to be executed.
This allows the programmer to use controlled looping in his LISP program.

The program form has the structure (PROG, list of program variables,
sequence of statements and atomic symbols...). An atomic symbol in the
list is the location marker for the statement beginning immediately after
that symbol. The first list after the symbol PROG is a list of program
variables. If there are none, then this should be written NIL or ().

Program variables are treated much like bound variables, but they are not
bound by LAMBDA. The value of each program variable is NIL until it has
been set to something else by either a SET form or a SETQ form. These forms
are used only to set program variables.

Ill - 7

Program statements, which are often executed for their effect
rather than their value, are normally executed in sequence. That is,
the statements are evaluated with the current association list, and then
the value is ignored. The sequence of statements executed may be altered
by the form GO. (GO A) causes a transfer to the statement with the
location marker A. The form GO can be used only as a statement on the top
level of a PROG or immediately inside a COND which is on the top level of
a PROG. If a conditional statement on the top level of a PROG has none of
its propositions true, then, unlike elsewhere, the program continues with
the next statement. The normal end of a program is the form RETURN. The
argument of RETURN is evaluated, and this is the value of the program. If
a program runs out of statements, it returns with the value NIL. The program
feature, like other LISP functions, can be used recursively.

Example :

rev (x) ::prog ( (y; z) ;

A (nul 1 (x)-*return (y);

z:=head(x);
atom(z)->-go(B));
z:=rev(z);

B y:=cons(z;y);

x:=tail(x);
go(A))

The predicate null is true if its argument is NIL. It is useful in
determining when the end of a list is reached. The function rev will
reverse a list on all levels so that

rev((A ((B C) I)))) = ((D (C B)) A).

IV. IMPLEMENTATION OF LISP ON THE SDf> SIGMA 7

'Oils section contains the specifications for an implementation of
the programming language LISP 1.5 on the SD5 SIGMA 7 at Vanderbilt
University. This implementation is based on the M. I. T. 7090 LISP
system. The major difference between the two systems is the omission
of the compiler and assembler from the SIGMA 7 system. In other words,
this system is an interpretive-only system; all routines associated with
the compiler, assembler, and loader arc not present in this implementation.

Hie SDS SIGMA 7 is a binary computer with a 32-bit word length and
65,536 words of storage, expandable to 131-072 words. There are 16 general
registers, 7 of which can be used for indexing. One level of indirect
addressing, with or without post-indexing, is allowed. All of memory is
addressable and alterable by byte (8-bit), halfword (2-byte), word (4-byte),
and doubleword (8-byte). The halfword addressability makes the elementary
functions extremely simple if free storage is limited to 2*'* or 32,768 words,
so that a pointer to a word in free storage may be contained in a halfword.
When the SDS Batch Processing Monitor is in use, it resides in the lower
19,000 words of memory.

The programming system used to translate the programming language LISP
1.5 is an interpretive system. The interpretive system is composed of three
major components. First, there is a translator which translates the source
language into internal list structures. This routine places the paired
arguments, called doublets, for evalquote, onto a list called the input list,
abbreviated I-list. A LISP program is simply a series of these doublets.

Second, there is the interpreter or universal function evalquote. A
control routine passes the pairs from the I-list to the interpreter for
execution. The interpreter interprets the application of its first
argument, which is an S-expression image of some M-expression, to its
second argument, which is the S-expression argument to the function. The
interpreter uses an association list, now abbreviated A-list, to keep track
of which variables are bound and which functions names are bound. The
interpreter, on its lowest level, links the source arguments to appropriate
primitives or source language functions. The third component of the interpre¬
tive system is the set of primitives.

In discussing the implementation of this programming system, three
things must be included. There must be a complete description of the system's
internal structures, the functions available to the user, and the running
procedures for the system. This section gives these descriptions.

4.1 Internal Structures

Five major areas of discussion evolve from a discussion of the internal
structures in the LISP system. First, we must specify the run-time storage
layout. That is, we must specify exactly where the major components of the
system will be when the system is in use. Second, we must consider the internal
representation of list structures. Third, we should consider the make up of
property lists, for both atomic symbols and for numeric constants. Fourth,
we should consider each of the special structures necessary to make the system
complete. Finally, we should consider the method of garbage collection and
the structures that the garbage collection routine uses. The primary purpose
of discussing these internal structures is to give the reader an idea of what

the real make up of this programming system is, rather than simply present
a functional description of the system.

The run-time storage layout is best representated by the following
diagram.

0000

Lists are structural forms built out of computer words as parts of
trees. In representating list structure, a computer word will be divided
as follows:

Bit Purpose

0 Reserved for garbage collection

1-15 head(x) - contains a displacement from the beginning of

the Free storage area
16 0 - normal

1 - indicates head of numeric p-list
17-31 tail(x) - contains a displacement from the beginning of

the Free storage area

To represent a word, a rectangle is used. Bits 0 and 16 are ignored, if
zero, and the word is represented by a rectangle divided into two sections.
The presence of a name in a section indicates a pointer to that atomic
symbol's property list. The pointer to NIL is represented by

Every atomic symbol has a property list. When an atomic symbol is

read, a p-list is created for it. A p-list is characterized by having a -1,

or hexadecimal 7FFF, as the first element of the list. The rest of the

list contains various indicators followed by pertinant properties of the

symbol, and/or flags. A flag is not followed by a property, but rather

indicates a property itself. The indicators and flags are:

ATOM - flag - the -1 which characterizes p-lists
TRACE - flag - indicates that this function should be traced
EXf'R - indicator - followed by a pointer to an S-expression
which represents some function
FEXPR - indicator - followed by a pointer to an S-expression
which represents a special form
SUBR - indicator - followed by linkage to machine language
subroutine, a function

FSUBR - indicator - followed by linkage to machine language
subroutine, a special form

APVAL - indicator - followed by permanent value of the symbol
PNAM - indicator - followed by a pointer to a list of full words
containing the symbols print name

PROP.

Full word storage is reserved for storage of elements of the system
which require a full word of significance. The primary use is for the

storing of print names, numbers, and linkages of subroutines.
Example :

The print name for the atomic symbol EXAMPLE is:

Numbers have a special p-list. The type of number
indicated by TYP, where logical words have TYP equal to
numbers have TYP equal to 1, and floating-point numbers
Example:

•~*-l

TYP

lJ

1

number

represented is
0 , fixed-point
have a TYP of 2.

One of the most important special structures is the object list. The
object list is a list of all atomic symbols in existence. The read function
uses this list to assure no duplications of p-lists. The structure is actually
28 lists. The first 26 correspond to the letters of the alphabet, and any
atomic symbol beginning with the i th letter will have its p-list on the i th

U.-L

list in the object list. The 27 list consists of all special symbols while
the 28^ list consists of all numbers.

Example :

heads of lists

Two other special lists have already been discussed. They are the
association list and the input list. Both of these lists, along with the
object list, are used during garbage collection to trace all active list
structures.

There arc several other special structures that should be mentioned.
Certain functions available to the user work with characters rather than
pointers to lists. These characters are called character objects. The
functions expecting character objects will consider the head of a list to be
an EBCDIC character rather than a displacement address. There are also
several buffers in the system. The character manipulation buffer, called
60FF0, is 120 bytes long. All functions designed to do character
manipulations use this buffer. There are three input buffers, each 80 bytes
long. Input is actually done with the middle (2 nc *) buffer. The other two

buffers are used for indication of errors by the errorl function. There

is also a 120 byte output buffer. Finally, a large section of the run¬
time storage layout is reserved for a push-down stack. When arguments
are passed to any subroutine, the push-down stack is used for passing
arguments. Whenever a. recursive routine is entered, the push-down stack
is used to save pertinent information. All of these special structures
are necessary to make the system complete.

When a word of Free or Full word storage is requested and none is
available, the garbage collector is called. A user may explicitly call
the garbage collector if he so desires. The user function is called
reclaim . The garbage collector traces all active lists through the object
list, the input list, and the current association list, setting bit 0 of
every free storage word it encounters to 1. For full words, the garbage
collector sets a corresponding bit in a bit table. When all lists have been
exhausted, the garbage collector makes a linear pass over free storage,
creating a new free storage list from words with bit 0 set to 0, and
resetting bit 0 if it, is set to 1. Then the garbage collector does the
same for full word storage using the bit table. The function reclaim has
no arguments and its value is NIL.

4.2 Functions and Constants in the LISP System

This section contains all functions available in the LISP System
as of August 1969.

Each entry contains the name of the object, the property under
which it is available (e.g., EXPR, FEXPR, SUBR, FS1JBR, or APVAL),
whether it. is a pseudo-function, functional (function having functions
as arguments), or predicate, and in some cases a definition of the
function as an M-expression. In the case of APVAL's, the value is
given.

Elementary Functions

car [x] : SUBR

head [x] : SUBR

cdr [x] : SUBR

tail [x] : SUBR

The elementary functions car and cdr always have some sort of value
rather than giving an error diagnostic. A chain of cdr's applied to an
atomic symbol will allow one to search its property list. Indiscriminate
use of these functions past the atomic level will result in non-list
structure and may appear as lengthy or even infinite garbage expressions
if printed.

The functions head and tail are identical to the functions car and
cdr respectively.
cons [x;y] : SUBR

com; obtains a new word from the free storage list and places its
two arguments in the head and tail of this word, respectively. It does not
check to see if the arguments are valid list structure. The value of con s

IV - 9

is a pointer to the word that was just created. If the free storage
list has been exhausted, cons calls the garbage collector to make
a new free storage list and then performs the cons operation.
atom [x] : SUBR predicate

The first word on the property list of an atomic symbol contains
-1 or 7FFFj£ in the head. The atom subroutine depends upon this, and
on the fact that NIL is located at 0.

ec^[x;y] : SUBR predicate

eq is true if its two arguments are identical list structure.
equal [x;y] : SUBR predicate

equal is true if its arguments are the same S-expression, although
they do not have to be identical list structures in the computer. It uses
eq on the atomic level and is recursive. Floating point numbers in
S-expressions are compared for numerical equality with a floating point
tolerance of 3 x 10Fixed point numbers are compared for numerical
equality.

list [x 1 ;...;x n ] : FSUBR

The value of list is a list of its arguments.
null [x] : SUBR predicate

The value of null is true if its argument is NIL which is located at
0 in the computer.

SUBR pseudo-function

SUBR pseudo-function

SUBR pseudo-function

pseudo-function

SUBR

The operator rpla c.a[x;y] replaces the head of x with y. Its value
is x, but x is something different from what it was before. In terms of
value, rplaca can be described by the equation.

rplac a[x;y] = cons [y;cdr[x]]. But the effect is quite different:
there is no cons involved and a new word is not created.
rplacd [x;y] replaces the tail of x with y.

These operators must be used with caution. They can permanently
alter existing definitions and other basic memory. They can be used to
create circular lists, which can cause infinite printing, and look

infinite to functions that search, such as e qual and subst .

!

The functions replhd and repltl are identical to the functions rplaca
and rplacd respectively.

Logical Connectives

and[x 1 ;x 2 ...,x r ] : FSUBR predicate

The arguments of and are evaluated in sequence, from left to right,
until one is found that is false, or until the end of the list is reached.
The value of and is false or true repectively.
or[Xj;x 2 ...,x n ] : FSUBR predicate

The arguments of or are evaluated in sequence from left to right, until
one is found that is true, or until the end of the list is reached. The
value of or is true or false respectively.
not[x] : SUBR predicate

The value of not is true if its argument is false, and false otherwise.

IV - 11

I nter pret er and Pr og_Feature
evalquote ifn;args ] : S!JBR

evalquoto [ fn; args ] = [get [ fn; FEXPR] get[fn; FSUBR]-*
eval[cons[fn;args];NIL]

T-*apply[fn; args; NIL]]

This definition shows that evalquote is capable of handling special
forms as a sort of exception. Apply cannot handle special forms and will
give an error if given one as its first argument.
apply [fn;args;a] : SUBR

In this description, spread can be regarded as a pseudo-function of
one argument. This argument is a list, s pread puts the individual items
of this list into the push-down stack.

These M-expressions should not be taken too literally. In many cases,
the actual program is a store and transfer where a recursion is suggested
by these definitions.

apply [fn;args;a]-[
null[fn]-*NIL;

atom[fn]-*[get[fn;EXPR]-*app.ly[expr; ^argsja];

f spread[args]

get [fn;SUBR]-* ^ $ALIST:=a; j" j
[ TSX subr 1 ^ J

T-*apply[cdr[sassoc[fn;a;X[ [ ];error[A2] ] ] ];args;a];
eq[car[fn];LABEL]-*apply[caddr[fn];args;const cons[cadr[fn];caddr[fn]];a]];
eq[car[fn];FUNARG]-*apply[cadr[fn];args;caddr[fn]];
eq[car[fn];LAMBDA]-*eval[caddr[fn];nconc[pair[cadr[fn];args];a]]

T-*apply [eval[fn;a];args;a] ]

1. The value of get is set aside. This is the meaning of the apparent free
or undefined variable.

eval[form;a]

SUBR

eval[form;a]=[

null [ form ]-*-NIL;
numberp [ f orm]-»-f orm;

atom [ f orra ]-*■[ get [ f orm; APVAL ]^-car [ apval 1 ];

T-*cdr [sassoc [ form; a; X [ [ ]; error [ A8 ] ] ] ] ];
eq [ car [ f orm ]; QUOTE ]-»-cadr [ f orm];
eq[car[form];FUNCTION]-*list[FUNARG;cadr[form];a];
eq[car[form] ;COND]-*-evcon[cdr[form] ;a];
eq[car[form] ;PROG]-*-prog[cdr[form] ;a];

atom[ car [form] ]-*[get [ car [ form]; EXPR]->-apply [ expr; ^evlis [ cdr [ form]; a]; a];

get[car[form]jFEXPRl^-applytfexprj^listtcdrtform];a];a];

/spread[evlis[cdr[form];a]];
get[car[form];SUBR]-^j$ALIST:=a;

[TSX subr,^4

^AC:=cdr[form]; |

get[car[form] ;FSUBR]-*-jMQ:=$ALIST:=a; p 5

|TSX fsubr, 1 4 J

.

T-*eval[cons[cdr[sassoc[car[form] ;a;X[ [] ;error[A9] ] ] ];

cdr[form]];a]];

T->-apply[ car [form]; evils [cdr [form] ;a] ;a] ]
evcon (c; a] = [null [ c]-»-error [ A3 ];

eval[caar[c] ;a]-»-eval[cadar[c] ;a];

T-*evcon[cdr[c]; a] ]

evlislmjaJ^maplisttn^Xt [j ] ;eval[car[j] ;a] ] ]

The PROG Feature

The PROG feature is an FSUBR coded into the system. It can best be
explained in English, although it is possible to define it by using M-expressions.

1. As soon as the PROG feature is entered, the list of program variables
is used to make a new list in which each one is paired with NIL. This is then
appended to the current a-list. Thus each program variable is set to NIL
at the entrance to the program.

1. The value of get is set aside. This is the meaning of the apparent free
or undefined variable.

IV - 13

2. 'Che remainder of the program is searched for atomic symbols
that are understood to bo location symbols. A go-list is formed in which
each location symbol is paired with a pointer into the remainder of the
program.

3. When a set or a setq is encountered, the name of the variable is
located on the a-list. The value of the variable (or edr of the pair) is
actually replaced with the new value.

If the variable is bound several times on the a-list, only the first
or most recent occurrence is changed. J.f the current binding of the
variable is at a higher level then the entrance to the prog , then the change
will remain in effect throughout the scope of that binding, and the old
f value will be lost.

If the variable does not occur on the a-list, then an error diagnostic
will occur.

4. When a re turn is encountered at any point, its argument is
evaluated and returned as the value of the most recent prog that has been
entered.

5. The form £0 may be used only in two ways.

a. (GO X) may occur on the top level of the prog , x must be a
location symbol of this pro g and not another one on a higher or lower level.

b. This form may also occur as one of the value parts of a
conditional expression, if this conditional expression occurs on the top
level of the prog .

If a go is used incorrectly or refers to a nonexistent location, an
error diagnostic will occur.

IV - 14

0

6. When the form cond occurs on the top level of a prog , it differs
from other conds in the following ways.

a. It is the only instance in which a go can occur inside a cond.

b. If the cpnd runs out of clauses, an error diagnostic will no
occur. Instead, the pro g will continue with the next statement.

7. When a statement is executed, this has the following meaning, with
the exception of the special foras cond , go, retu rn, setq and the pseudo-
function set , all of which are peculiar to prog .

The statement £ is executed by performing eval[s;a], where a is the
current a-list, and then ignoring the value.

8. If a prog runs out of statements, its value is NIL.

Defining Functions and Functions Useful for Property Lists
d efine [x] : SUBR pseudo-function

The argument of define , x, is a list of pairs

((u lV - Vn”

where each u is a name and each v is a A-expression for a function. For
each pair, define puts an EXPR on the property list for u pointing to v.

The function of define puts things on at the front of the property list.

The value of define is the list of u's.
define[x] = deflist[x;EXPR]

deflist[x;ind] : SUBR pseudo-function

The function deflist is a more general defining function. Its first
argument is a list of pairs as for define . Its second argument is the indicator
that is to be used. After deflist has been executed with (u^v^) amoung its
first argument, the property list of u i will begin:

u.

X

V.

1

If deflist or define is used twice on the same object with the
same indicator, the old value will be replaced by the new one.
attrib [x;e] : SUBR pseudo-function

The function attrib concatenates its two arguments by changing the
last element of its first argument to point to the second argument. Thus
it is commonly used to tack something onto the end of a property, list. The
value of attrib is the second argument.

For example

attrib [FF; (EXPR (LAMBDA (X) (COND ((ATOM.X) X) (T (FF (CAR X))))))]
would put EXPR followed by the LAMDBA expression for FF onto the end of
the property list for FF.

prop [x;y;u] : SUBR functional

The function prop searches the list x for an item that is e^ to y.

If such an element is found, the value of prop is the rest of the list
beginning immediately after the element. Otherwise the value is u[], where
u is a function of no arguments.

prop[x;y;u] = [null[x] -*■ u[];eq[car[x];y]+cdr[x];

T -»-prop[cdr[x];y;u]]

I£t[x;y] : SUBR

get is somewhat like prop ; however its value is car of the rest of
the list if the indicator is found, and NIL otherwise.

get[x;y[ = [mill[x] -> NII,;eq[car[x] ;y] -> cadr[x];

T •> get[cdr[x];y]]

cset [ob;val] : SUBR pseudo-function

This pseudo-function is used to create a constant by putting
the indicator APVAL and a value on the property list of an atomic
symbol. The first argument should be an atomic symbol; the second
argument is the value to be placed on that atomic symbol’s p-list.

The value of cset is the value of cons[val,NIL].
csetq [ob;val] : FSUBR pseudo-function

csetq is like cset except that it quotes its first argument
instead of evaluating it.

remprop [x;ind] : SUBR pseudo-function

The pseudo-function re mprop searches the list, x, looking for all
occurrences of the indicator ind. When such an indicator is found, its
name and the succeeding property are removed from the list. The two
"ends" of the list are tied together as indicated by the dashed line
below.

PROPERTY

The value of remprop is NIL.

When an indicator appears on a property list without a property following
it, then it is called a flag. An example of a flag is the indicator TRACE
which informs the interpreter that the function on whose property list it
appears is to be traced. There are two pseudo-functions for creating and
removing flags respectively.

flag[£;ind] : SUBR . pseudo-function

The pseudo-function flag puts the flag ind on the property list of
every atomic symbol in the list Z. Note that Z cannot be an atomic symbol,
and must be a list of atomic symbols. The flag is always placed immediately
following the first word of the property list, and the rest of the property
list then follows. The value of flag is NIL. No property list ever
receives a duplicated flag.

remflag [l;ind] : SUBR pseudo-function

remflag removes all occurrences of the indicator ind from the property
list of etch atomic symbol in the list Z. It does this by patching around
the indicator with a rplacd in a manner similar to the way remprop works.
Table Building and Table Reference Functions
pair [x;y] : SUBR

The function pair has as value the list of pairs of corresponding
elements of the lists x and y. The arguments x and y must be lists of the
same number of elements. They should not be atomic symbols. The value is
a dotted pair list, i.e. ((a ^ (« 2 • B 2 )

pairfxjy] = [prog[u;v;m]

u:= x;
v:= y;

A [null[u] -* [null[v] ■+ return[m];T -* error[F2]]];

[null[v] error[F3]];

m:= cons[cons[car[u];car[v]];m ];

u:= cdr[u];

v:= cdr[v];

go[A]]

IV - 18

sassoc[x;y;u] : SUM functional

The function sassoc searches y, which is a list of dotted pairs,
for a pair whose first element that is x. If such a pair is found, the
value of sassoc is this pair. Otherwise the function u of no arguments
is taken as the value of sassoc .

sassoc[x;y;u] = [null[y] u[];eq[caarfy];x] -*■ car[y];

T sassocfx;cdr[y];u]]

subst [x;y;z] : SUBR

The function suhst has as value the result of substituting x for all
occurrences of the S-expression y in the S-cxpression z.

subst.[x;y;z] = [equal[y;z] -> x;

atom[z] -*• z;

T -»• cons[subst[x;y;car[z]];subst[x;y;cdr[z]]]]

sublis [x;y] : SUBR

Here x is a list of pairs.

C( u l • vp (u 2

(u.

n

v ))
n J J

The value of sublis [x;y] is the result of substituting each v for
the corresponding u in y.

sublis[x;y] = [null[x] -»■ y;

null[y] y;

T ■+ search [x;

Mf. j ]; equal [y; caar[ j] ] ];

A[[j];cdar[j]];

*[[j]l[atom[y] -► y;

T cons [sublis[x;car[y] ];sublis[x;cdr[y] ]]]]]]

List Handling Functions
append [x;y] :

SUBR

The function append combines its two arguments into one new list.
The value of append is the resultant list. For example,
append [(A B) (C) ] = (A B C)
append[((A)) (C D)] = ((A) C D)

append[x;y] = [null[x] y; T -*■ cons[car[x];append[cdr[x];y]]]

Note that append copies the top level of the first list; append is like
nconc except that nconc does not copy its first argument.
cone t x 2 >X-n>». ■ >x^1 : FSUBR pseudo-function

c°nc concatenates its arguments by stringing them all together on
the top level. For example,

cone [ (A (B • C) D); (F); (G H) ] = (A (B • C) D F G H).
cone concatenates its arguments without copying them. Thus it
changes existing list structure and is a pseudo-function. The value of
cone is the resulting concatenated list.
nconc [x;y] : SUBR pseudo-function

The function nconc concatenates its arguments without copying the
first one. The operation is identical to that of attrjb except that the
value is the entire result, (i.e. the modified first argument, x).

The program for nconc[x;y] has the program variable m and is as
follows:

nconc[x;y] = prog[[m];

£null[x] -*■ return[y]];

A [null[cdr[m]] •+• go[B]];
m:=cdr[m];
go[A];

B rplacd[m;y];
return[x]]

copy [x] : SUBR

This function makes a copy of the list x. The value of copy
is the location of the copied list.

copy[x] = [null[x] ■+• NIL;atom[x] x;T -*■ cons[copy[car[x]];
copy[cdr[x]]]]

reverse [-2] : SUBR

This is a function to reverse the top level of a list. Thus

reverse[(A B (C • D))] = ((C • D) B A))

reverse[£] = prog[[v];
u:=£;

A [null[u] -* return[v]];
v:=cons[car[u];v];
u:=cdr[u];
to [A]]

member [x;£] : SUBR predicate

If the S-expression x is a member of the list £, then the value of
member is *T*. Otherwise, the value is NIL.

member[x;£.] = [null[£] -»■ F;equal[x;car[£]] ■** T;

T member [x; cdr [-t]]]

length [x] : SUBR

The value of length is the number of items in the list x. The list

( ) or NIL has length 0.

IV - 21

efface[x;£] : SUBR pseudo-function

The function efface deletes the first appearance of the item x

from the list £.

efface[x;£] = [null[£] -*■ NIL;

equal [x;car[£]] -*• cdr[£];

T -*■ rplacd[£;efface[x;cdr[£]]]]

These four functionals apply a function, f, to x, then to cdr[x],
then to cddr[x], etc.

Functionals or Functions with Functions as Arguments
maplist [x;f] : SUBR functional

The function maplist is a mapping of the list x onto a new list f[x].
maplist[x;f] = [null[x] NIL;T cons [f [x] ;maplist[cdr[x] ;f]] ]
mapcon [x;f] : SUBR pseudo-functional

The function mapcon is like the function maplist except that the
resultant list is a concatenated one instead of having been created by
cons- ing.

mapcon[x;f] = [null[x] NIL;T -*■ nconc[f [x] ;mapcon[cdr[x] ;f]] ]
ma£[x;f] : SUBR functional

The function ma£ is like the function maplist except that the value
°f ma£ is NIL, and ma£ does not do a cons of the evaluated functions.
map is used only when the action of doing f[x] is important.

The program for map[x;f] has the program variable m and is the

following:

map[x;f] = prog[[m];
m: = x;

LOOP [null [m] -*■ return[NIL] ];

f[m];

m:= cdr[m];

go[LOOP]]

search [x;p;f;u] : SUBR functional

The function search looks through a list x for an element that has
the property p, and if such an element is found the function f of that
element is the value of search . If there is no such element, the function
u of one argument x is taken as the value of search (in this case x is,
of course, NIL).

search[x;p;f;u] = [null[x] -*• u[x];p[x] -*■ f[x];T -*■ search[cdr[x];p;f;u]]
Arithmetic Functions

We shall now list all of the arithmetic functions in the System. They
must be given numbers as arguments; otherwise an error condition will result
The arguments may be any type of number. A function may be given some
fixed-point arguments and some floating-poing arguments at the same time.

If all of the arguments for a function are fixed-point numbers, then
the value will be a fixed-point number. If at least one argument is a
floating-point number, then the value of the function will be a floating¬
point number.

plus [x^;...;x^j is a function of any number of arguments whose value
is the algebraic sum of the arguments.

difference [x;yj has for its value the algebraic difference of its
arguments.

minus[x] has for its value -x.

IV - 23

times [x.^;... ;x^] is a function of any number of arguments, whose
value is the product (with correct sign) of its arguments.

addl[x] has x+1 for its value. The value is fixed-point or floating¬
point, depending on the argument.

subl [x] has x-1 for its value. The value is fixed-point or floating¬
point, depending on the argument.

max i^;... ;x n ] chooses the largest of its arguments of its value.

Note that max[3;2.0]= 3.0.

min tx^...;x^] chooses the smallest of its arguments for its value.

recip [x] computes 1/x. The reciprocal of any fixed point number is
defined as zero.

quotient [x;y] computes the quotient of its arguments. For fixed-
point arguments, the value is the number theoretic quotient. A divide
check or floating-point trap will result in a LISP error.

remainder [x;y] computes the number theoretic remainder for fixed-
point numbers, and the floating-point residue for floating-point arguments.

divide [x;y] = cons[quotient[x;y]; cons [remainder[x;y];NIL]]

expt [x;y] = x^. If both x and y are fixed-point numbers, this is
computed by iterative multiplication. Otherwise the power is computed by
using logarithms. The first argument cannot be negative.

We shall now list all of the arithmetic predicates in the System.

They may have fixed-point and floating-point arguments mixed freely. The
value of a predicate is *T* or NIL.

lessp [x;y] is true if x <y, and false otherwise.

greaterp [x;y] is true if x > y.

zerop [x] is true if x=0, or if |x| < 3 x 10

onep [x] is true if j x-11 < 3 x 10

minusp [x] is true if x is negative.

numbergi [x] is true if x is a number (fixed-point or floating-point).

fixp [x] is true only if x is a fixed-point number. If x is not a
number at all, an error will result.

floatp [x] is similar to fixp[x] but for floating-point numbers.

equal [x;y] works on any arguments including S-expressions incorporating
numbers inside them. Its value is true if the arguments are identical.
Floating-point numbers must satisfy |x-y| < 3 x 10 .

The logical functions operate on 32 bit words. The only acceptable
arguments are fixed-point numbers. These may be read in as hexadecimal
or decimal integers, or they may be the result of a previous computation.

logor[x^;...;x n J performs a logical OR on its arguments.

logand [x^;. ..;x r ] performs a logical AND on its arguments.

logxortXjj...; x r ] performs an exclusive OR

(0 v 0 = 0 , 1 v 0 = 0 v 1 = 1, 1 v. 1 = 0).

leftshift [x;n] = x X 2 n . The first argument is shifted left by the
number of bits specified by the second argument. If the second argument is
negative, the first argument will be shifted right. ,

If the first argument is logical, a logical shift is done and the result

is logical. If the first argument is fixed-point, an arithmetic shift is
done and the result is fixed-point. If the first argument is floating¬
point, a floating shift is done and the result is floating-point,
array [arg] • SUBR pseudo-function

Provision is made in LISP 1.5 for allocating blocks or storage for data.
The data may consist of numbers, atomic symbols or other S-expressions.

The pseudo-function array reserves space for arrays, and turns the
name of an array into a function that can be used to fill the array or locate

any element of it.

IV - 25

Arrays may have up to three indices. Each element (uniquely specified
by its co-ordinates) contains a pointer to an S-expression.

array is a function of one argument which is a list of arrays to be
declared. Each item is a list containing the name of an array, its
dimensions, and the word LIST. (Non-list arrays are reserved for future
developments of the LISP system.)

For example, to make an array called alpha of size 7 x 10, and one
called beta of size 3x4x5 one should execute:

array[((ALPHA (7 10) LIST) (BETA (3 4 5) LIST))]

After this has been executed, both arrays exist and their elements
are all set to NIL. Indices range from 0 to n-1.

alpha and beta are now functions that can be used to set or locate

elements of these respective arrays.

To set alpha . . to x, execute -
alpha[SET;x;i;j]

To set alpha 3 4 to (A B C) execute -
alpha[SET;(A B C);3;4]

Inside a function or program X might be bound to (A B C), I bound to 3,
and J bound to 4, in which case the setting can be done by evaluating -
(ALPHA (QUOTE SET) X I J)

To locate an element of an array, use the array name as a function
with the coordinates as axis. Thus any time after executing the previous
example -

alpha[3;4] = (ABC)

IV - 26

Arrays are stored as lists originating in the property list of
the array name. Indexing is accomplished by a linear search for the
n** 1 element of the array list.

Input and Output

rea< * [ ] : SUBR pseudo-function

The execution of read causes one list to be read from the SI device.
The list that is read is the value of read .
print [x] : SUBR pseudo-function

The execution of print causes the S-expression x to be printed on
the LO device. The value of print is its argument.
punch [x] : SUBR pseudo-function

The execution of punch causes S-expression x to be punched in BCD
card images on the PO device. The value of punch is its argument.
prinl [x] : SUBR pseudo-function

prinl prints an atomic symbol without terminating the print line.

The argument of prinl must be an atomic symbol.
terpri [ ] : SUBR pseudo-function

terpri terminates the print line.
mprint [x i] : SUBR pseudo-function

The execution of mprint causes the S-expression x to be written
in 80 character records on device F:i. The F: device must be assigned to
a physical device by an !ASSIGN control card preceeding the I LISP control
card. The value of mprint is the list printed.

1 < i < 5

inread [i]

SUBR

pseudo-function

The execution of mread causes one S-expression to be read from
the F:i device. The value of mread is the S-expression read.

1 <_ i <_ 5 .

rewind[i] : SUBR pseudo-function

rewind [i] rewinds the F:i device.

The value of rewind is NIL.

1 <_ i <_ 5

backspace [i] : SUBR pseudo-function

The execution of backspace causes the F:i device to be backspaced
one record. Caution in the use of this function is recommended, for if
an S-expression to be read from an F: device is more than 80 characters,
then it will occupy more than one record on the F: device, and a single
backspace will not move the device all the way back to the beginning of
the S-expression. The value of backspace is NIL,

1 i i £ 5 .

Packing and Unpacking Characters

When a sequence of characters is to be made into either a print
name or a numerical object, the characters must be put one by one into a
buffer called BOFFO. BOFFO is. used to store the characters until they
are to be combined. It is not available explicitly to the LISP programmer,
but the character-packing functions are described in terms of theip effects
on BOFFO. At any point, BOFFO contains a sequence of characters. Each
operation on BOFFO either adds another character at the end of the sequence
or clears BOFFO, i.e., sets BOFFO to the null sequence. The maximum length
of the sequence is 120 characters; an attempt to add more characters will

cause an error.

The character-packing- functions arc:
pack [c] : SUBR pseudo-function

The argument of pack must be a character object, pack adds the
character c at the end of the sequence of characters in BOFFO. The
value of pack is NIL.

clearbuff [ ] : SUBR pseudo-function

clearbuff is a function of no arguments. It clears BOFFO and has
value NIL. The contents of BUFFO are undefined until a clearbuff has been
performed.

mknam [ ] : SUBR pseudo-function

mknam is a function of no arguments. Its value is a list of full
words containing the characters in BOFFO in packed BCD form. The last word
is filled out with blanks if necessary. After mknam is performed, BOFFO ;
is automatically cleared. Note that intern [mknam[ ]] yields the object
whose print name is in BOFFO.

numob [ ] : SUBR pseudo-function

numob is a function of no arguments. Its value is the numerical object
represented by the sequence of characters in BOFFO. (Positive decimal integers
from 0 to 9 are converted so as to point to the corresponding character object.)

unpack [x]: : SUBR pseudo-function

This function has as argument a pointer to a full word, unpack considers
the full word to be a set of 4 BCD characters, and has as value a list of
these characters ignoring all characters including and following the first

blank.

intern [pname] : SUBR pseud-function

This function has as argument a pointer to a PNAME type structure
such as

Its value is the atomic symbol having this print name. If it does
not already exist, then a new atomic symbol will be created.

The Character-Classifying Predicates

liter[c]: : SUBR predicate

liter has as argument a character object. Its value is T if the
character is a letter of the alphabet, and F otherwise.
digit [c]: : SUBR predicate

digit has as argument a character object. Its value is T if the
character is a digit between 0 and 9, and F otherwise.
opchar fc]: : SUBR predicate

opchar has as argument a character object. Its value is T if the
character is +, -,•■/, *, or =, and F otherwise.
dash [c]: : SUBR predicate

dash has as argument a character object. Its value is T if the character
is an 11-punch minus, and F otherwise.

The Character-Reading Functions

The character-reading functions make it possible to read characters
one by one from input.

There is an object CURCHAR whose value is the character most recently
read (as an object). There is also an object CHARCOUNT whose value is an
integer object given the column just read on the card, i.e., the column
number of the character given by CURCHAR. There are three functions which
affect the value of CURCHAR:

startread [ ]: : SUBR pseudo-function

startread is a function of no arguments which causes a new card to be
read. The value of startread is the first character on that card, or more
precisely, the object corresponding to the first character on the card. If
and end-of-file condition exists, the value of startread is $EOF$. The value
of CURCHAR becomes the same as the output of startread , and the value of
CHARCOUNT becomes 1. Both CURCHAR and CHARCOUNT are undefined until a
startread is performed. A startread may be performed before the current
card has been completely read.

advance[ ]: : SUBR pseudo-function

advance is a function of no arguments which causes the next character to
be read. The value of advance is that character. After the 72 n< * character
on the card has been read, the next advance will have value $EOR$. After
reading $EOR$, the next advance will act like a startread , i.e., will read
the first character of the next card unless an end-of-file condition exists.
Hie new value of CURCHAR is the same as the output of advance ; executing
advance also increases the value of CHARCOUNT by 1. However, CHARCOUNT is

undefined when CURCHAR is either $EOR$ or $EOF$.

endread[ ]:

SUBR

pseudo-function

endread is a function of no arguments which causes the remainder of
the card to be read and ignored, endread sets CURCHAR to $EOR$ and leaves
CHARCOUNT undefined; the value of endread is always $EOR$. An advance
following endread acts like a startread . If CURCHAR already has value
$EOR$ and endread is performed, CURCHAR will remain the same and endread
will, as usual, have value $EOR$.

Diagnostic Function

errorl [ ]: : SUBR pseudo-function

error1 is a function of no arguments and has value NIL. It should be
executed only while reading characters from a card (or tape]). Its effect
is to mark the character just read, i.e., CURCHAR, so that when the end
of the card is reached, either by successive advances or by an endread ,
the entire card is printed out along with a visual pointer to the defective
character. For a line consisting of ABCDEFG followed by blanks, a pointer
to C would look like this:

V

ABCDEFG

A

If errorl is performed an even number of times on the same character, the
A will not appear. If errorl is performed before the first startread or
while CURCHAR has value $EOR$ or $EOF$, it will have no effect. Executing
a startread before the current card has been completed will cause the
errorl printout to be lost. The card is considered to have been completed
when CURCHAR has been set to $EOR$. Successive endreads will cause the
errorl printout to be reprinted. Any number of characters in a given

line may be marked by errorl .

Miscellaneous Functions

trace [x] : SUBR pseudo-function

The argument of trace is a list of functions. After trace has
been executed, the arguments and values of these functions are printed
each time the function is entered recursively. The value of trace is
NIL. Special forms cannot be traced.
untrace [x] : SUBR pseudo-function

This removes the tracing from all functions in the list x. The value
of untrace is NIL.

obkeep [s] : SUBR pseudo-function

The argument of obkeep is a list of atom names which the programmer
wishes to keep. All other atomic symbols are removed from the system. The
value of obkeep is NIL.

reserved [ ] : SUBR pseudo-function

The execution of reserved causes the printing of all atoms on the
object list. The value of reserved is NIL.
space [x] : SUBR pseudo-function

space[*T*] causes all output to be double-spaced, space [NIL] restores
the spacing to its original status. The value of space is NIL.
eject [ ] : SUBR pseudo-function

eject [ ] causes a skip to the top of the next page of output. Its
value is NIL.

verbos [x] : SUBR pseudo-function

verbos [NIL] causes reclaim not to print its message whenever it is
called, verbos[*T*] restores reclaim's message. Its value is NIL.

count [n]

SUBR

pseudo-function

count [n] turns the cons counter on and resets, the .counter. After
n conses have been executed, a cons counter trap occurs, count [NIL]
turns the counter on so as to continue counting from the state it was
in when last turned off. The value of count is NIL.
uncount [NIL] : SUBR pseudo-function

uncount [NIL] turns off the cons counter. Its value is NIL.
speak [NIL] : SUBR pseudo-function

The value of speak [NIL] is the number of conses counted since the
counter was last reset.

error [x] : SUBR pseudo-function

error causes an error diagnostic to be printed along with the
S-expression x. The value of error is x.
prog2 [x;y] : SUBR

the value of prog2 is its second argument. It is used mainly to
perform two pseudo-functions.
prog2[x;y] = y

cpl[x] : SUBR

cpl copies its argument which must be a list of a very special type.

FULL WORD

FULL WORD

The copied list is the value of cpl .

IV - 34

gensym [ ] : SUBR

The function gensym has no arguments. Its value is a new, distinct,
and freshly created atomic symbol with a print name of the form G001,

G002, ..., G999.

This function is useful for creating atomic symbol when one is
needed; each one is guaranteed unique, gensym names are not permanent
and will not be recognized if read back in.

££lect[q;(q 1 e 1 );(q 2 e 2 );...;(q n e n );e] : FSUBR

The q^'s in select are evaluated in sequence from left to right until
one is found that

<\ ± = q>

and the value of select is the value of the corresponding e.. If no such ...

i

q^ is found the value of select is that of e.

tempus [ ] : SUBR pseudo-function

Executing this will cause a time statement to appear in the output.

The value is NIL.

reclaim [ ] : SUBR pseudo-function

Executing this will cause a garbage collection to occur. The value
is NIL.

pause [ ] : SUBR pseudo-function

pause [ ] is a no operation function. Its value is NIL.
dump [low;high;title] : SUBR pseudo-function

The first two arguments must be absolute hexadecimal addresses. .
dump causes memory to be dumped in hexadecimal from location low to
location high . The value of dump is NIL.

intern[x] : SUBR pseudo-function

The argument of intern must be a PNAME type of structure, that is,
a list of full words forming a print name. If this print name belongs
to an already existing atomic symbol, this is found, otherwise a new
one is created. The value of intern in either case is an atomic symbol
having the specified print name.
remob [x] : SUBR

This removes the atom x from the object list. It causes the symbol
and all its properties to be lost unless the symbol is referred t° by
active list structure. When an atomic symbol has been removed, subsequent
reading of its name from input will create a different atomic symbol. Its
value is NIL.

traceset[x] : EXPR pseudo-function

traceset is a debugging aid. The argument x should be a list of
functions names. Each of these functions must be an EXPR which has a PROG
on the top level, traceset modifies the definition of the function so
that every SETQ on the first level inside the PROG is traced.

For example, suppose a PROG has the statement (SETQ A X). At run
time, if this statement is executed while X has the value (U V), then in
addition to setting the variable A, the function will print out.

(A =)

(U V)

untraceset [x] is part of the traceset package. Its argument is a list of
functions whose definitions are to be restored to their original condition.

IV - 36

printprop [x] : EXPR pseudo-function

If x is an atomic symbol, all of its properties will be printed in
the output. Nothing is changed by printprop .
punchdef [x] : EXPR pseudo-function

If x is a list of atomic symbols, each one having an EXPR or FEXPR
will have its definition punched out. Nothing is changed.

APVAL's

APVAL

value

BLANK

CHARCOUNT

COMMA

CURCHAR

DOLLAR

EOF

EOR

EQSI6N

F

LPAR

NIL

PERIOD

PLUSS

RPAR

SLASH

STAR

T

(BCD blank)

(character count during reading of characters)

(current character during reading of characters)

$

$EOF$

$EOR$

NIL

(

NIL

)

/

*

★•j 1 *

V. USER OPERATING PROCEDURES

5.1 The LISP Program

A program for execution in LISP consists of a sequence of
doublets. . The first list or atomic symbol of each doublet is in¬
terpreted as a function. Hie second is a list of arguments for the
function. They are evaluated by evalquote , and the value is printed.

The program should be terminated by the atomic symbol STOP. There is
no particular card format for writing LISP. Card boundaries are

ignored. ' ,

* s » ' ‘

If ! tfie liser? requires input data for his LISP <program, this d'ata

. i ' ’

should begi^on the next cqjrd. immediately j^ftei^ the 9 ard witty the

° ■ * * . • ■ 1 I j

STOP atomic ^s^inbol. The end of data,should*be indicated by ( eit!hei“ a

i : i ; . i 1 j | 1 ’

\ ! j \ ! ,

!EOp or a !I*IN carijl. ! 1 ’’

5.2 Tape Operations

r

The functions rewind , mprint , mread, 'and backspace are designed
to allow the user access to tape and other physical devices. Specifically,
they use the user DCB's F:l, F:2, F:3, F:4, and F:5. If used, the F:

devices must be assigned by IASSIGN control cards preceeding the !LISP

<

control card. *

5.3 System Messages '

Translation Phase

When the translation phase is initiated, the following message appears
as the heading.

* LISP 1.5

* AVAILABLE MEMORY

* FREE STORAGE = XXXXX (WORDS)

* FULL WORD STORAGE = XXXX (WORDS)

* PUSH-DOWN STACK = XXXX(WORDS)

Following this message is the source listing. Errors encountered
during the translation phase are discussed under Input/Output error
messages. Normally, an error in the translation phase will cause the
interpreter to be bypassed. In this case, the following message
would be found.

ERROR IN TRANSLATION PHASE INTERPRETER ABORTED
Interpreter Phase

The interpreter phase is begun by:

LISP 1.5 SYSTEM INITIATED 10:22 JUL 4,'69

When the interpreter is entered, it prints:

FUNCTION EVALQUOTE HAS BEEN ENTERED, ARGUMENTS.,
followed by the two arguments to evalquote .

At completion of the interpretation of a doublet, evalquote prints:
END OF EVALQUOTE, VALUE IS.,
followed by the value.

When the interpreter phase is. completed:

LISP 1.5 SYSTEM TERMINATED 10:25 JUL 4,'69
Garbage Collector

When the garbage collector is called, it prints the following;
RECLAIM m FREE n FULL

where m is the number of free words collected, and n is the number of
full words collected.

Error Diagnostics

When an error occurs, a diagnostic giving the nature of the error is
printed out. The diagnostic gives the type of error and in some cases

additional information about the error. If the DB option was specified,
then a backtrace is also printed. This is a list of functions that were
entered recursively but not completed at the time of the error.

In most cases, the program continues with the next doublet if in
debug mode. If not in debug mode, control is returned to the monitor.
Certain errors are fatal, and control is always passed to the monitor.
Interpreter Errors:

FUNCTION NOT DEFINED - APPLY

This occurs when an atomic symbol, given as the first argument
to apply , does not have a definition either on its property list or on
the a-list of apply . The atomic symbol immediately following the
diagnostic is the undefined symbol.

FUNCTION NOT DEFINED - EVAL

Eval expects the first object on a list to be evaluated to be an
atomic symbol. This frequently occurs when a parenthesis miscount causes
the wrong phase to be evaluated. The undefined symbol is printed.

WRONG NUMBER OF ARGUMENTS

A function expecting a fixed number of arguments was passed the
wrong number of arguments.

UNBOUND VARIABLE - EVAL

The atomic symbol in question is not bound on the a-list for eval
nor does it have an APVAL. The undefined symbol is printed.

CONDITIONAL UNSATISFIED - EVCON

None of the propositions following COND are true.

INVALID GO ARGUMENT

Go refers to a point not labelled.

VARIABLE UNBOUND - SET

Either set or setq is attempted on a nonexistent program variable.
The undefined symbol is printed.

Character-Handling Errors:

BUFFER OVERFLOW - PACK

FLOATING POINT NUMBER OUT OF RANGE - NUMOB
NUMERIC CONSTANT MISFORMED - NUMOB
Miscellaneous Errors:

CONS COUNTER TRAP

ARGUMENT LISTS NOT SAME LENGTH PAIR

Pair is used by the interpreter to bind variables to arguments.

If a function is given the wrong number of arguments, this error may
occur.

ARITHMETIC OVERFLOW
SYSTEM STACK OVERFLOW

The push-down stack is the memory device that keeps track of the
level of recursion. When recursion becomes very deep, this error may
occur. Non-terminating recursion will cause this error.

INVALID DUMP ARGUMENT
INVALID TRACESET ARGUMENT
Garbage Collector Errors:

FATAL ERROR - RECLAIM

This error occurs only when the system is so choked that it cannot
be restored. Control goes to the monitor.

Arithmetic Errors:

ILLEGAL NUMBER OF DIMENSIONS
WRONG NUMBER OF SUBSCRIPTS
SUBSCRIPT NOT NUMERIC
SUBSCRIPT OUT OF RANGE
INVALID ARGUMENT - EXPT

First argument cannot be negative.

INTEGER OVERFLOW - EXPT
REAL OVERFLOW - EXPT

ARITH FUNCTION GIVEN NON-NUMERIC ARGUMENT
Input - Output Errors:

PRIN1 ARG IS NON-ATOMIC

FIRST OBJECT ON INPUT LIST ILLEGAL - READ

This error occurs when the read program encounters a character
such as a ")" or out of context. This occurs frequently when there
is a parenthesis miscount.

CONTEXT ERROR - READ

The dot-notation was not used properly.

INVALID CHARACTER - READ
HEX CONSTANT MISFORMED
ILLEGAL $$ FORMAT
END OF FILE - READ

INVALID TAPE FUNCTION ARGUMENT

5.4 Control Card Options

The options listed below may be specified on the !LISP control

card.

DB - debug - After any error, a backtrace is given. Then execution
is continued with the next doublet.

NODB - no debug, default - After an error, the execution is terminated
and control is returned to the monitor.

LS - list source, default

NOLS - no list source

GO - Begin execution of the first doublet even if translation phase
errors occur.

NOGO - No execution phase.

If neither GO nor NOGO is specified, then the execution phase
will begin if no translation phase errors occur.

VI. CONCLUSIONS AND FUTURE CONSIDERATIONS

An interpretive system capable of translating the prograpning
language LISP 1.5 has been successfully implemented on the SDS SIGMA 7.
There are no restrictions to the language in this implementation. The
mathematical language LISP, with sufficient extensions to make it useful
in a programming environment, is now accessible to SIGMA 7 users. The
language's primary use has been in the field of artificial intelligence
research. It has been used for symbolic calculations in calculus,
mathematical logic, game playing, and other fields of artificial intelli¬
gence. It has also been useful in further understanding of information
structures in general. It is hoped that the implementation of LISP on
the SIGMA 7 might allow more people access to the language, so that its
study and use might prove more profitable.

In the future, the present implementation will be expanded to
include a compiler, assembler, and loader. The compiler may be called
by the user to translate any function from LISP into machine language.

When this is done, the function should be much faster in execution speed,
for the interpreter will link the source arguments to the compiled function
rather than execute it interpretively. The assembler and loader will allow
the LISP user to include assembly language subroutines which he himself has
written. These additions should improve the speed of the LISP system as
well as add to its flexibility.

APPENDIX I
LISP 1.5 FUNCTIONS

The functions

that are marked by an asterisk are

new

functions or

functions that are

different from the functions with ■

the :

same name in

M.I.T. 7090 LISP 1,

.5. See Section 4.2 for details on

all

functions.

ADD1

♦GENSYM

PROG2

ADVANCE

GET

PROP

AND

GO

PUNCH

APPEND

GREATERP

PUNCHDEF

APPLY

♦HEAD

QUOTE

♦ARRAY

INTERN

QUOTIENT

ATOM

' LABEL

READ

ATTRIB

♦LEFTSHIFT

RECIP

♦BACKSPACE

LENGTH

RECLAIM

CAR

LESSP

REMAINDER

CDR

LIST

REMFLAG

CLEARBUFF

LITER

REMOB

CONC

LOGAND

REMPROP

CONS

LOGOR

♦REPLHD

COPY

LOGXOR

♦REPLTL

COUNT

MAP

♦RESERVED

CPI

MAPCON

RETURN

CSET

MAPLIST

REVERSE

CSETQ

MAX

REWIND

DASH

MEMBER

RPLACA

DEFINE

MIN

RPLACD

DEFLIST

MINUS

SASSOC

DIFFERENCE

MINUSP

SEARCH

DIGIT

MKNAM

SELECT

DIVIDE

♦MPRING

SET

DUMP

♦MREAD

SETQ

EFFACE

NCONC

SPACE

EJECT

NOT

SPEAK

ENREAD

NULL

STARTREAD

EQ

NUMBERP

SUB1

EQUAL

NUMOB

SUBLIS

ERROR

♦OBKEEP

SUBST

ERROR1

ONEP

♦TAIL

EVAL

OPCHAR

♦TEMPUS

♦EVALQUOTE

OR

TERPRI

EVLIS

PACK

TIMES

EXPT

PAIR

TRACE

♦FIX

♦PAUSE

TRACESET

FIXP

PLUS

UNCOUNT

FLAG

PRIN1

UNPACK

♦FLOAT

PRINT

UNTRACE

♦FLOATP

PRINTPROP

UNTRACESET

FUNCTION

PROG

VERBOS
ZEROP ‘