Paradigms of Artificial Intelligence Programming
Case Studies in Common Lisp
- 1st Edition - October 1, 1991
- Latest edition
- Author: Peter Norvig
- Language: English
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 progra… Read more
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.
Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp
by Peter Norvig
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
- 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
- Edition: 1
- Latest edition
- Published: October 1, 1991
- Language: English
Read Paradigms of Artificial Intelligence Programming on ScienceDirect