>>37<<5552 >>37<>16<< >>37<<5552 44444 s>>37<<0 >>16<>12<< >>16<>16<< >>37<<242>>37<< >>37<<5552 >>17<<000>>17<< 11>>37<<11 >>37<>37<<55>>15<~~>60<<
LISP is a source language for writing algorithms. Unlike
most other languages, in which a source program consists of
a sequence of instructions to be executed in a certain
order, a LISP program usually (but not always) consists of a
collection of function definitions.
The basic object in LISP is a branching-tree type of
structure called an S-expression. All function definitions,
function arguments, function values, programs, instructions,
variables, constants, and data are S-expressions. At each
node of an S-expression there are two branches. The branches
eventually terminate in atoms. An S-expression is thus
defined recursively - it is either an atom or the concatena-
tion of two S-expressions.
o
lambda o
o o
x nil nil
o
times o
2 o
x o
x nil
fig. 1 - an S-expression
In the S-expression of figure 1, lambda, x, nil, times,
and 2 are atoms. The S-expression is the concatenation of
the S-expression lambda, which is an atom, with another
concatenation.
There is a notation for transmission of S-expressions
between LISP and the outside world. An atom is simply
spelled out. A concatenation is written as a left parenthe-
sis, the S-expression on the left side, a period, the S-
expression on the right side, and a right parenthesis. The
S-expression of figure 1 could be written
(lambda.((x.nil).((times.(2.(x.(x.nil)))).nil)))
j
Almost all S-expressions that are commonly used have a
chain of branches going off to the right, with the atom nil
at the end. From each node an S-expression hangs on the
left. Such an S-expression is called a list.
o
a o
b o
x o
y o
z nil
fig. 2 - a list
There is a special notation for lists, consisting of a
left parenthesis, the items of the list with spaces separat-
ing them, and a right parenthesis. Using list notation, the
S-expression of figure 2 is written
(a b x y z)
and that of figure 1 is written
(lambda (x) (times 2 x x))
Either format is permissible for input. In typing out S-
expressions, LISP uses list notation wherever possible.
There are two types of atoms. Numbers consist of one or
more digits, with or without a minus sign. Atomic symbols
contain at least one non-numeric character.
f
The three most basic functions in LISP are car, cdr, and
cons. These three, along with over 60 others, exist as
subroutines in the LISP program.
Given a nonatomic S-expression as an argument car finds
the left half. Cdr finds the right half.
car of (a.b) = a
cdr of (a.b) = b
Cons takes two arguments and concatenates them.
cons of a and b = (a.b)
Note that the car of a list is its first element, and the
cdr is the list of the remaining elements. The list of no
elements is the atomic symbol nil.
car of (a b c) = a
cdr of (a b c) = (b c)
cdr of (a) = nil
The cons of an S-expression and a list is the list with
the S-expression tacked onto the front.
cons of a and (b c) = (a b c)
9
LISP does arithmetic with the following functions. All
arguments must be numbers.
Plus takes any number of arguments and calculates their
sum.
Minus takes any number of arguments and calculates their
alternating sum, with the sign of the last argument
negative. Hence minus of one argument is its negation,
and minus of two arguments is their difference.
Times takes any number of arguments and calculates their
product.
Logand returns the bitwise and of its arguments.
Logor returns the bitwise inclusive or of its arguments.
Logxor returns the bitwise exclusive or of its arguments.
Add1 takes one argument and adds one to it.
Sub1 takes one argument and subtracts one from it.
Quotient takes two arguments and returns the quotient of
the integer division of the first by the second.
Remainder takes two arguments and calculates the remain-
der of the integer division of the first by the
second.
>>17<< LISP uses the atomic symbols t and nil to represent truth
and falsehood, respectively. Decisions are made by functions
called predicates. A predicate applies a test to its
argument and returns t or nil depending on the result.
Atom returns t if its argument is an atom (number or
atomic symbol) and nil if it a concatenation.
Numberp returns t only if its argument is a number. It
returns nil if it is an atomic symbol or a concatena-
tion.
Null returns t if its argument is nil, and returns nil
otherwise.
Equal takes two arguments and returns t if they have the
same structure, i.e. if they would look alike if
printed out.
Eq takes two arguments and returns t if they are exactly
the same. The difference between equal and eq is
explained later.
The argument of zerop must be a number. It returns t if
that number is plus zero.
The argument of minusp must be a number. It returns t if
that number is negative. Minus zero is negative.
Greaterp takes two numeric arguments and returns t if the
first is algebraically strictly greater than the
second.
4 Predicates are usually used with cond, the decision
making function. Cond takes an indefinite number of argu-
ments, called clauses, each of which is a list of one or
more (typically two) items. The first item of each clause is
the antecedent. The remaining items (if any) are conse-
quents. The clauses are examined one at a time until an
antecedent is found to be true (typically t, anything
different from nil will suffice). The corresponding conse-
quents are evaluated, and cond returns the value of the last
one (or, if there are no consequents, cond returns the value
of the antecedent). If the value of an antecedent is nil,
cond goes on to the next clause. If it runs out of
arguments, an error message is printed. In the examples
which follow, conditionals will be written in the "pure"
form with one consequent per clause. Programs may frequently
be shortened by using a less rigid format.
Logical quantities are manipulated with the functions and
and or. Each takes an indefinite number of logical arguments
and returns t if all of them or one of them, respectively,
is true. There is no function named not, but null may be
used to negate logical quantities. Remember that logand and
logor are used with numerical quantities, and and or with
logical ones.
Atomic symbols have the property that they may "stand
for" things. The thing for which an atomic symbol stands is
called its value. It may be any S-expression, atomic or
otherwise. The value of an atom may be the atom itself, as
is the case with t and nil. When an atom has a value, it is
said to be bound to that value. Not all atoms are bound. The
predicate valp may be used to determine whether an atomic
symbol has a value.
The function setq is used to bind atomic symbols. The
first argument is the symbol, the second is the value. Any
previous value of the symbol is lost. Setq is an example of
a pseudo-function. It is used for its effect rather than its
value. Pseudo-functions, like all other functions, must
return values, but the value is usually ignored. Setq
returns its second argument.
>>53<<
In LISP function calls are written as S-expressions,
using a variation of Polish notation. The S-expression used
is a list containing the function as the first item and the
arguments as the remaining items. Every function must
therefore be able to be written as an S-expression. For this
purpose, associated with each internal function in LISP is
an atomic symbol with the same name. The value of the symbol
is a number with an invisible flag giving the LISP program
the information it needs to call the subroutine.
Suppose, for example, that x stands for a and y stands
for (b c), and one wishes to take the cons of x and y,
obtaining (a b c). The atomic symbol cons is used, and the
call is the S-expression (cons x y). Note that the car of a
function call is the function, and the cdr is the argument
list. The procedure by which the S-expression (cons x y) is
transformed into (a b c) is called evaluation, and is the
most important procedure in LISP. Evaluation of a number
gets the number itself. Evaluation of an atomic symbol gets
the symbol's value. Evaluation of a nonatomic S-expression
(which must be a list) causes the arguments to be evaluated
(in most cases), and their values sent to the function.
Whether the arguments of a function are evaluated or not is
a property of the function. Except where otherwise speci-
fied, all functions have their arguments evaluated.
Since the arguments of functions are evaluated, they may
be other function calls, enabling functions to be nested
within each other. For example, to take the car of the cdr
of the car of whatever x is bound to, evaluate
(car (cdr (car x)))
If x evaluates to (1.3), then
(plus (minus (car x)) 5 (cdr x))
evaluates to 7.
Evaluation may be stopped with the function quote. Quote
takes one argument and returns it without evaluation. To
find the cons of a and (b c), obtaining (a b c), evaluate
(cons (quote a) (quote (b c)))
LISP will evaluate (quote a) to a and (quote (b c)) to (b c)
before sending them to cons. Evaluating (cons a (b c)) would
cause the value of c to be sent to the function b, and the
value of a concatenated with the result.
When writing LISP programs, great care must be taken to
evaluate the right things and quote the right things.
Following are some of the important exceptions to the
rule that all functions evaluate all arguments.
The function setq evaluates its second argument but not
its first. To increase the numerical value of x by one,
evaluate
(setq x (add1 x))
The function setqq is similar to setq but evaluates
neither argument. To bind x to (a b c), evaluate
(setqq x (a b c))
Setqq is usually used for defining constants at the top
level. For manipulating prog variables, setq is usually
required.
The function cond does not evaluate its arguments direct-
ly but evaluates the antecedents and consequents separately.
The antecedent of each argument is evaluated until one is
found to be true. The consequents are then evaluated.
The functions and and or evaluate only enough arguments
to determine the result. As soon as or finds a true
argument, or and finds a false one, all remaining arguments
are left unevaluated. This is useful in some applications.
Prog (see below) also has an unusual way of evaluating
its arguments.
An example of a conditional
(cond ((atom x) (quote a))
(y (quote (a b)))
(t (quote (a b c))))
evaluates to a if the value of x is atomic, or
(a b) if the value of y is not nil, or
(a b c) otherwise.
The third case works because t is bound to itself.
o
In addition to functions written as subroutines, func-
tions may be written by the programmer. These functions are
interpreted by LISP when they are called. A programmed
function is a list of three items, the first of which is
usually the atomic symbol lambda. Lambda is not a subroutine
but a special symbol which LISP recognizes. It has no value.
Like subroutines, programmed functions are usually given
names, and an atomic symbol of the same name is given a
value of the function. Functions defined with lambda are
called expr's and always have their arguments evaluated.
Suppose the symbol foo has a value of
(lambda (x) (times 2 x x))
Lambda identifies it as an expr, (x) is the dummy symbol
list, indicating that it takes one argument called x, and
(times 2 x x) is the actual definition. This function takes
one argument, squares it, multiplies by 2, and returns the
result.
(foo (plus 1 2)) evaluates to 18
(foo (foo (foo 1))) evaluates to 128
A predicate symbp to detect whether an S-expression is an
atomic symbol could be written as
(lambda (x) (and (atom x) (null (numberp x)))), or as
(lambda (y) (cond
((numberp y) nil)
((atom y) t)
(t nil)
))
This predicate, if defined, could be used exactly as one
would use atom or numberp.
Programmed functions may call any functions, including
themselves.
A function fact to find the factorial of a number could
be written as
(lambda (x) (cond ((zerop x) 1)
(t (times x (fact (sub1 x))))))
(fact 4) evaluates to 24
(fact (fact 3)) evaluates to 720
y
When LISP attempts to evaluate a function call, that is,
a nonatomic S-expression, it evaluates the function as many
times as necessary (usually once) until a subroutine or a
list beginning with lambda, nlamda, or label is found. If
lambda is found, the arguments are evaluated and paired with
the symbols on the dummy symbol list. Any old values of
these symbols are saved, and the symbols are bound to the
evaluated arguments. The definition is then evaluated and,
after restoring the previous bindings of the dummy symbols,
the value of the definition is returned as the value of the
call. Example - suppose that the second definition of symbp
is used. Find out whether a is a symbol.
symbp evaluates to (lambda (y) (cond ((numberp y) nil)
((atom y) t) (t nil)))
y evaluates to (1 2 3). This is its previous value
from some unrelated calculation.
Evaluate (symbp (quote a)).
The function symbp is evaluated to
(lambda (y) (cond ((numberp y) nil) ((atom y) t) (t nil)))
LISP recognizes this as an expr, so it evaluates each
argument
(quote a) is evaluated - its value is a
The dummy symbol list is (y). The old value of y, (1 2 3),
is saved.
y is bound to the evaluated argument.
y now evaluates to a.
(cond ((numberp y) nil) ((atom y) t) (t nil)), the
definition of the function, is evaluated. Cond, unlike most
functions, does not evaluate its arguments immediately, so
the arguments sent to cond are
((numberp y) nil), ((atom y) t), and (t nil).
(numberp y), the first antecedent, is evaluated.
Numberp evaluates its argument.
y is evaluated, obtaining a, which is sent to numberp.
a is not a number, so numberp returns nil.
cond goes to the next antecedent.
(atom y) is evaluated.
y evaluates to a, which is an atom, so atom returns t.
The second clause is true, so its consequent, t, is
evaluated.
t is bound to itself, so the value of the call to cond
is t.
y is restored to (1 2 3), its old value, and t is returned
as the value of (symbp (quote a)).
Hence a is a symbol.
d Functions like symbp and fact, being values of atomic
symbols, are relatively permanent and may be used repeat-
edly. When one wishes to use a function only once, it is not
necessary to give it a name and bind the atomic symbol of
the same name to it. The function itself may be used. Hence
((lambda (y) (cond ((numberp y) nil) ((atom y) t)
(t nil))) (quote a))
may be used to determine that a is a symbol.
If a function is recursive, however, it must be given a
name so that it may use that name in calling itself. An
attempt to calculate 4 factorial by evaluating
((lambda (x) (cond ((zerop x) 1) (t (times x (fact
(sub1 x)))))) 4)
would not work because fact has no value.
((label fact (lambda (x) (cond ((zerop x) 1) (t (times
x (fact (sub1 x))))))) 4)
will work. Label is used to temporarily bind the atomic
symbol fact to the definition of the factorial function.
A list consisting of label, a symbol, and a function is
equivalent to the function alone, except that the symbol is
temporarily bound to the function. The function can there-
fore call itself by referring to the symbol with which it is
labelled. The previous value of the symbol is restored when
the function is finished. Label should be used only with
expr's.
To write a function which does not have its arguments
evaluated, use nlamda instead of lambda. Functions defined
in this way are called fexpr's. In addition to not evaluat-
ing their arguments, they also have a different way of
binding arguments to the dummy symbol list. A fexpr may take
any number of arguments. There must be exactly one symbol on
the dummy symbol list. It will be bound to the list of all
of the arguments. Functions which do not evaluate their
arguments are usually used only on the top level for
"utility" purposes. Other functions do not, as a rule, call
them, and they are not usually recursive. Prindef, dex, fix,
trace, and untrace are examples of built-in functions which
do not evaluate their arguments.
h
Expr's may be conveniently defined by means of the
function dex. Dex takes three arguments and does not
evaluate them. The first is the name of the function to be
defined, the second is the dummy symbol list, and the third
is the definition.
(dex symbp (y) (cond ((numberp y) nil)
((atom y) t) (t nil)))
evaluates to symbp and defines symbp to be the expr
described above.
Programs in the usual sense may be written with the
functions prog, return, and go. Prog takes an indefinite
number of arguments and does not immediately evaluate them.
The first argument is the temporary variables list. The
value of each symbol on this list is saved, and each symbol
is bound to nil. These symbols may be used for temporary
storage by the program, and will have their original values
restored upon exit. Of the remaining arguments, atomic
symbols are interpreted as address tags and nonatomic
expressions as instructions. The previous values of the tags
are saved, and the tags are bound to pointers to the
appropriate locations in the program. The instructions are
then evaluated in sequence, and the values ignored. If the
program runs out of instructions, nil is returned. If the
function return is called, its evaluated argument is
returned as the value of the program. In either case the
temporary variables and address tags are restored. The
function go, with an address tag as an argument, causes a
transfer of control to the indicated address. Prog, like
other functions, may be nested. Return and go always refer
to the most recently entered prog. Program variables of
nested progs are saved independently at each level. On the
top level of a prog the rules for use of cond are relaxed.
If cond runs out of clauses, rather than giving an error
message it simply goes to the next statement of the program.
A typical use of prog is in the function reverse, which
reverses a list. Reverse could be defined by
(dex reverse (x) (prog (y)
z (cond ((null x) (return y)))
(setq y (cons (car x) y))
(setq x (cdr x))
(go z)
))
This takes advantage of the facts that the program variable
is initially bound to nil and that a cond may run out of
clauses in a prog.
,
LISP keeps a symbol table similar to those used by
debuggers and assemblers, containing an entry for each
symbol, whether it has a value or not. This table initially
contains
one entry for each subroutine, with a name the same as
that of the subroutine and a value of a number with an
invisible flag.
t and nil, with values of themselves
space, lpar, rpar, etc., with values of atomic symbols
whose names are the indicated characters.
lambda, nlamda, and label, with no values. These are
flags used internally by the LISP program.
Whenever an atomic symbol not appearing in the table is
read in, it is placed in the table with no value. It may
later be given a value.
The value of an atomic symbol is stored on the car of
that symbol. Taking the car of an atomic symbol gets its
value. It is illegal to take the car of a symbol with no
value, and it is very dangerous to take the car or cdr of a
number. The cdr of a symbol is normally nil, but any S-
expression may be stored there by the programmer.
f
S-expressions which look alike may occupy different
locations of memory. Expressions may also be different but
share common sub-expressions. Whenever an S-expression is
read in, a fresh copy of it is created in memory, even if
another copy already exists. Only atomic symbols are in
unique locations. For example, reading and evaluating
(setq x (quote ((a.b) (c.d)))) and
(setq y (quote ((a.b) (c.d))))
leaves memory looking like this -
x y
o o
o o o o
a b o o nil
c d
fig. 3 - non-identical S-expressions
x and y will both print out as ((a.b) (c.d)), and will
satisfy the predicate equal, but they will not be identical.
The predicate eq may be used to test for exact identity
between two S-expressions. In the example above, (eq x y)
would evaluate to nil. If x and y had been bound by
(setq x (quote ((a.b) (c.d)))) and
(setq y x)
they would be identical and would satisfy eq.
Equal could have been written in terms of eq as
(dex equal (x y) (cond
((and (numberp x) (numberp y)) (zerop (logxor x y)))
((or (numberp x) (numberp y)) nil)
((and (atom x) (atom y)) (eq x y))
((or (atom x) (atom y)) nil)
(t (and (equal (car x) (car y)) (equal (cdr x) (cdr y))))
))
>>17<< There are two S-expression modifying functions, rplaca
and rplacd, each taking two arguments and evaluating both.
They replace the car and cdr, respectively, of the first
argument with the second argument, and return the modified
first argument. If x and y are bound as in figure 3, (rplacd
(car x) (quote q)) removes the dotted line in the figure and
replaces it with a pointer to the atomic symbol q. It
returns (a.q), its modified first argument. The value of x
is now ((a.q) (c.d)). The value of y is not changed. If y
had been bound by (setq y x), so that its value was
identical with that of x, it too would have been changed.
Since the car of an atomic symbol is its value, rplaca may
be used to bind symbols, and rplacd may be used to store S-
expressions on the cdr of a symbol.
h
Other S-expression manipulating functions
Caar, cadr, cdar, cddr, and caddr are compositions of car
and cdr. They could have been defined by
(dex caar (x) (car (car x)))
(dex cadr (x) (car (cdr x)))
(dex cdar (x) (cdr (car x)))
(dex cddr (x) (cdr (cdr x)))
(dex caddr (x) (car (cdr (cdr x))))
For example, the cadr of (a b c) is the car of the cdr of (a
b c), or b. Caddr gets the third item from a list.
List takes (and evaluates) an indefinite number of
arguments and returns the list of them. List and cons are
the two functions that are used to create complex S-
expressions out of small ones.
(list 1 (cons (quote a) (quote b)) (plus 1 2 3))
evaluates to (1 (a.b) 6)
(list (quote (a b c)) (quote (d e f)))
evaluates to ((a b c) (d e f))
Append takes two arguments, which must be lists, and
appends them.
(append (quote (a b c)) (quote (d e f)))
evaluates to (a b c d e f)
Append makes a copy of the first list in order to avoid
modifying it. Append could have been defined by
(dex append (x y) (cond
((null x) y)
(t (cons (car x) (append (cdr x) y)))
))
Note that append and list are very different.
Nconc is the same as append except that it does not copy
its first argument but merely changes the nil at the end of
the first list to the second list. In doing so the first
list is permanently modified. Nconc could have been defined
by
(dex nconc (x y) (cond
((null x) y)
4 (t (prog (z)
(setq z x)
a (cond ((null (null (cdr z))) (go b))
(rplacd z y)
(return x)
b (setq z (cdr z))
(go a)
))))
Reverse takes one argument, which is a list, and reverses
it. It could have been defined by
(dex reverse (x) (prog (y)
a (cond ((null x) (return y)))
(setq y (cons (car x) y))
(setq x (cdr x))
(go a)
))
Subst takes three arguments and substitutes the first for
all appearances, on all levels, of the second in the third.
The third argument is not actually modified. Subst could
have been defined by
(dex subst (x y z) (cond
((equal y z) x)
((atom z) z)
(t (cons (subst x y (car z)) (subst x y (cdr z))))
))
Sassoc takes three arguments and looks up the first in
the second, which is a special type of table called an
association list. An association list is a list of dotted
pairs of atomic symbols with the S-expressions associated
with them. For example, to keep a table with the information
x=1 y=2 z=3
and not bind x, y, and z to these values, one could bind tab
to
((x.1) (y.2) (z.3))
Sassoc can look through a table in this format. It returns
the first pair which has a car identically equal to the
first argument.
(sassoc (quote y) tab no) evaluates to (y.2)
w The third argument is a function of no variables which is
called if the item is not found.
(sassoc (quote z) tab (quote (lambda nil
(quote (not found)))))
evaluates to (z.3). If z had not been found, (not found)
would have been returned as the value of the call to sassoc.
In order to save space in memory, a number may be used as
the third argument. If the search fails the uaf error
message will be printed along with the number. Sassoc could
have been written as
(dex sassoc (x y z) (cond
((null y) (z))
((eq x (caar y)) (car y))
(t (sassoc x (cdr y) z))
))
Length takes one argument, which is a list, and returns
its length, a number. It could have been defined by
(dex length (x) (cond
((null x) 0)
(t (add1 (length (cdr x))))
))
Nth takes two arguments, the first a number and the
second a list. It returns the list with the first n items
removed. Nth could have been defined by
(dex nth (n x) (cond
((greaterp 1 n) x)
(t (nth (sub1 n) (cdr x)))
))
Other predicates
Member takes two arguments, the second of which is a
list, and returns t if the first argument is a member of
that list. Equal is used for the comparison, so any S-
expression may be tested. The second argument is searched on
the top level only. Member could have been defined by
(dex member (x y) (cond
((null y) nil)
((equal x (car y)) t)
>>35<< (t (member x (cdr y)))
))
I/O operations
Read takes no arguments. It reads one S-expression from
the typewriter or a text file and returns that S-expression.
(read) evaluates to (a b c d) if the latter is typed in.
Prin1 takes one argument, and prints it or writes it on a
file with no extra punctuation. The value returned is the
original argument.
Print prints or writes its argument preceded by a
carriage return and followed by a space. The argument is
returned.
(print (quote (a b c))) prints out "
(a b c) " and returns (a b c)
Terpri prints or writes a carriage return. It takes no
arguments and returns nil.
Miscellaneous functions
Stop takes no arguments. It returns to the control
program (see below) for a change of input source, output
destination, etc.
Gensym takes no arguments. Each call to gensym creates a
new atomic symbol as if it had been read in and returns that
symbol. The names of the symbols are g001, g002, etc.
Eval takes one argument and returns its value. This means
that the argument is actually evaluated twice. If x is bound
to (cons 1 3), the value of (eval x) is (1.3), whereas the
value of x alone is (cons 1 3).
Apply takes two arguments, a function and an argument
list for the function. The function is called with the given
arguments. If the function is one which normally evaluates
all its arguments, they will not be evaluated again, but
simply taken from the second argument to apply, which was,
of course, evaluated already.
(apply (quote cons) (quote (a b))) sends a and b,
without further evaluation, to cons, thereby returning
(a.b).
>>16<<
Trace takes any number of arguments and does not evaluate
them. Each argument should be the name of an expr or fexpr.
Each function is traced, or modified so that it prints out
its name and evaluated arguments on entry, and its name and
returned value on exit. Nested or recursive functions cause
the printouts to occur in proper order at each entry and
exit.
If fact initially had a value of
(lambda (x) (cond ((zerop x) 1) (t (times
x (fact (sub1 x))))))
(trace fact) would evaluate to nil and redefine fact as
(lambda (x) (prog (99g)
(print (quote (enter fact)))
(print (list x))
(setq 99g
(cond ((zerop x) 1) (t (times
x (fact (sub1 x))))))
(print (quote (value fact)))
(return (print 99g))
))
Evaluation of (fact 3) would return 6 after printing
(enter fact)
(3)
(enter fact)
(2)
(enter fact)
(1)
(enter fact)
(0)
(value fact)
1
(value fact)
1
(value fact)
2
(value fact)
6
Untrace takes any number of arguments and does not
evaluate them. Each argument should be the name of a traced
function. Untrace restores each function to its original
definition.
Prindef is used to write the definitions of functions and
constants. It takes any number of arguments and does not
evaluate them. Each argument should be an atomic symbol with
a value. Prindef prints the definition of each symbol as a
) call to rplaca, and then returns a call to stop, which is
normally printed also. The resultant text, when read at a
later time, defines the atoms and then returns to the
control program.
(prindef fact) prints
(rplaca (quote fact) (quote (lambda (x) (cond ((zerop x) 1)
(t (times x (fact (sub1 x))))))))
(stop)
Prindef could have been defined by
(setqq prindef (nlamda (x) (prog nil
a (cond ((null x) (return (quote (stop)))))
(print (list
(quote rplaca)
(list (quote quote) (car x))
(list (quote quote) (eval (car x)))
))
(terpri)
(setq x (cdr x))
(go a)
)))
Fix is used to edit or modify functions. It takes three
arguments and does not evaluate them. The third is the name
of the function to be fixed. The first argument is
substituted for the second in each appearance in the
function, and the function is redefined to be the result.
Fix could have been defined by
(setqq fix (nlamda (x)
(rplaca (caddr x) (subst (car x) (cadr x)
(eval (caddr x))))
))
Prog2 is used to cause the evaluation of several func-
tions with a single call to eval. It takes one or more
arguments, evaluates all, and returns the last.
Mapcar is used to send each item of a list to a function
as the single argument of that function, and return the list
of the values returned. Mapcar takes two arguments and
evaluates both. The first is the list of arguments, the
second is the function. To cons each item of the list (a b c
d) with x, for example, evaluate
(mapcar (quote (a b c d))
(quote (lambda (y) (cons y (quote x)))))
m
obtaining
((a.x) (b.x) (c.x) (d.x))
Mapcar could have been defined by
(dex mapcar (x y) (cond
((null x) nil)
(t (cons (apply y (list (car x))) (mapcar (cdr x) y)))
))
p Output
Output normally goes to the typewriter or a text file,
depending on destination specified to the control program.
Error messages are always printed on the typewriter.
S-expressions which are nearly lists, such as
(a.(b.(c.d)))
are printed as
(a b c.d)
This format is also acceptable for input.
Negative numbers are printed with a minus sign. The radix
(octal or decimal) is determined by the control program. It
is normally decimal.
A carriage return is inserted after approximately every
65 characters of output not containing a carriage return. It
is never inserted in the middle of an atom.
To facilitate printing of characters that are not normal-
ly permitted in atomic symbol names, the atoms space, lpar,
rpar, red, black, period, tabul, backspace, and carret are
provided. Each of these is bound to a symbol whose name is
the indicated character. Hence, to type a left parenthesis,
evaluate
(prin1 lpar)
>>37<<
Input
Input comes from the typewriter or text file, depending
on the source specified to the control program.
Parentheses, period, and space separate atoms. Extra
spaces may be used anywhere except inside an atom. Spaces
may be omitted except where needed to separate atoms. Tab is
equivalent to space. () is equivalent to nil. When an S-
expression consists of an atom only it must be followed by a
separation character, usually space. This separator is saved
and used on the next call to read.
Carriage return and stop code are ignored.
0 to 7 in octal radix and 0 to 9 in decimal radix are
digits. An atom containing only digits, with an optional
minus sign, is a number. Plus signs are not permitted in
numbers. The absolute value of a number must not exceed
131071 decimal or 377777 octal.
Overbar causes the character immediately following to be
considered a letter regardless of what it actually is. The
overbar itself does not appear in the atom, and will not be
printed out when the atom is printed.
Other characters, including case shifts and all upper-
case characters, are letters, and atoms containing one or
more letters are atomic symbols. All atoms must begin and
end in lower case. Atomic symbols may be of any reasonable
length.
Backspace may be used to correct errors in typing. After
one or more characters of an atom have been typed, backspace
deletes those characters and starts the atom over. The
remainder of the S-expression is not affected. A backspace
immediately after a separation character starts the entire
S-expression over and prints out a carriage return.
1
Operation
Load the program, start at zero, and type the number of
core modules to be used. LISP stores itself on drum field
15, part of which it uses for pushdown stack and atom name
storage. Free storage remains in core at all times. LISP
sets an illegal memory reference return, which is removed
when it dismisses to ID with "b".
The control program
The control program is entered when LISP is first started
and whenever the function stop is called. When entered it
types a red shift and minus sign, and waits for control
characters to be typed. The first character specifies input
source.
t - from the typewriter
s - from Expensive Typewriter's text buffer, starting on
page 1
e - from Expensive Typewriter's text buffer, starting
from where it last read. When LISP is first started,
this is the same as "s".
The next character specifies output destination.
t - to the typewriter.
s - to a text buffer on drum field 7, starting on page 1.
e - to a text buffer on drum field 7, appending a new
page.
n - nowhere.
After "s" and "e", stop must be called to finish output.
If "o" is typed before the input source specification,
numbers will be read and printed in octal radix. Numbers are
decimal otherwise. If "b" is typed, LISP will dismiss to ID.
e
After leaving the control program, LISP reads S-expres-
sions and prints out their values. The LISP program could be
simulated by
(prog nil a (print (eval (read))) (go a))
Some other LISP programs, notably the version used on the
7094, use a different algorithm, in which a function and its
argument list are typed in as two separate S-expressions,
and the arguments are not evaluated on the top level. This
algorithm may be approximately simulated by
(prog nil a (print (apply (read) (read))) (go a))
Turning on sense switch 1 when LISP is running or
printing out will cause it to return to the top level read-
eval-print loop immediately. Temporarily bound symbols will
be restored to their original values. In very severe cases,
it may be necessary to hit call and restart at location
zero. In this case, temporary bindings will remain, and, if
a garbage collection was in progress, free storage will be
seriously damaged.
Upon detection of an error, LISP prints a 3-letter error
code on the typewriter, sometimes followed by the S-
expression in error. Most of these errors return to the
read-eval-print cycle as if sense switch one had been
raised. The more serious ones return to the control program.
When the latter happens, temporary bindings are not
restored.
uas (unbound atomic symbol) - The argument of a call to
eval is an atomic symbol with no value. The symbol in
error is printed. LISP restores old symbol bindings
and returns to the read-eval-print cycle.
uaf (unbound atomic function) - A symbol which is not
bound or is bound to itself, or a number without the
internal function flag, has been used as a function.
The symbol or number is printed. Same recovery as uas.
tfa (too few arguments) - A subr or expr has not been
given enough arguments, or the symbol list after
nlamda contains more than one symbol. The recovery is
the same as that for uas.
tma (too many arguments) - A subr or expr has been given
too many arguments, or the symbol list after nlamda is
empty. Same recovery as uas.
cva (car of valueless atom) - an attempt has been made to
calculate the car of an atomic symbol which has no
value. The symbol in error is printed. Same recovery
as uas.
t
icd (illegal conditional) - A call to cond has run out of
clauses. Same recovery as uas.
nna (non-numeric argument) - An argument to an arithmetic
function is not a number. Same recovery as uas.
dze (divide by zero) - The divisor for quotient or
remainder is zero. Same recovery as uas.
pce (pushdown capacity exceeded) - The length of the
pushdown list is too great. LISP returns to the
control program. Temporary bindings are not removed.
sce (storage capacity exceeded) - The free storage list
has been exhausted, and no space could be reclaimed by
the garbage collector. Same recovery as pce.
ace (atom capacity exceeded) - The atomic symbol object
table is full. Same recovery as pce.
nce (name capacity exceeded) - The atomic symbol name
table is full. Same recovery as pce.
imr (illegal memory reference) - An illegal memory
reference trap has occured, usually because of taking
the car or cdr of a number. Same recovery as pce.
iif (illegal input format) - An object which is not an S-
expression has been read. Same recovery as pce.
b
Appendix - built-in LISP functions
name number of args description
| evaluate or quote
| | PF if pseudo-function
| | | class
car 1 e general
cdr 1 e general
caar 1 e general car_ car
cadr 1 e general car_ cdr
cdar 1 e general cdr_ car
cddr 1 e general cdr_ cdr
caddr 1 e general car_ cdr_ cdr
cons 2 e general (x.y)
list n e general (x y z ...)
rplaca 2 e PF general y . (car x)
rplacd 2 e PF general y . (cdr x)
append 2 e general
nconc 2 e PF general (append x y) . x
reverse 1 e general
subst 3 e general subst x for y in z
sassoc 3 e general look up x in y, or call z
length 1 e general length of a list
nth 2 e general cdr of y x times
and n e logical x and y and z ...
or n e logical x or y or z ...
null 1 e predicate x = nil
atom 1 e predicate x is atom
numberp 1 e predicate x is number
valp 1 e predicate x is bound
>>35<< zerop 1 e predicate x = 0
minusp 1 e predicate x < 0
greaterp 2 e predicate x > y
eq 2 e predicate x is y exactly
equal 2 e predicate x looks like y
member 2 e predicate x is a member of y
plus n e arith x + y + z ...
minus n e arith ... - x + y - z
times n e arith x x y x z ...
logor n e arith x >>05<< y >>05<< z ...
logand n e arith x ^ y ^ z ...
logxor n e arith x ~ y ~ z ...
quotient 2 e arith [x/y]
remainder 2 e arith x - y x [x/y]
add1 1 e arith x + 1
sub1 1 e arith x - 1
read 0 PF I/O
prin1 1 e PF I/O print without punctuation
print 1 e PF I/O print with punctuation
terpri 0 PF I/O print carriage return
stop 0 PF misc. return to control program
gensym 0 PF misc. create symbol
quote 1 q misc.
setq 2 q,e PF misc. bind x to y
setqq 2 q PF misc. bind x to y, y not evaluated
cond n misc.
eval 1 e misc. value of x
apply 2 e misc. call x with y
>>52<< trace n q PF misc.
untrace n q PF misc.
prindef n q PF misc. print definitions
dex 3 q PF misc. define expr
fix 3 q PF misc. fix x for y in z
prog n misc.
go 1 e PF misc. go to x
return 1 e PF misc. return from program
mapcar 2 e misc. send each element of x to y
prog2 n e misc. last arg
built-in constants
name value
t t
nil nil
space
lpar (
rpar )
red
black
period .
tabul
backspace
carret
c 7
~~