paip-lisp

Paradigms of Artificial Intelligence Programming

This is the repository for the book Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp by Peter Norvig (1992). Here you'll find:

• A directory of all the Lisp code from the book.
• A pdf of the book, split into two parts (because GitHub can't handle big files) covering Chapters 1-14 (PAIP-part1.pdf) and 15-25 (PAIP-part2.pdf). The copyright has recently reverted to me, and I choose to share it under MIT license.
• A rough txt export, from the pdf, PAIP.txt, containing many errors.
• We're in the process of making a nice online version of the book; here's the first draft of a few sample chapters.

As seen on TV. See also: errata, comments, preface, retrospective.

Running the Code

There is no single "application" to run. Rather, there is a collection of source code files, duplicating the code in the book. You can read and/or run whatever you like. Lisp is an interactive language, and you will need to interact with the code to get benefit from it. Some hints:

• You will need a Common Lisp interpreter/compiler/environment. Here's a discussion of the options.
• You will always need (load "auxfns.lisp").
• You will need (requires "file"), for the various instances of file that you want to use. (If requires does not work properly on your system you may have to alter its definition, in auxfns.lisp.
• The function do-examples, which takes as an argument either :all or a chapter number or a list of chapter numbers, can be used to see examples of the use of various functions. For example, (do-examples 1) shows the examples from chapter 1. Access this by doing (requires "examples").

The Files

The index below gives the chapter in the book, file name, and short description for each file.

CH	Filename	Description
-	examples.lisp	A list of example inputs taken from the book
-	tutor.lisp	An interpreter for running the examples
-	auxfns.lisp	Auxiliary functions; load this before anything else
1	intro.lisp	A few simple definitions
2	simple.lisp	Random sentence generator (two versions)
3	overview.lisp	14 versions of LENGTH and other examples
4	gps1.lisp	Simple version of General Problem Solver
4	gps.lisp	Final version of General Problem Solver
5	eliza1.lisp	Basic version of Eliza program
5	eliza.lisp	Eliza with more rules; different reader
6	patmatch.lisp	Pattern Matching Utility
6	eliza-pm.lisp	Version of Eliza using utilities
6	search.lisp	Search Utility
6	gps-srch.lisp	Version of GPS using the search utility
7	student.lisp	The Student Program
8	macsyma.lisp	The Macsyma Program
8	macsymar.lisp	Simplification and integration rules for Macsyma
9-10		(functions from these chapters are in auxfns.lisp)
11	unify.lisp	Unification functions
11	prolog1.lisp	First version of Prolog interpreter
11	prolog.lisp	Final version of Prolog interpreter
12	prologc1.lisp	First version of Prolog compiler
12	prologc2.lisp	Second version of Prolog compiler
12	prologc.lisp	Final version of Prolog compiler
12	prologcp.lisp	Primitives for Prolog compiler
13	clos.lisp	Some object-oriented and CLOS code
14	krep1.lisp	Knowledge Representation code: first version
14	krep2.lisp	Knowledge Representation code with conjunctions
14	krep.lisp	Final KR code: worlds and attached functions
15	cmacsyma.lisp	Efficient Macsyma with canonical form
16	mycin.lisp	The Emycin expert system shell
16	mycin-r.lisp	Some rules for a medical application of emycin
17	waltz.lisp	A Line-Labeling program using the Waltz algorithm
18	othello.lisp	The Othello playing program and some strategies
18	othello2.lisp	Additional strategies for Othello
18	edge-tab.lisp	Edge table for Iago strategy
19	syntax1.lisp	Syntactic Parser
19	syntax2.lisp	Syntactic Parser with semantics
19	syntax3.lisp	Syntactic Parser with semantics and preferences
20	unifgram.lisp	Unification Parser
21	grammar.lisp	Comprehensive grammar of English
21	lexicon.lisp	Sample Lexicon of English
22	interp1.lisp	Scheme interpreter, including version with macros
22	interp2.lisp	A tail recursive Scheme interpreter
22	interp3.lisp	A Scheme interpreter that handles call/cc
23	compile1.lisp	Simple Scheme compiler
23	compile2.lisp	Compiler with tail recursion and primitives
23	compile3.lisp	Compiler with peephole optimizer
23	compopt.lisp	Peephole optimizers for compile3.lisp

---

Peter Norvig

Table of Contents: Chapters

• Part I Introduction to Common Lisp
• 1 Introduction to Lisp
• 2 A Simple Lisp Program
• 3 Overview of Lisp
• Part II Early AI Programs
• 4 GPS: The General problem Solver
• 5 Eliza: Dialog with a Machine
• 6 Building Software Tools
• 7 Student: Solving Algebra Word Problems
• 8 Symbolic Mathematics: A Simplification Program
• Part III Tools and Techniques
• 9 Efficiency Issues
• 10 Low-Level Efficiency Issues
• 11 Logic Programming
• 12 Compiling Logic programs
• 13 Object-Oriented Programming
• 14 Knowledge Representation and Reasoning
• Part IV Advanced AI Programs
• 15 Symbolic Mathematics with Canonical Forms
• 16 Expert Systems
• 17 Line-Diagram Labeling by Constraint Satisfaction
• 18 Search and the Game of Othello
• 19 Introduction to Natural Language
• 20 Unification Grammars
• 21 A Grammar of English
• Part V The Rest of Lisp
• 22 Scheme: An Uncommon Lisp
• 23 Compiling Lisp
• 24 ANSI Common Lisp
• 25 Troubleshooting

Table of Contents: Full

• Preface
• Why Lisp? Why Common Lisp?
• Outline of the Book
• How to use This Book
• Supplementary Texts and Reference Books
• A Note on Exercises
• Acknowledgments
• Part I Introduction to Common Lisp
• 1 Introduction to Lisp
• 1.1 Symbolic Computation
• 1.2 Variables
• 1.3 Special Forms
• 1.4 Lists
• 1.5 Defining New Functions
• 1.6 Using Functions
• 1.7 Higher-Order Functions
• 1.8 Other Data Types
• 1.9 Summary: The Lisp Evaluation Rule
• 1.10 What Makes Lisp Different?
• 1.11 Exercises
• 1.12 Answers
• 2 A Simple Lisp Program
• 2.1 A Grammar for a Subset of English
• 2.2 A Straightforward Solution
• 2.3 A Rule-Based Solution
• 2.4 Two paths to Follow
• 2.5 Changing the Grammar without Changing the Program
• 2.6 Using the Same Data for Several Programs
• 2.7 Exercises
• 2.8 Answers
• 3 Overview of Lisp
• 3.1 A Guide to Lisp Style
• 3.2 Special Forms
• Special Forms for Definitions
• Special Forms for Conditionals
• Special Forms for Dealing with Variables and Places
• Functions and Special Forms for Repetition
• Repetition through Recursion
• Other Special Forms
• Macros
• Backquote Notation
• 3.3 Functions on Lists
• 3.4 Equality and Internal Representation
• 3.5 Functions on Sequences
• 3.6 Functions for Maintaining Tables
• 3.7 Functions on Trees
• 3.8 Functions on Numbers
• 3.9 Functions on Sets
• 3.10 Destructive Functions
• 3.11 Overview of Data types
• 3.12 Input/Output
• 3.13 Debugging tools
• 3.14 Antibugging Tools
• Timing Tools
• 3.15 Evaluation
• 3.16 Closures
• 3.17 Special Variables
• 3.18 Multiple Values
• 3.19 More about Parameters
• 3.20 The Rest of Lisp
• 3.21 Exercises
• 3.22 Answers
• Part II Early AI Programs
• 4 GPS: The General problem Solver
• 4.1 Stage 1: Description
• 4.2 Stage 2: Specification
• 4.3 Stage 3: Implementation
• 4.4 Stage 4: Test
• 4.5 Stage 5: Analysis, or "We Lied about the G"
• 4.6 The Running Around the Block Problem
• 4.7 The Clobbered Sibling Goal Problem
• 4.8 The Leaping before You Look Problem
• 4.9 The recursive Subgoal problem
• 4.10 The Lack of Intermediate Information Problem
• 4.11 GPS Version 2: A More General problem Solver
• 4.12 The New Domain problem: Monkey and Bananas
• 4.13 The Maze Searching Domain
• 4.14 The Blocks World Domain
• The Sussman Anomaly
• 4.15 Stage 5 Repeated: Analysis of Version 2
• 4.16 The Not Looking after You Don't Leap Problem
• 4.17 The Lack of Descriptive Power Problem
• 4.18 The Perfect Information Problem
• 4.19 The Interacting Goals Problem
• 4.20 The End of GPS
• 4.21 History and References
• 4.22 Exercises
• 4.23 Answers
• 5 Eliza: Dialog with a Machine
• 5.1 Describing and Specifying Eliza
• 5.2 Pattern Matching
• 5.3 Segment Pattern Matching
• 5.4 The Eliza Program: A Rule-Based Translator
• 5.5 History and References
• 5.6 Exercises
• 5.7 Answers
• 6 Building Software Tools
• 6.1 An Interactive Interpreter Tool
• 6.2 A Pattern-Matching Tool
• 6.3 A Rule-Based Translator Tool
• 6.4 A Set of Searching Tools
• Searching Trees
• Guiding the Search
• Search Paths
• Guessing versus Guaranteeing a Good Solution
• Searching Graphs
• 6.5 GPS as Search
• 6.6 History and References
• 6.7 Exercises
• 6.8 Answers
• 7 Student: Solving Algebra Word Problems
• 7.1 Translating English into Equations
• 7.2 Solving Algebraic Equations
• 7.3 Examples
• 7.4 History and References
• 7.5 Exercises
• 7.6 Answers
• 8 Symbolic Mathematics: A Simplification Program
• 8.1 Converting Infix to Prefix Notation
• 8.2 Simplification Rules
• 8.3 Associativity and Commutativity
• 8.4 Logs, Trig, and Differentiation
• 8.5 Limits of Rule-Based Approaches
• 8.6 Integration
• 8.7 History and References
• 8.8. Exercises
• Part III Tools and Techniques
• 9 Efficiency Issues
• 9.1 Caching Results of Previous Computations: Memoization
• 9.2 Compiling One Language into Another
• 9.3 Delaying Computation
• 9.4 Indexing Data
• 9.5 Instrumentation: Deciding What to Optimize
• 9.6 A Case Study in Efficiency: The SIMPLIFY Program
• Memoization
• Indexing
• Compilation
• The Single-Rule Compiler
• The Rule-Set Compiler
• 9.7 History and References
• 9.8 Exercises
• 9.9 Answers
• 10 Low-Level Efficiency Issues
• 10.1 use Declarations
• 10.2 Avoid Generic Functions
• 10.3 Avoid Complex Argument Lists
• 10.4 Avoid Unnecessary Consing
• Avoid Consing: Unique Lists
• Avoid Consing: Multiple Values
• Avoid Consing: Resources
• 10.5 Use the Right Data Structures
• The Right Data Structure: Variables
• The Right Data Structure: Queues
• The Right Data Structure: Tables
• 10.6 Exercises
• 10.7 Answers
• 11 Logic Programming
• 11.1 Idea 1: A Uniform Data Base
• 11.2 Idea 2: Unification of Logic Variables
• Programming with Prolog
• 11.3 Idea 3: Automatic Backtracking
• Approaches to Backtracking
• Anonymous Variables
• 11.4 The Zebra Puzzle
• 11.5 The Synergy of Backtracking and Unification
• 11.6 Destructive Unification
• 11.7 Prolog in Prolog
• 11.8 Prolog Compared to Lisp
• 11.9 History and References
• 11.10 Exercises
• 11.11 Answers
• 12 Compiling Logic programs
• 12.1 A prolog Compiler
• 12.2 Fixing the Errors in the Compiler
• 12.3 Improving the Compiler
• 12.4 Improving the Compilation of Unification
• 12.5 Further Improvements to Unification
• 12.6 The User Interface to the Compiler
• 12.7 Benchmarking the Compiler
• 12.8 Adding More Primitives
• 12.9 The Cut
• 12.10 "Real" Prolog
• 12.11 History and References
• 12.12 Exercises
• 12.13 Answers
• 13 Object-Oriented Programming
• 13.1 Object-Oriented Programming
• 13.2 Objects
• 13.3 Generic Functions
• 13.4 Classes
• 13.5 Delegation
• 13.6 Inheritance
• 13.7 CLOS: The Common Lisp Object System
• 13.8 A CLOS Example: Searching Tools
• Best-First Search
• 13.9 Is CLOS Object-Oriented?
• 13.10 Advantages of Object-Oriented programming
• 13.11 History and References
• 13.12 Exercises
• 14 Knowledge Representation and Reasoning
• 14.1 A Taxonomy of Representation Languages
• 14.2 Predicate Calculus and its Problems
• 14.3 A Logical Language: Prolog
• 14.4 Problems with Prolog's Expressiveness
• 14.5 Problems with Predicate Calculus's Expressiveness
• 14.6 Problems with Completeness
• 14.7 Problems with Efficiency: Indexing
• 14.8 A Solution to the Indexing Problem
• 14.9 A Solution to the Completeness Problem
• 14.10 Solutions to the Expressiveness Problems
• Higher-Order Predications
• Improvements
• A Frame Language
• Possible Worlds: Truth, Negation, and Disjunction
• Unification, Equality, Types, and Skolem Constants
• 14.11 History and References
• 14.12 Exercises
• 14.13 Answers
• Part IV Advanced AI Programs
• 15 Symbolic Mathematics with Canonical Forms
• 15.1 A Canonical Form for Polynomials
• 15.2 Differentiating Polynomials
• 15.3 Converting between Infix and Prefix
• 15.4 Benchmarking the Polynomial Simplifier
• 15.5 A Canonical Form for Rational Expressions
• 15.6 Extending Rational Expressions
• 15.7 History and References
• 15.8 Exercises
• 15.9 Answers
• 16 Expert Systems
• 16.1 Dealing with Uncertainty
• 16.2 Caching Derived Facts
• 16.3 Asking Questions
• 16.4 Contexts Instead of Variables
• 16.5 Backward-Chaining Revisited
• 16.6 Interacting with the Expert
• 16.7 Interacting with the Client
• 16.8 MYCIN, A Medical Expert System
• 16.9 Alternatives to Certainty Factors
• 16.10 History and References
• 16.11 Exercises
• 16.12 Answers
• 17 Line-Diagram Labeling by Constraint Satisfaction
• 17.1 The Line-Labeling Problem
• 17.2 Combining Constraints and Searching
• 17.3 Labeling Diagrams
• 17.4 Checking Diagrams for Errors
• 17.5 History and References
• 17.6 Exercises
• 18 Search and the Game of Othello
• 18.1 The Rules of the Game
• 18.2 Representation Choices
• 18.3 Evaluating Positions
• 18.4 Searching Ahead: Minimax
• 18.5 Smarter Searching: Alpha-Beta Search
• 18.6 An Analysis of Some Games
• 18.7 The Tournament Version of Othello
• 18.8 Playing a Series of Games
• 18.9 More Efficient Searching
• 18.10 It Pays to Precycle
• 18.11 Killer Moves
• 18.12 Championship Programs: Iago and Bill
• Mobility
• Edge Stability
• Combining the Factors
• 18.13 Other Techniques
• Interative Deepening
• Forward Pruning
• Nonspeculative Forward Pruning
• Aspiration Search
• Think-Ahead
• Hashing and Opening Book Moves
• The End Game
• Metareasoning
• Learning
• 18.14 History and References
• 18.15 Exercises
• 18.16 Answers
• 19 Introduction to Natural Language
• 19.1 Parsing with a Phrase-Structure Grammar
• 19.2 Extending the Grammar and Recognizing Ambiguity
• 19.3 More Efficient parsing
• 19.4 The Unknown-Word Problem
• 19.5 Parsing into a Semantic Representation
• 19.6 Parsing with Preferences
• 19.7 The Problem with Context-Free Phrase-Structure Rules
• 19.8 History and References
• 19.9 Exercises
• 19.10 Answers
• 20 Unification Grammars
• 20.1 Parsing as Deduction
• 20.2 Definite Clause Grammars
• 20.3 A Simple Grammar In DCG Format
• 20.4 A DCG Grammar with Quantifiers
• 20.5 Preserving Quantifier Scope Ambiguity
• 20.6 Long-Distance Dependencies
• 20.7 Augmenting DCG Rules
• 20.8 History and References
• 20.9 Exercises
• 20.10 Answers
• 21 A Grammar of English
• 21.1 Noun Phrases
• 21.2 Modifiers
• 21.3 Noun Modifiers
• 21.4 Determiners
• 21.5 Verb Phrases
• 21.6 Adverbs
• 21.7 Clauses
• 21.8 Sentences
• 21.9 XPs
• 21.10 Word Categories
• 21.11 The Lexicon
• Verbs
• Auxiliary Verbs
• Nouns
• Pronouns
• Names
• Adjectives
• Adverbs
• Articles
• Cardinal and Ordinal Numbers
• Prepositions
• 21.12 Supporting the Lexicon
• 21.13 Other Primitives
• 21.14 Examples
• 21.15 History and References
• 21.16 Exercises
• Part V The Rest of Lisp
• 22 Scheme: An Uncommon Lisp
• 22.1 A Scheme Interpreter
• 22.2 Syntactic Extension with Macros
• 22.3 A Properly Tail-Recursive Interpreter
• 22.4 Throw, Catch, and Call/cc
• 22.5 An interpreter Supporting Call/cc
• 22.6 History and References
• 22.7 Exercises
• 22.8 Answers
• 23 Compiling Lisp
• 23.1 A Properly Tail-Recursive Lisp Compiler
• 23.2 Introducing Call/cc
• 23.3 The Abstract Machine
• 23.4 A Peephole Optimizer
• 23.5 Languages with Different Lexical Conventions
• 23.6 History and References
• 23.7 Exercises
• 23.8 Answers
• 24 ANSI Common Lisp
• 24.1 Packages
• The Seven Name Spaces
• 24.2 Conditions and Error Handling
• Signaling Errors
• Handling Errors
• 24.3 Pretty Printing
• 24.4 Series
• 24.5 The Loop Macro
• Anatomy of a Loop
• Iteration Control (26.6)
• End-Test Control (26.7)
• Value Accumulation (26.8)
• Variable Initialization (26.9)
• Conditional Execution (26.10)
• Unconditional Execution (26.11)
• Miscellaneous Features (26.12)
• 24.6 Sequence Functions
• Once-only: A Lesson in Macrology
• Avoid Overusing Macros
• MAP-INTO
• REDUCE with :key
• 24.7 Exercises
• 24.8 Answers
• 25 Troubleshooting
• 25.1 Nothing Happens
• 25.2 Change to Variable Has No Effect
• 25.3 Change to Function Has No Effect
• 25.4 Values Change "by Themselves"
• 25.5 Built-In Functions Don't Find Elements
• 25.6 Multiple Values Are Lost
• 25.7 Declarations Are Ignored
• 25.8 My Lisp Does the Wrong Thing
• 25.9 How to Find the Function You Want
• 25.10 Syntax of LOOP
• 25.11 Syntax of COND
• 25.12 Syntax of CASE
• 25.13 Syntax of LET and LET*
• 25.14 Problems with Macros
• 25.15 A Style Guide to Lisp
• When to Define a Function
• When to Define a Special Variable
• When to Bind a Lexical Variable
• How to Choose a Name
• Deciding on the Order of Parameters
• 25.16 Dealing with Files, Packages, and Systems
• 25.17 Portability Problems
• 25.18 Exercises
• 25.19 Answers
• Appendix
• Bibliography
• Index