Common LISP: A Gentle Introduction to Symbolic Computation

Preface vii
Note to Instructors ix
Acknowledgements xiii
1. Functions and Data
	1.1. Introduction
	1.2. Functions On Numbers
	1.3. Three Kinds of Numbers
	1.4. Order Of Inputs Is Important
	1.5. Symbols
	1.6. The Special Symbols T and NIL
	1.7. Some Simple Predicates
	1.8. The EQUAL Predicate
	1.9. Putting Functions Together
		1.9.1. Defining ADD0
		1.9.2. Defining ADD1
		1.9.3. Defining TWOP
		1.9.4. Defining ONEMOREP
	1.10. The NOT Predicate
	1.11. Negating A Predicate
	1.12. Number of Inputs to a Function
	1.13. Errors
	Advanced Topics
	1.14. The History of Lisp
2. Lists
	2.1. Lists Are The Most Versatile Data Type
	2.2. What Do Lists Look Like?
	2.3. Lists of One Element
	2.4. Nested Lists
	2.5. Length of Lists
	2.6. NIL: The Empty List
	2.7. Equality of Lists
	2.8. FIRST, SECOND, THIRD, and REST
	2.9. Functions Operate On Pointers
	2.10. CAR and CDR
		2.10.1. The CDR of a Single-Element List
		2.10.2. Combinations of CAR and CDR
		2.10.3. CAR and CDR of Nested Lists
		2.10.4. CAR and CDR of NIL
	2.11. CONS
		2.11.1. CONS and the Empty List
		2.11.2. Building Nested Lists With CONS
		2.11.3. CONS Can Build Lists From Scratch
	2.12. Symmetry of CONS and CAR/CDR
	2.13. LIST
	2.14. Replacing the First Element of a List
	2.15. List Predicates
	Advanced Topics
	2.16. Unary Arithmetic with Lists
	2.17. Nonlist Cons Structures
	2.18. Circular Lists
	2.19. Length of Nonlist Cons Structures
3. EVAL Notation
	3.1. Introduction
	3.2. The EVAL Function
	3.3. EVAL Notation Can Do Anything Box Notation Can Do
	3.4. Evaluation Rules Define the Behavior of EVAL
	3.5. Defining Functions in EVAL Notation
	3.6. Variables
	3.7. Evaluating Symbols
	3.8. Using Symbols and Lists as Data
	3.9. The Problem of Misquoting
	3.10. Three Ways to Make Lists
	3.11. Four Ways to Misdefine a Function
	3.12. More About Variables
	Lisp on the Computer
	3.13. Running Lisp
	3.14. The Read-Eval-Print Loop
	3.15. Recovering From Errors
	Lisp Toolkit: ED
	Keyboard Exercise
	Advanced Topics
	3.16. Functions of No Arguments
	3.17. The QUOTE Special Function
	3.18. Internal Structure of Symbols
	3.19. Lambda Notation
	3.20. Scope of Variables
	3.21. EVAL and APPLY
4. Conditionals
	4.1. Introduction
	4.2. The IF Special Function
	4.3. The COND Macro
	4.4. Using T as a Test
	4.5. Two More Examples of COND
	4.6. COND and Parenthesis Errors
	4.7. The AND and OR Macros
	4.8. Evaluating AND and OR
	4.9. Building Complex Predicates
	4.10. Why AND and OR are Conditionals
	4.11. Conditionals are Interchangeable
	Lisp Toolkit: STEP
	Advanced Topics
	4.12. Boolean Functions
	4.13. Truth Tables
	4.14. DeMorgan™s Theorem
5. Variables and Side Effects
	5.1. Introduction
	5.2. Local and Global Variables
	5.3. SETF Assigns a Value to a Variable
	5.4. Side Effects
	5.5. The LET Special Function
	5.6. The LET* Special Function
	5.7. Side Effects Can Cause Bugs
	Lisp Toolkit: DOCUMENTATION and APROPOS
	Keyboard Exercise
	Advanced Topics
	5.8. Symbols and Value Cells
	5.9. Distinguishing Local from Global Variables
	5.10. Binding, Scoping, and Assignment
