Paradigms of Artificial Intelligence Programming

Paradigms of Artificial Intelligence Programming

by Peter Norvig
Released June 2014
Publisher(s): Morgan Kaufmann
ISBN: 9780080571157

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book 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.

Table of contents

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

Product information

  • Title: Paradigms of Artificial Intelligence Programming
  • Author(s): Peter Norvig
  • Release date: June 2014
  • Publisher(s): Morgan Kaufmann
  • ISBN: 9780080571157