.

L' I S P
ProgrammerGs Manual
MIT Artific1al Intel11genoe Project

. .
I
. "

!
(
 __ M01UFICATlQNS

1 .. cons(a,d) 3/3/59
2. .consw (",) 3/3/59
3. cOPY(L) 3/3/59
4. equal (Ll,L2) 3/3/59
5. eralls(L) 3/3/59
6. erase(L) 3/3/59
7. mapllst(L,f) 3/3/59
8. Open SubroutInes 3/3/59
9. aearch(L,p,f,u) 3/3/59
10. apply 3/3/59
 1/1

CONS (a,d)

cons (a,d) puts comb{a#d) into a register taken from free

storage, and returns with the location of this register
as its value. It may be written as:
cons (~,d) a consw(comb(a,d

CONS STQ Tl
ARS 18
ADD Tl_
SXD Tlll4
LXD FREE 4
TXH *+4,4,0
SXD FROUT,4
TSX FROUT+l,4
LXD FROUT,4
LDQ 0,4
STQ FREE
STO 0,4
PXD 0,4
LXD Tl,.4
TRA 1,4
1
Tl PZE
status: Checked auto

March 3, 1959 Modification number 1

Author: J. Mccarthy Makes obsolete:
 1/1

CONSW (w)

consw (w) takes the first word in the tree storage list,
puts w in 1ti and returns with the location of the word
as the value of consw(w)o consw(w) may be called by the
instruction
TSX CONsw i 4 ,
o

CONSW SYN CONS + 3

(See cons(a,d}
St&&UB: Checked outo

~rch 3# 1959 Modification number 2

Author: Jo MCCarthy Makes obsolete

"
 1/1

COpy (L)

The list atru~ture 8ta~ting 1n (L) is copied

intofree storage and the value of copy (L) is the loca-
t10n of the lead word of the cop1ed structureo

co~y (L) (L - 0-70,car(L) --l-4L,l~conB(copy(car{L})g

copy(cdr(L))

status: copy (L) 1s ava1lab1e as a debugged SAP

language subroutineo

March 3, 1959 Modification number 3

Author: J. Mccarthy Makes obsolete:
 1/1
EQUAL (L1,L2)

equal [L1,12) compares the list structures start1ng at

Ll and 12, and the result 1s 1 if the structures agree
both 8S to forms and as to the 1dentities of the objeots
1n corresponding placeso
equal(L1,L2) - (L1-L2~1, car(Ll) -'~Vcar(L2)--1~O~
1-4equals(car(Ll),car(12)11equals(cdr(Llftcdr(L2)
Status: equal(Ll,L2) 1s available as a debugged
SAP language subroutlneo

March 3, 1959 Mod1ficat1on number 4

Author: Ko Mal1ng Makes obsolete:

r
 1/1
ERALIS (L)
eral1s{L) erases the list structure starting in Lo

subroutine (era11s(L
I L ,... OV'car(L) iII[I-l~return
M eraae(L)
8

eralis (a~d(M
eralia (dec(M
\return

Status: Checked outo

March 3, 1959 Modification number 5

Author: Jo MCCarthy Makes obsolete:

r ..
 1/1
ERASE (L)
erase (L) returns the word in location L to free
storage$ and has as its value the former contents of
the erased word.

ERASE SXD T144

PDX 0,
CLA 0,4
LDQ FREE
STQ 0,4
8m FREE,4
LXD Tl,4
TRA 1,
0

Tl

Status: Checked outo

March 3, 1959 Modification number 6

Author: Jo McCarthy Makes obsolete:
 1/1
MAPLIST (L,t)
maplist (L,t) constructs a I1st in free storage whose
elements are in 1-1 cor~espondence with the elements

-' of the list Lo The address portion of the element of

, the new l1st at J, correspond1,ng to the element at L
conta1ns f{car(Lo The value of mapllst 1s the address
of the new l1st.
a) "fast" map11st
map11st(L,f)/L-O~return(O)
maplist = cons(f(L),O)
M = map11st
al L cdr (L)
1:11

cdr(M) a cons(f(L)~O)
cdr(L) ~ o-.return(maplIst)
M - cdr{M)
, go(a1)
, b) "slow" map11at
mapl1st(L,f,) -(L=~O,l~cons(t(L) ,mapl1st( cdr(L) ,f)
r , ...

status: Both maplists have been checked outo

In compilIng, the fast maplist is used, as it saves
about 103 mIlliseconds per ljat element 01' Lo (75 jZsavIng)

March 3, 1959 Modification number 7

" Makes obsolete:
Author: 30 Mccarthy

. \

( ,
I

\.
 1/1
OPEN SUBROUTINES
r
10 add(w) extracts the 15 bit add~ess of the word Wo
20 car(n). The value of car(n) is the 15 bit contents
of the address part ot the register in locat1on n.
30 cdr(n}. The value of cdr(n) 1s the 1~ bit contents
of the decrement part of the register 1n location no
40 comb(a,d) combines tow 15 bit quant1t1es to make
a 36 bit word.
5. cwr(n) is the 36 b1t contents of the register no
60 dec(n) extracts the 15 bit decrement of the word Wo
7. rep1~ca(j,k) replaces the address of k with the
15 b1t word j. ~
8. replacd(j,k) replaces' the decrement ot ~ with the
15 bit word ~'. ~

March 3, 1959 Modificat1on number 8

Makes obsolete:
 1/1
SEARCH (L,p,f,u)
search(L,p,f,u) examines the list L for an element
satisfying the cond1tion p, and 1t 1t tinds one~ 1t
' ex1ts with f ot that element; if the search 1s un-
successful, search(L,p,t,u) exits with the value of the
expression u.

search(L,p,r,u) ~ (L-O-+u,p(L~t(L),l~search(cdr(L),
p,t ,u
Status: Checked out.

Maroh 3, 1959 Mod1fication number 9

Author Jo McCarthy Makes obsolete:
 ,/
3/1
The Universal function - APPLY
WRITING LISP FOR APPLY AND EVAL .
APPLY and EVAL understand lists whose first elements are
function names or symbols to denote certain special expres-
sions' built into EVALo The sueceeding elements are taken to
be the arguments ot the functions, or part of the expression.
Since we do not yet have an input program to read infixes
or rearrange parentheSiS we must write the above lists in re-
stricted external notation. Thus, the following translation
hold between our usual notation and the notation approprIate
for read-in to apply and eval.
Usual Notation Restricted Notation
x x
car(x) (car,x)
cons{x,y) (oons,x,r)
cons(car(x),cdr(y (cons, (car,x), (cdr,y
EVAL
Eval(E,A) is a function that evaluates the lisp expression
E using the list of pairs A to determine the values of var1ab~eso
If E 1s a variable name, it searches A tor the value paired
with E and takes this value. If E is a function it evaluates
the arguments of the functlon and then uses apply to evalu~te
the tunctiono In addition, it recognized certain spec1al
expressions describP-d below.
The expression (const,C) indicates that the symbol C is a
constant and not to be looked up on the A list.
(sub,E) does a subllst on the result ot evaluating the
expression E, using the entire list A as a list ot substitutions.
(cond,(Pl,e l ),(P2,e 2 )---(Pk,e k is the eonditional expres-
slon.The Pl are evaluated successively until one is tound with a
value of 1. The corresponding e 1 is evaluated. It none of
the PI are 1, error is enter
(vareIB)(~iable expression) oauses the evaluation ot the
expressi on paired with the object B on the A li.sto
- -
(vaJ'c,C)(v:-.t-iable constant) causes the item paired with C on
the A-list to be the value of eval.
(intv,N) causes the integer value ot N to be looked up on
the prope!:ty list ot No At present only 0,1, and MINUS!. are
allowable as N
 3/2
The following are examples of statements 1n our usual
notation and in the restricted notation necessary tor eval:
Usual Eval
x x
cons(x,y) (cons,x,y)
(Pl e 1 ,P2 e2--~~ e k ) (cond,(Plel),(P21e2),---(Pk,ek)
L=1 (EQUAL,L,(INTV,l
APPLY
APply(F,L,A) is a function that evaluates a 'function ~
tor the arguments given 1n the list L. In addition the values
ot previously bound variables and some function definitions are
given by the l1st of pairs, A.
It the function F is an object, it may be basic (car,cdr,cons),
in which case it is built into part of apply, it may be defined
on its property list by either a 704 program or a lisp expres-
Sion, or it may be paired on its A list with a lisp expressiona
It the def1nition of F 1s an expresa10~ it must be the
name ot a function object, or else beg1n with iam~~. or label,
fOllowed by lambda.
It F is a subexpreasion it may have the same form described
above, or it may be an expression, that when evaluated det~nes
the function 1n a manner acceptable to applyo
,The list of arguments must have the same number or elements
as F has arguments, or an error may resulto
(Certain built-in functions: eog. list, may have an arbitrary
number of argumentso)
The first element of L is interpreted as the first argument,
the second element 8S the second argument, etc.
The expression (label, name,(P when it appears as a
lunati'on is treated exactly as F would be, except that the name
is paired with F and put on the A, list given to all lower level
uses of . apply and evalo This permIts writing recursions within
a statement. For example the definition ot the "slown mapliat
using label is:
(LABEL,MAPLIST, (LAMBDA, (L,F), (COND, EQUAL(INTV ,0) ,L),
( INTV, 0) ) " .: ( INN, 1 ) , ( CONS, (It' , L) , (MA PLIST, (C DR, L) ,F) ) ) ) ) )
The functions built 1n to Apply are (car,cdr,cons,l1st,)
and there are also two predicates null and atom. This value ot
null is 1 only it its argument is the null list, 0, and the
value of atom is 1 only if its argument is an objecto
 3/3
Lisp program tor sin'g le statement interpreter
APPLY(F,L,A)-select(car(F);
-1,app2(F,L,A);
lambda,eval(caddr(F),append(pair(cadr(F),L),A;
label,apply(caddr(F),L,append(pair(cadr(F),caddr
(F ,A;
apply(eval(F,A) ,L,A
EVAL{E,A)-select(car(E);
-l,search(A,~(J,caar(J)=B'~(J,cadar(J,error);
mtv ,8earch(cadr(E),~(J,car(J)-1nt),~(J,cdadr(J,
error) ;
sub,sublls(A,eval(cadr(E),AJ
const,cadr(E);
label,eval(caddr(E),append(pair(cadr(E),caddr(E,
, A;
varc,8earch(A,~(J,cadar(J)=cadr(E,~(J,cadar(Jt
error) ;
care,search(A,~(J,caar(J)-cadr(E,A(J,eval(cadar(J),
cdr(J ,error};
apply(car(E),mapllst(cdr(E),A(J,eval(car(J),A),A
APP2(F,L,A)=select(F;car,caar(L);cdr,cdar(L);cons,cons(car(L),cadr(L;
11st,LJnul1,car(L)~O;atom,caar(L)--1;
search(F,A(J,car(J)-8ubr~xpr),
A(J,(car(J)=8ubr~apP3(F,L,
l~apply(cadr(J),L,A}1
search(A,A(J,caar(J)-F),~(J,apply(cadar(J),L,A,
error) )
evcon(E,A) = (E-~error,eval(caar(E),A~eval(cadar(E},4,~evcon
'( cdr(E) ,A})

r March 3, 1959 Modificat1on number 10

Author: S. RUBsell
 MODIFICATIONS
11. Function Names 3/20/59
12. mapl1st(L,f) 3/20/59 (replaces no. 7)
 1/1
FUNCTION NAMES
It was agreed in an Artificial Intelligence Project
meet1ng that. the follow1ng abbreviations tor the elementary
functions would be usedo
sin arsin sinh as1nh
cos arcos cosh aeosh
tan artan tanh atanh
cot arcot eoth aeoth
sec arsec sech asech
cse arcse each acseh
a + b - c is written (plus,a,b,(minus,c
a.b is written (times,a,b,(recip,c
-C
a.b 1s written (times,a,b(recip,(t1mes,c,d)
c:a
aebo~Dl is wr1tten (t1mes,a,b,(recip,c),(recip,d
V
U is written (power,u,v)
logbx 1s written (log,b,x)
Note: The natural logar1thm is denoted by (log,e~x)

The symbol In is not used for this purposeo

-

March 20, 1959 Modif1cat1on number 11

Author: N. Rochester Makes obsolete:
 1/1
MAPLIST (L,t)
maplist (L,t) constructs a list in free storage whose
elements are 1n 1-1 corr~spondence w1th the elements
ot the list L. The address port1on of the element ot
the new list at J. correspond1ng to the element at L
contains f(L). The value ot maplist is the address ot
the new list.
a) "fast" maplist
maplist(L,t).~O~return(O)
maplist-cons(t(L),O)
M-mapllst
al !,wcdr(L)
cdr(M) ..cons(f(L).O)
cdr(L)-O~return(maplist)
M-cdr(M)
\go(a1)
b) "slow maplist lt
mapllst(L,t)-(L-O~O,1~cons(t(L),map11st(cdr(L)3f) _

status: Both maplists have been checked out. In

compiling, the fast mapllst 1s used, as it saves about 103
milliseconds per 11st element ot L. (75;rsavlng)

March 20, 1959 Mod1fication number 12

Author: Jo Mccarthy Makes obsolete: Mod no 0 0 7
 MODIFICATIONS
130 EQl(Ll,L2) 3/27/59
14,. CP1(L) 3/27/59
150 PRINT(L) 3/27/59
160 FLVAL(L) 4/3/59
. 17. MAKENU(L) 4/3/59
18. NUTERN(L) 4/3/59
190 PRDCT(L,K) 4/3/59
20. SUM(L,K) 4/3/59
 1/1
EQl(Ll,L2)

eql(Ll,L2) compares the one level lists at Ll and L20

ItUs value is 1 i t the two lists are ident1ca1 6 and zero
otberwlse.

eq1(Ll,L2)-(L1DL2~1,

LlOVL2-~O,

l~cwr(car(LlDcwr(car(L2Aeql(

cdr(Ll),cdr(L2)

Status: Available as a debugged SAP subroutlneo

March 27, 1959 Modification n~ber 13

Author: K. Maling

r
 1/1
CP1(L)
r
cpl(L) copies the one-level list beginning at L into
tree storage, and returns with the location of the copied
list as its value.

cpl(L)m(L=~O,

1~cons(con8w(cwr(car(L),cpl(cdr(L

status: Available as a debugged SAP subroutine.

March 27, 1959 Modification .number 14

Author: Ko Maling

r
 1/1

r PRINT(L)

prlnt(L) prints the list at L in restricted external

notation, using 119 character l1neso pr1nt(L) requires the
subroutines pr1nl(L), prln2(L)" terpr1, MISPH2 (or UASPH2)
ail beaded b7 P, and save, unsave, error unheadedo
prlnt(L)=(car(L).-1~pr1nl(L),

l~(pr1n2(LPAR2).pr1nt(car(L.

(cdr(L)=O~pr1n2(RPAR2),

l~(pr1n2(COMMA2)~pr1nt(cdr(L

prinl(L) prints the pr1nt-name on the property l1st.

SUBROUTINE (prinl(L
/car(L)!-l error
81 cdr(L)mO error
L=cdr(L)
car(L)~PNAME go(al)
L-c8r(cdr(L
a2 pr~n2(cwr(car(L

cdr(L)=O return
L=cdr(L)
\ gO(82)

pr1n2 prints up to 6 characters 1n one word when the

characters are justi~ied to the lett. followed by the illegal
character whose octal torm is 110
status: print(L) is ava1lable as a debugged SAP programo

.r March 27, 19.59 Modification number 15

Author: J. Mccarthy
 1/1
PLVAL (L)
r
flval(L) f1nds the address of the floating po1nt represen-
tation ot the number represented by the property list L. The
value ot flval(L) 1s the address ot the floating point number.
flval(L) =- /car(L)t'-l....,error
Bl cdr(L)aO-terror
L=cdr(L)
ca~(L)~LOAT~gO(Bl)

\return(cdar(L

status: Available as a debugged SAP subroutineo

April 3. 1959 Modification number 16

Author: S. Goldberg

r
 I,
1/1
MAKENU(L)

makenu(L) makes an numerical object or the list

strUcture at L, and adds 1t to the number list. The value
of makenu(L) 1s the' address ot the constructed obJec~ list.

Status: Available as a debugged SAP Bubrout1ne.

April 3, 1959 Modif1cat1on number 17

Author: So Goldberg

r
 1/1
NUTERN(L)
nutern(L) searches the number list tor a n~ber equal
to the floating pOint number L. If no number 1s round on the
numbe~ 11st, a new property l1st 1s tormed, using makenu.
The value of the function is the address ot a property list
which represents the floating point number L.
Dutern(L)=/Val l=L
return(seareh(cdr(nu11st),
Lambda(J,search(car(J~

Lambda(J,car(J)=PLOAT),
Lambda(J 3 cdar(J)aval 1),
Lambda(J,O)~

Lambda(J,car(J,
",
Lambda(J,makenu(Liet(numb,
, FL6A~,consw(~wr(val 1)

status: Available as a debugged SAP subroutine

April 3, 1959 Moditication number 18

Author: So Goldberg
 1/1
PRDCT(L.,K)
prdet(L.K) computes the product ot two floating point
numbers represented on the property lists Land K. Its value
is the address of an object containing the product.

status: Ava1lable 8S a ' debugged SAP subroutine.

April 3. 1959 Modificat1on number 19

Author: s. Goldberg
 1/1
SUM(L~K)

sum(L,K) computes the sum ot the floatIng point numbers

represented by the object lIsts Land Ko Its value 1s the
address of an object contaInIng the sumo

status: AvaIlable as a debugged SAP subroutIne.

AprIl 36 1959 ModIf1cat1on number 20

Author: So Goldberg
 MODIFICATIONS
21. desc[u;m] 4/7/59
22. pick [Sbt] 4/7/59
23. mapcar(L,f) 4/9/59
24. GREATR(J"K) 4/9/59
25. format [n;t;v] 4/29/59
26. SUBSTR(RbS) 4/15/59
 1/1

desctu.;m]

desc[u;m] descends a list structure m guing in the address

or decrement d1rection according to the list u. Each element of
the list u 1s either A or D.
We have
desC[u;mJ=[null[uJ...... m;ato~[mJ--"error;car[uJ-A~desc[cdr
[u] ; ear-em]] jcar[~=D-)dese(cdr[u]sC~t~JJ;l~errorJ
As an example
,wtl
desc[ (A,A,D) a (u~ v ,wU
:H(v)"-cdaar [e u, v)
~~;~w11l be u~ed by the ful'lctions created by format.
Even by itself it will operate faster when used by ~pll than
the eorrespond1ng composItion of car and cdro
........ -

status: SAP routine not yet checked out-

-
AprIl 7~ 1959 MOdif1cation number 21
Author: Jo Mccarthy and Ko Mallng Makes obsolete
 1/1

piCkrSDf]

p1ck(s;t] has as value, a list each of whose elements 1s

,A or D and which gives the location of the symbol s in the
atructvre f. The value of p1ck[s;fJ can be used by des~ to
get the element of a structure in a g~ven pOBitiooo
We have
pick[s;f] .. [null[tJ4NO;equal[a;fJ~i\;1-? '7\[ [u]~ [eqUal[U;NO]
~1\([vJ;[eqUal[V3NO~N061-7COnS[D.;vJ]][PiCk[S' iCdrrfJ]J8l-:)
conS[AiuJ]J[PiCk[Sicar[tJ]])
As an example
P1Ck[V; (U, V :lW)] -(A,A,D,A)
21ek will be used by format.

status: 'LISP routine not checked out. There 'are no plans to

write a SAP version but the version for apply will be debugged~

April 7, 1959 Modification number 22

Authors: J. Mccarthy and K. Maling Makes obsolete
 1/1
mapcar(L~f}

mapcar is like maplist except that it does not construct

a new list and it has 0 as its value. As as example of the use
of mapcar~ suppose one wanted to replace with CO the variables
in list L.
mapcar(L~(var(car(L)~replaca(L,CO),l~O

mapcar(L~f)~(LaO~O,

f(L)-~O,

1-4mapcar(cdr(L),f

status: Available as a debugged SAP rout1neo .

April 91) 1959 Modification number 23

Author: Nu Rochester

r
 1/1
0"
GREATR(J,K)
This 1s the predicate J)K , it takes as arguments two
15 bit numbers and has a one bit quantity as value. It 1s
written in SAP

GREATR TLQ ~c-.....3

PXD 0,0
'1'RA 1,4
CLA INTV:'.
'TRA 1.4
INTV1 HTR ,,1

Status: Checked out.

Date: Apr!l 9D 1959 Modification number 24

Author: N. Ro~hes'er
 1/1

format[nyi';v]
forrnat[n;f~V] has the value n. n is an object~ f is some list
structure and v is a list of variable~ occurring in f~ Its execu-
tion causes n and the variables of v to become functions \'lhich are
available to APPLYc This is best explained by an example.
Consider format[SHAKESPEARE;(UNDER#GREENWOOD,TREE)S(GREEN-
WOOD" TREE)]
There are two variables involved~ GREENWOOD and TREE
Then, the e2tecution of format generates three functions to tJhlch
\'1e, could give argumenta

s~kespeare[SPREADINGbCHESTNUT]
gl'eenwood [(BENEATH" SPREADING ,CHESTNUT)]
tree fiBENEATH, SPREADING 0 CHESTNUT D
Executing these functions in turn gives
(UNDER~SPREADING~CHESTNUT)
SPREADING
and CHESTNUT respectively
Th'l:l,~ :i!.hakesneare has as argument a list u which must contain

as many tepms as v'(; and substitutes In f for one occurrence of each,

variable ~n v the corresponding variable in Uo
greemtJood and ~ree ,have as argument a li-st structure g and
pick ~ut,the element in g which,occupies a position corresponding
co their,Us in f'o
forma't [ncf ;~}o.[ fn;f;v] c rAE J
[sot] ;t] [attrib [n;subI1s[ [[V;v Jr.;f] ; [pp
formatp [v]]] (EXPR.!l {L..4.MBDA p Vb (SUBLIS.OJ (LISTpP) # (CONST"F) n]]
formatq[n 5f;v]]JJJ
formatp.,[v] [null [vJ--7I\;T--9 conal aUbst[ car [v] ,;X; (LIST" (CONSTs,x) ~x)] ;
=tl

fOl'>!Ilatp{cdr[v]J JJ
formatq, ~;fFvJ~ [nUll[ V]-7DiT-7A[[Z] 8[Z=NO-,error~T~A[[ xaY]oY]
[attri,b [c ar [v] ;aubst[z-;Rg,(EXPR, LAfl1BDA8 (x) e (DESCbRDX)) )JJ]
[f'ormat9[n.~f9cdr [v]]]]] [PiCk [car [v] bfJ])

statue: APPLY routine not yet ' ~hecked outo

Au1;hor :I.o McCa'rthy and Ko Mallng Modif'ieatil::>n Noo 25
(' April 29, 1959
 1/1
SUBSTR(R~S)

substr(RiS) is the proposition that the list structure S

:J.B a substructure of the 1~8t structure Ro
8ubstr(R~S)~EQUAL(R8S~T

NULL (R)~F

ATOM (R)~F

SUBSTR(CAR(R),S~T

T4SUBSTR(CDR (n) ~S)

.
Q
f

;If\ . ~
.:.-. .. Available as a debugged LISP function for applyo
STATUS:
'
...~.ui.
~~. ~ .
-tA '
.. - ,~ ..

11 151! 1959
Author: Jo Slagle Modification number 26