Common Lisp. A Gentle Introduction To Symbolic Computation

Preface......Page 5
Note to Instructors......Page 7
Acknowledgements......Page 11
1.1 INTRODUCTION......Page 13
1.2 FUNCTIONS ON NUMBERS......Page 14
1.3 THREE KINDS OF NUMBERS......Page 15
1.4 ORDER OF INPUTS IS IMPORTANT......Page 16
1.5 SYMBOLS......Page 18
1.6 THE SPECIAL SYMBOLS T AND NIL......Page 19
1.7 SOME SIMPLE PREDICATES......Page 20
1.8 THE EQUAL PREDICATE......Page 22
1.9.1 Defining ADD1......Page 24
1.9.2 Defining ADD2......Page 25
1.9.3 Defining TWOP......Page 27
1.9.4 Defining ONEMOREP......Page 28
1.10 THE NOT PREDICATE......Page 30
1.11 NEGATING A PREDICATE......Page 32
1.12 NUMBER OF INPUTS TO A FUNCTION......Page 34
1.13 ERRORS......Page 36
1.14 THE HISTORY OF LISP......Page 39
2.2 WHAT DO LISTS LOOK LIKE?......Page 43
2.4 NESTED LISTS......Page 45
2.5 LENGTH OF LISTS......Page 47
2.6 NIL: THE EMPTY LIST......Page 49
2.7 EQUALITY OF LISTS......Page 50
2.8 FIRST, SECOND, THIRD, AND REST......Page 51
2.9 FUNCTIONS OPERATE ON POINTERS......Page 53
2.10 CAR AND CDR......Page 54
2.10.1 The CDR of a Single- Element List......Page 56
2.10.2 Combinations of CAR and CDR......Page 57
2.10.3 CAR and CDR of Nested Lists......Page 59
2.10.4 CAR and CDR of NIL......Page 62
2.11 CONS......Page 64
2.11.1 CONS and the Empty List......Page 67
2.11.3 CONS Can Build Lists From Scratch......Page 68
2.12 SYMMETRY OF CONS AND CAR/ CDR......Page 69
2.13 LIST......Page 70
2.14 REPLACING THE FIRST ELEMENT OF A LIST......Page 75
2.15 LIST PREDICATES......Page 78
2.16 UNARY ARITHMETIC WITH LISTS......Page 82
2.17 NONLIST CONS STRUCTURES......Page 84
2.18 CIRCULAR LISTS......Page 86
2.19 LENGTH OF NONLIST CONS STRUCTURES......Page 87
3.1 INTRODUCTION......Page 89
3.2 THE EVAL FUNCTION......Page 90
3.3 EVAL NOTATION CAN DO ANYTHING BOX NOTATION CAN DO......Page 91
3.4 EVALUATION RULES DEFINE THE BEHAVIOR OF EVAL......Page 92
3.5 DEFINING FUNCTIONS IN EVAL NOTATION......Page 94
3.6 VARIABLES......Page 96
3.7 EVALUATING SYMBOLS......Page 98
3.8 USING SYMBOLS AND LISTS AS DATA......Page 99
3.9 THE PROBLEM OF MISQUOTING......Page 100
3.10 THREE WAYS TO MAKE LISTS......Page 101
3.11 FOUR WAYS TO MISDEFINE A FUNCTION......Page 103
3.12 MORE ABOUT VARIABLES......Page 104
3.13 RUNNING LISP......Page 109
3.15 RECOVERING FROM ERRORS......Page 110
3.16 FUNCTIONS OF NO ARGUMENTS......Page 115
3.17 THE QUOTE SPECIAL FUNCTION......Page 116
3.18 INTERNAL STRUCTURE OF SYMBOLS......Page 117
3.19 LAMBDA NOTATION......Page 118
3.20 SCOPE OF VARIABLES......Page 121
3.21 EVAL AND APPLY......Page 122
4.2 THE IF SPECIAL FUNCTION......Page 125
4.3 THE COND MACRO......Page 128
4.4 USING T AS A TEST......Page 129
4.5 TWO MORE EXAMPLES OF COND......Page 130
4.6 COND AND PARENTHESIS ERRORS......Page 131
4.8 EVALUATING AND AND OR......Page 134
4.9 BUILDING COMPLEX PREDICATES......Page 135
4.10 WHY AND AND OR ARE CONDITIONALS......Page 137
4.11 CONDITIONALS ARE INTERCHANGEABLE......Page 138
4.12 BOOLEAN FUNCTIONS......Page 144
4.13 TRUTH TABLES......Page 145
4.14 DEMORGAN’S THEOREM......Page 146
5.2 LOCAL AND GLOBAL VARIABLES......Page 149
5.3 SETF ASSIGNS A VALUE TO A VARIABLE......Page 150
5.4 SIDE EFFECTS......Page 152
5.5 THE LET SPECIAL FUNCTION......Page 153
5.6 THE LET* SPECIAL FUNCTION......Page 156
5.7 SIDE EFFECTS CAN CAUSE BUGS......Page 159
5.8 SYMBOLS AND VALUE CELLS......Page 165
5.9 DISTINGUISHING LOCAL FROM GLOBAL VARIABLES......Page 167
5.10 BINDING, SCOPING, AND ASSIGNMENT......Page 169
6.1 INTRODUCTION......Page 171
6.2 PARENTHESIS NOTATION VS. CONS CELL NOTATION......Page 172
6.3 THE APPEND FUNCTION......Page 173
6.4 COMPARING CONS, LIST, AND APPEND......Page 176
6.5.1 REVERSE......Page 177
6.5.2 NTH and NTHCDR......Page 178
6.5.4 REMOVE......Page 180
6.6.1 MEMBER......Page 182
6.6.2 INTERSECTION......Page 184
6.6.4 SET- DIFFERENCE......Page 185
6.6.5 SUBSETP......Page 186
6.7 PROGRAMMING WITH SETS......Page 187
6.8.1 ASSOC......Page 191
6.8.2 RASSOC......Page 192
6.9 PROGRAMMING WITH TABLES......Page 193
6.10.1 SUBST......Page 204
6.11 EFFICIENCY OF LIST OPERATIONS......Page 205
6.12 SHARED STRUCTURE......Page 206
6.13 EQUALITY OF OBJECTS......Page 207
6.14 KEYWORD ARGUMENTS......Page 210
7.2 FUNCALL......Page 213
7.3 THE MAPCAR OPERATOR......Page 214
7.4 MANIPULATING TABLES WITH MAPCAR......Page 215
7.5 LAMBDA EXPRESSIONS......Page 217
7.7 WRITING ASSOC WITH FIND- IF......Page 219
7.8 REMOVE- IF AND REMOVE- IF- NOT......Page 222
7.9 THE REDUCE OPERATOR......Page 225
7.10 EVERY......Page 226
7.11 OPERATING ON MULTIPLE LISTS......Page 236
7.12 THE FUNCTION SPECIAL FUNCTION......Page 237
7.14 SCOPING AND LEXICAL CLOSURES......Page 238
7.15 WRITING AN APPLICATIVE OPERATOR......Page 241
7.16 FUNCTIONS THAT MAKE FUNCTIONS......Page 242
8.1 INTRODUCTION......Page 243
8.2 MARTIN AND THE DRAGON......Page 244
8.3 A FUNCTION TO SEARCH FOR ODD NUMBERS......Page 246
8.4 MARTIN VISITS THE DRAGON AGAIN......Page 248
8.5 A LISP VERSION OF THE FACTORIAL FUNCTION......Page 249
8.6 THE DRAGON’S DREAM......Page 250
8.7 A RECURSIVE FUNCTION FOR COUNTING SLICES OF BREAD......Page 252
8.8 THE THREE RULES OF RECURSION......Page 253
8.9 MARTIN DISCOVERS INFINITE RECURSION......Page 256
8.10 INFINITE RECURSION IN LISP......Page 258
8.11.1 Double- Test Tail Recursion......Page 260
8.11.2 Single- Test Tail Recursion......Page 262
8.11.3 Augmenting Recursion......Page 264
8.12.1 List- Consing Recursion......Page 266
8.12.2 Simultaneous Recursion on Several Variables......Page 268
8.12.3 Conditional Augmentation......Page 270
8.12.4 Multiple Recursion......Page 272
8.13 TREES AND CAR/ CDR RECURSION......Page 274
8.14 USING HELPING FUNCTIONS......Page 278
8.15 RECURSION IN ART AND LITERATURE......Page 280
8.16 ADVANTAGES OF TAIL RECURSION......Page 291
8.18 THE LABELS SPECIAL FUNCTION......Page 294
8.19 RECURSIVE DATA STRUCTURES......Page 295
9.1 INTRODUCTION......Page 299
9.3 THE FORMAT FUNCTION......Page 300
9.4 THE READ FUNCTION......Page 304
9.5 THE YES- OR- NO- P FUNCTION......Page 305
9.6 READING FILES WITH WITH- OPEN- FILE......Page 306
9.7 WRITING FILES WITH WITH- OPEN- FILE......Page 307
9.8 PARAMETERS TO FORMAT DIRECTIVES......Page 311
9.9 ADDITIONAL FORMAT DIRECTIVES......Page 312
9.10 THE LISP 1.5 OUTPUT PRIMITIVES......Page 313
9.11 HANDLING END- OF- FILE CONDITIONS......Page 314
9.12 PRINTING IN DOT NOTATION......Page 315
9.13 HYBRID NOTATION......Page 316
10.1 INTRODUCTION......Page 319
10.2 UPDATING A GLOBAL VARIABLE......Page 320
10.3.1 The INCF and DECF Macros......Page 321
10.3.2 The PUSH and POP Macros......Page 322
10.3.3 Updating Local Variables......Page 324
10.4 WHEN AND UNLESS......Page 325
10.5 GENERALIZED VARIABLES......Page 326
10.6 CASE STUDY: A TIC- TAC- TOE PLAYER......Page 327
10.7 DO- IT- YOURSELF LIST SURGERY......Page 344
10.8.1 NCONC......Page 346
10.8.3 Other Destructive Functions......Page 348
10.9 PROGRAMMING WITH DESTRUCTIVE OPERATIONS......Page 349
10.10 SETQ AND SET......Page 350
11.2 DOTIMES AND DOLIST......Page 353
11.3 EXITING THE BODY OF A LOOP......Page 354
11.4 COMPARING RECURSIVE AND ITERATIVE SEARCH......Page 356
11.5 BUILDING UP RESULTS WITH ASSIGNMENT......Page 357
11.6 COMPARING DOLIST WITH MAPCAR AND RECURSION......Page 358
11.7 THE DO MACRO......Page 359
11.8 ADVANTAGES OF IMPLICIT ASSIGNMENT......Page 361
11.9 THE DO* MACRO......Page 363
11.10 INFINITE LOOPS WITH DO......Page 364
11.11 IMPLICIT BLOCKS......Page 365
11.12 PROG1, PROG2, AND PROGN......Page 371
11.13 OPTIONAL ARGUMENTS......Page 372
11.14 REST ARGUMENTS......Page 373
11.15 KEYWORD ARGUMENTS......Page 375
11.16 AUXILIARY VARIABLES......Page 376
12.1 INTRODUCTION......Page 377
12.2 TYPEP AND TYPE- OF......Page 378
12.3 DEFINING STRUCTURES......Page 379
12.5 ACCESSING AND MODIFYING STRUCTURES......Page 381
12.6 KEYWORD ARGUMENTS TO CONSTRUCTOR FUNCTIONS......Page 382
12.7 CHANGING STRUCTURE DEFINITIONS......Page 383
12.8 PRINT FUNCTIONS FOR STRUCTURES......Page 390
12.9 EQUALITY OF STRUCTURES......Page 392
12.10 INHERITANCE FROM OTHER STRUCTURES......Page 393
13.2 CREATING AN ARRAY......Page 395
13.4 ACCESSING AND MODIFYING ARRAY ELEMENTS......Page 397
13.5 CREATING ARRAYS WITH MAKE- ARRAY......Page 398
13.6 STRINGS AS VECTORS......Page 399
13.7 HASH TABLES......Page 400
13.8 PROPERTY LISTS......Page 401
13.9 PROGRAMMING WITH PROPERTY LISTS......Page 403
13.10 PROPERTY LIST CELLS......Page 413
13.11 MORE ON SEQUENCES......Page 414
14.2 MACROS AS SHORTHAND......Page 417
14.3 MACRO EXPANSION......Page 418
14.4 DEFINING A MACRO......Page 420
14.5 MACROS AS SYNTACTIC EXTENSIONS......Page 423
14.6 THE BACKQUOTE CHARACTER......Page 424
14.7 SPLICING WITH BACKQUOTE......Page 426
14.8 THE COMPILER......Page 427
14.10 COMPILING ENTIRE PROGRAMS......Page 429
14.11 CASE STUDY: FINITE STATE MACHINES......Page 430
14.12 THE &BODY LAMBDA- LIST KEYWORD......Page 441
14.13 DESTRUCTURING LAMBDA LISTS......Page 442
14.14 MACROS AND LEXICAL SCOPING......Page 445
14.16 DYNAMIC SCOPING......Page 447
14.17 DEFVAR, DEFPARAMETER, DEFCONSTANT......Page 451
14.18 REBINDING SPECIAL VARIABLES......Page 452
Appendix A The SDRAW Tool......Page 455
Appendix B The DTRACE Tool......Page 465
CHAPTER 1 ANSWERS......Page 473
CHAPTER 2 ANSWERS......Page 481
CHAPTER 3 ANSWERS......Page 491
CHAPTER 4 ANSWERS......Page 497
CHAPTER 5 ANSWERS......Page 502
CHAPTER 6 ANSWERS......Page 504
CHAPTER 7 ANSWERS......Page 510
CHAPTER 8 ANSWERS......Page 516
CHAPTER 9 ANSWERS......Page 529
CHAPTER 10 ANSWERS......Page 532
CHAPTER 11 ANSWERS......Page 535
CHAPTER 12 ANSWERS......Page 541
CHAPTER 13 ANSWERS......Page 543
CHAPTER 14 ANSWERS......Page 547
Glossary......Page 551
Historical Material......Page 567
Other Lisp Textbooks......Page 568
Index......Page 569
Contents......Page 579