6. List Data Structures
	6.1. Introduction
	6.2. Parenthesis Notation vs. Cons Cell Notation
	6.3. The APPEND Function
	6.4. Comparing CONS, LIST, and APPEND
	6.5. More Functions on Lists
		6.5.1. REVERSE
		6.5.2. NTH and NTHCDR
		6.5.3. LAST
		6.5.4. REMOVE
	6.6. Lists as Sets
		6.6.1. MEMBER
		6.6.2. INTERSECTION
		6.6.3. UNION
		6.6.4. SET-DIFFERENCE
		6.6.5. SUBSETP
	6.7. Programming With Sets
	6.8. Lists As Tables
		6.8.1. ASSOC
		6.8.2. RASSOC
	6.9. Programming With Tables
	Lisp Toolkit: SDRAW
	Keyboard Exercise
	Advanced Topics
	6.10. Trees
		6.10.1. SUBST
		6.10.2. SUBLIS
	6.11. Efficiency of List Operations
	6.12. Shared Structure
	6.13. Equality of Objects
	6.14. Keyword Arguments
7. Applicative Programming
	7.1. Introduction
	7.2. FUNCALL
	7.3. The MAPCAR Operator
	7.4. Manipulating Tables With MAPCAR
	7.5. Lambda Expressions
	7.6. The FIND-IF Operator
	7.7. Writing ASSOC With FIND-IF
	7.8. REMOVE-IF and REMOVE-IF-NOT
	7.9. The REDUCE Operator
	7.10. EVERY
	Lisp Toolkit: TRACE and DTRACE
	Keyboard Exercise
	Advanced Topics
	7.11. Operating on Multiple Lists
	7.12. The FUNCTION Special Function
	7.13. Keyword Arguments to Applicative Operators
	7.14. Scoping and Lexical Closures
	7.15. Writing An Applicative Operator
	7.16. Functions That Make Functions
8. Recursion
	8.1. Introduction
	8.2. Martin and the Dragon
	8.3. A Function to Search for Odd Numbers
	8.4. Martin Visits The Dragon Again
	8.5. A Lisp Version of the Factorial Function
	8.6. The Dragon™s Dream
	8.7. A Recursive Function for Counting Slices of Bread
	8.8. The Three Rules of Recursion
	8.9. Martin Discovers Infinite Recursion
	8.10. Infinite Recursion in Lisp
	8.11. Recursion Templates
		8.11.1. Double-Test Tail Recursion
		8.11.2. Single-Test Tail Recursion
		8.11.3. Augmenting Recursion
	8.12. Variations on the Basic Templates
		8.12.1. List-Consing Recursion
		8.12.2. Simultaneous Recursion on Several Variables
		8.12.3. Conditional Augmentation
		8.12.4. Multiple Recursion
	8.13. Trees and CAR/CDR Recursion
	8.14. Using Helping Functions
	8.15. Recursion in Art and Literature
	Lisp Toolkit: The Debugger
	Keyboard Exercise
	Advanced Topics
	8.16. Advantages of Tail Recursion
	8.17. Writing New Applicative Operators
	8.18. The LABELS Special Function
	8.19. Recursive Data Structures
9. Input/Output
	9.1. Introduction
	9.2. Character Strings
	9.3. The FORMAT Function
	9.4. The READ Function
	9.5. The YES-OR-NO-P Function
	9.6. Reading Files with WITH-OPEN-FILE
	9.7. Writing Files with WITH-OPEN-FILE
	Keyboard Exercise
	Lisp Toolkit: DRIBBLE
	Advanced Topics
	9.8. Parameters to Format Directives
	9.9. Additional Format Directives
	9.10. The Lisp 1.5 Output Primitives
	9.11. Handling End-of-File Conditions
	9.12. Printing in Dot Notation
	9.13. Hybrid Notation
