Case Studies in Common Lisp To order this title, and for more information, click here
By Peter Norvig
Description
Paradigms of AI Programming is the first text to teach advanced Common Lisp techniques in the context of building major AI
systems. By reconstructing authentic, complex AI programs using state-of-the-art Common Lisp, the book teaches students and professionals
how to build and debug robust practical programs, while demonstrating superior programming style and important AI concepts. The author
strongly emphasizes the practical performance issues involved in writing real working programs of significant size. Chapters on troubleshooting
and efficiency are included, along with a discussion of the fundamentals of object-oriented programming and a description of the main
CLOS functions. This volume is an excellent text for a course on AI programming, a useful supplement for general AI courses and an indispensable
reference for the professional programmer.
Contents
Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp by Peter Norvig
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
Books and book related electronic products are priced in US dollars (USD), euro (EUR), and Great Britain Pounds (GBP). USD prices apply to the Americas and Asia Pacific. EUR prices apply in Europe and the Middle East. GBP prices apply to the UK and all other countries.
Home | Elsevier Sites | Privacy Policy | Terms and Conditions | Feedback | Site Map | A Reed Elsevier Company