This highly accessible introduction to Lisp is suitable both for novices approaching their first programming language and experienced programmers interested in exploring a key tool for artificial intelligence research. The text offers clear, reader-friendly explanations of such essential concepts as cons cell structures, evaluation rules, programs as data, and recursive and applicative programming styles.
The treatment incorporates several innovative instructional devices, such as the use of function boxes in the first two chapters to visually distinguish functions from data, use of evaltrace notation in later chapters to illustrate the operation of evaluation rules, and "Dragon stories" to explain recursion. The book contains nearly 400 diagrams and illustrations, and 77 pages of answers to exercises. Advanced topics and "toolkit" sections, and a variety of complete programs, extend readers' programming power.
Author(s): David S. Touretzky
Series: Dover Books on Engineering
Edition: Illustrated
Publisher: Dover Publications
Year: 2013
Language: English
Pages: 608
Tags: scheme; functional programming; programming languages
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-
