Norvig Paradigms of Artificial Intelligence Programming

Case Studies in Common Lisp
1. Auflage 2014
ISBN: 978-0-08-057115-7
Verlag: Elsevier Science & Techn.
Format: EPUB
Kopierschutz: 6 - ePub Watermark

E-Book, Englisch, 946 Seiten

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.

Autoren/Hrsg.

Norvig, Peter

Inhaltsverzeichnis

1;Front Cover;1
2;Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp;4
3;Copyright Page;5
4;Table of Contents;18
5;Preface;8
6;PART I: INTRODUCTION TO COMMON LISP;30
6.1;CHAPTER 1. Introduction to Lisp;32
6.1.1;1.1 Symbolic Computation;35
6.1.2;1.2 Variables;37
6.1.3;1.3 Special Forms;38
6.1.4;1.4 Lists;39
6.1.5;1.5 Defining New Functions;41
6.1.6;1.6 Using Functions;43
6.1.7;1.7 Higher-Order Functions;47
6.1.8;1.8 Other Data Types;51
6.1.9;1.9 Summary: The Lisp Evaluation Rule;51
6.1.10;1.10 What Makes Lisp Different?;54
6.1.11;1.11 Exercises;60
6.1.12;1.12 Answers;61
6.2;CHAPTER 2. A Simple Lisp Program;63
6.2.1;2.1 A Grammar for a Subset of English;64
6.2.2;1.1 A Straightforward Solution;64
6.2.3;2.3 A Rule-Based Solution;68
6.2.4;2.4 Two Paths to Follow;71
6.2.5;2.5 Changing the Grammar without Changingthe Program;72
6.2.6;2.6 Using the Same Data for Several Programs;72
6.2.7;2.7 Exercises;75
6.2.8;2.8 Answers;75
6.3;CHAPTER 3. Overview of Lisp;77
6.3.1;3.1 A Guide to Lisp Style;78
6.3.2;3.2 Special Forms;79
6.3.3;3·3 Functions on Lists;98
6.3.4;3.4 Equality and Internal Representation;99
6.3.5;3.5 Functions on Sequences;101
6.3.6;3.6 Functions for Maintaining Tables;102
6.3.7;3.7 Functions on Trees;105
6.3.8;3.8 Functions on Numbers;107
6.3.9;3.9 Functions on Sets;107
6.3.10;3.10 Destructive Functions;108
6.3.11;3.11 Overview of Data Types;110
6.3.12;3.12 Input/Output;112
6.3.13;3.12 Input/Output;112
6.3.14;3.13 Debugging Tools;114
6.3.15;3.14 Antibugging Tools;116
6.3.16;3.15 Evaluation;120
6.3.17;3.16 Closures;121
6.3.18;3.17 Special Variables;122
6.3.19;3.18 Multiple Values;124
6.3.20;3.19 More about Parameters;126
6.3.21;3.20 The Rest of Lisp;132
6.3.22;3.21 Exercises;132
6.3.23;3.22 Answers;132
7;PART II: EARLY AI PROGRAMS;136
7.1;CHAPTER 4. GPS: The GeneraProblem Solver;138
7.1.1;4.1 Stage 1: Description;140
7.1.2;4.2 Stage 2: Specification;141
7.1.3;4.3 Stage 3: Implementation;142
7.1.4;4.4 Stage 4: Test;145
7.1.5;4.5 Stage 5: Analysis, or ''We Lied about the C;148
7.1.6;4.6 The Running Around the Block Problem;148
7.1.7;4.7 The Clobbered Sibling Goal Problem;148
7.1.8;4 · 8 The Leaping before You Look Problem;150
7.1.9;4.9 The Recursive Subgoal Problem;150
7.1.10;4.10 The Lack of Intermediate InformationProblem;152
7.1.11;4.11 GPS Version 2: A More GeneralProblem Solver;154
7.1.12;4.12 The New Domain Problem: Monkeyand Bananas;161
7.1.13;4.13 The Maze Searching Domain;163
7.1.14;4·14 The Blocks World Domain;165
7.1.15;4.15 Stage 5 Repeated: Analysis of Version 2;171
7.1.16;4.16 The Not Looking after You Don^tLeap Problem;172
7.1.17;4.17 The Lack of Descriptive Power Problem;173
7.1.18;4.18 The Perfect Information Problem;174
7.1.19;4.19 The Interacting Goals Problem;174
7.1.20;4.20 The End of GPS;175
7.1.21;4.21 History and References;176
7.1.22;4.22 Exercises;177
7.1.23;4.23 Answers;178
7.2;CHAPTER 5. ELIZA: Dialog with a Machine;180
7.2.1;5.1 Describing and Specifying ELIZA;183
7.2.2;5.3 Segment Pattern Matching;188
7.2.3;5.4 The ELIZA Program: A Rule-BasedTranslator;192
7.2.4;5.5 History and References;196
7.2.5;5.6 Exercises;196
7.2.6;5.7 Answers;199
7.3;CHAPTER 6. Building Software Tools;204
7.3.1;6.1 An Interactive Interpreter Tool;204
7.3.2;6.2 A Pattern-Matching Tool;207
7.3.3;6.3 A Rule-Based Translator Tool;217
7.3.4;6.4 A Set of Searching Tools;218
7.3.5;6.5 GPS as Search;240
7.3.6;6.6 History and References;242
7.3.7;6.7 Exercises;243
7.3.8;6.8 Answers;244
7.4;CHAPTER 7. STUDENT: Solving AlgebraWord Problems;248
7.4.1;7.1 Translating English into Equations;249
7.4.2;7.2 Solving Algebraic Equations;254
7.4.3;7.3 Examples;260
7.4.4;7.4 History and References;263
7.4.5;7.5 Exercises;263
7.4.6;7.6 Answers;265
7.5;CHAPTER 8. Symbolic Mathematics:A Simplification Program;267
7.5.1;8.1 Converting Infix to Prefix Notation;269
7.5.2;8.2 Simplification Rules;271
7.5.3;8.3 Associativity and Commutativity;275
7.5.4;8.4 Logs, Trig, and Differentiation;277
7.5.5;8.6 Integration;281
7.5.6;8.7 History and References;288
7.5.7;8.8 Exercises;289
8;PART III: TOOLS AND TECHNIQUESO O;292
8.1;CHAPTER 9. Efficiency issues;294
8.1.1;9.1 Caching Results of Previous Computations:Memoization;298
8.1.2;9.2 Compiling One Language into Another;304
8.1.3;9.3 Delaying Computation;309
8.1.4;9.4 Indexing Data;317
8.1.5;9.5 Instrumentation: Deciding Whatto Optimize;317
8.1.6;9.6 A Case Study in Efficiency: TheSIMPLIFY Program;324
8.1.7;9.7 History and References;336
8.1.8;9.8 Exercises;337
8.1.9;9.9 Answers;339
8.2;CHAPTER 10. Low-Level Efficiency Issues;344
8.2.1;10.1 Use Declarations;345
8.2.2;10.2 Avoid Generic Functions;351
8.2.3;10.3 Avoid Complex Argument Lists;351
8.2.4;10.4 Avoid Unnecessary Consing;357
8.2.5;10.5 Use the Right Data Structures;368
8.2.6;10.6 Exercises;375
8.2.7;10.7 Answers;376
8.3;CHAPTER 11. Logic Programming;377
8.3.1;11.1 Idea 1: A Uniform Data Base;379
8.3.2;11.2 Idea 2: Unification of Logic Variables;381
8.3.3;11.3 Idea 3: Automatic Backtracking;396
8.3.4;11.4 The Zebra Puzzle;402
8.3.5;11.5 The Synergy of Backtracking andUnification;405
8.3.6;11.6 Destructive Unification;406
8.3.7;11.7 Prolog in Prolog;409
8.3.8;11.8 Prolog Compared to LispMany;409
8.3.9;11.9 History and References;411
8.3.10;11.10 Exercises;412
8.3.11;11.11 Answers;415
8.4;CHAPTER 12. Compiling LogicPrograms;417
8.4.1;12.1 A Prolog Compiler;419
8.4.2;12.2 Fixing the Errors in the Compiler;426
8.4.3;12.3 Improving the Compiler;428
8.4.4;12.4 Improving the Compilation of Unification;430
8.4.5;12.5 Further Improvements to Unification;436
8.4.6;12.6 The User Interface to the Compiler;437
8.4.7;12.7 Benchmarking the Compiler;440
8.4.8;12.8 Adding More Primitives;442
8.4.9;12.9 The Cut;449
8.4.10;12.10 '^ear Prolog;453
8.4.11;12.11 History and References;455
8.4.12;12.12 Exercises;455
8.4.13;12.13 Answers;458
8.5;CHAPTER 13. Object-Oriented Programming;463
8.5.1;13,1 Object-Oriented Programming;464
8.5.2;13.2 Objects;465
8.5.3;13.3 Generic Functions;468
8.5.4;13.4 Classes;468
8.5.5;13.5 Delegation;470
8.5.6;13.6 Inheritance;472
8.5.7;13.7 GLOS: The Common Lisp Object System;474
8.5.8;13.8 A CLOS Example: Searching Tools;477
8.5.9;13.9 Is CLOS Object-Oriented?;483
8.5.10;13.10 Advantages of Object-OrientedProgramming;484
8.5.11;13.11 History and References;485
8.5.12;13.12 Exercises;488
8.6;CHAPTER 14. Knowledge Representationand Reasoning;489
8.6.1;14.1 A Taxonomy of Representation Languages;491
8.6.2;14.2 Predicate Calculus and its Problems;492
8.6.3;14.3 A Logical Language: Prolog;494
8.6.4;14.4 Problems with Prolog's Expressiveness;494
8.6.5;14.5 Problems with Predicate Calculus'sExpressiveness;497
8.6.6;14.6 Problems with Completeness;498
8.6.7;14.7 Problems with Efficiency: Indexing;501
8.6.8;14.8 A Solution to the Indexing Problem;501
8.6.9;14.9 A Solution to the Completeness Problem;511
8.6.10;14.10 Solutions to the Expressiveness Problems;514
8.6.11;14.11 History and References;532
8.6.12;14.12 Exercises;533
8.6.13;14.13 Answers;535
9;PART IV: ADVANCED AI PROGRAMS;536
9.1;CHAPTER 15. Symbolic Mathematicswith Canonical Forms;538
9.1.1;15.1 A Canonical Form for Polynomials;539
9.1.2;15.2 Differentiating Polynomials;547
9.1.3;15.3 Converting between Infix and Prefix;548
9.1.4;15.4 Benchmarking the Polynomial Simplifier;551
9.1.5;15.5 A Canonical Form for Rational Expressions;555
9.1.6;15.6 Extending Rational Expressions;556
9.1.7;15.7 History and References;557
9.1.8;15.8 Exercises;557
9.1.9;15.9 Answers;558
9.2;CHAPTER 16. Expert Systems;559
9.2.1;16.1 Dealing with Uncertainty;561
9.2.2;16.2 Caching Derived Facts;565
9.2.3;16.3 Asking Questions;567
9.2.4;16.4 Contexts Instead of Variables;570
9.2.5;16.5 Backward-Chaining Revisited;572
9.2.6;16.6 Interacting with the Expert;577
9.2.7;16.7 Interacting with the Client;579
9.2.8;16.8 MYCIN, A Medical Expert System;581
9.2.9;16.9 Alternatives to Certainty Factors;586
9.2.10;16.10 History and References;587
9.2.11;16.11 Exercises;588
9.2.12;16.12 Answers;591
9.3;CHAPTER 17. Line-Diagram Labeling by ConstraintSatisfaction;593
9.3.1;17.1 The Line-Labeling Problem;594
9.3.2;17.2 Combining Constraints and Searching;599
9.3.3;17.3 Labeling Diagrams;606
9.3.4;17.4 Checking Diagrams for Errors;615
9.3.5;17.5 History and References;623
9.3.6;17.6 Exercises;624
9.4;CHAPTER 18. Search and theGame of Othello;625
9.4.1;18.1 The Rules of the Game;626
9.4.2;18.2 Representation Choices;628
9.4.3;18.3 Evaluating Positions;636
9.4.4;18.4 Searching Ahead: Minimax;639
9.4.5;18.5 Smarter Searching: Alpha-Beta Search;644
9.4.6;18.6 An Analysis of Some Games;646
9.4.7;18.7 The Tournament Version of Othello;651
9.4.8;18.8 Playing a Series of Games;655
9.4.9;18.9 More Efficient Searching;659
9.4.10;18.10 It Pays to Precycle;662
9.4.11;18.11 Killer Moves;663
9.4.12;18.12 Championship Programs: lago and Bill;666
9.4.13;18.13 Other Techniques;675
9.4.14;18.14 History and References;680
9.4.15;18-15 Exercises;681
9.4.16;18.16 Answers;682
9.5;CHAPTER 19. Introduction toNatural Language;684
9.5.1;19-1 Parsing with a Phrase-Structure Grammar;685
9.5.2;19.2 Extending the Grammar andRecognizing Ambiguity;689
9.5.3;19.3 More Efficient Parsing;691
9.5.4;19.4 The Unknown-Word Problem;693
9.5.5;19.5 Parsing into a Semantic Representation;694
9.5.6;19.6 Parsing with Preferences;699
9.5.7;19.7 The Problem with Context-FreePhrase-Structure Rules;707
9.5.8;19.8 History and References;708
9.5.9;19.9 Exercises;708
9.5.10;19.10 Answers;709
9.6;CHAPTER 20. Unification Grammars;713
9.6.1;20.1 Parsing as Deduction;714
9.6.2;20.2 Definite Clause Grammars;718
9.6.3;20.3 A Simple Grammar in DCG Format;721
9.6.4;20.4 A DCG Grammar with Quantifiers;725
9.6.5;20.5 Preserving Quantifier Scope Ambiguity;729
9.6.6;20.6 Long-Distance Dependencies;731
9.6.7;20.7 Augmenting DCG Rules;733
9.6.8;20.8 History and References;740
9.6.9;20.9 Exercises;741
9.6.10;20.10 Answers;742
9.7;CHAPTER 21. A Grammar of English;744
9.7.1;21.1 Noun Phrases;746
9.7.2;21.2 Modifiers;747
9.7.3;21.3 Noun Modifiers;748
9.7.4;21.4 Determiners;750
9.7.5;21.5 Verb Phrases;751
9.7.6;21.6 Adverbs;752
9.7.7;21.7 Clauses;752
9.7.8;21.8 Sentences;754
9.7.9;21.9 XPs;756
9.7.10;21.10 Word Categories;759
9.7.11;21.11 The Lexicon;761
9.7.12;21.12 Supporting the Lexicon;768
9.7.13;21.13 Other Primitives;774
9.7.14;21.15 History and References;777
9.7.15;21.16 Exercises;778
10;PART V: THE REST OF LISP;780
10.1;CHAPTER 22. Scheme: An Uncommon Lisp;782
10.1.1;22.1 A Scheme Interpreter;785
10.1.2;22.2 Syntactic Extension with Macros;791
10.1.3;22.3 A Properly Tail-Recursive Interpreter;795
10.1.4;22.4 Throw, Catch, and Call/cc;797
10.1.5;22.5 An Interpreter Supporting Call/cc;802
10.1.6;22.6 History and References;805
10.1.7;22.7 Exercises;807
10.1.8;22.8 Answers;809
10.2;CHAPTER 23. Compiling Lisp;813
10.2.1;23.1 A Properly Tail-Recursive Lisp Compiler;825
10.2.2;23.2 Introducing Call/cc;839
10.2.3;23.3 The Abstract Machine;839
10.2.4;23.4 A Peephole Optimizer;846
10.2.5;23.5 Languages with Different LexicalConventions;850
10.2.6;23.6 History and References;854
10.2.7;23.7 Exercises;855
10.2.8;23.8 Answers;857
10.3;CHAPTER 24. ANSI Common Lisp;863
10.3.1;24.1 Packages;863
10.3.2;24.2 Conditions and Error Handling;866
10.3.3;24.3 Pretty Printing;868
10.3.4;24.4 Series;868
10.3.5;24.5 The Loop Macro;869
10.3.6;24.6 Sequence Functions;881
10.3.7;24.7 Exercises;892
10.3.8;24.8 Answers;892
10.4;CHAPTER 25. Troubleshooting;895
10.4.1;25.1 Nothing Happens;896
10.4.2;25.2 Change to Variable Has No Effect;897
10.4.3;25.3 Change to Function Has No Effect;898
10.4.4;25.4 Values Change "by Themselves'';902
10.4.5;25.5 Built-in Functions Don't Find Elements;903
10.4.6;25.6 Multiple Values Are Lost;903
10.4.7;25.7 Declarations Are Ignored;904
10.4.8;25.8 My Lisp Does the Wrong Thing;905
10.4.9;25.9 How to Find the Function You Want;906
10.4.10;25.10 Syntax of LOOP;907
10.4.11;25.11 Syntax of COND;907
10.4.12;25.12 Syntax of CASE;908
10.4.13;25.13 Syntax of LET and LET;909
10.4.14;25.14 Problems with Macros;909
10.4.15;25.15 A Style Guide to Lisp;916
10.4.16;25.16 Dealing with Files, Packages, and Systems;919
10.4.17;25.17 Portability Problems;923
10.4.18;25.18 Exercises;924
10.4.19;25.19 Answers;925
11;Appendix: Obtaining the Codein this Book;926
12;Bibliography;930
13;Index;948