10. Assignment
	10.1. Introduction
	10.2. Updating a Global Variable
	10.3. Stereotypical Updating Methods
		10.3.1. The INCF and DECF Macros
		10.3.2. The PUSH and POP Macros
		10.3.3. Updating Local Variables
	10.4. WHEN and UNLESS
	10.5. Generalized Variables
	10.6. Case Study: A Tic-Tac-Toe Player
	Lisp Toolkit: BREAK and ERROR
	Keyboard Exercise
	Advanced Topics
	10.7. Do-It-Yourself List Surgery
	10.8. Destructive Operations on Lists
		10.8.1. NCONC
		10.8.2. NSUBST
		10.8.3. Other Destructive Functions
	10.9. Programming With Destructive Operations
	10.10. SETQ and SET
	11. Iteration and Block Structure
	11.1. Introduction
	11.2. DOTIMES and DOLIST
	11.3. Exiting the Body of a Loop
	11.4. Comparing Recursive and Iterative Search
	11.5. Building Up Results With Assignment
	11.6. Comparing DOLIST with MAPCAR and Recursion
	11.7. The DO Macro
	11.8. Advantages of Implicit Assignment
	11.9. The DO* Macro
	11.10. Infinite Loops with DO
	11.11. Implicit Blocks
	Keyboard Exercise
	Lisp Toolkit: TIME
	Advanced Topics
	11.12. PROG1, PROG2, and PROGN
	11.13. Optional Arguments
	11.14. Rest Arguments
	11.15. Keyword Arguments
	11.16. Auxiliary Variables
12. Structures and The Type System
	12.1. Introduction
	12.2. TYPEP and TYPE-OF
	12.3. Defining Structures
	12.4. Type Predicates for Structures
	12.5. Accessing and Modifying Structures
	12.6. Keyword Arguments to Constructor Functions
	12.7. Changing Structure Definitions
	Lisp Toolkit: DESCRIBE and INSPECT
	Keyboard Exercise
	Advanced Topics
	12.8. Print Functions for Structures
	12.9. Equality of Structures
	12.10. Inheritance from Other Structures
13. Arrays, Hash Tables, And Property Lists
	13.1. Introduction
	13.2. Creating an Array
	13.3. Printing Arrays
	13.4. Accessing and Modifying Array Elements
	13.5. Creating Arrays With MAKE-ARRAY
	13.6. Strings as Vectors
	13.7. Hash Tables
	13.8. Property Lists
	13.9. Programming With Property Lists
	Array Keyboard Exercise
	Hash Table Keyboard Exercise
	Lisp Toolkit: ROOM
	Advanced Topics
	13.10. Property List Cells
	13.11. More On Sequences
14. Macros and Compilation
	14.1. Introduction
	14.2. Macros as Shorthand
	14.3. Macro Expansion
	14.4. Defining a Macro
	14.5. Macros as Syntactic Extensions
	14.6. The Backquote Character
	14.7. Splicing With Backquote
	14.8. The Compiler
	14.9. Compilation and Macro Expansion
	14.10. Compiling Entire Programs
	14.11. Case Study: Finite State Machines
	Lisp Toolkit: PPMX
	Keyboard Exercise
	Advanced Topics
	14.12. The &BODY Lambda-List Keyword
	14.13. Destructuring Lambda Lists
	14.14. Macros and Lexical Scoping
	14.15. Historical Significance of Macros
	14.16. Dynamic Scoping
	14.17. DEFVAR, DEFPARAMETER, DEFCONSTANT
	14.18. Rebinding Special Variables
Appendix A. The SDRAW Tool
Appendix B. The DTRACE Tool
Appendix C. Answers to Exercises
Glossary
Further Reading
Index I-