Weismann Lisp1.5 Primer 1967 PDF
Weismann Lisp1.5 Primer 1967 PDF
Weismann Lisp1.5 Primer 1967 PDF
5 PRIMER
' INDEX
FUNC 'FION DESCRIPTIONS
l!msuaL No. Arnuments Type & Pqze Function No. Arnumcnts . Type & Page
The primer starts simply with a formaL definition of a symbolic expression, its
syntax and graphical representation. Two alternative machine-readable notations
are defined for representing symbolic expressions. Once the student becomes
familiar with recognizing symbolic expressions, he learns how to take them apart
into smaller elements or put them together into larger expressions using the
elementary LISP functions CAR, CDR, and CONS. The early chapters of this book
are essential to the understanding of LISP. They expose the reader to the
LISP formalism and give him an opportunity to acquire the necessary skills for
processing symbolic data. Learning these skills is analogous to learning the
rules of arithmetic.
Recursion i s a s n a t u r a l t o symbolic d a t a m a n i p u l a t i o n a s i t e r a t i o n i s t o
numerical d a t a processing. LISP i s d e s i g n e d t o make r e c u r s i o n e a s y t o u s e ,
and r e c u r s i v e f u n c t i o n s a r e a s i g n i f i c a n t p a r t of t h e domain of LISP expres-
sions. S i n c e n u m e r i c a l d a t a i s a l s o allowed i n LISP, i t e r a t i v e f u n c t i o n s c a n
b e d e f i n e d u s i n g t h e PROG x e a t u r e , i n which s t a t e m e n t s a r e e v a l u a t e d i n ALGOL-
l i k e s e r i a l fashion.
LISP is not an easy language to learn because of the functional syntax and
insidious parenthetical format; this is particularly true for those experienced
with more conventional programming languages. However, LISP is consistent in
its syntax no matter how complex the expression. Careful attention to this
fact may make learning easier. The carefully graduated sets of exercises can
help in this regard. They have been selected for use with or without a computer.
They may be used on-line if a time-sharing system is at hand. Otherwise, the
solutions given in Appendix A can be used for comparison. These solutions have
been computer-checked for accuracy and correctness.
vii
ACKNOWLEDGMENTS
C l a r k Weissman
viii
TABLE OF CONTENTS
Page
PREFACE . ......................... .... . iii
ACKNOWLEDGMENTS. . . . . . . . . . . . . . . . . . . . . . .... .
CHAPTER 1 INTRODUCTION . . . . . . . . . . . . . . . . . .... .
1.1 Purpose of This Document . . . . . . . . . . . . .
1.2 Document Conventions . . . . . . . . . . . . . . .
1.3 LISPApplications. . . . . . . . . . . . . . . . .
CHAPTER2 SYMBOLICEXPRESSIONS . . . . . . . . . . . . . .... .
2.1 AtomicSymbols . . . . . . . . . . . . . . . . . .
2.2 Dot Notation . . . . . . . . . . . . . . .... .
2.3 Graphical Representation of Dotted Pairs .... .
2.4 Exercises . . . . . . . . . . . . . . . . .... .
CHAF'TER 3 SYMBOLIC EXPRESSIONS IN LIST NOTATION . . . . . .... .
3.1 ListElements . . . . . . . . . . . . . . .... .
3.2 NIL . . . . . . . . . . . . . . . . . . . .... .
3.3 Transforming List Notation to Dot Notation . . . .
3.4 Transforming Dot Notation to List Notation . . . .
3.5 Graphical Representation of Lists . . . . . . . . .
3.6 Exercises . . . . . . . . . . . . . . . . . . . . .
CHAPTER 4 NUMBERS . . . . . . . . . . . . . . . . . . . . . . . . .
4.1 Integer Numbers . . . . . . . . . . . . . . . . . .
4.2 OctalNumbers. . . . . . . . . . . . . . . . . . . .
4.3 Floating-Point Numbers . . . . . . . . . . . . . . .
4.4 Decimal Point or Dotted Pair Resolution . . . . . .
4.5 Exercises . . . . . . . . . . . . . . . . . . . . .
xii
Page
APPENDIX A EXERCISE ANSWERS ................... 183
APPENDIX B GLOSSARY . . . . . . . . . . . . . . . . . . . . . . .
APPENDIX C REFERENCES......................
APPENDIX D INDEX TO TECHNICAL TERMS . . . . . . . . . . . . . . .
xiii
CHAPTER 1.
INTRODUCTION
This manual has two principal goals: (1) to introduce the programming language
LISP and present a systematic exposition of symbolic computation, and (2) to
serve as a self-tutor for those wishing to acquire a practical facility with
the LISP 1.5 programming language.
DOCUMENT CONVENTIONS
(LAMBDA v u r l i s t body)
All programs and data in the LISP programming language are in the form of
symbolic expressions usually referred to as S-expressions. S-expressions are
of indefinite length and have a branching binary tree structure, so that signi-
ficant sub-expressions can be readily isolated. The bulk of available memory
in a computer is used for storing S-expressions in list-structure form. This
type of memory organization frees the programmer from the necessity of allocating
storage for different sections of his program or data. It also makes LISP
programs and data homogeneous (i.e., programs can be treated as data and vice
versa by other programs), a unique feature of the language.
ATOMIC SYMBOLS
Definition:
Examples :
A
APPLE
PART2
EXTRALONGSTRINGOFLETTERS
AlB66X4ZZ
These symbols are called atomic because they are taken as a whole and are not
viewed as individual characters. Thus A, B, and AB are three distinct and
unrelated atomic symbols.
'some recent LISP implementations have liberalized this definition. They accept
as literal atoms any character string that cannot be interpreted as a number.
2.2 DOT NOTATION
All non-atomic S-expressions are written in what is called dot notation. They
are built of atomic symbols and the punctuation marks:
( left parenthesis
) right parenthesis
. period or dot
has atomic symbol A as its left part, and atomic symbol B as its right part.
Thus, a non-atomic S-expression is always a dotted pair.
Definition:
An S-expression is either:
1. An atom, e.g., A1
2. A dotted pair of atoms, e.g., (A . B)
3. A dotted pair of S-expressions, e.g., ( (A . B) . C )
The general form of a dotted pair is: a left parenthesis, an S-expression, one
or more spaces, a dot, one or more spaces, an S-expression, and a right
parenthesis.
Examples:
ATOM
(A B)
(A . ATOM)
(ATOM1 . (BETA . C))
((U V) x)
((U V) (x (Y z)))
GRAPHICAL REPRESENTATION OF DOTTED PAIRS
A l l non-atomic S-expressions a r e i n t e r n a l l y r e p r e s e n t e d a s a b i n a r y t r e e
structure, i.e., a t r e e s t r u c t u r e w i t h b u t two branches a t each node. It i s
o f t e n h e l p f u l t o t h e s t u d e n t t o "see" t h e g r a p h i c a l r e p r e s e n t a t i o n of t h i s t r e e
structure.
Symbol Meaning
'
A g r a p h i c a l node w i t h a l e f t and r i g h t branch ( i . e . , a memory cel:)
F i r s t t h e graph of
i s g i v e n by
The graph of
( ( A . B ) . C )
Examples :
((((A . B) . C) D) (DD . (CC (BB AA))))
((((A . B) . (A . B ) ) (A B)) (A B))
Level 2
Level 3
Level 4
2.4 EXERCISES
ATOM
A B
AlB2C3
NIL
(X)
LISP
432
ONE
(MY . NAME)
2TIMES
11. A .B
12. X . Y . Z
13. (YOU . AND . ME)
14. (X . Y)
15. (NIL . NIL)
Dot n o t a t i o n i s n e c e s s a r y and s u f f i c i e n t t o r e p r e s e n t a l l l i s t s t r u c t u r e s i n
LISP, and, i n f a c t , i s t h e fundamental concept upon which t h e programming
language is b u i l t . However, i t l e a v e s much t o b e d e s i r e d a s a convenient
programming n o t a t i o n f o r S-expressions, p a r t i c u l a r l y because of i t s e x c e s s of
p a r e n t h e s e s and d o t s . L i s t notation was invented t o improve t h i s s i t u a t i o n and
s i m p l i f y t h e r e a d i n g and w r i t i n g of S-expressions.
For example, t h e l i s t
(A . (B . (C . (D . NIL))))
W
LIST ELEMENTS
and
a r e e n t i r e l y e q u i v a l e n t i n LISP.
3.2 -
NIL
Identity 1:
Examples:
or equivalently
(atom) - (atom
I
. ( ))
(A) 5 (A . NIL)
(EXTRALONGATOM) E (EXTRALONGATOM . NIL)
(NIL . MIL)
(( 1 ( )>
Rule 1:
Since
(C . NIL)
Hence, t h e f i n a l S-expression i s given by
(A ((B C) Dl)
(A c) (Dl))
(A . ((B C) . .
(D NIL)))
Now, expanding the sublist (B C) we find
Examples :
/(A B C) (A . (B . (C . NIL)))
((A B) C) ((A . (B . NIL)) . (C . NIL))
(A B (C D)) (A . (B . ((c . (D . NIL)) . NIL)))
. NIL) . NIL)
-
((A) E ((A
( (NIL) r ((NIL . NIL) . NIL)
(0> (NIL . NIL)
(A (B . C)) E (A . ((B . C) . NIL))
Prom the above examples you can see that Identity 1 can be stated alternatively
as: When converting from list to dot notation, the only atom that appears
adjacent to a right parenthesis is NIL.
For complicated dotted pairs, the following procedure can be followed starting
with any dotted pair:
1. I f t h e r i g h t p a r t of t h e d o t t e d p a i r i s a n atom and n o t NIL,
conversion t o l i s t n o t a t i o n i s impossible.
2. I f t h e r i g h t p a r t of t h e d o t t e d p a i r i s non-atomic (i.e., a
l i s t o r a d o t t e d p a i r ) o r NIL--treat NIL h e r e a s ()--then
a. d e l e t e t h e l a s t r i g h t p a r e n t h e s i s of t h e d o t t e d p a i r
b. d e l e t e the dot
c. d e l e t e t h e f i r s t l e f t p a r e n t h e s i s of t h e r i g h t p a r t ; t h e
l e f t p a r t t h e r e b y becomes t h e f i r s t element of t h e l i s t
d. r e p e a t t h e procedure on t h e remaining d o t t e d p a i r s .
(A . (B . N I L ) )
t h e most n e s t e d d o t t e d p a i r i s
(B . NIL)
Representing NIL by ( ) and applying t h e procedure above, w e f i n d
Applying t h e procedure a g a i n , we g e t t h e l i s t
For t h e c a s e
(A . ( ( B . C) . (D . NIL)))
r e p e a t e d a p p l i c a t i o n of t h e procedure y i e l d s t h e s e e x p r e s s i o n s :
a l i s t , b u t r e c o g n i z e t h a t i t i s i n mixed n o t a t i o n . Mixed n o t a t i o n i s p e r f e c t l y
a c c e p t a b l e t o LISP and i s q u i t e common i n LISP S-expressions.
L i s t s can b e transformed i n t o t h e i r e q u i v a l e n t d o t n o t a t i o n ; g r a p h i c a l r e p r e -
s e n t a t i o n of d o t t e d p a i r s i s covered i n S e c t i o n 2 . 3 . T h i s s e c t i o n w i l l review
t h a t m a t e r i a l , b u t w i t h t h e i n t r o d u c t i o n of NIL.
(A . NIL)
But
(A . NIL) I (A)
List Dotted P a i r
(A B C) (A . (B . (C . NIL)))
(A (B) C) (A . ( ( B . N I L ) . (C . N I L ) ) )
(A . (B . ((C . NIL) . N I L ) ) )
-
List D o t t e d Pair
T r a n s f o r m t h e s e lists t o t h e i r f u l l y expanded d o t n o t a t i o n e q u i v a l e n t s .
1. (ATOM)
2. ((LISP))
3. (((MORE YET)))
4. (HOW ABOUT THIS)
5. (DONT (GET (FOOLED)))
, Now go t h e o t h e r w a y - - d o t t e d p a i r s t o lists.
6. (XI . NIL)
7. (NIL . (X1 . N I L ) )
8. (KNOW . (THY . (SELF . N I L ) ) )
9. ((BEFORE . (AND . (AFTER . NIL))) . NIL)
lo. (A . ( ( ( B . (C . N I L ) ) . NIL) . N I L ) )
To w h a t S - e x p r e s s i o n s d o t h e s e g r a p h s c o r r e s p o n d ?
CHAPTER 4.
NUMBERS
(ALPHA . 960)
a r e l e g a l S-expressions.
i s u n a c c e p t a b l e f o r LISP.
Examples :
+123
+I23
-321
-1~10
=~-1000
+53
Thus,
i s unacceptable f o r LISP.
Examples :
123Q
12342
77743
248
3410
4.3 FLOATING-POINT NUMBERS
Examples :
3.14159 +3.14159
+l.OE-3 +O .001
-976.00333 -976003.00
0.2733+2 +27.30
23.E-1 +2.30
17. +17.00
For instance,
(1.2.3.4)
(1.2 . 3.4)
is perfectly proper.
EXERCISES-
(Q IQ)
(5E (E . . NIL))
(E5 . 5E)
(1.E * 1Q)
43
4.4
(A. 9)
(B .9.9)
(9.9.9)
(1.23 77Q3 27 2735 0.3213-7 ALPHA Q . 32)
Convert the following to list notation, if possible.
When we input to the LISP system, we are communicating with a supervisor program
that always expects two inputs, both S-expressions. If we call this pair of
S-expressions s1 and s2 respectively, the first S-expression, sl, is always
treated by the supervisor as:
(We will focus on the former case here, and examine the latter case in subse-
quent chapters.) Since functions have arguments, the second S-expression, s2'
is always a list of the arguments for the function whose name is the S-expression
S1*
SIN 90'
SIN (90)
where the first S-expression, sl, is SIN and the second S-expression, s2, is
the list (90)--the list of the single argument required by SIN.
As another example, in LISP the function PLUS performs the operation of addition
of its arguments. We can compute the sum of three numbers by giving the
following pair of S-expressions to the supervisor:
--
PLUS (1 2 3)
S
1 S2
5.2 CONS
CONS refers to "the construct of" and is the function that is used to build S-
expressions. It has two arguments that are both S-expressions.
Definition :
For example, given the arguments A and B, we can CONS them by giving the
supervisor
--
CONS (A B)
s1 s2
which means (A . B) .
If the arguments were the lists (A) and (B) , we would write
which is equivalent to
Examples :
CONS(M N) = (M . N)
CONS((A . B) C) = ((A . B) . C)
CONS(A (B C D)) = (A . (B C D ) ) = (A B C D)
5.3 CAR
Definition:
--
CAR ( (M
S
1 S2
. N) )
Examples :
CAR((A . B)) = A
CAR(((A . B) . C ) ) = (A . B)
CAR((A B C D)) = A
CAR(((A B C) D E)) = (A B C)
CAR(FO0) = undefined f o r atoms
5.4 -
CDR
Definition:
CDR ( (M
r---
. N) )
which i s e q u i v a l e n t t o N.
(A B)
i s removed, t h e remainder i s t h e r i g h t p a r t , B.
Thus,
CAR ( ( A . B)) = A
CDR ((A . B)) = B
CAR ((A B ) ) = A
CDR ((A B ) ) = (B)
Examples :
CDR((A . Y)) = Y
CDR((A . (ATOM) ) ) = (ATOM)
CDR((A B C D ) ) = (B C D)
CDR(FO0) = undefined f o r atoms
I n t h e graph we n o t e t h a t
1. CDR ( ((A B) C D) ) = (C D)
2. CDR of t h e o u t p u t of ( I ) , i.e . ,
CDR ( (C D) ) = (D)
3. CAR of t h e o c t p u t of ( 2 ) , i . e . ,
CAR ( (D) ) = D
y i e l d s t h e name
CADDR
CADDR ( ((A B) C D) ) = D
CAR((LEFT . RIGHT))
CDR((LEFT . RIGHT))
CONS (LEFT RIGHT)
CAR((A B C D))
CAR(((A) B C D))
CAR((A (B C Dl))
CAR(((A . B) C D E))
CDR((TH1S SENTENCE IS A LIST))
CDR((H0W (ABOUT THIS)))
CDR(((D0T . PAIR1) (DOT . PAIR2)))
CONS (CAR CDR)
CDR ( (EMPTY) )
CDR((CAR CDR))
CAR ( ( (CAR) CDR) )
CONS(A ( 1)
CONS (754 100)
CAR((1 . (2.0 . (30.OE-1 . 774))))
CDR((1 . (2.0 . (30.OE-1 . 774))))
CONS((A . B) NIL)
CAR((((((ALPHA))))))
CAR CDR
CDR ( (C A T) ) = (A T)
then
CAR ( (A T) ) = A
Q.E.D.
T h i s sequence may b e a b b r e v i a t e d a s f o l l o w s :
where the format is given in Polish prefix notation. (LISP programmers p:refer
calling this format "function notation", where the function always precedes its
arguments.)
Furthermore, in Church's lambda notation
Definition:
I I l i s t of v a r i a b l e s , i . e . ,
varZist
--
(LAMBDA ( J K)
I--
(CONS K J ) )
form, i . e . , body
Examp l e g :
1. (LAMBDA ( ) 1) T h i s i s a lambda e x p r e s s i o n w i t h no
lambda v a r i a b l e s , i . e . , varzist is
NIL. The form i s t h e numerical
c o n s t a n t 1.
2. (LAMBDA (X) 1) This lambda expression has X as the
only lambda variable. Again, the form
is the numerical constant 1. This
example shows that it is not necessary
for the variable to appear in the form.
With Church's lambda notation, both the form and the correspondence between
variables of the function and their values are made explicit by the syntax
of lambda expressions. A lambda expression is the definition of a function.
Conditions:
Mechanics.:
(LAMBDA (J K) (CONS J K) ) (A B)
1
--
CONS (A B)
S
1 s2
(CONS J K)
6.4 PARENTHESES
The lambda e x p r e s s i o n
(LAMBDA (A B) (CONS A B ) )
and
(CONS A B)
Before we l e a v e lambda e x p r e s s i o n s , n o t e t h e f o l l o w i n g e x p r e s s i o n s :
6.6 EXERCISES
7.1 VARIABLES
(LAMBDA (X) X)
the lambda variable X is the form. If we call this function
7.2 CONSTANTS
All constants are elementary forms. Since LISP allows numerical and symbolic
data, there can be numerical and symbolic constants. All numbers are con-
stants in LISP. In addition, most LISP implementations have T and NIL as
symbolic constants for ease of programming condit:ional expressions (as we shall
see in Chapter 11). Apart from these cases, any S-expression may be "quoted"
to make it a symbolic constant. Quoting is performed by the special form QUOTE
described in Chapter 9.
Cfname parameters)
where fname is the name of a built-in function, and parameters may be one or
more variables or constants. In fact, parameters may be empty (i.e., there
may be no variables or constants) if fname is a function of no arguments.
(EXPT X 2)
where EXPT is the fname, and variable X and constant 2 are parameters. Other
examples include
(CONS T NIL)
(CAR X)
(CDRABLE)
(NOARGFUNCTION)
(CONS T NIL)
Try e v a l u a t i n g t h e s e lambda e x p r e s s i o n s :
Note:
Problems 1 and 2 a r e "identit:yl' f u n c t i o n s i n t h a t
t h e y always e v a l u a t e t o t h k i r arguments. Problems
9 and 1 0 a r e " c o n s t a n t " f u n c t i o n s which always
evaluate t o t h e constant specified, i n t h i s case
3.14159, r e g a r d l e s s of t h e v a l u e of t h e argument.
However, t h e s e arguments a r e r e q u i r e d by lambda
conversion. Also, t h e s u p e r v i s o r e x p e c t s a p a i r
of S-expressions a t t h e t o p l e v e l . Further, note
t h a t t h e l i s t of v a r i a b l e s i n problem 1 0 i s empty.
I n LISP, a f u n c t i o n w i t h a n empty v a r i a b l e l i s t i s
a f u n c t i o n of no arguments. For p r o p e r LISP s y n t a x ,
we must always i n c l u d e t h e l i s t of v a r i a b l e s , even
when empty. I n such c a s e s , NIL i s a s a c c e p t a b l e
as ( 1 -
Evaluate :
To apply LISP to more complex problems, we must be able to create more powerful
programs, i.e., more complex forms. This chapter takes a major step in that
direction. It generalizes the concept of a simple form by introducing
composition of forms.
(fname parameters)
If we let args stand for zero or more elementary or composed forms, we can write
down the syntax for a composed form as
It follows from this syntax that, if fname is CAR and args is the elementary
form (CDR J) , then
is a composed form. It also follows from the recursive nature of the syntax
that, if fnme is CONS and args is the composed form (CAR (CDR J)), then
Definition:
I n g r e a t e r d e t a i l , e v a l u a t i o n c o n s i s t s of e v a l u a t i n g a l l args of t h e composed
form, one a t a t i m e ( g e n e r a l l y from l e f t t o r i g h t ) , by t h e f o l l o w i n g s t e p s :
1. I f args i s a c o n s t a n t , t h e c o n s t a n t i s r e t u r n e d a s t h e v a l u e of args.
2. I f a r g s i s a v a r i a b l e , i t s b i n d i n g i s r e t r i e v e d and r e t u r n e d as t h e
v a l u e of args.
4. I f a r g s i s a composed form, a l l p a r t i a l r e s u l t s ( i . e . , t h e v a l u e s of
a l r e a d y e v a l u a t e d a r g s ) a r e saved, and s t e p s 1 through 5 a r e a p p l i e d
recursively t o that args.
5. A f t e r a l l args a r e e v a l u a t e d , t h e v a l u e of t h e f u n c t i o n ( i . e . , fname),
a p p l i e d t o t h e v a l u e s of i t s arguments ( i . e . , a l l t h e a r g s ) , is
r e t u r n e d a s t h e v a l u e of t h e composed form.
Examples :
i s evaluated. T h i s form h a s t h e s y n t a x
(CONS argl a r g 2 )
-51-
where a r g i s t h e simple form (CAR J ) , and a r g 2 i s t h e composed form
1
(CAR (CDR J ) ) . Evaluating t h e s e arguments from l e f t t o r i g h t , we g e t
a r g l = (CAR J ) = A
where a r g
21
i s t h e simple f o m (CDR J ) .
To e v a l u a t e a r g 2 , we r e c u r and f i r s t e v a l u a t e
a r g 2 = (CAR arg21) = B
(CONS argl a r g 2 ) = (A . B)
The v a l u e of t h e composed form, (A . B), i s t h e v a l u e of t h e o r i g i n a l lambda
expression.
(CONS X argl)
argl = (CONS Y arg12)
arg12 = (CONS Z NIL)
Evaluation of t h e s e forms y i e l d s
arg12 = (CONS Z NIL) = (C)
argl = (CONS Y arg12) = (B C)
(CONS X argl) = (A B C)
and the last value, (A B C), is the value of the lambda expression.
we see that the generalization is achieved by allowing any composed form, args,
to appear in lieu of any parameter of a simple form. The discussion of form
composition is not complete, however, until one further generalization is
considered: the generalization of fname.
CAR ( (A)) = A
'.yL'-,
--
(LAT%BDA (J) (CAR J ) ) ((A))
S
1 "2
= .A
This truth holds equally well in composed forms. For this truth to be self
evident, consider the syntactic entity fexp, defined as either a function name,
i.e., fname, or a functional expression. Then the syntax of the most general
composed form is given by
Examples :
These four forms aptly demonstrate the complexity that is possible with form
composition. Observe that forms [l] and [2] are semantically equivalent forms,
as are fo m s [3] and [4] . Note further that form [4] is obtained from form [3]
by substituting an equivalent lambda expression for CONS and by substituting
form [2] for form [I].
The rule for evaluating nested lambda expressions is exactly the same as that
for evaluating composed forms given in Paragraph 8.2 (with one addition to step
5). Since we have generalized the syntax of composed forms as given in that
paragraph, by replacing fname by f e q , step 5 should now read (with the addition
underscored) :
"5. A f t e r a l l a r g s a r e e v a l u a t e d , t h e v a l u e of t h e
f u n c t i o n ( i . e . , f e w ) , a p p l i e d t o t h e v a l u e s of i t s
arguments ( i . , a l l t h e a r g s ) , i s r e t u r n e d a s t h e
v a l u e of t h e composed form. I f - f e w i s a lambda
e x p r e s s i o n , a l l lambda v a r i a b l e s a r e bound by lambda
conversion t o t h e v a l u e s of i t s arguments ( i . e . , all
t h e a r g s ) and t h e v a l u e of t h e lambda form i s t h e v a l u e
of t h e composed form."
Examples :
I f J i s bound t o (A B) , then
(CAR J ) = A
( (LAMBDA (K) (CAR K)) J ) = A
((LAMBDA (K) (CAR K)) (CDR J ) ) = B
E v a l u a t e the f o l l o w i n g :
For t h e a r g u m e n t
c o m p o s e and evaluate your own l a m b d a expressions (using only CAR and CDR)
t h a t evaluate exactly as t h e f o l l o w i n g abbreviations (see P a r a g r a p h 5.5).
12. CAAR
13. CADR
14. CDAR
15. CADAR
E v a l u a t e the f o l l o w i n g :
9.1 -
LIST
(LIST) = NIL
(LIST ~ 1 ) = (CONSAI NIL)
(LIST A 1 A2) = (CONS A 1 (CONS A 2 NIL))
(LIST A1 A2 ... AN) = (CONS A 1 (CONS A 2 (CONS ... (CONS AN NIL) ... ) ) )
Examples :
(LIST 1 2) = ( 1 2)
(CONS 1 2) = (1 . 2)
(LIST T NIL 35) = (T NIL 35)
(LIST T (LIST NIL (LIST 3 5 ) ) ) = (T (NIL ( 3 5 ) ) )
(LAMBDA (X Y) (LIST (CONS X Y) (LIST X Y ) ) ) (A B) = ((A . B) (A B))
9.2 QUOTE
The s y n t a x of QUOTE i s g i v e n by
(QUOTE e )
i s e v a l u a t e d by f i r s t e v a l u a t i n g t h e v a r i a b l e X and t h e n applying t h e f u n c t i o n
CAR t o t h a t v a l u e . I n t h e second example, however, we s e e t h e s u p p r e s s i o n of
e v a l u a t i o n y i e l d e d by QUOTE. The form
(QUOTE X)
i s e v a l u a t e d by simply r e t u r n i n g t h e argument X. We do n o t e v a l u a t e X a s we
d i d i n t h e f i r s t example. We speak of X a s being quoted.
Examples :
e v a l u a t e s t o ALPHA.
e v a l u a t e s t o (ALPHA . BETA) .
(LAMBDA (J) (CONS (QUOTE J ) J ) ) (FOO)
e v a l u a t e s t o (J . FOO) .
S i n c e a r b i t r a r y S-expressions i n LISP may look l i k e forms, QUOTE must be u.sed
t o r e p r e s e n t symbolic c o n s t a n t s a s d a t a of forms. Otherwise, an a t t e m p t w i l l
be made t o e v a l u a t e t h e d a t a a s a form--a situation that usually results i n
an e r r o r . For example, t h e form
(CAR ( 1 2 3 ) )
(CAR (QUOTE (1 2 3 ) ) ) = 1
9.3 EVALQUOTE
When e v a l u a t e d , t h e form y i e l d s a v a l u e
(CONS T NIL)
-60-
which i s i t s e l f a l e g a l form. I f we e v a l u a t e form [2], we g e t
(T . NIL) = (T)
The s y n t a x of EVAL i s g i v e n by
(EVAL e )
has t h e s t r u c t u r e
(EVAL e )
where
It i s i n t e r e s t i n g t o n o t e t h a t t h e v a l u e of form [ l ] above i s e x a c t l y t h e v a l u e
of e i n t h i s example. Hence, t h e v a l u e of
--
CONS (A B)
S
1 s2
Consider t h e g e n e r a l t o p - l e v e l p a i r of S-expressions f o r t h e s u p e r v i s o r a s
(EVAL E)
where t h e b i n d i n g of E i s g i v e n a s
We a r e t o e v a l u a t e t h e form
(EVAL E)
where t h e binding of E i s
CONS (A B)
a t t h e t o p l e v e l , and n e c e s s a r y t o write
Evaluate:
C o m p a r e y o u r a n s w e r s f o r p r o b l e m s 1-5 a n d 1 6 - 2 0 .
E v a l u a t i n g lambda e x p r e s s i o n s a t t h e t o p l e v e l i s a one-shot p r o p o s i t i o n . If
we wish t o e v a l u a t e t h e same e x p r e s s i o n f o r d i f f e r e n t arguments, w e must e n t e r
t h e e n t i r e doublet again. A f t e r e v a l u a t i o n , t h e s t a t e of t h e LISP system i s a s
i t was p r i o r t o execution. This i s d e s i r a b l e f o r many s i t u a t i o n s , i n c l u d i n g
debugging, code execution, and program f o r m u l a t i o n . However, f o r t h e m a j o r i t y
of c a s e s , we would l i k e t o s a v e t h e e x p r e s s i o n a s p a r t of t h e LISP system, g i v e
i t a f u n c t i o n name, and u s e i t r e p e a t e d l y t o b u i l d l a r g e r programs. We can do
t h i s w i t h t h e pseudo-function DEFINE.
Pseudo-functions a r e e x p r e s s i o n s t h a t a r e used l i k e f u n c t i o n s , b u t f o r t h e i r
e f f e c t r a t h e r than f o r t h e i r value. They have " s i d e e f f e c t s 1 ' of i n t e r e s t , b u t
e f f e c t s n o t r e f l e c t e d i n t h e v a l u e of t h e e x p r e s s i o n . Input-output functions
a r e o t h e r examples of pseudo-functions.
DEFINE ( e )
1 1
DEFINE ((
12
i s t h e g e n e r a l s y n t a x f o r t h e complete DEFINE e x p r e s s i o n .
Example :
DEFINE ( (
12
(THIRD I N 3 SECONDOFlST)
10.3 REDEFINING
I f , a f t e r d e f i n i n g a f u n c t i o n , you f i n d t h e d e f i n i t i o n t o be i n e r r o r o r you
wish t o change t h e f u n c t i o n ' s d e f i n i t i o n ( i . e . , change t h e f u n c t i o n ' s lambda
expression) f o r o t h e r r e a s o n s , you need o n l y u s e DEFINE a g a i n w i t h t h e o l d
f u n c t i o n name and a new lambda expression. The new lambda e x p r e s s i o n w i l l b e
compiled and r e f e r e n c e d under t h e o l d name. The o l d compiled code i s d i s c a r d e d
and cannot be r e f e r e n c e d a g a i n . A s w i t h l i s t s t r u c t u r e t h a t i s d i s c a r d e d and
c o l l e c t e d l a t e r , d i s c a r d e d compiled code may b e c o l l e c t e d l a t e r . The g e n e r a l
problem of i n t e r n a l s t o r a g e management i n LISP systems i s handled by a program
c a l l e d t h e "garbage col.lector". I n some LISP systems, t h e s p a c e occupied by
t h e o l d code cannot be reclaimed and i s l o s t t o t h e system. Repeated r e d e f i n i -
t i o n s b u i l d up such "garbage" and should be avoided.
F e e l f r e e t o r e d e f i n e programs a t w i l l . I f you t r y v a r i o u s d e f i n i t i o n s on an
a c t u a l computer, be c a r e f u l n o t t o d e f i n e programs whose names a r e system
f u n c t i o n s , a s you w i l l r e d e f i n e f u n c t i o n s p o s s i b l y used i n t e r n a l l y by t h e system
and thereby g e t i n t o t r o u b l e . A r e p r e s e n t a t i v e s e t of system f u n c t i o n names t o
be avoided i s l i s t e d on t h e i n s i d e f r o n t and back covers of t h i s book.
10.4 EXERCISES
The class of functions that can be formed with what we know so far is quite
limited and not very interesting. We need functions that branch conditionally
on the value of forms and thereby allow a much larger class of functions to be
defined. The special form COND accepts an indefinite number of arguments and
conditionally evaluates these arguments based upon their values. COND thus
allows us to perform analysis of differing cases.
A conditiomZ expression is a special form in LISP and has the following syntax:
where the p are forms that evaluate to NIL or not NIL, and the ei are forms
i
that can have any desired value.
Examples :
1. The f u n c t i o n NOT r e t u r n s a s i t s v a l u e t h e n e g a t i o n of i t s s i n g l e
argument. I f i t s argument i s NIL, i t r e t u r n s n o t NIL, i . e . , T.
I f i t s argument i s n o t NIL, i t r e t u r n s NIL. It can b e d e f i n e d i n
LISP a s f o l l o w s :
X
- -
Y X + Y
true true true
true false false
false true true
false false true
11.3 SELECT
11.4 EXERCISES
Evaluate the following:
The LISP world is divided on this matter into two camps: purists and pragmatists.
Purists call the test functions predicates, and require such functions to return
one of two values--true or false. The pragmatist argues that conditional forms,
as implemented on all LISP systems, test only for NIL. He, like the purist,
defines a predicate as a function that returns either T (true) or NIL (false).
However, he postulates that an additional class of functions exist that may have
NIL as but one value in an infinite domain of non-NIL values. Since NIL is half
the domain of predicate functions, these functions are called semi-predicutes
and may be used in the predicate position of conditional expressions, e.g,, the
pi of a COND clause. CDR is a perfect example of a semi-predicate.
This chapter examines a number of predicates built into most LISP systems.
12.1 ATOM
The predicate ATOM has one argument. The value of ATOM is T if the value of
the argument is an atomic symbol; otherwise, the value of ATOM is NIL.
Examples :
(ATOM T) = T
(ATOM 1.23) = T
(ATOM NIL) = T
(ATOM (QUOTE AVERYLONGSTRINGOFLETTERS)] = T
(ATOM (QUOTE (A B C)) ) = NIL
(ATOM (CONS T NIL)) = NIL
(ATOM (CDR (QUOTE (A)))) = T
12.2
Note:
The p r e d i c a t e EQ i s v e r y implementation-dependent,
based upon t h e c a n o n i c a l form of s t r u c t u r e s i n t e r -
n a l l y used.by a given LISP system. You a r e t h e r e f o r e
advised t o c o n s u l t your own p a r t i c u l a r r e f e r e n c e
literature.
Examples :
(EQ T T) = T
(EQ T NIL) = N I L
(EQ ( ) NIL) = T
(EQ (QUOTE A) (QUOTE B)) = NIL
(EQ (ATOM (QUOTE B)) T) = T
12.3 EQUAL
(EQUAL T T) = T
(EQUAL NIL NIL) = T
(EQUAL 1.23 1.23) = T
(EQUAL (QUOTE (A B ) ) (QUOTE (A B ) ) ) = T
(EQUAL (LIST T) T) = NIL
(EQUAL 174 1 5 ) = T
Note:
(FIXP N) = T i f N e v a l u a t e s t o a n i n t e g e r o r o c t a l number
= NIL i f N e v a l u a t e s t o a f l o a t i n g - p o i n t number
= Undefined i f N e v a l u a t e s t o a non-numeric S-expression
(FLOATP N) = T i f N e v a l u a t e s t o a f l o a t i n g - p o i n t number
= NIL i f N e v a l u a t e s t o a n i n t e g e r o r o c t a l number
= Undefined i f N e v a l u a t e s t o a non-numeric S-expression
I f t h e d e f i n i t i o n of MEMBER u s e s EQ r a t h e r than
EQUAL, t h e v a l u e of L 1 must be a l i t e r a l atom
i f MEMBER i s ever t o r e t u r n T . I f EQUAL i s used,
t h e v a l u e of L1 may be any S-expression.
(NOT P) = T i f P e v a l u a t e s t o NIL
= N I L i f P e v a l u a t e s t o any non-NIL S-expression
Note:
Note:
(AND) = T
OR i s a s p e c i a l f o b and t a k e s an i n d e f i n i t e number
of arguments, n o t a l i s t of arguments. The argu-
ments of OR a r e e v a l u a t e d i n sequence from l e f t t o
r i g h t , u n t i l one i s found t h a t i s non-NIL, or until
t h e end of t h e l i s t i s reached. The v a l u e of OR i s
T i f any argument i s non-NIL; t h e remaining argu-
ments a r e unevaluated. The v a l u e of OR i s NIL i f
a l l arguments a r e NIL. Also,
(OR ) = NIL
12.7 EXERCISES
Evaluate t h e s e p a i r s f o r EVALQUOTE:
X
- Y
- X EQUIV Y
true true true
true false false
false true false
false false true
EQUIV (T T) = T
EQUIV (T NIL) = NIL
EQUIV (NIL T) = NIL
EQUIV (NIL NIL) = T
X
- -
Y X + Y
true true true
true false false
false true true
false false true
IMPLIES (T T) = T
IMPLIES (T NIL) = NIL
IMPLIES (NIL T) = T
IMPLIES (NIL NIL) = T
19. Define t h e p r e d i c a t e INSEQ t h a t i s T i f a l i s t of 5 elements a r e a l l
numbers i n ascending o r descending o r d e r and NIL otherwise. Do n o t
u s e COND; u s e n e s t e d lambda e x p r e s s i o n s . T e s t i t w i t h t h e s e EVALQUOTE
pairs :
INSEQ ( ( 1 2 3 4 5 ) ) = T
INSEQ ( ( 5 4 3 2 1 ) ) = T
INSEQ ((1Q 2.0 99 l O O O Q 1080.0)) = T
INSEQ ((10Q 1 0 10.0 11.0 1 2 4 ) ) = NIL
INSEQ ((10 9 8 74 7 ) ) = NIL
EQN (A A) = T
EQN ( 1 1.0) = NIL
EQN (77Q 774) = T
EQN ((A) A) = NIL
CHAPTER 13.
ARITHMETIC FUNCTIONS
Chapter 4 discusses the LISP syntax of numbers; it might pay to review that
chapter. Let us review three important points:
The numerical arguments to arithmetic functions may be any type of number, i.e.,
integer, octal, or floating-point. An arithmetic function may be given some
fixed-point (i.e., integer or octal) and some floating-point 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. (Integer and octal arguments
always yield an integer value.) If at least one argument is a floating-point
number, then the value of that function will be a floating-point number.
CONS (A B)
whereas A and B a r e v a r i a b l e s i n t h e simple form
(CONS A B)
DIFFERENCE (x y) = x - y
DIFFERENCE h a s f o r i t s v a l u e t h e a l g e b r a i c d i f f e r e n c e of i t s arguments.
MINUS (x) = -x
ADDl (x) = x + 1
SUBl (x) = x - 1
QUOTIENT (x y) = x / y
REMAINDER (x y)
DIVIDE (x y)
DIVIDE returns as its value a list of the QUOTIENT and the REAMINDER of its
arguments. It could be defined by:
EXPT (x y) = xY
RECIP (x) = 1 / x
ABSVAL (x) = I x 1
ABSVAL r e t u r n s a s i t s v a l u e t h e a b s o l u t e v a l u e of i t s argument. If x is
p o s i t i v e , i t r e t u r n s x. I f x i s n e g a t i v e , i t r e t u r n s t h e v a l u e of MINUS(x).
FLOAT (x)
ENTIER (x)
ENTIER (93.75) = 93
ENTIER (-3.75) = -3
ENTIER (0.35) = 0
ENTIER (-0.35) = 0
Note:
where x i s i n r a d i a n s .
DEFINE ( (
(SIN (LAMBDA (X) (PLUS X (TIMES -1.6666666673-1 X X X)
(TIMES 8.3333333333-3 X X X X X)
(TIMES -1.9841269843-4 X X X X X X X)
(TIMES 2.7557319223-6 X X X X X X X X X)))) ))
EXERCISES
Evaluate :
PLUS (1 2 3 4 5 6 7 8 9 10)
DIFFERENCE (99 3.14159)
TIMES (2 2 2 2 2 2 2 2 2 2)
ADD1 (777774)
SUB1 (1.0)
MINUS (-0)
MAX (10 124 10.000000001)
MIN (10 124 9.999999999)
QUOTIENT (55 3)
QUOTIENT (55.0 34)
REMAINDER (55 3)
REMAINDER (55 3.0)
DIVIDE (55 3)
DIVIDE (55 3.0)
DIVIDE (55 34)
ENTIER (123.4)
ENTIER (-123.4
ENTIER (0.7)
ENTIER (-0.7)
SQRT (25)
RECIP (3.0)
:RECIP (3)
F'LOAT (123456789)
ABSVAL (-3.14159)
LOGOR (777774 123454)
LOGOR (7070741 123454)
LOGXOR (7777741 123454)
28. LOGXOR (7070741 123454)
29. LOGAND (777774 123454)
30. LOGAND (7070741 123454)
31. LEFTSHIFT (741 1)
32. LEFTSHIFT (741 -1)
The functions we have thus far defined have used lambda expressions, composition
of forms, and conditional expressions. A still wider class of functions can be
defined using these methods and the method of recursion.
It takes time and practice to think recursively, particularly if you have pro-
gramming experience with the linear flow of control common with algebraic
languages. You cannot be taught to think recursively, but you can learn t:o
think recursively. To help you learn, I give some helpful heuristics, exa-mples,
and more examples.
(CONS X Y)
we are making an explicit call upon the function CONS. CONS, in this case, is
an already existing function. In a recursive function definition, for (say)
function f, we likewise make explicit calls upon functions; however, one or
more such calls are made upon the function f itself. The only apparent differ-
ence between calls upon CONS and calls upon f is that f is the function being
described. But LISP doesn't mind. In most algebraic languages, the programmer
is cautioned not to write subroutines that call upon themselves, since that is
recursion and most algebraic languages cannot handle recursion. In LISP we do
it all the time. For example, it is syntactically and semantically proper to
write
ATOMLIST (R)
I f ATOM A , then
If ATOM B , t h e n
I f ATOM C , t h e n T;
E l s e NIL
E l s e NIL
E l s e NIL
(ATOMLIST (LAMBDA (A B C)
(COND ((ATOM A) (COND ((ATOM B) (ATOM C))
(T F)))
(T F))))
(ATOM (CAR L ) )
(CADDDDDDDDDDDDDDDDDDDR L)
(CDR L)
(NULL L)
DEFINE ( (
(ATOMLIST (LAMBDA (L) (COND ((NULL L) ,T )
( (ATOM (CAR L) ) (ATOMLIST (CDR L ) ) )
ATOMLIST (NIL) = T
1. S t a r t w i t h a t r i v i a l c a s e , o r a t e r m i n a l c a s e i n which t h e r u l e f o r
computation i s known. Some t y p i c a l t r i v i a l o r t e r m i n a l c a s e s a r e :
f o r S-expressions, atoms;
f o r l i s t s , NIL;
f o r numbers, 0 , l .
3. Combine t h e t r i v i a l o r t e r m i n a l c a s e w i t h t h e o t h e r , u s i n g t h e t r i v i a l
o r terminal case f i r s t i n a conditional expression.
2. I n t h e t r i v i a l c a s e where n = 0, then
DEFINE ( (
(FACTORIAL (LAMBDA (N) (COND ((ZEROP N) 1 )
( T (TIMES N (FACTORIAL (SUB1 M ) ) ) ) ) ) ) ) )
FACTORIAL (n) = (TIMES n (TIMES n-1 ... (TIMES 2 (TIMES 1 1)) ... ) )
14.3 MORE RECURSIVE EXAMPLES
The following function definitions are pedagogical devices. Although these
functions are available in LISP, these definitions may not exactly replicate
those in a given system.
2. The function APPEND has two arguments, both lists. The value is a
list formed by appending the second list to the first. For example:
3. The function LAST has one argument, a list. The value is the last
top-level element of the list.
t h e f u n c t i o n ASSOC (E L) s e a r c h e s t h e l i s t L f o r a p a i r , t h e f i r s t .
element of which i s e q u a l t o Em I f such a p a i r i s found, i t i s
r e t u r n e d a s t h e v a l u e of ASSOC. Otherwise, t h e v a l u e i s NIL, e . g . ,
Example :
14.5 EXERCISES
1. Evaluate
f o r t h e f o l l o w i n g arguments:
j! A
J f (A B)
d
( ( X . Y) . (X. z))
-8 (A B C)
)
C
(A (C . E))
2. Evaluate
1,'
(K A Y) (E V E)
I*
/;> ( E L L I N ) (HE L EN)
3. Define
Evaluate
J.
TWIST (((A . B) . C ) )
* >
TWIST ( ( A B C))
TWIST (((A . B)))
4. Let u s p l a n how t o d e f i n e , r e c u r s i v e l y , t h e f u n c t i o n
SUM (x y) = x + y
(SUM (LAMBDA (X Y)
(COND ( (ZEROP Y) X)
(T (SUM (ADD1 X) (SUB1 Y)))))
Using t h i s d e f i n i t i o n , show t h e arguments and v a l u e s of SUM each time
i t i s entered f o r
SUM ( 1 2)
PROD (x y) = x * y
Hint :
6. We know t h a t d i v i s i o n i s e s s e n t i a l l y r e p e a t e d s u b t r a c t i o n , and t h a t
t h e remainder i n d i v i s i o n i s t h e r e s i d u e when s u b t r a c t i o n i s no
longer possible. Therefore, d e f i n e recursively
Use t h i s a l g o r i t h m t o d e f i n e GCD (x y ) ; e . g . ,
GCD (7 7) = 7
GCD (19 7 ) = 1
GCD (28 35) = 7
10. Define
AMONG ( a R)
AMONG (X (A B X)) = T
AMONG (X (A B ( X ) ) ) = NIL
11. Define
INSIDE (a e )
INSIDE (X (A B X)) = T
INSIDE (X (A (X) B ) ) = T
INSIDE (X ( A . (B . x))) = T
12. Define
COPYN (x n)
COPYN ( (A B) 3) = ((A B) (A B) (A B) )
Most LISP systems have functions LENGTH, UNION, INTERSECTION, REVERSE, and
SUBST available as built-in functions. If you e,rrin redefining such functions
to the computer, you can "crash" the system. For that reason, I have avoided
name clashes in the following problems, but realize the direct correspondence
between these names and LENGTHS, UNIONS, INTERSECT, REVERSAL, and REPLACE,
respectively.
13. Define
LENGTHS (R)
14. Define
UNIONS (x y)
which returns a list that contains every element that is in one list
or the other or both. The order in which the elements are presented
is first, all the elements that are in the first list, x, and not in
the second list, y, and second, all elements in the second list, y,
whether or not they are in list x.
Hint :
INTERSECT (x y )
INTERSECT ((A B C) (B C D ) ) = (B C)
INTERSECT ((A B C) (D E F ) ) = NIL
16. Define
REVERSAL (R)
which r e v e r s e s t h e o r d e r of t o p - l e v e l elements of t h e l i s t R; e . g . ,
REVERSAL ( ( ( A B) D (D E) G) ) = (G (D E) D (A B ) )
Hint :
17. Define
DELETE (a R)
DELETE (Y (X Y z ) ) = (X Z)
19. Define t h e p r e d i c a t e
INSEQ (R)
which is T if list P. contains a numerical sequence in proper ascending
or descending order, and NIL otherwise.
Hint :
INSEQ (1 2 3 4) = T
INSEQ (40 30 2 1) = T
INSEQ (1 23 24 27 26 30) = NIL
INSEQ (10.0 9 8 7.4 2.3) = T
INSEQ (A B C D E) = NIL
20. Define
REPLACE (a b x)
which is a function that replaces the atom b by the atom a for every
occurrence of b in x. a, b, and x are S-expressions.
REPLACE (A B (A B C D)) = (A A C D)
REPLACE (TWO TO (WE TO HAVE TO CATS)) = (WE TWO HAVE TWO CATS)
CHAPTER 15.
THE PROGRAM FEATURE
(LAMBDA v a r Z i s t body)
(PROG v a r Zist s t a t e m e n t s )
The l i s t of v a r i a b l e s , v a r Z i s t , a s w i t h lambda e x p r e s s i o n s , c o n t a i n s t h e
v a r i a b l e s of t h e PROG r e q u i r e d by t h e s t a t e m e n t s . The s t a t e m e n t s a r e themselves
S-expressions.
We u s u a l l y c a l l t h e v a r i a b l e s a s s o c i a t e d w i t h t h e lambda e x p r e s s i o n lambda
v a r i a b l e s , and t h o s e a s s o c i a t e d w i t h t h e PROG, program o r prog v a r i a b l e s . The
l i s t of program v a r i a b l e s , j u s t l i k e t h e l i s t of lambda v a r i a b l e s , must always
b e p r e s e n t i n t h e s t r u c t u r e of t h e e x p r e s s i o n . I f w e have none, t h e n t h e l i s t
i s e n t e r e d a s NIL o r ( ) .
(SETQ P I 3.14159)
LOCl (SETQ R N)
(SETQ AREA (TIMl3S R P I R ) )
(SETQ R N)
Statements are normally executed in sequence. Executing a statement means
evaluating the form. Program statements are often executed for their effect
rather than for their value, as with SETQ above. The GO statement is a perfect
example of execution for effect rather than value. GO is a function used to
cause a transfer to a named statement. It is a function of one argument that
is not evaluated--that argument being a statement label, e.g.,
(GO LOC1)
To exit from a PROG, we use RETURN. RETURN is a function of one argument, and
the argument is evaluated. The value of the argument is returned as the value
of the PROG. A RETURN statement terminates the PROG form and no further
statements are executed.
We can also exit from a PROG without the RETURN statement by just "running outs'
of statements. In that case, the value of the PROG is always NIL.
If we nest a PROG within a PROG, within a PROG, etc., the GO, RETURN, SETQ,
etc., will have a scope local to the most recent PROG. For example, GO cannot
transfer to a statement label within another higher- or lower-level PROG.
S i m i l a r l y , RETURN t a k e s you "up" one l e v e l t o t h e n e x t h i g h e r e x p r e s s i o n . In
c e r t a i n s p e c i a l c a s e s , SETQ may b e used on v a r i a b l - e s d e f i n e d by a h i g h e r - l e v e l
PROG. These v a r i a b l e s are t h e n c a l l e d free variables and r e q u i r e s p e c i a l
attention. W e w i l l d i s c u s s v a r i a b l e s and t h e i r b i n d i n g s i n t h e n e x t c h a p t e r .
15.5 EXAMPLES
FACTORIAL--recursive definition
DEFINE ( (
(FACTORIAL (LAMBDA (N)
(COND ((ZEROP N) 1 ) (T (TIMES N (FACTORIAL (SUB1 N ) ) ) ) ) ) )
1)
DEFINE ( (
(FACTORIAL (LAMBDA (N) (PROG (Y) ,
(SETQ Y 1 )
TAG1 (COND ((ZEROP N) (RET'URN Y) ) )
(SETQ Y (TIMES N Y))
(SETQ N (SUB1 N))
I n t h e s e examples, t h e r e c u r s i v e d e f i n i t i o n a p p e a r s t o b e s i m p l e r t h a n t h e
one u s i n g t h e program f e a t u r e . I n o t h e r problems i t may b e o t h e r w i s e . The
c h o i c e of whether t o u s e t h e program f e a t u r e o r t o u s e "pure LISP" i n writing a
program, depends i n l a r g e measure on t h e problem. S t y l e i n programming i s o f t e n ,
however, t h e s t r o n g e r influence--as noted by F i s h e r Black.
9
Example:
G i v e n a l i s t of n u m b e r s , d e f i n e the f u n c t i o n SORT,
w h i c h s o r t s these n u m b e r s i n t o odd o r even and
r e t u r n s a l i s t of t w o s u b l i s t s of t h e f o r m :
((odd-count l i s t - o f - o d d - n u m b e r s ) (even-count l i s t - o f - e v e n - n u m b e r s ) )
DEFINE ((
(SORT (LAMBDA (X) (PROG (ODD EVEN ODDCNT EVENCNT L )
(SETQ L X) (SETQ ODDCNT 0) (SETQ EVENCNT 0)
LOOP (COND ((NULL L) (RETURN ( L I S T ( L I S T ODDCNT ODD)
( L I S T EVENCNT E V E N ) ) ) )
((EVENP (CAR L ) )
(SETQ EVEN (PROG2 (SETQ EVENCNT (ADD1 EVENiCNT) )
(CONS (CAR L ) EVEN) ) ) )
(T (SETQ ODD (PROG2 (SETQ ODDCNT (ADD1 ODDCNT))
(CONS (CAR L ) ODD)) ) ) )
(SETQ L (CDR L ) )
(GO LOOP) 1)) ))
Note:
T h e c o n d i t i o n a l clause
c o u l d have been w r i t t e n
-110-
(T (PROG2 (SETQ ODDCNT (ADD1 ODDCNT) )
(SETQ ODD (CONS (CAR L) ODD) ) ) )
I chose the former method to emphasize the return of the value of the last argu-
ment. In fact, some systems generalize PROG2 to PROGN, a special form of an
indefinite number of arguments that returns the value of the last argument.
PROGN can be defined as a macro (see Chapter 19) in terms of PROG2.
15.7 EXERCISES
NEGCNT (2)
which counts the number of negative numbers at the top level of list R.
1. A parabola if discriminant = 0
2. An ellipse if discriminant < 0
3. A hyperbola if discriminant > 0
Define
CURVE (a b c)
DEFINE ( (
(LENGTHS (LAMBDA (M)
(COND ((NULL M) 0)
(T (ADD1 (LENGTHS (CDR M) 1)) 1) 1 )
DEFINE ( (
(LAST (LAMBDA (L)
(COND ((NULL L) NIL)
((NULL (CDR L) ) (CAR L) )
(T (LAST (CDR L ) ) ) ) ) ) 1)
D e f i n e LAST u s i n g PROG.
5. REVERSAL
6. PAIRS
7. DELETE
P ( n , r ) = n! / (n-r)!
PERMUT (n r ) = n! / (n-r)!
C(n,r) = n! / r ! (n-r)!
D e f i n e , w i t h and w i t h o u t PROG
COMBIN (n r ) = n! / r! (n-r)!
10. An interesting way to obtain the combinations of n different things
taken r at a time is to construct Pascal's triangle. The triangle
looks like this:
r=O
n=O -+ 1 r=l
n=l + 1 1 r=2
Y
n=2 -+ 1 2 1 r=3
n=3 -+ 1 3 3 1 r=4
n=4 -+ 1 4 6 4 l Y r +
n=5 -+ 1 5 1 0 1 0 5 1
and ignoring the triangular format, use your definition for COMBIN to
define
PASCAL (n)
PASCAL (5) =
(1)
(1 1)
(1 2 1)
(1 3 3 1)
(1 4 6 4 1)
(1 5 10 10 5 1)
NIL
CHAPTER 16.
VARIABLES AND THEIR BINDING
BOUND VARIABLES
Rule:
An e x p r e s s i o n t o b e e v a l u a t e d h a s a c o n t e x t g i v e n by t h e c u r r e n t b i n d i n g s of a l l
its variables. S i n c e t h e v a l u e of t h e e x p r e s s i o n depends upon t h e c u r r e n t
b i n d i n g s , t h e v a l u e of t h e e x p r e s s i o n depends upon i t s c o n t e x t . Change t h e
c o n t e x t and you (probably) change t h e v a l u e of t h e e x p r e s s i o n .
On t h e o t h e r hand, v a r i a b l e s a r e d e f i n e d by e x p r e s s i o n s ; t h e i r scope of d e f i n i -
t i o n , i n which a g i v e n b i n d i n g may b e r e t r i e v e d , i s r e s t r i c t e d t o t h e e x p r e s s i o n
i n which t h e y were d e f i n e d . O u t s i d e t h a t scope, t h e b i n d i n g , o r even t h e
v a r i a b l e i t s e l f , does n o t e x i s t . For lambda v a r i a b l e s , t h e s c o p e i s t h e body
of t h e lambda e x p r e s s i o n . For program v a r i a b l e s , t h e s c o p e i s t h e statements
of t h e program e x p r e s s i o n .
F r e q u e n t l y , however, a n e x p r e s s i o n may r e f e r e n c e a v a r i a b l e i t h a s n o t d e f i n e d .
I f t h i s r e f e r e n c e i s t o b e meaningful, t h e v a r i a b l e must b e d e f i n e d and bound a t
some h i g h e r l e v e l such t h a t i t s scope encompasses t h e immediate e x p r e s s i o n . We
speak of such r e f e r e n c e s a s " f r e e r e f e r e n c e s " and c a l l t h e v a r i a b l e s free
variables .
Examine t h e e x p r e s s i o n
P I i s a f r e e v a r i a b l e i n t h e innermost lambda e x p r e s s i o n ,
C2*
-
f o l l o w s d u r i n g t h e evaluation of t h e innermost lambda e x p r e s s i o n .
--
((R
C
. 2)
2
(PI . 3.14159)
C
1
(J . 2) ... )
(TIMES 2 P I R)
i s e v a l u a t e d , t h e a - l i s t i s searched f o r t h e v a l u e s of v a r i a b l e s R and P I . R
i s found i n t h e c u r r e n t c o n t e x t , l a b e l e d c 2 , b u t P I i s found a t a h i g h e r c o n t e x t
l e v e l , labeled c Thus, f r e e v a r i a b l e s a r e e v a l u a t e d by searching through t h e
1'
complete a - l i s t , independent of c o n t e x t , u n t i l t h e f i r s t occurrence of t h e
v a r i a b l e i s encountered. I f a f r e e v a r i a b l e h a s rrot been bound a t some h i g h e r
l e v e l , no a s s o c i a t i o n w i l l be found on t h e a - l i s t and an e r r o r w i l l r e s u l t .
CONSTANTS
(CSET vl v2)
(CSETQ P I 3.14159)
Note t h a t CSET a t t h e t o p l e v e l i s
CSET ( P I 3.14159)
The b i n d i n g of v a r i a b l e s on a n a - l i s t i s a d e q u a t e f o r i n t e r p r e t e r s where t h e
lambda e x p r e s s i o n i s saved and e v a l u a t e d each t i m e ; b u t i t i s i n a d e q u a t e f o r
compiled f u n c t i o n s s i n c e t h e symbolic e x p r e s s i o n s a r e t r a n s l a t e d i n t o machine
code and d i s c a r d e d . Compiled f u n c t i o n s a l s o r u n one o r two o r d e r s of magnitude
f a s t e r t h a n i n t e r p r e t e d f u n c t i o n s by e l i m i n a t i n g t h e c o s t l y a - l i s t s e a r c h e s
during evaluation.
I f a v a r i a b l e i s an o r d i n a r y one, a s t o r a g e l o c a t i o n i s r e s e r v e d f o r i t on t h e
push-down l i s t when t h e e x p r e s s i o n i n which i t i s d e f i n e d i s e v a l u a t e d . Other
f u n c t i o n s cannot f i n d t h i s p r i v a t e c e l l , making i t impossible t o u s e i t a s a
f r e e v a r i a b l e on most systems. Ordinary v a r i a b l e s a r e lambda and program
variables, i.e., dummy v a r i a b l e s . After t h e parent expression is evaluated
and e v a l u a t i o n moves t o a h i g h e r - l e v e l e x p r e s s i o n , t h e r e s e r v e d l o c a t i o n i s
r e l e a s e d , and i t s c o n t e n t s a r e l o s t , analogous t o r e l e a s i n g c o n t e x t on an
a-list .
S p e c i a l v a r i a b l e s a r e used f o r c o n s t a n t s and f r e e v a r i a b l e s . Such v a r i a b l e s
have i n d i c a t o r s a s s o c i a t e d w i t h t h e i r names ( i n some implementation-dependent
manner) d e s i g n a t i n g them a s s p e c i a l v a r i a b l e s . When a f u n c t i o n u s e s a v a r i a b l e
f r e e l y , t h e q u a n t i t y i n t h e v a l u e c e l l i s t h e v a l u e of t h e v a r i a b l e .
SPECIAL ( ( P I DOG))
T h i s c h a p t e r h a s no e x e r c i s e s because of t h e d i f f e r e n t t r e a t m e n t g i v e n v a r i a b l e s
by d i f f e r e n t implementations. The a r e a s of common t r e a t m e n t , s u c h a s dummy
v a r i a b l e s , have been covered by p r e v i o u s c h a p t e r s . For more i n f o r m a t i o n and
e x e r c i s e s , c o n s u l t t h e LISP e x p e r t f o r your system.
C H A P T E R 17.
DEBUGGING, INPUT-OUTPUT, AND SUPERVISORS
S y n t a c t i c E r r o r Sources
1. READ b a l k s b e c a u s e of a n i n s u f f i c i e n t number of r i g h t
parentheses.
2. READ b a l k s because a n S - e x p r e s s i o n b e g i n s w i t h a r i g h t
p a r e n t h e s i s - - a symptom of a n e x c e s s of r i g h t p a r e n t h e s e s
i n t h e p r i o r S-expression read.
3. READ b a l k s because a n S - e x p r e s s i o n w r i t t e n i n d o t - n o t a t i o n
h a s "too many d o t s v - - a symptom of a p o o r l y formed S -
expression.
4. READ b a l k s because of a n i l l e g a l l y s p e l l e d atom. Check t h e
l e g a l s y n t a x of numbers and l i t e r a l atoms allowed by your
system. Watch o u t f o r t h e c l a s s i c e r r o r of i n t e r c h a n g i n g
t h e numbers z e r o and one, and t h e l e t t e r s "0" and 'rI".
Also, i f t h e S - e x p r e s s i o n b e i n g r e a d was o r i g i n a l l y produced
by a LISP p r i n t o u t on c a r d , t a p e , o r d i s c , any u n u s u a l l y
s p e l l e d l i t e r a l atoms p r e v i o u s l y e n t e r e d a s s t r i n g s ( s e e
Paragraph 17.6) have p r o b a b l y been s t r i p p e d of t h e s t r i n g
q u o t i n g a p p a r a t u s and p r i n t e d a s a l i t e r a l s t r i n g . You
cannot re-read such s t r i n g s without r e s t o r i n g t h e s t r i n g
quoting apparatus.
Semantic E r r o r Sources
1. Check s y n t a x e r r o r p o s s i b i l i t i e s .
8. Terminating c o n d i t i o n s of r e c u r s i v e f u n c t i o n s a r e v e r y
important. Check t h a t you have t h e r i g h t c o n d i t i o n s , t h e
proper number of them, and have s i t u a t e d them i n t h e proper
place i n the recursive function definition.
DIAGNOSTIC TOOLS
Other n o n - s t a n d a r d d i a g n o s t i c t o o l s , t h a t a l l o w even g r e a t e r c o n t r o l of
program e x e c u t i o n a r e u s u a l l y p r e s e n t i n a given LISP system. These too:Ls
i n c l u d e u s e r a c c e s s t o t h e e r r o r message and unwind c o n t r o l ; c o n d i t i o n a l
t r a p s on CONS u s a g e ; and v a r i o u s b r e a k p o i n t t r a p s and t r a c e s . The l i t e r a t u r e
f o r your system probably e x p l a i n s t h e i r o p e r a t i o n and should b e c o n s u l t e d .
RATOM i s a machine-language r o u t i n e t h a t c o n v e r t s c h a r a c t e r s t r i n g s i n t o
i n t e r n a l atomic s t r u c t u r e . When a non-numeric c h a r a c t e r s t r i n g i s r e a d , i t
must be compared w i t h t h e c h a r a c t e r r e p r e s e n t a t i o n of a l l l i t e r a l atoms seen
s o f a r , t o determine whether t h i s s t r i n g i s a new atom o r a r e f e r e n c e t o one
seen b e f o r e .
There must b e r a p i d a c c e s s t o a l l t h e atoms i n the system. There e x i s t s , t h e r e -
f o r e , a l i s t c a l l e d t h e o b j e c t list, o r OBLIST, of a l l l i t e r a l atoms. To speed
up t h e s e a r c h f o r comparisons, t h e OBLIST i s u s u a l l y o r g a n i z e d as a l i s t of a
hundred o r s o s u b l i s t s o r "buckets". The atoms a r e d i s t r i b u t e d among t h e
b u c k e t s by a computation upon t h e i r H o l l e r i t h p r i n t names (hash c o d i n g ) , which
y i e l d s a r e a s o n a b l y uniform and random d i s t r i b u t i o n of atoms among t h e b u c k e t s .
LPAR c
WAR 1
BLANK space
PERIOD
SLASH
EQSIGN
UPARROW
DOLLAR
STAR
PLUSS
DASH
SUPERVISORS
--
FOO (A B C)
DEFINE ( (
(SUP3 (LAMBDA ( ) (PROG ( )
TAG1 (TEREAD)
(PRINT (EVAL (READ) ) )
(GO TAGl)))) 1)
(CAR (QUOTE (A B C ) ) )
CSET ( P I 3.14159)
CAR ( ( P I ) ) = P I
5. An e x p r e s s i o n e v a l u a t e d a t t h e t o p l e v e l t h a t e x p l i c i t l y PRINTS i t s
v a l u e may have t h e v a l u e 05 t h e e x p r e s s i o n o u t p u t twice--once by t h e
e x p l i c i t c a l l t o PRINT, and once by EVALQUOTE, which always p r i n t $ t h e
v a l u e of t h e e x p r e s s i o n , e . g . ,
PRINT (ABCD)
yields
ABCD
ABCD
17.9 EXERCISES
E v a l u a t e the f o l l o w i n g i n o r d e r :
1. PRINT ( ( L I S T ) )
2. TERPRI N I L
TERPRI NIL
3. (LAMBDA (X Y) (PROG ( )
( P R I N 1 X) ( P R I N 1 BLANK) ( P R I N 1 Y) (TERPRI))) (ATOM1 ATOM2)
4. READ N I L
then enter:
(NOW HEAR THIS)
5. (LAMBDA (J) (CONS (READ) J ) ) ((ANYTHING))
then enter:
(INPUT)
6. (LAMBDA NIL (PROG ( P I R)
(SETQ P I 3 . 1 4 1 5 9 )
TAG (SETQ R (READ))
(COND ((EQUAL (QUOTE END) R) (RETURN R ) ) )
(PRINT (TIMES 2 P I R ) )
(GO TAG))) N I L
E n t e r a n u m b e r f o r R. T h e p r o g r a m r e t u r n s the c o m p u t a t i o n of
2 * PI * R a n d then r e a d s a g a i n .
Y o u can s t o p t h e l o o p by e n t e r i n g
END
7. (LAMBDA ( ) (LIST LPAR RPAR BLANK PERIOD SLASH EQSLGN DOLLAJ3 STAR
(QUOTE $$* NOW HEAR T H I S *) (QUOTE $$+ - 5 3 3 . 1 7 + ) ) ) (
8. CDR ((A B C ) ) CDR ((1 2 3 ) ) entered on one l i n e .
9. 1. CSET(PERCENT $$*%*)
2. (LAMBDA ( ) PERCENT) (. )
3. (LAMBDA (J) J ) (PERCENT)
10. CAR ((A B C ) ) ) ) ) ) ) ) ) ) ) ) ) )
11. D e f i n e EVALQUOTE g i v e n i n the t e x t a s SUP2 t o a v o i d a n a m e clash
w i t h a p o s s i b l e EVALQUOTE i n y o u r s y s t e m . T r y SUP2 w i t h these cases:
sup30
1. (CAR ( L I S T (QUOTE ( A ) ) ) )
2. (CONS (QUOTE A) (QUOTE B ) )
3. (CSETQ K 3 . 1 4 1 5 9 )
4. (CONS K N I L )
5. (PROG (X) (PRIN1 (QUOTE X))
( P R I N ~ $$* *) (PRINI (QUOTE SQUARE)) (TERPRI) (TERPRI)
(SETQ x O)
TAGl (COND ((EQUAL X 10) (RETURN (QUOTE END))))
( P R I N 1 X) ( P R I N 1 $$* *) (PRIN1 (TIMES X X ) ) (TERPRI)
(SETQ X (ADD1 X ) )
(GO TAGl))
1. ((A B C ) ) CAR
2. ((A B C ) ) CDR
3. (A B) EQ
4. (1 2 3 4 ) PLUS
5. (K 3.14159) CSET
6. NIL (LAMBDA () K)
1. Saves t h e symbolic p a i r s .
2. P r i n t s t h e p a i r f o r i n s p e c t i o n a f t e r i n p u t , l i k e a n echo.
3. Queries your acceptance o r r e j e c t i o n of t h e p r i n t e d p a i r .
4. I f you answer NO, i t loops f o r a n o t h e r p a i r .
5. I f you answer YES, SUP5 p r i n t s t h e p a i r , followed by a n e q u a l
s i g n , followed by t h e v a l u e of t h e p a i r , and t h e n loops f o r
another p a i r .
OPERATE (op a b)
OPERATE (+ 3 4) = 7
OPERATE (* 3 4) = 12
In LISP, functional arguments are extremely useful and further expand the class
of LISP functions. We call the class of functions that take this type of
argument funct<onaZs.
18.1 FUNCTION
When arguments are transmitted to a function, they are always evaluated, except
when they are transmitted to a special form which controls how its arguments are
evaluated. When we use functions or functional expressions as arguments, we
wish to transmit these arguments unevaluated. The special form FUNCTION is used
for this purpose in LISP. FUNCTION acts very much like QUOTE, and in fact in
some LISP systems, FUNCTION and QUOTE are often interchangeable. FUNCTION is
used with functional arguments to signal that a function is being transmitted as
an argument.
FUNCTION is a special form that takes one argument, a function name or a lambda
expression. It has the form
(FUNCTION fexp)
DEFINE ( (
(MAP (LAMBDA (X FN) (PROG ( )
TAG1 (COND ((ATOM X) (RETURN X) ) )
(FN X)
(SETQ X (CDR X))
(GO TAG11 1)) 1)
Example:
yields
(THIS IS (A LIST))
( I S (A L I S T ) )
((A L I S T ) )
NIL
18.3 MAPLIST
MAPLIST (X FN)
where the first argument, X, must be a list, and the second argument, FN, must
be a function of one argument. The value of MAPLIST is a new list of the values
of FN applied to the successive CDR segments of list X. That is, the value of
MAPLIST (X FN) can be expressed as the value of t'he form
DEFINE ( (
(MAPLIST (LAMBDA (X FN)
(COND ((NULL X) NIL)
(T (CONS (FN X) (MAPLIST (CDR X) FN) ) ) ) ) ) ) )
Examples :
DEFINE ( (
(SQUARECAR (LAMBDA (X) (TIMES (CAR X) (CAR X) ) ) ) ) )
(LAMBDA (J) (MAPLIST J (FUNCTION CDR)) ) ((A B C)) = ((B C ) (C) NIL)
The function MAPCAR is a function like MAPLIST, in that it lists the values of
functional argument FN successively applied to each element of list X. It
differs from MAPLIST, in that it applies FN to each element of the list X; i.e.,
the CAR of what FN is applied to in MAPLIST. MAPCAR is defined by
DEFINE ((
( W C A R (LAMBDA (X FN)
(COND ((NULL X) NIL)
(T (CONS (FN (CAR X) ) (MAPCAR (CDR X) FN) ) ) ) ) ) ) )
Examples:
In example [I], ADD1 is the functional argument, and the lambda expression adds
one to each element in a list of numbers. In example [ 21 , we have a lambda expres-
sion as the functional argument. The result is the input list with each numerical
element replaced by its square.
DEFINE ( (
(MAPC (LAMBDA (X FN) (PROG ( )
A (COND ((ATOM X) (RETURN X)))
(FN (CAR x))
(SETQ X (CDR X))
(GO A) 1)) 1)
Example:
THIS
IS
(A LIST)
NIL
18.6 CAUTIONS
Most functionals ( . e functions that take functional arguments) cannot be used
at the top level, since the special form FUNCTION must be evaluated. As we
know, EVALQUOTE quotes arguments when transmitting them, thus FUNCTION would not
be evaluated. Therefore, use functionals only in lambda expressions.
18.7 EXERCISES
Evaluate the following:
J' I. (LAMBDA (L) (MAP L (FUNCTION PRINT)) ) ((TRY THIS SIMPLE CASE FIRST))
Note:
I f we consider t h e f u n c t i o n a l argument h e r e a s a
separate function, i t is evident t h a t i t contains
a bound v a r i a b l e J , and a f r e e v a r i a b l e Y. This
f r e e v a r i a b l e r e q u i r e s a SPECIAL d e c l a r a t i o n , even
though i t i s bound i n YDOT.
i .
\j h \ YDOT ((A B C D E) Z)
YDOT ((AB C D E) ( 1 2 3 4 5))
TYPE (x)
For example,
CAR CDR
A
i \
CAR CDR s I
A t B P C
Similarly, the list
i s t h e graph
i s t h e g r a p h of a c i r c u l a r l i s t ( i . e . , the t a i l p o i n t s b a c k t o t h e head) t h a t
can o c c u r i n LISP a s t h e r e s u l t of computation. Of course, i t s printed repre-
s e n t a t i o n i s i n f i n i t e i n l e n g t h , and i s of t h e form
CMARY
I
-+JOHN DOE
4
RPLACD r e p l a c e s t h e CDR of X by Y. I t s v a l u e i s X, b u t
X i s now a d i f f e r e n t s t r u c t u r e from what i t was b e f o r e .
The v a l u e of RPLACD can be d e s c r i b e d by t h e v a l u e of t h e
form
(CONS (CAR X) Y)
-146-
However, t h e e f f e c t i s q u i t e d i f f e r e n t ; t h e r e i s no CONS
involved, only p o i n t e r s a r e changed.
X
CAR CDR,
+ A B
b
E v a l u a t i n g t h e form
y i e l d s t h e graph
X
E v a l u a t i n g t h e form
(RPLACD X Y)
y i e l d s t h e graph
X
CAR CDR
A
Y
+ D - - E
n
F
E v a l u a t i n g t h e form
y i e l d s t h e graph
CAR CDR
w B C
I t
Evaluating the f o m
(NCONC X Y)
y i e l d s t h e graph
X
E v a l u a t i n g t h e form
(NCONC X XI
What i s t h e b e s t way t o o r g a n i z e a h i g h l y s t r u c t u r e d , y e t i n d e f i n i t e c o l l e c t i o n
of p r o p e r t i e s f o r a group of mathematical objects--a r e s t r i c t e d d i c t i o n a r y of
E n g l i s h words, f o r example? One s i m p l e s o l u t i o n i s t o have t h e d a t a o r g a n i z e d
l i k e an a - l i s t , i.e., a l i s t of p a i r s . One element of each p a i r c o u l d b e a
l i t e r a l atom t h a t r e p r e s e n t s t h e mathematical o b j e c t ; t h e o t h e r element of t h e
p a i r could be t h e l i s t of p r o p e r t i e s . Then f u n c t i o n s l i k e ASSOC could b e used
t o s e a r c h t h e l i s t f o r d e s i r e d i n f o r m a t i o n , u s i n g t h e l i t e r a l atoms a s i n d i c e s .
An a l t e r n a t i v e s o l u t i o n i s t o d i r e c t l y " a t t a c h " t h e p r o p e r t i e s of i n t e r e s t t o
each atom. The a t t a c h m e n t i s achieved by means of a p r o p e r t y l i s t o r p - l i s t
t h a t i s a s s o c i a t e d w i t h e a c h l i t e r a l atom. For many a p p l i c a t i o n s , t h e u s e of
p r o p e r t y l i s t s o f t e n improves t h e speed and f l e x i b i l i t y of problem s o l u t i o n b y ,
r e p l a c i n g c o s t l y l i s t s e a r c h e s w i t h d i c t i o n a r y - l i k e lookup on t h e p r o p e r t y l i s t .
CAR
v
I
OTHER DATA
CDR
b SEX - - F
I
PARENTS c b AGE
w d 4
CLARK
GET (X Y) GET i s a f u n c t i o n t h a t s e a r c h e s t h e l i s t X f o r a n
i n d i c a t o r E ~ U A L ' t o Y. I f such a n i n d i c a t o r it; found,
i t s property--the n e x t l i s t element ( i . e . , t h e CAR of
t h e r e s t of t h e l i s t ) - - i s r e t u r n e d a s t h e v a l u e of GET.
Otherwise, t h e v a l u e of GET i s NIL.
PUT (X Y 2) T h i s f u n c t i o n p u t s on t h e p r o p e r t y l i s t of t h e l i t e r a l
atom X t h e i n d i c a t o r Y followed by t h e p r o p e r t y Z. Any
previous p r o p e r t y of Y i s r e p l a c e d by 2. The v a l u e of
PUT i s Y.
Assume the property list for ELLIN given in Paragraph 19.4. We may evaluate the
following expressions:
After evaluation of this last example, the property list of ELLIN is augmented
by the indicator SISTERS and the property (HILLARY WENDY).
The result of this form is the deletion of the indicator SEX and the
property F from the p-list ELLIN.
19.6 MACROS
'some systems use EQ rather than EQUAL in property list search functions, thereby
requiring literal atoms as indicators.
As we have already seen, functions can he compiled by DEFINE or by top-level
evaluation of a lambda expression. In the latter case, evaluation means first
compile and then run the compiled code with the supplied arguments. This is
often called "compiling at run-time". This distinction is significant because
it enables compiled code to operate where previously an interpreter was necessary.
In particular, it affects the code that is compiled for a function that enables
that function to retrieve the correct binding for variables at run-time.
The function MACRO takes an argument list in the same format as DEFINE, e.g.,
As with DEFINE, MACRO compiles each of these definitions. Now watch closely,
for here comes the difference. When a macro function (defined by MACRO)
used in a lambda expression, either at the top level or within a DEFINE, the
macro function is executed before the lambda expression (of which it is part)
is compiled. The argument for the macro is the form in which it is used. In
other words, the macro function is run before compile-time for its effect on
the lambda expression. What does this buy us? That depends on the macro, but
essentially it allows us to expand elements of the lambda expression before it
is compiled, by substituting (for all occurrences of the macro function and
its arguments) other expressions tailored to the particular use of the macro
i n t h e lambda expression. We c a l l t h i s macro expansion. For example, i t permits
us t o d e f i n e a " s p e c i a l form" of a n i n d e f i n i t e number of arguments by c o n v e r t i n g
t h a t s p e c i a l form t o a composition of n e s t e d f u n c t i o n s each having two arguments--
t h e n e s t i n g being determined by examination of t h e p a r t i c u l a r u s e of t h e s p e c i a l
form i n t h e g i v e n lambda expression.
Take, f o r example,
(PLUS Xl x* 0 . . xn)
MACRO ( (
(PLUS (LAMBDA (L) (*EXPAND L (QUOTE *PLUS)))) ) )
(PLUS Xl x* x3 x4)
(*EXPAND form f n )
we get
(*PLUS Xl (PLUS x2 x3 x 4 ) )
f n = *PLUS
thereby y i e l d i n g
DEFINE ( (
(*EXPAND (LAMBDA (FORM FN)
(COND ( (NULL (CDDR FORM)) (CADR FORM))
(T (CONS FN
(CONS (CADR FORM)
(CONS(CONS (CAR FORM) (CDDRFORM))NIL) 1))))) 1)
f n = *PLUS
(CDDR f o m ) = NIL
(CADR form) = x4
Thus, t h e form
(PLUS x4)
g e t s r e p l a c e d by j u s t x 4 , y i e l d i n g t h e f i n a l expanded e x p r e s s i o n
3. A macro d e f i n i t i o n of t h e s p e c i a l form.
4. MACRO r e c o g n i t i o n by t h e compiler.
(CSETQ A B)
i s encountered,
(CSET (QUOTE A) B)
w i l l be s u b s t i t u t e d and compiled.
19.9 EXERCISES
For t h e l i s t s
and
3. Define NCONC
6. Define t h e f u n c t i o n
SUITS ( p l a y e r )
7. Define t h e f u n c t i o n
LONGSUIT ( p l a y e r )
8. Define t h e f u n c t i o n
POINTS ( p l a y e r )
that returns as its value the point-count of the given hand. Assume
function SUITS has already sorted the hand; assume the following point
system:
STOPPERS (player)
BALANCED (player)
that is T if there are at least three cards in each suit of the hand,
and NIL otherwise. Assume function SUITS has already sorted the hand.
Use all your functions from problems 5-10 on an unsorted hand to
define the function
OPENBID (player)
Condition -
Bid
12. *MAX and *MIN exist as functional counterparts of MAX and MIN, but
having only two arguments. Define the macros MAXIMUM and MINIMUM.
13. In the last chapter, dealing with functional arguments, we saw that
we must always use the special form FUNCTION, when we wish to quote a
functional expression appearing as an argument of another functional
expression; e.g.,
14. If you define LIST as a macro and it's wrong, you can wreck the system.
Therefore, define LIST1 as a macro that does exactly what LIST does.
(CONS xn NIL)
as its last expansion. In other words, we want
LIST1 (A B C) = (A B C)
and not
Hint :
The treatment for other operators, such as logarithmic and trigonometric opera-
tors would not be significantly more difficult, but would require expanding the
descriptive text without contributing more instructive material to the chapter.
The formal syntax of the algebraic expression is listed below as a series of
syntax equations in Backus Normal Form (BNF). l2 For those not familiar with
this formal language for describing the syntax of formal languages, the English
language interpretation of each equation is given.
I
<primary> ::= <variable> <constant>( (<expression>)
A primary is either a variable, or
a cons-bant, or a parenthesized
expression.
-161-
Syntax Equation English Interpretation
PROGRAM STRATEGY
A+B (PLUS A B)
AX+3 + BX1.2 - 3X (PLUS (TIMES A (EXPT X 3))
(DIFFERENCE (TIMES B (EXPT X 2))
(TIMES 3 X)))
With this knowledge, the strategy is to translate the given eqression into the
desired prefix form, differentiate that form, and translate the resulting form
back to infix notation. Though it is not obvious at this point, the solution
also requires a program to perform algebraic simplification of the symbolic
results of differentiation, and a supervisory program to control program
execution and to perform input-output.
i t would r e t u r n t h e v a l u e
((EXPT A 3 ) + 7)
CSET ( DIGITS
CSET ( ALPHA (A B C .. . Z ) )
The r e a s o n f o r t h e s e b i n d i n g s w i l l become c l e a r e r a f t e r t h e d i s c u s s i o n of t h e
s u p e r v i s o r program DIFF.
[ I N Z P R E (LAWBOA ( E l
(PROG ( X I
(SETQ X (EXPRESSION € 1 )
(CON0 ( ( N U L L X ) ( P R I N T (QUOTE ( POORLY FORMED EXPRESSION) ) 1 )
( T (RETURN X I ) ) ) ) )
( D I G I T (LAMBDA tE)
(PROG ( X I
(SETQ X (ASSOC (CAR E l D I G I T S ) )
(COND ( ( N U L L X ) (RETURN N I L ) )
( T (RETURN (CONS (CADR X ) (CDR € 1 1 ) ) ) ) ) )
( V A R I A B L E (LAMBDA ( E 1
(CON0 ((MEMBER (CAR E ) ALPHA) E)
(T NIL))) 1
(CONSTANT (LAMBDA ( E 1
(PROG ( X Y )
(CON0 ( (NULL (SETQ X ( D I G I T € 1 ) (RETURN N I L ) ) )
A (SETQ Y (CONS (CAR X I Y ) )
(SETQ E (CDR € 1 )
(CON0 I (OR ( N U L L € 1 (NULL (SETP X ( O I G I T E))))
(RETURN (CONS (NUMBER (REVERSE Y) 1 E ) ) 1 )
(GO A ) ) ) )
(NUHBER (LAMBOA ( € 1
(PROG ( X I
(SETQ X 0 )
A (COND ( ( N U L L € 1 (RETURN X I ) 1
(SETQ X (PLUS ( T I M E S X 10) ( C A R € 1 ) )
(SETQ E (CDR € 1 )
(GO A ) ) ) )
(PRIMARY (LAHBDA ( € 1
(PROG ( X I
(COND ( ( S E T 0 X ( V A R I A B L E E l ) (RETURN X ) )
( (SETQ X (CONSTANT E 1 ) (RETURN X ) 1
( ( N O T (EQ (CAR € 1 LPAR) 1 (RETURN N I L ) )
( ( N O T (SETQ X (EXPRESSION LCOR € 1 ) ) ) (RETURN N I L ) )
( ( N U L L (CDR X I ) (RETURN N I L ) )
( ( E Q (CADR X I R P A R ) (RETURN (CONS (CAR X ) (CDDR X ) ) ) )
(T NIL)))))
(SECONDARY (LAMBDA ( E l
(PROG ( X Y )
(COND ( ( N U L L (SETQ X (PRIMARY E ) I 1 (RETURN N I L )
I ( N U L L (COR X ) (RETURN X I )
( ( N O T (EQ (CADR X ) UPARROW) 1 (RkTURN X I )
( ( S E T Q Y (CONSTANT (CDDR X) 1 )
(RETURN (CONS ( L I S T (QUOTE E X P T ) ( C A R X I ( C A R Y ) I (CDH Y ) ) )
( T (RETURN N I L ) ) ) ) ) I
(TERM (LAMBDA ( € 1
(PROG ( X Y 2 )
(SETQ X (SECONDARY E l 1
(CON0 ( ( O R ( N U L L X I (NULL (CDR X ) ) ) (RETURN X I ) )
(SETQ Z (CDDR X ) 1
(SETQ Y (QUOTE QUOTIENT)
(CON0 (EQ (CADR X I SLASH) (GO A ) 1 )
(SETQ Y (QUOTE T I H E S ) )
(COND ( ( E Q (CADR X ) STAR) (GO A ) ) )
(SETQ Z (CDR X I )
A (CON0 ( ( S E T Q Z (TERM 2 ) )
(RETURN (CONS ( L I S T Y (CAR X I (CAR 2 ) ) (CDR Z ) 1 ) 1
(1 (RETURN X ) ) ) ) ) )
( E X P R E S S I O N (LAMBDA ( € 1
(PROG ( E X P X Y OP)
(COND ( ( N U L L € 1 (RETURN N I L ) )
( ( N U L L (SETQ X (TERM E l ) ) (RETURN N I L ) ) )
(SETQ EXP (CAR X I )
E (CON0 ( ( N U L L ( C D R X ) ) (RETURN E X P I )
( ( € 0 (CADR X I PLUSS) ( S E T 0 OP (QUOTE PLUS) 1 )
( ( E Q (CADR X I DASH) ( S E T 0 OP (QUOTE D I F F E R E N C E ) ) )
( 1 (RETURN (CONS EXP (CDR X ) ) ) ) )
(CON0 ( ( N U L L (SETQ Y (TERH (CDDR X I 1 ) 1 (RETURN N I L ) ) 1
( S E T 0 EXP ( L I S T OP EXP (CAR V ) )
(SET0 X Y )
(GO € ) ) I )
73
73
74
74
d du dv
5. -
dx
(uv) = v-+u-
dx dx
76
80
7.
d
- (un) = n u
n-1 & . if n = constant
dx dx '
(OERIV (LAMBDA ( E X I
(COND ( ( A T O H € 1 (CON0 ( ( E Q E X I 1 ) ( T 0 1 ) )
((OR (EQ (CAR € 1 (QUOTE P L U S ) ) ( € 0 ( C A R E) ( Q U O T E D I F F E R E N C E ) 1 )
( L I S T (CAH E l ( O E R I V ( C A D R €1 X ) ( D E R I V ( C A U M I E ) X I ) )
( ( E Q (CAR € 1 (QUOTE T I M E S ) )
( L I S T (CUOTE PLUS)
( L I S T ( C A R El (CADDR E l (UErXIV ( C A D 2 E l X I )
( L I S T ( C A R E l (CAUR € 1 ( U t S I V (CAUDK L ) X I ) ) )
( ( E Q (CAR E l (QUOTE Q U O T I E N T ) )
( L I S T (CAR E )
( L I S T (QUOTE DIFFERENCE)
( L I S T ( Q U O T E T I M E S ) ( C A O D R € 1 ( O E R I V (CAW E l X I )
( L I S T ( Q U U T E T I M E S ) ( C A D S E l ( D E K I V (CADDK E ) X I ) )
( L I S T ( O U O T t T I M E S ) ( C A D D K E l (CADDR E ) ) ) )
( (EO (CAR € 1 ( Q U O T E E X P T ) 1
( L I S T (CUOTt TIMES)
( L I S T (QUOTE T I M E S ) (CAUUK E )
(COND ( ( E Q U A L ( C A D D R E) 2 1 ( C A D K E 1 1
( T ( L I S C (CAR € 1 ( C A W € 1 ( S U t 5 1 (CADDi4 € ) I ) ) ) )
( D E R I V (CADR E l X I ) )
(T NIL))))
The s t r u c t u r e of t h e f u n c t i o n DERIV i s simple. It i s one c o n d i t i o n a l expres-
s i o n w i t h s i x c o n d i t i o n a l c l a u s e s ; each c l a u s e s a t i s f i e s one o r two d i f f e r e n t i a -
tion rules. Since t h e r u l e s a r e determined by t h e a r i t h m e t i c o p e r a t i o n , and a
non-atomic p r e f i x e x p r e s s i o n always h a s t h e form
( o p e r a t o r argument argument )
1 2
t h e p r e d i c a t e s i n each c l a u s e determine i f t h e g i v e n e q r e s s i o n s a t i s f i e s i t s
r u l e by examining t h e e;epressionrs o p e r a t o r ( t h e CAR of t h e e q r e s s i o n . ) (For
atomic e x p r e s s i o n s , r u l e s 1 and 2 a r e d e t e c t e d by t h e p r e d i c a t e ATOM.) If the
p r e d i c a t e i s t r u e , t h e c l a u s e a p p l i e s i t s r u l e by simple e v a l u a t i o n o r by u s i n g
r e c u r s i v e c a l l s upon DERIV.
IN2PR.E would r e t u r n t h e p r e f i x e x p r e s s i o n
f o r DERIV. I f t h i s e x p r e s s i o n i s d i f f e r e n t i a t e d w i t h r e s p e c t t o X, t h e second
c l a u s e ( l i n e 74) would be s a t i s f i e d , and r u l e 3 would be a p p l i e d , y i e l d i n g t h e
expression
T h i s e x p r e s s i o n i s n o t completely e v a l u a t e d . For
and
(PLUS (TIMES X (DERIV argument21 X))
(TIMES 2 (DERIV argumentz2 X)))
Again, f o r
f o r argument 12.
The f i n a l r e c u r s i v e c a l l t o DERIV w i t h
argument = X
121
(PLUS (TIMES 6 X) 2)
or i n i n f i x notation
(DIFFERENCE a b)
i n t o an e x p r e s s i o n of t h e form
(PLUS (MINUS b) a )
( S I M P L I F Y (LAMBCA ( E l
(PROG ( A 8 C 0)
( C O N 0 ( ( A T O M E ) ( R E T U R N €1 1 )
(SETQ A ( S I M P L I F Y (CAPP E) 1 )
( C O N 0 ( ( E Q ( S E T O C ( C A R E l ) (QUOTE M I N U S ) )
(RETURN (SMINUS ( L I S T C A ) ) ) ) )
( S E T O B ( S I M P L I F Y (CADDR € 1 ) )
( C O N 0 ( ( E Q C (QUOTE D1FFEAENCE) 1
( R E T U R N ( S P L U S (LIST (QUOTE PLUS)
( S M I N U S ( L I S T (QUOTE MINUS) 0 ) 1 A ) ) ) 1 )
(SETO O ( L I S T C A 8 ) )
( R E T U R N ( S E L E C T C ( ( Q U O T E P L U S ) (SPLUS 0 ) 1
((QUOTE T I M E S ) I S T I M E S D l )
( (QUOTE QUOTIENT) (SOUOTIENT Q))
((QUOTE E X P I ) (SEXPT D l )
0 1))))
20.5.1 SPLUS
For a n e x p r e s s i o n of t h e form
(PLUS a b)
1. a and b = c o n s t a n t a + b 111
3. b = O a
4. b = constant, a # constant (PLUS b a ) t
5. a = b (TIMES 2 a I t
6. a = (MINUS al)
b = (MINUS bl)
7. a = (MINUS a l ) , b = a l 0
8. a = (MINUS al) ,b # constant (PLUS b a)'
9. b = (MINUS b l ) , a = bl 0
10. b = (MINUS b l ) , a # c o n s t a n t (PLUS a b)'
11. a l l else (PLUS a b ) +
ISPLUS ( L A M B D A ( € 1
( C O N 0 ( (NUHBERP (CADDR € 1 )
(COND ( (NUMBERP (CADR E ) ) ( E V A L E 1 )
( I Z E R O P (CAODR € 1 ) 1CAOR € 1 )
( T ( C O L L E C T ( L I S T ( C A R € 1 (CAODR € 1 (CADR E ) ) ) ) ) )
(TIMES a b)
Value L i n e No.
1. a and b = c o n s t a n t a * b 133
CSTIMES (LAMBDA ( € 1 13 1
(CON0 ( (NUMBERP (CADOH E 1 ) 132
(CON0 ( (NUMBERP (CADR E 1 ) ( € V A L € 1 133
( ( Z E R O P (CADDR € 1 ) 0) 134
( ( O N E P (CADDH E l ) (CAUR € 1 ) 135
( 1 (COLLECT ( L I S T (CAR € 1 (CAODR € 1 (CADR € ) ) ) ) I ) 136
((NUHBERP (CADK E ) 1 137
(COND ( I Z E H O P ( C A D R E l ) 0 1 13 8
( ( O N E P (CADK E l 1 lCADUR € 1 ) 139
( T (COLLECT € 1 ) ) ) 140
( ( E Q U A L (CADR € 1 (CADDR E 1 ) 141
ISEXPT ( L I S T (QUOTE E X P T ) ( C A O K E ) 2 ) ) 1 142
( ( A N D (NOT (ATOM (CADI2 E l ) ) ( € 4 (CAADR E ) (QUOTE M I N U S ) ) ) 143
(CON0 ( ( A N D (NOT (ATOM (CADOR € 1 1 1 144
(EO (CAADUR E ) ( Q U O T E M I N U S ) 1 ) 145
( C O L L E C T ( L 1 S T ( C A R E ) ( C A D A D R E ) (CAUR ( C A D O R E ) ) ) ) ) 146
( ( E Q U A L (CADADR € 1 (CADDH E l ) 147
( L I S T (QUOTE M I N U S ) ( L I S T (QUOTE EXPT) (CADOR € 1 2)1 ) 148
(1 (COLLECT ( L I S T ( C A R E l (CAUDR € 1 (CADR € 1 ) ) ) ) ) 149
t ~ h ee x p r e s s i o n i s f u r t h e r s i m p l i f i e d by t h e f u n c t i o n COLLECT, which i s
described l a t e r .
t t ~ h e e x p r e s s i o n i s f u r t h e r s i m p l i f i e d by t h e f u n c t i o n SEWT, which i s d e s c r i b e d
later.
-173-
( (AND ( N O T ( A T O M (CADDR E 1 ) 1 ( E d (CAADD3 E l ( Q U 3 T E MINUS) 1 ) 1 50
(COND ( ( E Q U A L (CADR (CADDR E l ) (CAUK € 1 1 151
( L I S T ( Q U O T E M I N U S ) ( L I S T ( Q U D T E E K P T ) ( C A D K E l 2))) 152
( T (COLLECT E l ) ) ) 153
( T (COLLECT E ) ) ) ) ) 154
20.5.3 COLLECT
Rule L i n e No.
( C O L L E C T ( LAMBDA ( E 1 155
(COND ( ( A T O M E l E l 156
( ( A T O H (CADOR El) 157
ICOND ( ( A T O M (CAUR E l l € 1 158
( 1 ( C O L L E C T ( L I S T ( C A R € 1 (CADDR € 1 ( C A D R € 1 ) ) ) ) ) 159
( ( A N D ( E Q (CAR € 1 (CAADDR k ) ) (NUMBERP ( C A D R ( C A U D H € 1 11 1 160
(CQNO ( (NUMUERP (CAOR E l J 16 1
( L I S T (CAR E ) 162
( € V A L ( L I S T ( C A R € 1 (CADR € 1 (CADR (CADUR € 1 ) ) ) 163
(CADDR (CAOUR E l ) ) ) 164
( ( A T O M (CADR € 1 ) € 1 165
( ( A N D ( E Q (CAR E ) [CAADR E l ) (NJHBERP (CADADH E l 1 ) 166
( L I S T (CAR € 1 167.
( € V A L ( L I S T ( C A R € 1 (CADADR € 1 ( C A D K (CADDR E l ) ) ) 168
( L I S T ( C A R E ) (CAOOR (CADH E J 1 169
(LAUUK [CAODR E l ) ) 1 ) 170
(T El)) 17 1
(1 E ) ) ) ) 172
he expression i s f u r t h e r s i m p l i f i e d by a r e c u r s i v e c a l l t o COLLECT.
-174-
20.5.4 SQUOTIENT
(QUOTIENT a b)
(TIMES a (QUOTIENT 1 b ) )
and a call to STIMES is made with the new expression. SQUOTIENT does not make
a zero-divide check, i.e., b is assumed # 0.
( S Q U O T I E N T ( L A M B D A (E) 173
(COND ( ( E Q U A L ( C A D R € 1 (CADDR E 1 ) 1 ) 174
( ( A N D (NUWBERP (CADR E l (ZEROP (CADR € 1 1 ) O ) 175
[ ( A N D (NUMBERP (CADR € 1 ) ( O N E P ( C A D R € 1 ) 1 E l 176
( (NUMBEKP (CADDR E 1 ) 17 7
( C O N 0 ( (NUHBERP (CADR E 1 ) ( €VAL E 1 1 178
( ( O N E P (CADDR €11 (CADR E l 1 479
( T (COLLECT ( L I S T (QUUTE T I M E S ) 180
( Q U O T I E N T 1.0 (CADDR E l ) (CADR E l ) ) ) ) ) 181
( ( A N D (NOT ( A T O M (CADDR € ) ) I ( E Q (CAADD3 E ) (QUOTE M I N U S ) 1 ) 182
( S T I M E S ( L I S T (QUOTE T I M E S ) (CADR € 1 183
( L I S T (OUGTE MINUS) 184
( L I S T (QUOTE QUOTIENT) 185
1 ( C A D R (GADDR € 1 ) ) ) 1 ) 1 186
( T ( S T I M E S ( L I S T (QUOTE T I M E S J ( C A D R € 1 187
( L I S T (QUOTE Q U O T I E N T ) 1 (CAODR E 1 ) 1 ) 1 ) l 188
(EXPT a b )
2. b - 1
3. a and b = constant
4. a=atom (EXPT a b) 193
5. a = (EXPT a l bl) (EXPT al b * bl) 194
(EWT a l b)
t 198
6. a = (MINUS a l l , b = even
4-
7. a = (MINUS a l l , b = odd (MINUS (EWT al b ) ' ) 200
8. a l l else (EXPT a b ) 197
(SEXPT (LAMBOA ( € 1
(COND ( (ZEROP (CADDR E ) 1 1
( ( O N E P (CADUR E l ) (CAOR E l )
( (NUHBERP (CADR E 1 1 ( € V A L € 1 )
( ( A T O M (CAOR E l ) € 1
(EQ (CAAOR E) (QUOTE E X P T ) )
( L I S T (QUOTE E X P T ) (CADADH El
( T I M E S (CADOR € 1 (CADOR (CAOK E ) ) ) ) )
( ( N O T ( E Q (CAADK E l ( Q U U l t M I N U S ) ) ) E )
( ( E V E N P (CAUDR € 1 )
(SEXPT ( L I S T (QUOTE E X P T ) (CA0AOR € 1 (CADDR E) 1)
( 1 ( L I S T (QUOTE M I N U S )
(SEXYT ( L I S T (QUOTE E X P T ) (CAOADR € 1 (CADUR € 1 ) ) ) ) ) ) )
20.5.6 SMINUS
(MINUS a )
h he expression i s f u r t h e r s i m p l i f i e d by a r e c u r s i v e c a l l t o SEXPT.
Rule Value L i n e No.
1. a = constant
2. a = (MINUS al) a
1
3. a l l else (MINUS a )
fSMINUS (LAMBDA ( E l
(CON0 ( (NUMBERP (CADH E 1 ) l EVAL E 1 )
( (AND (NOT ( A C O M (CADK El 1 )
( € 0 (CAADR E ) (QUOTE M I N U S ) ) ) (CADAOR E l )
(T €))I)
T r a n s l a t i n g from p r e f i x t o i n f i x n o t a t i o n i s c o n s i d e r a b l y simpler t h a n v i c e
v e r s a , and PRE2IN i s a s i m p l e r f u n c t i o n than IN2PRE. There a r e only two
problems: (1) determining when t o p a r e n t h e s i z e a n expression t o remove
ambiguity, and (2) p r i n t i n g t h e expression i n a " p r e t t y " i n f i x form.
should p r i n t a s
whereas
should p r i n t a s
EXPT
TIMES, QUOTIENT
PLUS, MINUS
-177-
where TIMES and QUOTIENT (and PLUS and MINUS) have e q u a l precedence. The
f u n c t i o n WRAP provides t h e p a r e n t h e s e s when c a l l e d .
b u t t h i s i s n o t done h e r e .
( P R E 2 I N (LAMBDA ( € 1
(PROG ( 1
(CON0 ((NUMBERP € 1 (PHOG2 ( P R I N E ) ( P K I N B L A N K ) ) )
((ATOM € 1 [ P R I N E l )
( T (SELECT (CAK E)
((QUOTE P L U S ) (XPLUS € 1 )
((UUUTE MINUS) (XHINUS E ) )
((QUOTE T I M E S ) ( X T I M E S E l )
( ( Q U O T E O U O T I E N T ) (XQUOTIENT E l
( ( U U u T E E X P T ) (XLXPT E l ) € 1 ) ) 1 ) )
I X P L U S (LAMBDA ( € 1 217
(PROG ( 1 2 18
(CON0 ( (NUMBERP (CADK E 1 1 2119
(RETURN (XPLUS ( L I S T (CAN E l (CADUR E l [CAUK € 1 ) ) ) ) ) 220
( P R E 2 I N (CADR E l 1 221
( P R I N BLANK) 222
(CON0 ( ( A N D (NOT (ATOM (CADDR E l ) ) ( E Q (CAADDR € 1 (QUOTE M I N U S ) ) ) 223
(GO X I ) 224
( ( A N D (NUMBERP (CADDR E l ) ( M I N U S P (CADDR E ) ) ) ( 6 0 X I ) ) 225
( P R I N PLUSS) 226
( P R I N BLANK) 227
X ( P R E Z I N (CADDR € ) ) I ) ) 22 8
( X M I N U S (LAHBDA ( € 1
(PROG ( 1
( P R I N DASH)
( P R I N BLANK)
( P R E 2 I N (CADR E 1 ) 1 ) 1
( X T I H E S (LARBDA ( € 1
(PROG ( X I
(SETO X (QUOTE ( P L U S M I N U S ) 1 )
(CON0 ( ( A T O M (CADR E l ) ( P R I N (CAOH E l ) )
( ( M E M B E R (CAADR E ) X ) (WRAP LCAOR € 1 ) )
( T ( P R E Z I N (CADR E ) ) ) )
(COND ( (ATOH (CADDA E ) LPRIN t CADDR E ) 1 )
((MEMBER (CAADDR € 1 X ) (WRAP (CADOR E l ) )
( T ( P R E 2 I N (CADDR € ) ) I ) ) ) )
(XQUOTIENT (LAMBDA ( E l
(PROG ( X )
( S E T Q X (QUOTE ( P L U S M I N U S ) ) )
(CON0 ( ( A T O M ( C A D R € 1 ) ( P R I N (GADR € 1 ) )
((MEMBER (CAADR E l X I ( W R A P ( C A O R € 1 ) )
( T ( P R E 2 I N (CAOR € 1 ) 1 )
( P R I N SLASH)
(CON0 ( (ATOM (CADOR E ) ) ( P R I N (CAODR € 1 ) 1
( (MEMBER ( CAADDR E 1 X ) ( M ~ ~ A(CADDRP E 1) )
[ T I P R E 2 I N (CADDR E ) ) ) ) ) ) )
(XEXPT (CAHBDA ( E )
(PROG 0
(CON0 ( ( A T O M (CADR E l ) ( P R I N (CADK E l )
( T (WRAP (CADR € ) ) ) I
( P R I N UPARROW)
( P R I N (CADDR € ) ) I ) )
20.7 DIFF
DIFF is the supervisor for the complete program. It controls the evaluation of
the previously discussed functions, and input-output.
whereupon, control is given to the function UADER (line 281) to return a list
of all the non-blank characters of the infix expression to be differentiated.
To satisfy the demands of READER, the infix eqression must be terminated by
a comma (line 286). If the expression ends with a period, READER returns the
value END (line 285) and DIFF exits to EVALQUOTE with the value FINIS (line 272).
If the expression returned by READER can't be translated by INZPRE, INZPRE
prints the message
The message
IS-
( 0 IFF (LAMBDA ( 1
(PROG ( X Y )
A (TERPRI)
(MAPCAR (QUOTE (THE D t R I V A T I V E * $ $ O F - $ 1 1
( F U N C T I O N (LAMBOA ( J ) ( P R O G Z ( P R I N J ) ( P H I N B L A N K ) 1 ) ))
(TERPRI 1
(TEREAD)
(SET0 X (KEADERIJ
(COND ( (EQUAL X (QUOTE END 1 (RETURN (QUOTE F I N I $1 1
( ( N U L L (SETQ X ( I N 2 P R E X I ) ) (GO A ) ) )
B ( P R I N T (QUOTE $ $ $ WITH RESPECT TO-$))
(BEREAD)
(COND ( (NOT (ATOM ( S E T U Y ( C A R ( R € A D E K ) ) 1 ) (GO 8 ) 1 )
( P R I N T (QUOTE $$$IS-$))
( P R E 2 I N (SIMPLIFY (DEHIV X Y ) ) )
(TERPRI
(GO A ) ) ) )
(READER (LAMBDA ( 1
(PROG ( X Y )
A (SETQ X (HEADCH) 1
(COND ( ( E Q X B L A N K ) ( G O A ) 1
((EQ X P E R I O D ) (RETURN ( O U b T E E N D ) ) )
( ( E Q X COMMA) (&ETURN ( R E V E R S E Y ) ) ) )
(SETQ Y (CONS X Y)
(GO A ) ) ) )
With the program now completely described, we can examine a few t y p i c a l examples
of i t s operation.
DIFF ( )
THE DERIVATIVE OF-
CHAPTER 2.
1. Yes
2. No. T h i s i s a n example of two l i t e r a l atoms.
3. Yes
4. Yes
5. No. There a r e no p a r e n t h e s e s i n a n atomic symbol.
6. Yes
7. Yes
8. Yes
9. No. This i s a dotted p a i r .
10. No. F i r s t character not a l e t t e r . (On some systems t h i s may b e a n
a c c e p t a b l e l i t e r a l atom because i t i s obviously n o t a number.)
11. No. P a r e n t h e s e s missing.
12. No. P a r e n t h e s e s missing.
13. No. Too many d o t s w i t h o u t p r o p e r p a r e n t h e s e s .
14. Yes
15. Yes
rfiTWO THREE
Eel
THREE NIL
19. (A. (B . ((C . NIL) . (D . N I L ) ) ) )
20. (((A. B) . ( C . D)) . ( E . ( ( F . G) . H ) ) )
CHAPTER 3 .
1. (ATOM . NIL)
2. ( ( L I S P . NIL) . NIL)
3. (((MORE . (YET . NIL)) . NIL) . NIL)
4. (HOW . (ABOUT . (THIS . N I L ) ) )
5. (DONT . ((GET . ((FOOLED . NIL) . NIL)) . NIL))
6. (XI)
7. (NIL X1)
8. (KNOW THY SELF)
9. ( (BEFORE AND AFTER))
10. (A ((B C ) ) )
11. ((W)) ((W . NIL) . NIL)
12. (NIL NIL NIL) = . (NIL . (NIL . N I L ) ) )
(NIL
(W (B) B) = (W . ( ( B . NIL) . (B . NIL)))
-
13.
14. ((((NEST)))) ((((NEST . NIL) . NIL) . NIL) . NIL)
15. ( ((A) B) (C) D) ( ( ( A . NIL) . (B . NIL)) . ((C . NIL) . (D . NIL)))
CHAPTER 4 .
1. Y e s
2. Y e s (5 E)
3. Y e s (E5 . 5)
4. Yes ( 1 . 0 . 1Q)
3
5. Yes 43 is a literal atom and not 0 X 8
6. Yes 4.4
7. No
8. Yes (B . 9.9)
9. No
CHAPTER 5.
LEFT
RIGHT
(LEFT . RIGHT)
A
(A)
A
(A B)
(SENTENCE IS A LIST)
((ABOUT THIS))
((DOT . PAIR2))
(CAR . CDR)
NIL E ( )
(CDR)
(CAR)
(A)
.
-
(754 100)
1
(2.0 3.0 774) . (2.0 . (3.0 . 774))
((A B))
((((A;LPHA))))
T h e r e l a t i o n s h i p among CONS, CAR, a n d CDR i s t h a t CONS p u t s t o g e t h e r t h a t
w h i c h CAR and CDR tear a p a r t . M o r e exactly, if t h e a r g u m e n t t o CAR a n d t o
CDR i s t h e s a m e S - e x p r e s s i o n , s , a n d t h e t w o a r g u m e n t s t o CONS are t h . e values
of t h e CAR a n d CDR of t h i s S - e x p r e s s i o n , then t h e value o f CONS i s t h e
o r i g i n a l S-expression, i.e., (CONS (CAR s) (CDR s ) ) = s.
CAR CDR CAR = CADAR
CAR CAR = CAAR
-
CAR CDR = CADR
CDR CDR
CAR CDR CDR = CADDR
CAR CDR CDR CDR = CADDDR
CAR CAR = CAAR
CDR CAR = CDAR
CAR CAR CAR CDR = CAAADR
CAR CAR CDR = CAADR
CAR CDR CAR CDR = CADADR
-
V a r i-
able Binding
X ATOM
Y (LIST)
J (THREE ELEMENT L I S T )
K (THREE ELEMENT L I S T )
U VERY
v GOOD
Y ONE
X (THEN . ANOTHER)
A (A (B 7742))
VARIABLE ((A B))
J NIL
empty empty
U ALPHA
V BETA
Variable B i n d inq
BETA
ALPHA
ALPHA
BETA
ALPHA
u BETA
15. FIRST (FIRST)
SECOND SECOND
CHAPTER 7 .
1. ATOM
2. (LIST)/
3. THREE
4. (ELEMENT L I S T )
5. (VERY . GOOD)
6. (ONE THEN . ANOTHER) (ONE . (THEN . ANOTHER))
7. B,
8. (B) -
9. 3.14159
10. 3.14159
11. ALPHA.
12. BETA
13. BETA
14. ALPHA
15. FIRST
CHAPTER 8.
2. LIST-]
3. NIL
4. 43
5. NUMBER
6 Y
7. (((LIST)))
(A B)
(LAMBDA (J) (CAR (CDR (CDR J ) ) ) ) ( (1 2 3 4) ) = 3
(LAMBDA (X) (CAR (CAR X ) ) ) ( ( (A B C) D) ) = A
(LAMBDA (Y) (CAR (CDR Y ) ) ) ( ( ( A B C) D) ) = D
(LAMBDA (2) (CDR (CAR Z) ) ) ( ((A B C ) D) ) = (B C)
(LAMBDA (VARIABLE) (CAR (CDR (CAR VARIABLE) ) ) ) ( ((A B C) D) ) := B
(A C)
(A C)
(A)
(C)
(0 A) (D C ) )
C W T E R 9.
X
J
(AN S EXPRESSION)
A
(J)
(QUOTE . EXPR)
CAR ( ( A . BETA)) = A
(NOW I S THE TIME FOR ALL GOOD MEN TO COME TO THE AID OF THE PAJXTY)
(A B)
(LAMBDA (X) X)
(ONE TWO THREE)
(ONE TWO THREE)
(NIL F NIL F NIL F )
( F F F F F F )
( ( N I L F F ) (T T T ) (NIL N I L N I L ) (123 1 2 3 123))
X
J
(AN S EXPRESSION)
A
(J)
21. ABLE
22. (ABLE QUOTE ABLE)
23. EVAL ((CAR (QUOTE (ABLE))) ) = ABLE
24. (CONS A B)
25. EVAL ((CDR (QUOTE (A B ) ) ) ) = (B)
CHAPTER 10.
2-4. DEFINE ( (
(SECOND (LAMBDA (Y) (CADR Y) ) )
(THIRD (LAMBDA (Z) (CAR (CDDR Z ) ) ) )
(CADDDDR (LAMBDA (J) (CAR (CDDDDR J ) ) ) )
>)
SECOND ( (A B C D E) ) = B
THIRD ( (A B C D E) ) = C
CADDDDR ( (A B C D E) ) = E
C W T E R 11.
1. TRUE
2. 1
3. U n d e f i n e d , as there i s n o non-NIL c o n d i t i o n a l clause.
4. (TI
5. NOP
6. DEFINE ( ( (OR2 (LAMBDA (X Y) (COND (X T) (Y T I (T N I L ) ) ) ) ))
7. DEFINE ( ( (XOR2 (LAMBDA (X Y)
(COND (X (COND (Y NIL) (T T ) ) ) (Y T) (T N I L ) ) ) ) ))
8. DEFINE ( ( (AND2 (LAMBDA (X Y)
(COND (X (COND (Y T ) (T N I L ) ) ) (T NIL) ) ) ) ) )
9. (SELECT T (pl el) ( p 2 e2) ... (pn en) (error))
lo. (COND ((EQUAL p pl) el) ((EQUAL p p 2 ) e2) . ..
((EQUAL p pn) en) (T e ) )
CHAPTER 1 2 .
1. ( T F T F )
4. NIL
6. NIL
8. NIL
10. NIL
11. NIL
14. T
15. N I L , since HEAR i s n o t a t o p - l e v e l m e m b e r of l i s t (NOW (HEAR T H I S ) ) .
R a t h e r , HEAR i s a member of t h e s u b l i s t (HEAR T H I S ) , and MEMBER
tests o n l y f o r e l e m e n t s a t t h e t o p level of a l i s t .
16. T
17. DEFINE ( ( (EQUIV (LAMBDA (X Y) (EQ X Y ) ) ) ) )
18. DEFINE ( ( (IMPLIES (LAMBDA (X Y) (OR (EQ X Y) Y) ) ) ) )
19. T h i s p r o g r a m can be e a s i l y w r i t t e n w i t h c o n d i t i o n a l s and recursion.
H o w e v e r , s i n c e t h e s t u d e n t has n o t learned these techniques, t h e f o l l o w i n g
e x p r e s s i o n i s r e q u i r e d (see exercise 1 9 of C h a p t e r 1 4 f o r recursive s o l u t i o n ) :
DEFINE ((
(IMSEQ (LAMBDA (J)
( (LAMBDA (V W X Y Z ) (AND
(AND (NUMBERP V) (NUMBERP W) (NUMBERP X) (NUMBER2 Y) (NUMBERP Z ) )
(OR (AND (LESSP V W) (LESSP W X) (LESSP X Y) (LESSP Y Z ) )
(AND (GREATERP V W) (GREATERP W X) (GREATER2 X Y) (GREATEFU? Y Z ) ) ) ) )
(CAR J ) (CADR J ) (CADDR J ) (CADDDR J ) (CAR (CDDDDR J ) ) ) ) )
Note t h a t t h e u s e of n e s t e d lambda e x p r e s s i o n s p e r m i t s u s t o bind V t o
t h e f i r s t l i s t element, W t o t h e second, X t o t h e t h i r d , e t c . This
p r a c t i c e c r e a t e s temporary s t o r a g e f o r t h e s e p a r t i a l r e s u l t s and s i m p l i f i e s
t h e t o t a l e x p r e s s i o n a s w e l l a s reduces t h e t o t a l computation, s i n c e we
need compute t h e s e r e p e a t e d l y used arguments o n l y once.
CHAPTER 13.
NIL
2. X
E
NO
L
3. DEFINE ( ( (TWIST (LAMBDA ( S ) (COND ((ATOM S ) S)
(T (CONS (TWIST (CDR S ) )
(TWIST ( C U S ) ) ) ) ) ) ) 1)
A
(B A)
(C . ( B . A ) ) = (C B . A)
(((NIL . C) . B) . A)
(NIL . (B . A)) = (NIL B . A)
4. DEFINE ( ( (SUM (LAMBDA (X Y) (COND ((ZEROP Y) X) (T (SUM (ADD1 X) (SUB1 Y ) ) ) ) ) ) ))
ARGS OF SUM
1
2
ARGS OF SUM
2
1
ARGS OF SUM
3
0
VALUE OF SUM
3
VALUE OF SUM
3
VALUE OF SUM
3
D E F I N E ( ( (PROD (LAMBDA (X Y) (COND ((ZEROP Y) 0)
(T (SUM X (PROD X (SUB1 Y ) ) ) ) 1)) ))
D E F I N E ( ( (REMXY (LAMBDA (X Y) (COND ((LESSP X Y) X)
((EQUAL X Y) 0)
(T (REMXY (DIFFERENCE X Y) Y ) ) ) ) ) ))
D E F I N E ( ( (COUNT (LAMBDA (E)
(COND ((NULL E ) 0) ((ATOM E ) 1)
( T (PLUS (COUNT (CAR E ) ) (COUNT (CDR E) ) ) I ) 1) ) )
D E F I N E ( ( ( F I B B (LAMBDA (N)
(COND ( (ONEP N) 1) ((EQUAL 2 N) 1)
( T (PLUS ( F I B B ( S U B 1 N ) ) (FIBB (DIFFERENCE N 2) ) ) ) ) ) ) ) )
D E F I N E ( ( (GCD (LAMBDA (X Y) (COND ((GREATERP X Y) (GCD Y X ) )
((ZEROP (REMAINDER Y X) ) X)
( T (GCD X (REMAINDER Y X) ) ) ) ) ) ) )
D E F I N E ( ( (AMONG (LAMBDA (A L ) (COND ((NULL L ) N I L )
( ( E Q A (CAR L ) ) T )
(T (AMONG A (CDR L ) ) ) ) ) ) 1)
D E F I N E ( ( ( I N S I D E (LAMBDA ( A E ) (COND ((ATOM E ) (EQ A E ) )
( ( I N S I D E A (CAR E ) ) T )
( T ( I N S I D E A (CDR E ) ) ) I ) ) 1)
D E F I N E ( ( (COPYN (LAMBDA (X N) (COND ( (ZEROP N) N I L )
(T (CONS X (COPYN X (SUB1 N ) ) ) ) ) ) ) ))
D E F I N E ( ( (LENGTHS (LAMBDA ( L ) (COND ((NULL L ) 0)
( T (ADD1 (LENGTHS (CDR L ) ) ) ) ) ) ) ))
D E F I N E ( ( (UNIONS (LAMBDA (X Y) (COND ((NULL X) Y)
((MEMBER (CAR X) Y) (UNIONS (CDR X) Y ) )
(T (CONS (CAR X) (UNIONS (CDR X) Y) ) ) ) ) ) ) )
DEFINE ( ( (INTERSECT (LAMBDA (X Y) (COND ((NULL X) NIL)
( (MEMBER (CAR X) Y) (CONS (CAR X)
(INTERSECT (CDR X) Y ) ) )
( T (INTERSECT (CDR X) Y ) ) ) ) ) ) )
D E F I N E ( ( (REVERSAL (LAMBDA (L) (COND ((NULL L ) N I L )
(T ( M P E N D (REVERSAL CCDR L ) )
( L I S T (CAR L ) ) ) ) ) ) ) 1)
17. DEFINE ( ( (PAIRS (LAMBDA ( L 1 L 2 ) (COND ((NULL L 1 ) NIL)
(T (CONS (CONS (CAR L 1 ) (CAR L 2 ) )
(PAIRS (CDR L 1 ) (CAR L 2 ) ) ) ) ) ) ) 1)
18. DEFINE ( ( (DELETE (LAMBDA (A L ) (COND ((NULL L ) NIL)
((EQ A (CAR L ) ) (DELETE A (CDR L ) ) )
(T (CONS (CAR L) (DELETE A (CDR L) ) ) ) ) ) ) ) )
19. DEFINE ( (
(INSEQ (LAMBDA (L) (OR (INSEQA L ) (INSEQA (REVERSE L ) ) ) ) )
(INSEQA (LAMBDA (L) (COND ((NULL L ) T)
((NULL (CDR L ) ) T)
((NOT (NUMBERP (CAR L ) ) ) N I L )
((NOT (NUMBERP (CADR L ) ) ) N I L )
((LESSP (CAR L ) (CADR L ) ) (INSEQA (CDR L) ) )
(T N I L ) ) ) )
1)
20. DEFINE ( ( (REPLACE (LAMBDA (A B X) (COND ((ATOM X) (COND ((EQUAL B X) A) ( T X ) ) )
(T (CONS (REPLACE A B (CAR X))
(REPLACE A B (CDR X)) ) ) ) ) ) ) )
CHAPTER 15.
PASCAL (15)
(1)
(1 1 )
(1 2 1)
(1 3 3 1)
(1 4 6 4 1)
(1 5 1 0 1 0 5 1)
(1 6 15 20 1 5 6 1)
(1 7 2 1 3 5 35 2 1 7 1)
(1 8 2 8 5 6 7 0 5 6 2 8 8 1)
(1 9 3 6 8 4 1 2 6 1 2 6 8 4 3 6 9 1 )
(1 1 0 4 5 1 2 0 2 1 0 252 2 1 0 1 2 0 4 5 1 0 1 )
(1 11 5 5 1 6 5 3 3 0 4 6 2 4 6 2 3 3 0 1 6 5 5 5 11 1)
( 1 1 2 6 6 220 4 9 5 7 9 2 9 2 4 7 9 2 4 9 5 220 6 6 1 2 1.)
(1 13 7 8 2 8 6 7 1 5 1 2 8 7 1 7 1 6 1 7 1 6 1 2 8 7 7 1 5 286 78 1 3 1)
( 1 1 4 9 1 3 6 4 1 0 0 1 2002 3 0 0 3 3 4 3 2 3 0 0 3 2 0 0 2 1.001 3 6 4 9 1 1 4 1)
(1 15 1 0 5 4 5 5 1 3 6 5 3 0 0 3 5 0 0 5 6 4 3 5 6 4 3 5 5 0 0 5 3 0 0 3 1 3 6 5 4 5 5 1 0 5 15 1)
NIL
PASCAL (16) i s t h e l a r g e s t t r i a n g l e p o s s i b l e w i t h t h i s d e f i n i t i o n s i n c e
16! i s maximum f i x e d - p o i n t a c c u r a c y of a 48-bit machine.
CHAPTER 16.
There a r e no e x e r c i s e s f o r t h i s c h a p t e r .
CHAPTER 1 7 .
1. (LIST)
(LIST)
2. blank l i n e
NIL
blank l i n e
NIL
3. ATOM1 ATOM2
NIL
4. (NOW HEAR THIS)
5. ( (INPUT) ANYTHING)
6. For R=5 , 31.4159
For R=50 , 314.159
For R=10 , 62.8318
For END , END
7. (( ) ./ = $ * NOW HEAR THIS -533.17)
8. (B C)
9. 1. % T h i s e x p r e s s i o n b i n d s t h e l i t e r a l atom $$*%* t o t h e name PERCENT.
The $ $ - a r t i f a c t i s t h e o n l y way t o e n t e r i l l e g a l r e a d c h a r a c t e r s .
2. %
3. PERCENT
10. A
11. 1. A
2. (B C)
3. ( A . B)
4. 3.14159
5. 3.14159
12. 1. (A)
2. ( A . B)
3. 3.14159
4. (3.14159)
5. X SQUARE
0 0
1 1
2 4
3 9
4 16
5 25
6 36
7 49
8 64
9 81
END
13. DEFINE ( (
(SUP4 (LAMBDA ( ) (PROG (S1 S2 ARGS)
A (TEREAD) (SETQ ARGS NIL)
(SETQ S2 (READ))
(SETQ S 1 (READ))
B (COND ( (NULL S2) (GO C) ) )
(SETQ ARGS (CONS (LIST (QUOTE QUOTE) (CAR S2)) ARGS))
(SETQ s 2 (CDR ~ 2 ) )
(GO B)
C (PRINT (EVAL (CONS S 1 (REVERSE ARGS))) )
(GO A) ) ) )
11
1. A
2. (B C)
3. NIL
4. 10
5. 3.14159
6. 3.14159
14. DEFINE ( (
(SUP5 (LAMBDA ( ) (PROG (X Y Z)
A (TEREAD) (SETQ Z NIL)
(SETQ X (READ))
(SETQ Y (READ))
(PRIN X) (PRIN Y) (TERPRI)
(COND ( (EQ (QUOTE NO) (READ)) (GO A) ) )
(PRIN X) (PRIN Y) (PRIN BLANK) ( P R I N ~ EQSIGN) (PRIN BLANK)
B (COND ((NULL Y) (GO C ) ) )
(SETQ Z (CONS ( L I S T (QUOTE QUOTE) (CAR Y ) ) Z))
(SETQ Y (CDR Y) )
(GO B)
C (YRIN (EVBL (CONS X (REVERSE Z ) ) ) )
(TERPRI)
(GO A ) ) ) ) 1)
15. DEFINE ( ( ( P I (LAMBDA (X) (PROG ( H I )
(PRINT (QUOTE (ENTER MAX X) ) )
(SETQ H I (READ))
(SETQ X (TIMES X 1 . 0 ) )
(PRINT (QUOTE $$$
XSQUARE SQRTX RECIPX FACTORI.ALX
( L I S T 2 xl x 2 x3 N I L )
and w i t h r e p e a t e d a p p l i c a t i o n t o
r a t h e r than
which i s t h e l i s t we d e s i r e .
A m o r e p r a c t i c a l s o l u t i o n i s t o r e d e f i n e *EXPAND as say *EXPANDS.
DEFINE ( (
(*EXPANDS (LAMBDA (FORM FN)
(COND ((NULL (CDDR FORM))
(CONS F N (CONS (CADR FORM) (QUOTE (NIL) ) ) ) )
( T (CONS F N
(CONS (CADR FORM)
(CONS (CONS (CAR FORM) (CDDR FORM)) N I L ) ) ) ) ) ) ) ))
T h e n define L I S T 1 as
MACRO ( (
( L I S T 1 (LAMBDA (J) (*EXPANDS J (QUOTE C O N S ) ) ) ) ))
I n t h i s approach t h e f o r m
becomes
(CONS xl ( L I S T 1 x2 x3))
and w i t h repeated a p p l i c a t i o n
15. DEFINE ((
( P R I N T Q 1 (LAMBDA (J) (PROG ( )
T 1 (COND ((NULL J) (RETURN ( T E R P R I ) ) ) )
( P R I N (CAR J ) ) ( P R I N BLANK)
(SETQ J (CDR J ) )
(GO T 1 ) ) ) ) 1)
MACRO ( (
(PRINTQ (LAMBDA (J) (LIST (QUOTE PRINTQl)
(LIST (QUOTE QUOTE)
(CDR J))))) 1)
The form
a-list
A synonym f o r a s s o c i a t i o n l i s t .
association list
A l i s t of d o t t e d p a i r s used by i n t e r p r e t i v e LISP systems t o p a i r bound
v a r i a b l e s with t h e i r values. It i s of t h e form
-
atom
A synonym f o r atomic symbol.
atomic symbol
The elementary form of a n S-expression. There a r e l i t e r a l atoms and
numeric atoms. A l i t e r a l atom c o n s i s t s of a s t r i n g of c a p i t a l l e t t e r s
and decimal d i g i t s of i n d e f i n i t e l e n g t h t h a t b e g i n s w i t h a l e t t e r ; e.g.,
A, BOY22, 2122. Numeric atoms a r e r e a l , i n t e g e r , o r o c t a l numbers d i s -
t i n g u i s h e d by t h e i r syntax. ( c . f . Chapter 4)
binding
The a s s o c i a t i o n of a v a r i a b l e w i t h a v a l u e w i t h i n some e x p r e s s i o n c o n t e x t .
There may b e m u l t i p l e b i n d i n g s f o r a v a r i a b l e during i t s l i f e t i m e a s i t i s
used i n m u l t i p l e c o n t e x t s ; however, t h e r e i s o n l y one binding c u r r e n t a t
a time. Lambda and program e x p r e s s i o n s a r e t h e p r i n c i p a l ways t o c r e a t e
bindings. (See z e r o - l e v e l b i n d i n g s )
bound v a r i a b l e s
A v a r i a b l e named i n t h e l i s t of v a r i a b l e s f o l l o w i n g LAMBDA o r PROG i n
lambda o r program e x p r e s s i o n s i s bound w i t h i n t h e scope of t h a t e x p r e s s i o n .
During e v a l u a t i o n of t h e s e e x p r e s s i o n s , t h e v a l u e of t h e v a r i a b l e i s t h e
v a l u e of t h e corresponding argument i n t h e f u n c t i o n c a l l . For example,
f o r (LAMBDA ( J K) body) ( 1 2 ) , J h a s v a l u e 1 and K h a s v a l u e 2 a t any of
t h e i r o c c u r r e n c e s i n t h e body.
character object
A l i t e r a l atom, t h e v a l u e of which p r i n t s a s a s p e c i a l c h a r a c t e r . For
example,
common v a r i a b l e
V a r i a b l e s used f o r communication between compiled and i n t e r p r e t e d e!xpressions
f o r LISP systems having both a compiler and a n i n t e r p r e t e r .
composed form
The c o n c a t e n a t i o n of forms such t h a t t h e v a l u e of one form i s used a s t h e
argument f o r a n o t h e r form. This i s w r i t t e n i n a n e s t e d f o r m a t , e . g . ,
conditional expression
An e x p r e s s i o n c o n t a i n i n g a l i s t of c l a u s e s . The v a l u e of t h e c o n d i t i o n a l
e x p r e s s i o n i s t h e v a l u e of t h e form corresponding t o t h e f i r s t ( l e f t m o s t )
p r e d i c a t e e x p r e s s i o n t h a t e v a l u a t e s t o non-NIL. E v a l u a t i o n proceeds l e f t
t o r i g h t only a s f a r a s t h e f i r s t non-NIL e x p r e s s i o n . No form i s e v a l u a t e d
i f i t s p r e d i c a t e e x p r e s s i o n i s NIL.
constant
A v a r i a b l e , t h e v a l u e of which never changes d u r i n g computation, o r a
quoted expression. The f o l l o w i n g a r e examples of c o n s t a n t s :
(QUOTE (A B C))
3.14159
T
context
The b i n d i n g s f o r v a r i a b l e s d u r i n g a p a r t i c u l a r computation. For r e c u r s i v e
e v a l u a t i o n of a f u n c t i o n o r a n e x p r e s s i o n , t h e c o n t e x t a t any time i s t h e
c u r r e n t s t a t e of i t s v a r i a b l e s . V a r i a b l e s used f r e e i n a n e x p r e s s i o n a r e
s a i d t o be o u t s i d e t h e scope of t h a t e x p r e s s i o n a s t h e e x p r e s s i o n does n o t
\
c o n t r o l t h e b i n d i n g s of t h e f r e e v a r i a b l e s .
dot notation
The fundamental n o t a t i o n of LISP f o r r e p r e s e n t i n g non-atomic S-expressions.
Dot n o t a t i o n c o n t a i n s l e f t p a r e n t h e s e s , r i g h t p a r e n t h e s e s , atoms, and d o t s .
A non-atomic S-expression i s always a d o t t e d p a i r of S-expressions of t h e
form
CONS (s s ) =
1 2 (sl s2)
dummy v a r i a b l e
I f t h e s y s t e m a t i c s u b s t i t u t i o n of a l i t e r a l atom f o r one used a s a v a r i a b l e
i n a n e x p r e s s i o n does n o t change t h e meaning ( i . e . , t h e v a l u e r e t u r n e d ) of
t h e e x p r e s s i o n , t h e v a r i a b l e i s a dummy v a r i a b l e . A l l lambda and program
v a r i a b l e s a r e dummy v a r i a b l e s .
element
The t o p - l e v e l c o n s t i t u e n t s of a l i s t . These c o n s t i t u e n t s may be atomic o r
non-atomic. I f they a r e l i s t s , t h e y may themselves have elements. Thus,
( 1 has no elements
(A) has one element
(A (B)) has two elements, one of which is a list of
one element.
empty list-
A list having no elements. This list is also equivalent to the literal
atom, NIL.
expression_
A synonym for S-expression in most contexts in this text. In some
instances it may refer to an arithmetic expression.
form
An S-expression that may be a simple constant, a variable, a simple form,
a composed form, or a special form. It may be evaluated when some corres-
pondence has been set up between the variables contained in the S-expression
and a set of arguments. The correspondence is not part of the form.
(See function.)
free variable
A varisble that is used, but not bound within the scope of an express.ion.
A free variable can only be determined free by considering the context in
which it appears. In the expression
function
An expression containing a form and a correspondence between the variables
in the form and the arguments of the function. A lambda expression is a
function, sometimes called a functional expression.
correspondence
functional expression
See function.
function composition
See composed forms.
global bindings
See zero-level bindings.
label notation
A scheme for temporarily naming a lambda expression, so that the expression
may call itself recursively. Recursive functions call themselves by their
names. Lambda expressions are functions without names. Thus, label
notation gives a temporary name to a lambda expression. The notation has
the form
labels
See statement labels.
lambda conversion
The process of evaluating lambda expressions. All arguments are paired
with variables in the list of variables foll.owing the LAMBDA. Then the
form inside the lambda expression is evaluated using those values of the
variables.
lambda expression
See lambda notation.
lambda notation
The notation first used by Church for converting forms into functions. In
LISP, lambda notation is used for lambda expressions such that
list
A shorthand notation for an S-expression of the form
list structure
A list of lists.
literal at=
See atomic symbol.
macro expansion
A coniputational process that transforms one form into some other forrr~.
The transformation rule is embedded in the definition of a LISP function.
This function is invoked by the system (usually at compile-time) and given
as its argument the form containing the name of the function. The value
of the function is the new form which replaces the old form in whatever
context the old form appeared. Generally, the transformation involves
expanding the old form into a composed form of primitive function calls;
however, any arbitrary computation is possible. Macros are used to define
special forms in compiler-based LISP systems.
object list
A s p e c i a l system s t r u c t u r e t h a t c o n t a i n s a l l t h e l i t e r a l atoms r e a d by
t h e system. I n most systems, t h e o b j e c t l i s t i s c a l l e d t h e OBLIST and i s
manufactured by d i s t r i b u t i n g t h e l i t e r a l atoms i n t o a s e r i e s of s u b l i s t s ,
c a l l e d b u c k e t s , by a computation (hashing) upon t h e i r H o l l e r i t h p r i n t
names. It p e r m i t s f a s t atom r e c o g n i t i o n d u r i n g r e a d i n g .
ordinary variable
A synonym f o r bound v a r i a b l e .
parameters
An elementary atomic form t h a t i s e i t h e r a c o n s t a n t o r a v a r i a b l e .
p-list
A synonym f o r p r o p e r t y l i s t .
pointer
An i n t e r n a l machine a d d r e s s . It d e s i g n a t e s o r p o i n t s t o a l o c a t i o n of
interest.
predicate
I n mathematics, a f u n c t i o n , t h e v a l u e of which i s t r u e o r f a l s e . I n LISP,
a f u n c t i o n , t h e v a l u e of which i s T ( t r u e ) o r NIL ( f a l s e ) . (See a l s o
semi-predicate.)
p r i n t name
The o r i g i n a l s t r i n g of c h a r a c t e r s r e a d by t h e system, r e p r e s e n t i n g t h e
i n t e r n a l name f o r a l i t e r a l atom. T h i s s t r i n g of c h a r a c t e r s i s p r i n t e d
a s t h e name of t h e l i t e r a l atom by PRINT and o t h e r p r i n t f u n c t i o n s .
prog e x p r e s s i o n
A synonym f o r program e x p r e s s i o n .
prog v a r i a b l e
A synonym f o r program v a r i a b l e .
program e x p r e s s i o n
An e x p r e s s i o n of t h e form
(PROG ( v a r i a b l e s ) s t a t e m e n t s )
t h a t a l l o w s e v a l u a t i o n of s t a t e m e n t s i n s e r i a l f a s h i o n . (See program
feature. )
program f e a t u r e
A f e a t u r e i n LISP t h a t a l l o w s programs, c o n t a i n i n g s t a t e m e n t s , t o b e
executed i n s e r i a l f a s h i o n . It a l s o p e r m i t s i t e r a t i o n and t h e u s e of
temporary v a r i a b l e s .
program v a r i a b l e
A temporary v a r i a b l e t h a t i s d e c l a r e d i n t h e l i s t of v a r i a b l e s f o l l o w i n g
t h e PROG i n a program e x p r e s s i o n . Program v a r i a b l e s a r e i n i t i a l l y a s s i g n e d
t h e , v a l u e NIL; however, t h e y may b e a s s i g n e d a r b i t r a r y v a l u e s by t h e pseudo-
f u n c t i o n s SET and SETQ. They a r e a l s o bound and dummy v a r i a b l e s .
property list
The l i s t s t r u c t u r e a s s o c i a t e d w i t h a l i t e r a l atom t h a t may b e used f o r
s t o r i n g i n f o r m a t i o n t o b e a s s o c i a t e d w i t h t h e l i t e r a l atom. The p r o p e r t y
l i s t is a convenient information r e p o s i t o r y t h a t permits r a p i d , dictionary-
like retrieval.
pseudo-function
An e x p r e s s i o n t h a t i s c a l l e d a s i f i t were a f u n c t i o n , b u t f o r i t s e f f e c t
rather than f o r its value, e.g., READ, PRINT, DEFINE.
push-down l i s t
The l a s t - i n - f i r s t - o u t (LIFO) memory a r e a used by t h e system f o r s a v i n g
p a r t i a l r e s u l t s of r e c u r s i v e f u n c t i o n s . G e n e r a l i z e d LIFO s t o r a g e f o r u s e r s
i s p o s s i b l e by u s i n g CONS (push) o r CDR (pop) on any l i s t .
quo t i n &
The t e c h n i q u e used by LISP t o s u p p r e s s e x p r e s s i o n e v a l u a t i o n . Quoting
creates constant data within functions. The s p e c i a l form QUOTE i s used
f o r quoting.
recursion
R e c u r s i o n i s a t e c h n i q u e f o r d e f i n i n g a computation on a g i v e n datum, The
p r o c e s s u s u a l l y produces a p a r t i a l s o l u t i o n and r e d u c e s t h e datum t o a
s i m p l e r form. The same p r o c e s s i s t h e n r e a p p l i e d t o t h i s s i m p l e r form
of t h e datum. Again a p a r t i a l s o l u t i o n and a s i m p l e r form a r e o b t a i n e d .
The p r o c e s s c o n t i n u e s u n t i l some t e r m i n a l datum o b t a i n s , whereupon a l l
p a r t i a l s o l u t i o n s a r e combined i n some f a s h i o n t o produce t h e f i n a l
solution. To compute r e c u r s i v e l y t h e f a c t o r i a l of N , f o r example, w e have
where N i s t h e p a r t i a l s o l u t i o n and (N-1) i s t h e s i m p l e r form upon which
we r e p e a t t h e f a c t o r i a l computation. This process recurs u n t i l t h e
t e r m i n a l c o n d i t i o n N = 0 i s reached, whereupon t h e p a r t i a l r e s u l t s a r e
combined t o form t h e f i n a l answer; e . g . ,
scope
The domain i n which a v a r i a b l e i s d e f i n e d , i . e . , i t s binding can be
retrieved. The domain i s expressed a s t h e l i m i t s of a g i v e n expression.
semi-predicate
A f u n c t i o n , t h e v a l u e of which i s e i t h e r NIL ( f a l s e ) o r non-NIL ( t r u e ) .
The implementation of COND i n most LISP systems t e s t s only f o r NIL. There-
f o r e , any f u n c t i o n t h a t r e t u r n s a v a l u e of NIL o r non-NIL may b e used i n
t h e p r e d i c a t e p o s i t i o n of a c l a u s e of a c o n d i t i o n a l e x p r e s s i o n . CDR and
SETQ a r e two examples of semi-predicates. (See a l s o p r e d i c a t e . )
S-expression
A symbolic e x p r e s s i o n of a r b i t r a r y l e n g t h t h a t i s e i t h e r atomic o r repre-
s e n t s a s t r u c t u r e having two branches a t each node. The s i m p l e s t form of
a n S-expression i s a n atomic symbol. A non-atomic S-expression i s e i t h e r :
1. A d o t t e d p a i r of atoms, e.g.,
2. A d o t t e d p a i r of S-expressions, e.g.,
special c e l l
See v a l u e c e l l .
s p e c i a l form
A form given s p e c i a l treatment by LISP. It i s a form having a n
' i n d e f i n i t e number of arguments and/or arguments t h a t a r e unevaluated and
given t o t h e s p e c i a l form t o c o n t r o l e v a l u a t i o n .
special variable
V a r i a b l e s t h a t have bindings i n t h e v a l u e c e l l . They a r e used f o r
c o n s t a n t s and/or f r e e v a r i a b l e s . Such v a r i a b l e s have t o be d e c l a r e d
( i n some systems) b e f o r e they a r e used w i t h t h e pseudo-function SPECIAL.
UNSPECIAL removes such v a r i a b l e s from s p e c i a l s t a t u s .
statement l a b e l s
A l i t e r a l atom appearing a t t h e top l e v e l (statement l e v e l ) of a pr~ogram
e x p r e s s i o n i s used a s t h e name f o r t h e form following t h e l a b e l . This
name may be used i n a GO s t a t e m e n t t o t r a n s f e r c o n t r o l t o t h e labelled form.
statements
A s e r i e s of non-atomic forms t h a t c o n s t i t u t e t h e body i n a program
expression. The s t a t e m e n t s a r e e v a l u a t e d i n s e r i e s f o r t h e i r e f f e c t
on v a r i a b l e s r a t h e r t h a n t h e i r v a l u e . A l l LISP forms a r e l e g a l s t a t e m e n t s .
Recursion i s p e r m i t t e d . The GO and RETURN s t a t e m e n t s a l l o w c o n t r o l over
t h e sequence of s t a t e m e n t execution.
value c e l l
A p l a c e used t o s t o r e t h e v a l u e of a s p e c i a l v a r i a b l e . The v a l u e c e l l i s
a s s o c i a t e d w i t h t h e l i t e r a l atom name of t h e s p e c i a l v a r i a b l e s o t h a t t h e
v a l u e may be r e t r i e v e d by a l l f u n c t i o n s , independent of c o n t e x t . (See
zero-level bindings.)
z e r o - l e v e l bindings
A v a r i a b l e t h a t has a v a l u e a t t h e t o p l e v e l (the zero l e v e l ) i s bound a t
t h e top l e v e l . I t has a scope t h a t i s g l o b a l , i . e . , may be used f r e e l y
a t any l e v e l s i n c e i t i s defined f o r a l l l e v e l s . V a r i a b l e s w i t h zero l e v e l
bindings a r e e s t a b l i s h e d by CSET o r CSETQ (and SET and SETQ f o r some
systems) and a r e u s u a l l y system c o n s t a n t s .
APPENDIX C
REFERENCES
Timothy P. Hart and Thomas G. Evans, "Notes on Implementing LISP for the
M-460 ~omputer." in Edmund C. Berkeley and Daniel G. Bobrow (eds.),
The Programing Language LISP: I t s Operation and Applications, 2nd ed.
(Cambridge, Massachusetts: The MIT Press, 1966), p. 191.
L. Peter Deutsch and Edmund C. Berkeley, "The LISP Implementation for the
PDP-1 ~omputer,"in Edmund C. Berkeley and Daniel G. Bobrow (eds.), The
Programming Language LISP: I t s Operation and Applications, 2nd ed.
(Cambridge, Massachusetts: The MIT Press, 1966), p. 326.
A RATOM, 126
A-list (see association list) unusual spelling, 128
APVAL, 117 (see also variables) Atoms (see atomic symbol)
Arguments :
arithmetic expressions, 82 B
composed forms , 50-55 Backtrace, 123 (see also error:
COND, 70 diagnostic tools)
debugging, 121-124 Backus Normal Form, 161
DEFINE, 66 Binding variables, 114-115 (see
EVAJiQUOTE, 62, 130-132 also variables)
functional arguments, 137, 141 Black, Fisher, 109
lambda expressions, 38-43 BNF, 161
nature of variables, 114 Breakpoints, 124 (see also error:
QUOTE, 59 diagnostic tools)
rapport with supervisor, 29
simple forms, 48 C
special forms, 58 Character objects, 129-130
Arithmetic: Character strings, 127-128
arithmetic functions, 83-86 .Church,Alonzo, 38
numbers, 25-27 Compile-time, 151 (see also macro)
number conversion, 76, 82 Compiling, 68
Association list, 115 Composition of forms (see form)
Atomic symbol : Composition of functions (see form)
examples, 5 Conditional clause, 70
literal atom, 5 Conditional expressions:
numbers : evaluation, 70-71
floating point, 27 inside program expression, 108
integers, 25-26 syntax, 70, 72
octals, 26 Constants:
object list, 127 elementary form, 47
Constants (Cont ) : . bad forms, 60
numbers, 25-27, 82 CAR, 31
quoted data, 59-60 CDR, 32
Context, 115-117 (see also conditional expressions, 71, 108
variables) unquoted data, 60
EVALQUOTE :
D definition, 130-132
Debugging, 44, 121 (see also mechanics of operation, 60-63
error) supervisor rapport, 29
Document conventions: Evaluation, 61 (see also form)
meta variables, 2
pedagogic variables, 2 F
$$-artifact, 128-129 False, 74
Dotted pair: Form:
decimal point resolution, 27 composed form:
definition, 6 definition, 50
graphical representation, 7-10 evaluation, 51, 54
Dot notation, 17-19 (see also nested lambda expressions, 53-54
S -expression) syntax, 50, 53
Dummy variable, 44-45 (see also contrast with function, 38-39
variables) elementary form:
constants, 47
E evaluation, 46 -48
Error : simple form, 47-48
diagnostic tools, 123-124 syntax, 47
high probability check list, variables, 46
121-123 special form:
number syntax, 25 -26 evaluation, 58
reclefinition, 68 macro requirements, 155
semantic class, 122 nature of, 58
syntax class, 121 value, 46
undefined evaluation: Form vs. function, 38
arithmetic functions, 82 Free variables, 109, 116-117 (see
arithmetic predicates, 76-77 also variables)
Function: List :
name, 66 circular, 145
necessary requirements, 39 construction:
Functional arguments, 137-141 APPEND, 97
Functional expression, 39-40, 53 CONS, 30
Functionals, 137 LIST, 58
Function definition, 39, 66 NCONC, 147
Function notation, 38 R P W A , 146
RPLACD, 146
G elements, 13-14
Garbage collector, 68, 156 empty list, 14
Gord, Elaine, 121 graphical representation, 19-22,
144-145
I knotted, 145
Indicator, 150-152 (see also modifying structures, 146-149
property list) predicate functions, 77
In£ix notation, 163 push-down, 119
Interpreter, 68, 115, 118, 152 re-entrant, 145
threaded, 145
use of NIL, 14
Label notation, 98 List notation, 15-17 (see also
Labels (see statement labels) S -expression)
Lambda conversion, 41-43 List structure, 13, 145 (see also list)
Lambda expression: Literal atoms, 5 (see also atomic
definition, 39-40 symbo1)
evaluation, 41 Logical connectives, 78-79
examples, 40-41
LABEL, 98
syntax, 40 Macro:
Lambda notation, 38-45 macro definitions, 152, 155
Lambda variables, 40, 42 (see macro expansion, 152
also variables) nature of, 151-152
LIFO, 119 Memory management, 68
N GO, 108
NIL : labels, 107
definition of, 14 RETURN, 108
falsity, 74 syntax, 106
result: of computation, 33 Program feature (see program
Number conversion, 76, 82 expression)
Numbers (see atomic symbol) Program variables, 106 (see also
Numeric atoms, 25-27 (see also variables)
atomic symbol) Property list, 117, 149 (see also list)
Propositional connective, 72, 80
0 Pseudo-function, 66
Object list, 127-128 Push-down list, 119
OBLIST, 127-128
On-line, 121, 134, 161
Q
P Quoting:
Parameters, 38, 47 character strings, 128
Parentheses: symbolic constants, 59
dot notation, 6
lambda expressions, 43-44 R
P-list (see property list) Read line, 126
Pointer, 7, 34, 125-126, 145-147 Recursion:
Predicate, 74 examples, 96-98
Prefix notation, 38, 163 heuristics for use, 95
Print line, 126 label notation, 98
Print name, 125-130, 149 macro limitations, 155
Program expression: nature of method, 93
evaluation, 107-108 recursive function calls, 92
program variables, 106 terminal conditions, 95
programming styles, 109 variable bindings, 115
scope of definition, 108-109 Run time, 151 (see also macro)
statements:
conditional expressions, 108 S
flow of control, 107-108 Scale factors (see atomic symbol)
Scope: T
of expression, 43-44 Time-sharing, 121
GO, 108 Top -level:
RETURN, 108 bindings, 117
of variables, 116 function calls, 42, 53
semantic errors, 122 (see also list element, 77
error) nature of, 132-133
Semi-predicate: restrictions, 132-133, 141
application example, 164 supervisor, 29-30, 60-63, 132-133
definition, 74 Trace, 124 (see also error:
S -expression: diagr.~ostictools)
building larger ones, 30-31 Trees (see S-expression)
definition, 6 True, 74
dot notation, 6-10
extracting sub -expressions, u
31 -33 Unwind, 123 (see also error:
graphical representation, 7-10, diagnostic tools)
19-22
list notation, 13-22 v
Special cell, 117-119 (see also Value cell, 117-119, 149 (see also
variables) variables)
Special forms (see form) Variables :
Statement, 106-109 APVAL, 117
Statement labels, 107 binding values:
String, 127-128 lambda conversion, 41, 117
String quoting, 122, 128 global bindings, 118
Sub -expression (see S -expression) on a-list, 115
Supervisors, 29-30, 130-133 (see zero-level bindings, 117-118; 130
a1so EVALQUOTE) bound vari.ables, 114, 132
Symbolic expression (see S- context, 1.15-117
expression) declarations, 119
Syntax errors, 121 (see also dummy vari.ables:
error) definiti.on, 44-45
dummy v a r i a b l e s (Cont .) :
lambda v a r i a b l e s , 40
program v a r i a b l e s , 106
e l e m e n t a r y forms, 46-47
f r e e v a r i a b l e s , 1 0 9 , 116-118,
142
: i n i t i a l i z e d by PROG, 106
n a t u r e o f , 114
o r d i n a r y v a r i a b l e s , 118-119
scope, 116
s e t t i n g values :
CSET, CSETQ, 118
SET, SETQ, 107
s p e c i a l c e l l , 117-119
v a l u e c e l l , 117-119, 149
s p e c i a l v a r i a b l e s , 118-119
z
Z e r o - l e v e l b i n d i n g s , 117-118, 130
FUNCTION DESCRIPTIONS
(Continued from front cover)