Leseproben

Preface
paradigm n 1 an example or pattern; esp an outstandingly clear or typical example. –Longman’s Dictionary of the English Language, 1984 This book is concerned with three related topics: the field of artificial intelligence, or AI; the skill of computer programming; and the programming language Common Lisp. Careful readers of this book can expect to come away with an appreciation of the major questions and techniques of AI, an understanding of some important AI programs, and an ability to read, modify, and create programs using Common Lisp. The examples in this book are designed to be clear examples of good programming style–paradigms of programming. They are also paradigms of AI research–historically significant programs that use widely applicable techniques to solve important problems. Just as a liberal arts education includes a course in “the great books” of a culture, so this book is, at one level, a course in “the great programs” that define the AI culture.1 At another level, this book is a highly technical compendium of the knowledge you will need to progress from being an intermediate Lisp programmer to being an expert. Parts I and II are designed to help the novice get up to speed, but the complete beginner may have a hard time even with this material. Fortunately, there are at least five good texts available for the beginner; see page xiii for my recommendations. All too often, the teaching of computer programming consists of explaining the syntax of the chosen language, showing the student a 10-line program, and then asking the student to write programs. In this book, we take the approach that the best way to learn to write is to read (and conversely, a good way to improve reading skills is to write). After the briefest of introductions to Lisp, we start right off with complex programs and ask the reader to understand and make small modifications to these programs. The premise of this book is that you can only write something useful and interesting when you both understand what makes good writing and have something interesting to say. This holds for writing programs as well as for writing prose. As Kernighan and Plauger put it on the cover of Software Tools in Pascal: Good programming is not learned from generalities, but by seeing how significant programs can be made clean, easy to read, easy to maintain and modify, human-engineered, efficient, and reliable, by the application of common sense and good programming practices. Careful study and imitation of good programs leads to better writing. The proud craftsman is often tempted to display only the finished work, without any indication of the false starts and mistakes that are an unfortunate but unavoidable part of the creative process. Unfortunately, this reluctance to unveil the process is a barrier to learning; a student of mathematics who sees a beautiful 10-line proof in a textbook can marvel at its conciseness but does not learn how to construct such a proof. This book attempts to show the complete programming process, “warts and all.” Each chapter starts with a simple version of a program, one that works on some examples but fails on others. Each chapter shows how these failures can be analyzed to build increasingly sophisticated versions of the basic program. Thus, the reader can not only appreciate the final result but also see how to learn from mistakes and refine an initially incomplete design. Furthermore, the reader who finds a particular chapter is becoming too difficult can skip to the next chapter, having gained some appreciation of the problem area, and without being overwhelmed by the details. This book presents a body of knowledge loosely known as “AI programming techniques,” but it must be recognized that there are no clear-cut boundaries on this body of knowledge. To be sure, no one can be a good AI programmer without first being a good programmer. Thus, this book presents topics (especially in parts III and V) that are not AI per se, but are essential background for any AI practitioner. Why Lisp? Why Common Lisp?
Lisp is one of the oldest programming languages still in widespread use today. There have been many versions of Lisp, each sharing basic features but differing in detail. In this book we use the version called Common Lisp, which is the most widely accepted standard. Lisp has been chosen for three reasons. First, Lisp is the most popular language for AI programming, particularly in the United States. If you’re going to learn a language, it might as well be one with a growing literature, rather than a dead tongue. Second, Lisp makes it easy to capture relevant generalizations in defining new objects. In particular, Lisp makes it easy to define new languages especially targeted to the problem at hand. This is especially handy in AI applications, which often manipulate complex information that is most easily represented in some novel form. Lisp is one of the few languages that allows full flexibility in defining and manipulating programs as well as data. All programming languages, by definition, provide a means of defining programs, but many other languages limit the ways in which a program can be used, or limit the range of programs that can be defined, or require the programmer to explicitly state irrelevant details. Third, Lisp makes it very easy to develop a working program fast. Lisp programs are concise and are uncluttered by low-level detail. Common Lisp offers an unusually large number of useful predefined objects, including over 700 functions. The programming environment (such as debugging tools, incremental compilers, integrated editors, and interfaces to window systems) that surround Lisp systems are usually very good. And the dynamic, interactive nature of Lisp makes it easy to experiment and change a program while it is being developed. It must be mentioned that in Europe and Japan, Prolog has been as popular as Lisp for AI work. Prolog shares most of Lisp’s advantages in terms of flexibility and conciseness. Recently, Lisp has gained popularity worldwide, and Prolog is becoming more well known in the United States. As a result, the average AI worker today is likely to be bilingual. This book presents the key ideas behind Prolog in chapters 11 and 12, and uses these ideas in subsequent chapters, particularly 20 and 21. The dialect of Lisp known as Scheme is also gaining in popularity, but primarily for teaching and experimenting with programming language design and techniques, and not so much for writing large AI programs. Scheme is presented in chapters 22 and 23. Other dialects of Lisp such as Franz Lisp, MacLisp, InterLisp, ZetaLisp, and Standard Lisp are now considered obsolete. The only new dialect of Lisp to be proposed recently is EuLisp, the European Lisp. A few dialects of Lisp live on as embedded extension languages. For example, the Gnu Emacs text editor uses elisp, and the AutoCad computer-aided design package uses AutoLisp, a derivative of Xlisp. In the future, it is likely that Scheme will become a popular extension language, since it is small but powerful and has an officially sanctioned standard definition. There is a myth that Lisp (and Prolog) are “special-purpose” languages, while languages like Pascal and C are “general purpose.” Actually, just the reverse is true. Pascal and C are special-purpose languages for manipulating the registers and memory of a von Neumann-style computer. The majority of their syntax is devoted to arithmetic and Boolean expressions, and while they provide some facilities for forming data structures, they have poor mechanisms for procedural abstraction or control abstraction. In addition, they are designed for the state-oriented style of programming: computing a result by changing the value of variables through assignment statements. Lisp, on the other hand, has no special syntax for arithmetic. Addition and multiplication are no more or less basic than list operations like appending, or string operations like converting to upper case. But Lisp provides all you will need for programming in general: defining data structures, functions, and the means for combining them. The assignment-dominated, state-oriented style of programming is possible in Lisp, but in addition object-oriented, rule-based, and functional styles are all supported within Lisp. This flexibility derives from two key features of Lisp: First, Lisp has a powerful macro facility, which can be used to extend the basic language. When new styles of programming were invented, other languages died out; Lisp simply incorporated the new styles by defining some new macros. The macro facility is possible because Lisp programs are composed of a simple data structure: the list. In the early days, when Lisp was interpreted, most manipulation of programs was done through this data structure. Nowadays, Lisp is more often compiled than interpreted, and programmers rely more on Lisp’s second great flexible feature: the function. Of course, other languages have functions, but Lisp is rare in allowing the creation of new functions while a program is running. Lisp’s flexibility allows it to adapt as programming styles change, but more importantly, Lisp can adapt to your particular programming problem. In other languages you fit your problem to the language; with Lisp you extend the language to fit your problem. Because of its flexibility, Lisp has been succesful as a...