Touretzky D.S. COMMON LISP: A Gentle Introduction to Symbolic Computation

Touretzky, David S.
Common LISP : a gentle introduction to symbolic computation, 1990. p. 587This book is about learning to program in Lisp. Although widely known as
the principal language of artificial intelligence research — one of the most
advanced areas of computer science — Lisp is an excellent language for
beginners. It is increasingly the language of choice in introductory
programming courses due to its friendly, interactive environment, rich data
structures, and powerful software tools that even a novice can master in short
order.Note to Instructors1. Functions and Data 1
1.1. Introduction 1
1.2. Functions On Numbers 2
1.3. Three Kinds of Numbers 3
1.4. Order Of Inputs Is Important 4
1.5. Symbols 6
1.6. The Special Symbols T and NIL 7
1.7. Some Simple Predicates 8
1.8. The EQUAL Predicate 10
1.9. Putting Functions Together 12
1.9.1. Defining ADD1 12
1.9.2. Defining ADD2 13
1.9.3. Defining TWOP 15
1.9.4. Defining ONEMOREP 16
1.10. The NOT Predicate 18
1.11. Negating A Predicate 20
1.12. Number of Inputs to a Function 22
1.13. Errors 24
Advanced Topics 26
1.14. The History of Lisp 27
2. Lists 31
2.1. Lists Are The Most Versatile Data Type 31
2.2. What Do Lists Look Like? 31
2.3. Lists of One Element 33
2.4. Nested Lists 33
2.5. Length of Lists 35
2.6. NIL: The Empty List 37
2.7. Equality of Lists 38
2.8. FIRST, SECOND, THIRD, and REST 39
2.9. Functions Operate On Pointers 41
2.10. CAR and CDR 42
2.10.1. The CDR of a Single-Element List 44
2.10.2. Combinations of CAR and CDR 45
2.10.3. CAR and CDR of Nested Lists 47
2.10.4. CAR and CDR of NIL 50
2.11. CONS 52
2.11.1. CONS and the Empty List 55
2.11.2. Building Nested Lists With CONS 56
2.11.3. CONS Can Build Lists From Scratch 56
2.12. Symmetry of CONS and CAR/CDR 57
2.13. LIST 58
2.14. Replacing the First Element of a List 63
2.15. List Predicates 66
Advanced Topics 69
2.16. Unary Arithmetic with Lists 70
2.17. Nonlist Cons Structures 72
2.18. Circular Lists 74
2.19. Length of Nonlist Cons Structures 75
3. EVAL Notation 77
3.1. Introduction 77
3.2. The EVAL Function 78
3.3. EVAL Notation Can Do Anything Box Notation Can Do 79
3.4. Evaluation Rules Define the Behavior of EVAL 80
3.5. Defining Functions in EVAL Notation 82
3.6. Variables 84
3.7. Evaluating Symbols 86
3.8. Using Symbols and Lists as Data 87
3.9. The Problem of Misquoting 88
3.10. Three Ways to Make Lists 89
3.11. Four Ways to Misdefine a Function 91
3.12. More About Variables 92
Contents xvii
Lisp on the Computer 96
3.13. Running Lisp 97
3.14. The Read-Eval-Print Loop 98
3.15. Recovering From Errors 98
Lisp Toolkit: ED 99
Keyboard Exercise 101
Advanced Topics 103
3.16. Functions of No Arguments 103
3.17. The QUOTE Special Function 104
3.18. Internal Structure of Symbols 105
3.19. Lambda Notation 106
3.20. Scope of Variables 109
3.21. EVAL and APPLY 110
4. Conditionals 113
4.1. Introduction 113
4.2. The IF Special Function 113
4.3. The COND Macro 116
4.4. Using T as a Test 117
4.5. Two More Examples of COND 118
4.6. COND and Parenthesis Errors 119
4.7. The AND and OR Macros 122
4.8. Evaluating AND and OR 122
4.9. Building Complex Predicates 123
4.10. Why AND and OR are Conditionals 125
4.11. Conditionals are Interchangeable 126
Lisp Toolkit: STEP 129
Advanced Topics 131
4.12. Boolean Functions 132
4.13. Truth Tables 133
4.14. DeMorgan’s Theorem 134
5. Variables and Side Effects 137
5.1. Introduction 137
5.2. Local and Global Variables 137
5.3. SETF Assigns a Value to a Variable 138
5.4. Side Effects 140
5.5. The LET Special Function 141
5.6. The LET* Special Function 144
5.7. Side Effects Can Cause Bugs 147
Lisp Toolkit: DOCUMENTATION and APROPOS 149
Keyboard Exercise 151
Advanced Topics 152
5.8. Symbols and Value Cells 153
5.9. Distinguishing Local from Global Variables 155
5.10. Binding, Scoping, and Assignment 157
6. List Data Structures 159
6.1. Introduction 159
6.2. Parenthesis Notation vs. Cons Cell Notation 160
6.3. The APPEND Function 161
6.4. Comparing CONS, LIST, and APPEND 164
6.5. More Functions on Lists 165
6.5.1. REVERSE 165
6.5.2. NTH and NTHCDR 166
6.5.3. LAST 168
6.5.4. REMOVE 168
6.6. Lists as Sets 170
6.6.1. MEMBER 170
6.6.2. INTERSECTION 172
6.6.3. UNION 173
6.6.4. SET-DIFFERENCE 173
6.6.5. SUBSETP 174
6.7. Programming With Sets 175
6.8. Lists As Tables 179
6.8.1. ASSOC 179
6.8.2. RASSOC 180
6.9. Programming With Tables 181
Lisp Toolkit: SDRAW 185
Keyboard Exercise 188
Advanced Topics 192
6.10. Trees 192
6.10.1. SUBST 192
6.10.2. SUBLIS 193
6.11. Efficiency of List Operations 193
6.12. Shared Structure 194
6.13. Equality of Objects 195
Contents xix
6.14. Keyword Arguments 198
7. Applicative Programming 201
7.1. Introduction 201
7.2. FUNCALL 201
7.3. The MAPCAR Operator 202
7.4. Manipulating Tables With MAPCAR 203
7.5. Lambda Expressions 205
7.6. The FIND-IF Operator 207
7.7. Writing ASSOC With FIND-IF 207
7.8. REMOVE-IF and REMOVE-IF-NOT 210
7.9. The REDUCE Operator 213
7.10. EVERY 214
Lisp Toolkit: TRACE and DTRACE 216
Keyboard Exercise 219
Advanced Topics 223
7.11. Operating on Multiple Lists 224
7.12. The FUNCTION Special Function 225
7.13. Keyword Arguments to Applicative Operators 226
7.14. Scoping and Lexical Closures 226
7.15. Writing An Applicative Operator 229
7.16. Functions That Make Functions 230
8. Recursion 231
8.1. Introduction 231
8.2. Martin and the Dragon 232
8.3. A Function to Search for Odd Numbers 234
8.4. Martin Visits The Dragon Again 236
8.5. A Lisp Version of the Factorial Function 237
8.6. The Dragon’s Dream 238
8.7. A Recursive Function for Counting Slices of Bread 240
8.8. The Three Rules of Recursion 241
8.9. Martin Discovers Infinite Recursion 244
8.10. Infinite Recursion in Lisp 246
8.11. Recursion Templates 248
8.11.1. Double-Test Tail Recursion 248
8.11.2. Single-Test Tail Recursion 250
8.11.3. Augmenting Recursion 252
8.12. Variations on the Basic Templates 254
8.12.1. List-Consing Recursion 254
8.12.2. Simultaneous Recursion on Several Variables 256
8.12.3. Conditional Augmentation 258
8.12.4. Multiple Recursion 260
8.13. Trees and CAR/CDR Recursion 262
8.14. Using Helping Functions 266
8.15. Recursion in Art and Literature 268
Lisp Toolkit: The Debugger 271
Keyboard Exercise 274
Advanced Topics 278
8.16. Advantages of Tail Recursion 279
8.17. Writing New Applicative Operators 282
8.18. The LABELS Special Function 282
8.19. Recursive Data Structures 283
9. Input/Output 287
9.1. Introduction 287
9.2. Character Strings 288
9.3. The FORMAT Function 288
9.4. The READ Function 292
9.5. The YES-OR-NO-P Function 293
9.6. Reading Files with WITH-OPEN-FILE 294
9.7. Writing Files with WITH-OPEN-FILE 295
Keyboard Exercise 296
Lisp Toolkit: DRIBBLE 298
Advanced Topics 299
9.8. Parameters to Format Directives 299
9.9. Additional Format Directives 300
9.10. The Lisp 1.5 Output Primitives 301
9.11. Handling End-of-File Conditions 302
9.12. Printing in Dot Notation 303
9.13. Hybrid Notation 304
10. Assignment 307
10.1. Introduction 307
10.2. Updating a Global Variable 308
10.3. Stereotypical Updating Methods 309
10.3.1. The INCF and DECF Macros 309
10.3.2. The PUSH and POP Macros 310
Contents xxi
10.3.3. Updating Local Variables 312
10.4. WHEN and UNLESS 313
10.5. Generalized Variables 314
10.6. Case Study: A Tic-Tac-Toe Player 315
Lisp Toolkit: BREAK and ERROR 325
Keyboard Exercise 328
Advanced Topics 332
10.7. Do-It-Yourself List Surgery 332
10.8. Destructive Operations on Lists 334
10.8.1. NCONC 334
10.8.2. NSUBST 336
10.8.3. Other Destructive Functions 336
10.9. Programming With Destructive Operations 337
10.10. SETQ and SET 338
11. Iteration and Block Structure 341
11.1. Introduction 341
11.2. DOTIMES and DOLIST 341
11.3. Exiting the Body of a Loop 342
11.4. Comparing Recursive and Iterative Search 344
11.5. Building Up Results With Assignment 345
11.6. Comparing DOLIST with MAPCAR and Recursion 346
11.7. The DO Macro 347
11.8. Advantages of Implicit Assignment 349
11.9. The DO* Macro 351
11.10. Infinite Loops with DO 352
11.11. Implicit Blocks 353
Keyboard Exercise 355
Lisp Toolkit: TIME 358
Advanced Topics 359
11.12. PROG1, PROG2, and PROGN 359
11.13. Optional Arguments 360
11.14. Rest Arguments 361
11.15. Keyword Arguments 363
11.16. Auxiliary Variables 364
12. Structures and The Type System 365
12.1. Introduction 365
12.2. TYPEP and TYPE-OF 366
12.3. Defining Structures 367
12.4. Type Predicates for Structures 369
12.5. Accessing and Modifying Structures 369
12.6. Keyword Arguments to Constructor Functions 370
12.7. Changing Structure Definitions 371
Lisp Toolkit: DESCRIBE and INSPECT 372
Keyboard Exercise 374
Advanced Topics 377
12.8. Print Functions for Structures 378
12.9. Equality of Structures 380
12.10. Inheritance from Other Structures 381
13. Arrays, Hash Tables, And Property Lists 383
13.1. Introduction 383
13.2. Creating an Array 383
13.3. Printing Arrays 385
13.4. Accessing and Modifying Array Elements 385
13.5. Creating Arrays With MAKE-ARRAY 386
13.6. Strings as Vectors 387
13.7. Hash Tables 388
13.8. Property Lists 389
13.9. Programming With Property Lists 391
Array Keyboard Exercise 393
Hash Table Keyboard Exercise 395
Lisp Toolkit: ROOM 399
Advanced Topics 401
13.10. Property List Cells 401
13.11. More On Sequences 402
14. Macros and Compilation 405
14.1. Introduction 405
14.2. Macros as Shorthand 405
14.3. Macro Expansion 406
14.4. Defining a Macro 408
14.5. Macros as Syntactic Extensions 411
14.6. The Backquote Character 412
14.7. Splicing With Backquote 414
14.8. The Compiler 415
14.9. Compilation and Macro Expansion 417
Contents xxiii
14.10. Compiling Entire Programs 417
14.11. Case Study: Finite State Machines 418
Lisp Toolkit: PPMX 425
Keyboard Exercise 427
Advanced Topics 429
14.12. The &BODY Lambda-List Keyword 429
14.13. Destructuring Lambda Lists 430
14.14. Macros and Lexical Scoping 433
14.15. Historical Significance of Macros 435
14.16. Dynamic Scoping 435
14.17. DEFVAR, DEFPARAMETER, DEFCONSTANT 439
14.18. Rebinding Special Variables 440
Appendix A. The SDRAW Tool A-1
Appendix B. The DTRACE Tool B-1
Appendix C. Answers to Exercises C-1
Glossary G-1
Further Reading FR-1
Index I-1