The Table of Contents for Lisp follows.
Additional information about this book, along with access to software, is
available via http://www.ai.mit.edu/people/phw/Books/
Contents
In this Table of Contents, you learn about what Lisp contains
in detail.
1 Understanding Symbol Manipulation
- Symbol Manipulation Is Like Working with Words and Sentences
- Lisp Helps Make Computers Intelligent
- Lisp Promotes Productivity and Facilitates Education
- Lisp Is the Right Symbol-Manipulation Language To Learn
- CommonLisp Is the Right Lisp To Learn
- Beware of False Myths
- Summary
- References
2 Basic Lisp Primitives
- Lisp Means Symbol Manipulation
- Lisp Procedures and Data Are Symbolic Expressions
- Lists Are Like Bowls
- FIRST and REST Take Lists Apart
- Quoting Stops Evaluation
- Some Old Timers Use CARs and CDRs
- SETF Assigns Values to Symbols
- SETF Accepts Multiple Symbol-Value Pairs
- Certain Atoms Evaluate to Themselves
- CONS, APPEND, and LIST Construct Lists
- CONS, APPEND, and LIST Do Not Alter Symbol Values
- NTHCDR, BUTLAST, and LAST Shorten Lists
- LENGTH and REVERSE Work on Top-Level Elements
- ASSOC Looks for Indexed Sublists
- Lisp Offers Integers, Ratios, and Floating-Point Numbers, among Others
- A Few Primitives for Numbers Round Out a Basic Repertoire
- Summary
3 Procedure Definition and Binding
- DEFUN is Lisp's Procedure-Definition Primitive
- Parameter Variable Values Are Isolated by Virtual Fences
- Special Variable Values Are Not Isolated by Virtual Fences
- Procedures Match Parameters to Arguments
- LET Forms Bind Parameters to Initial Values
- LET Forms Produce Nested Fences
- LET Forms Evaluate Initial-Value Forms in Parallel
- LET* Forms Evaluate Initial-Value Forms Sequentially
- Progressive Envelopment and Comment Translation Help Define New Procedures
- Summary
4 Predicates and Conditionals
- A Predicate Is a Procedure That Returns True or False
- EQUAL, EQ, EQL, and = Are Equality Predicates
- MEMBER Tests for List Membership
- Keyword Arguments Modify Behavior
- LISTP, ATOM, NUMBERP, and SYMBOLP Are Data-Type Predicates
- NIL Is Equivalent to the Empty List
- NULL and ENDP Are Empty-List Predicates
- There Are Many Number Predicates
- AND, OR, and NOT Enable Elaborate Testing
- Predicates Help IF, WHEN, and UNLESS Choose among Alternatives
- Predicates Help COND Choose among Alternatives
- CASE Is Still Another Conditional
- Conditionals Enable DEFUN To Do Much More
- Problem Reduction Helps Define New Procedures
- Summary
5 Procedure Abstraction and Recursion
- Procedure Abstraction Hides Details Behind Abstraction Boundaries
- Recursion Allows Procedures To Use Themselves
- Recursion Can Be Efficient
- Recursion Can Be Used To Analyze Nested Expressions
- Optional Parameters Eliminate the Need for Many Auxiliaries
- Advanced Programmers Use Rest, Key, and Aux Parameters
- Only a Few Lisp Primitives Are Really Necessary
- Summary
- References
6 Data Abstraction and Mapping
- Data Details Stifle Progress
- Data Abstraction Facilitates Progress
- You Should Use Readers, Constructors, and Writers Liberally
- It Is Useful To Transform and To Filter
- Recursive Procedures Can Transform and Filter
- Recursive Procedures Can Count and Find
- Cliches Embody Important Programming Knowledge
- MAPCAR Simplifies Transforming Operations
- REMOVE-IF and REMOVE-IF-NOT Simplify Filtering Operations
- COUNT-IF and FIND-IF Simplify Counting and Finding Operations
- FUNCALL and APPLY Also Take a Procedure Argument
- LAMBDA Defines Anonymous Procedures
- Summary
- References
7 Iteration on Numbers and Lists
- DOTIMES Supports Iteration on Numbers
- DOLIST Supports Iteration on Lists
- DO Is More General than DOLIST and DOTIMES
- LOOP Never Stops, Almost
- PROG1 and PROGN Handle Sequences Explicitly
- Summary
8 File Editing, Compiling, and Loading
- Programs and Data Reside in Files
- File Specifications Tend to Have Baroque Forms
- ED Takes You to an Editor
- Emacs Is a Particularly Powerful Lisp Editor
- COMPILE-FILE Compiles Files
- LOAD Causes Lisp To Read from Files
- Summary
- References
9 Printing and Reading
- PRINT and READ Facilitate Simple Printing and Reading
- FORMAT Enables Exotic Printing
- WITH-OPEN-FILE Enables Reading from Files
- Optional Arguments in READ Forms Specify End-of-File Treatment
- WITH-OPEN-FILE Enables Printing to Files
- READ Does Not Evaluate Expressions, but EVAL Evaluates Twice
- Special Primitives Manipulate Strings and Characters
- READ-LINE and READ-CHAR Read Strings and Characters
- Summary
10 Rules for Good Programming and Tools for Debugging
- Following Rules of Good Programming Practice Helps You To Avoid Bugs
- Big Programs Require Abstraction and Modularity
- Most Programmers use TRACE, STEP, and BREAK with Varying Frequency
- TRACE Causes Procedures To Print Their Arguments and Values
- STEP Causes Procedures To Proceed One Step at a Time
- BREAK Stops Evaluation so that You Can Evaluate Forms
- TIME, DESCRIBE, and DRIBBLE Are Helpful Too
- Debugging Is Implementation Specific
- Summary
- References
11 Properties and Arrays
- Each Way of Storing Data Has Constructors, Readers, and Writers
- Properties Enable Storage in Symbolically Indexed Places
- GET and SETF are the Custodians of Properties
- Arrays Enable Storage in Numerically Indexed Places
- MAKE-ARRAY, AREF, and SETF are the Custodians of Arrays
- Summary
12 Macros and Backquote
- Macros Translate and Then Evaluate
- The Backquote Mechanism Simplifies Template Filling
- The Backquote Mechanism Simplifies Macro Writing
- Optional, Rest, and Key Parameters Enable More Powerful Macros
- Macros Deserve Their Own File
- Summary
13 Structures
- Structure Types Facilitate Data Abstraction
- Structure Types Enable Storage in Procedurally Indexed Places
- Individual Structure Types Are New Data Types
- One Structure Type Can Include the Fields of Another
- Structure Types Are Important Components of Big Systems
- DESCRIBE Prints Descriptions
- DEFSTRUCTs Deserve Their Own File
- Summary
14 Classes and Generic Functions
- What to Do Depends on What You Do it to
- You Can Make Ordinary Procedures Data Driven, Albeit Awkwardly
- Methods Are Procedures Selected from Generic Functions by Argument Types
- Classes Resemble Structure Types but Resonate Better with Generic Functions
- Any Nonoptional Argument's Class Can Help Select a Method
- Classes Enable Method Inheritance
- The Most Specific Method Takes Precedence over the Others
- Parameter Order Helps Determine Method Precedence
- Simple Rules Approximate the Complicated Class Precedence Algorithm
- Methods Can Be Specialized to Individual Instances
- Method Selection Involves Three Steps
- Object-Oriented Programming Offers Advantages, Not Magic
- Summary
- References
15 Lexical Variables, Generators, and Encapsulation
- LETs Produce Nested Fences
- Nested Fences Provide Variable Values
- Procedure Calls Usually Do Not Produce Nested Fences
- Nested Definitions do Produce Nested Fences
- Generators Produce Sequences
- Nameless Procedures Produce Nested Fences
- Nameless Procedures Can Be Assigned to Variables
- The Free Variables in Nameless Procedures Can Be Encapsulated
- Encapsulation Enables the Creation of Sophisticated Generators
- Generators Can Be Defined by other Procedures
- Nameless Procedures Become Lexical Closures
- Summary
- References
16 Special Variables
- Bindings Could Be Kept on a Record of Calls
- Some Variables Are Declared To Be Special Forevermore
- Special-Variable Bindings Are Actually Kept on a Stack
- DEFVAR Can Assign as Well as Declare
- Some Variable Instances Can Be Special while Others Are Lexical
- Both Lexical and Special Variables Can Be Free Variables
- Summary
17 List Storage, Surgery, and Reclamation
- Lists Can Be Represented by Boxes and Pointers
- Boxes and Pointers Can Be Represented by Bytes
- CONS Builds New Lists by Depositing Pointers in Free Boxes
- APPEND Builds New Lists by Copying
- NCONC and DELETE Can Alter Box Contents Dangerously
- SETF Also Can Alter Box Contents Dangerously
- EQ Checks Pointers Only
- Garbage Collection Reclaims Abandoned Memory
- Lisp Allows You To Write Inefficient Procedures
- Simple Garbage Collectors Use the Mark and Sweep Approach
- Simulation Procedures Expose Garbage Collection Details
- MARK Places Marks on Useful Chunks
- SWEEP Collects Unmarked Chunks
- Marking Can Be Done without Recursion
- Our Nonrecursive Marking Procedure Leaves a Trail of Pointers
- Some Garbage Collectors Are Incremental
- Summary
18 Lisp in Lisp
- It Is Easy To Build a Simple Interpreter for a Lisplike Language
- MICRO-EVAL and MICRO-APPLY Work Together To Evaluate Forms
- Traces Show How MICRO-EVAL and MICRO-APPLY Work Together
- Closures Encapsulate Environments
- Special Variable Binding Can Be Arranged
- Lisp Does Call-by-Value Rather Than Call-by-Reference
- Lisp Can Be Defined in Lisp
- Fancy Control Structures Usually Start Out as Basic Lisp Interpreters
- Summary
19 Examples Involving Search
- Breadth-First and Depth-First Searches Are Basic Strategies
- Best-First Search and Hill-Climbing Require Sorting
- Summary
- References
20 Examples Involving Simulation
- Projects Involve Events and Tasks
- Structures Can Represent Events and Tasks
- Simulation Procedures Can Propagate Event Times
- Event and Task Structures Require Special Printing Procedures
- An Event List Keeps Simulation in Step with the Simulated Project
- Summary
21 The Blocks World with Classes and Methods
- The Blocks-World Program Handles Put-On Commands
- Object-Oriented Programming Shifts Attention from Procedures to Objects
- Object-Oriented Programming Begins with Class Specification
- Slot Readers Are Generic Functions
- The Blocks-World Program's Methods Are Transparent
- Before and After Methods Simplify Bookkeeping
- Slot Writers Are Generic Functions
- Object-Oriented Programming Enables Automatic Procedure Assembly
- You Can Control How Instances Are Printed
- The Number-Crunching Methods Can Be Ignored
- The Blocks-World Program Illustrates Abstraction
- Summary
- References
22 Answering Questions about Goals
- The Blocks-World Program Can Introspect into its Own Operation
- Remembering Generic Function Calls Creates a Goal Tree
- Macros Enable Method-Defining Procedures To Be Defined
- The Goal Tree Is Easy to Display
- The Goal Tree Answers Questions
- Summary
- References
23 Constraint Propagation
- Constraints Propagate Numbers through Arithmetic Boxes
- Constraints Propagate Probability Bounds through Logic Boxes
- Classes Represent Assertions and Logical Constraints
- Generic Functions Enforce Constraints
- More Information Moves Probability Bounds Closer
- Summary
- References
24 Symbolic Pattern Matching
- Matching Compares Patterns and Datums Element by Element
- MATCH Keeps Variable Bindings on an Association List
- Matching Is Easily Implemented by a Recursive Procedure
- Matching Is Better Implemented Using Procedure Abstraction
- Unification Is Generalized Matching
- Summary
- References
25 Streams and Delayed Evaluation
- Streams Are Sequences of Data Objects
- We Can Represent Streams Using Lists
- We Can Delay Evaluation by Encapsulation
- We Can Represent Streams Using Delayed Evaluation
- Summary
- References
26 Rule-Based Expert Systems and Forward Chaining
- Forward Chaining Means Working from Antecedents to Consequents
- We Use Streams To Represent Assertions and Rules
- Our First Pass Concentrates on MATCH and the Binding Stream
- Our Second Pass Concentrates on the Procedures that Surround MATCH
- Simple Rules Help Identify Animals
- Rules Facilitate Question Answering and Probability Computing
- Our Forward-Chaining Program Illustrates Abstraction
- Summary
- References
27 Backward Chaining and PROLOG
- Our Backward Chainer Borrows Procedures from our Forward Chainer
- Backward Chaining Means Working from Consequents to Antecedents
- Our First Pass Concentrates on MATCH, UNIFY, and the Binding Stream
- Our Second Pass Concentrates on the Procedures that Surround MATCH and UNIFY
- Completing Our Backward-Chaining Program Involves a Few Auxiliary Procedures
- Simple Rules Help Identify Animals
- Our Backward Chainer Implements a Language like Prolog
- Our Backward-Chaining Program Illustrates Abstraction
- Summary
- References
28 Interpreting Transition Trees
- Procedures Can Produce Multiple Values
- Natural-Language Interfaces Produce Database Commands
- Transition Trees Capture English Syntax
- A Transition Tree Interpreter Follows an Explicit Description
- Multiple-Valued Procedures Embody Transition Trees
- Our Interpreter Uses Explicit Transition-Tree Descriptions
- We Use a Macro To Simplify Tree Definition
- A Read, Analyze, and Report Loop Adds a Finishing Touch
- Summary
- References
29 Compiling Transition Trees
- Transition Trees Can Be Compiled from Transparent Specifications
- Compilers Treat Programs as Data
- Compiled Programs Run Faster
- Compilers Are Usually Major Undertakings
- Lisp Itself Is Either Compiled or Interpreted
- Summary
30 Procedure-Writing Programs and Database Interfaces
- Grammars Can Be Sophisticated
- Answering Requests Is Done in Three Steps
- Most Database Commands Transform Relations into Relations
- English Questions Correspond to Database Commands
- Our Simulated Database Supports an Improved Grammar
- The Relational Database Can Be Faked
- The Database Illustrates Data Abstraction
- Summary
31 Finding Patterns in Images
- Generating All Possible Matches Helps Isolate the Correct Match
- Constraints Are Needed To Isolate the Correct Match
- The Search Tree Can Be Pruned Using Geometric Information
- Matches Have To Be Checked for Global Consistency
- Matching Is Harder if Mismatches Are Allowed
- Keeping Track of Mismatches Improves Efficiency
- The Cost of Filtering Has To Be Weighed against the Cost of Searching
- Multiple Matching Attempts Lead to Recognition
- Edges Provide More Constraint than Points
- Summary
- References
32 Converting Notations, Manipulating Matrices, and Finding Roots
- It Is Easy to Translate Infix Notation to Prefix
- Sparse Matrices Can Be Represented as Lists of Lists
- Complex Numbers Constitute Another Numeric Data Type
- Roots of Quadratic Equations Are Easy To Calculate
- Roots of Cubic Equations Can Be Calculated
- Roots of Quartic Equations Are Harder To Calculate
- Summary
- References
Appendix: The Computation of the Class Precedence List
- Make Initial Lists
- Make a List of Precedence Pairs
- Make a List of Precedence List Candidates
- Select a Candidate
- Shrink the List of Precedence Pairs
- Repeat
Problem Solutions
Glossary
Bibliography
Index of LISP Primitives Used in this Book
Index of LISP Definitions
General Index