Lisp (Third Edition)---Contents

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/

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

Contents