Paradigms of Artificial Intelligence Programming

Case Studies in Common Lisp

1st Edition - October 1, 1991
Imprint: Morgan Kaufmann
Author: Peter Norvig
Language: English
Paperback ISBN:
9 7 8 - 1 - 5 5 8 6 0 - 1 9 1 - 8
eBook ISBN:
9 7 8 - 0 - 0 8 - 0 5 7 1 1 5 - 7

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 Artificial Intelligence Programming

Purchase options

BLOOM INTO SPRING SAVINGS

Save up to 25% on books and eBooks!

Shop now

Institutional subscription on ScienceDirect

Request a sales quote

Resources

Textbook support for instructors(opens in new tab/window)

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

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

Life Sciences

Physical Sciences & Engineering

Social Sciences & Humanities

Health