AI algorithms, data structures, and idioms in Prolog, Lisp, and Java

Cover......Page 1
Title Page......Page 5
Contents......Page 7
Preface......Page 13
Part I: Language Idioms and the Master Programmer......Page 19
1.1 Introduction......Page 21
1.2 Selected Examples of AI Language Idioms......Page 24
1.3 A Brief History of Three Programming Paradigms......Page 29
1.4 A Summary of Our Task......Page 33
Part II: Programming in Prolog......Page 35
2.1 Introduction: Logic-Based Representation......Page 37
2.2 Prolog Syntax......Page 38
2.3 Creating, Changing, and Tracing a Prolog Computation......Page 42
2.4 Lists and Recursion in Prolog......Page 43
2.5 Structured Representations and Inheritance Search......Page 46
Exercises......Page 50
3.1 Introduction......Page 51
3.2 Using cut to Control Search in Prolog......Page 54
3.3 Abstract Data Types (ADTs) in Prolog......Page 56
Exercises......Page 60
4.1 Production System Search in Prolog......Page 61
4.2 A Production System Solution to the FWGC Problem......Page 64
4.3 Designing Alternative Search Strategies......Page 70
Exercises......Page 76
5.1 Meta-Interpreters, Types, and Unification......Page 77
5.2 Types in Prolog......Page 79
5.3 Unification, Engine of Variable Binding and Evaluation......Page 82
Exercises......Page 86
6.1 An Introduction to Meta-Interpreters: Prolog in Prolog......Page 87
6.2 A Shell for a Rule-Based Expert System......Page 91
6.3 A Prolog Planner......Page 100
Exercises......Page 103
7.1 Machine Learning: Version Space Search......Page 105
7.2 Explanation Based Learning in Prolog......Page 118
Exercises......Page 124
8.1 Natural Language Understanding in Prolog......Page 125
8.2 Prolog-Based Semantic Representations......Page 126
8.3 A Context-Free Parser in Prolog......Page 129
8.4 Probabilistic Parsers in Prolog......Page 132
8.5 A Context-Sensitive Parser in Prolog......Page 137
8.6 A Recursive Descent Semantic Net Parser......Page 138
Exercises......Page 141
9.1 Dynamic Programming Revisited......Page 143
9.2 The Earley Parser......Page 144
9.3 The Earley Parser in Prolog......Page 152
Exercises......Page 157
10.1 Prolog: Towards a Declarative Semantics......Page 159
10.2 Prolog and Automated Reasoning......Page 162
10.3 Prolog Idioms and Extensions......Page 163
Part III: Programming in Lisp......Page 167
11.1 Introduction to Symbol Expressions......Page 169
11.2 Control of Lisp Evaluation......Page 172
11.3 Programming in Lisp: Creating New Functions......Page 174
11.4 Program Control in Lisp: Conditionals and Predicates......Page 175
Exercises......Page 178
12.1 Functions, Lists, and Symbolic Computing......Page 179
12.2 Lists as Recursive Structures......Page 181
12.3 Nested Lists, Structure, and car/cdr Recursion......Page 184
Exercises......Page 186
13.1 Variables and Datatypes......Page 189
13.2 Search: The Farmer, Wolf, Goat, and Cabbage Problem......Page 195
Exercises......Page 201
14.1 Higher-Order Functions and Abstraction......Page 203
14.2 Search Strategies in Lisp......Page 207
Exercises......Page 211
15.1 Pattern Matching: Introduction......Page 213
15.2 Interpreters and Embedded Languages......Page 221
Exercises......Page 223
16.1 A Simple Logic Programming Language......Page 225
16.2 Streams and Stream Processing......Page 227
16.3 A Stream-Based Logic Programming Interpreter......Page 229
Exercises......Page 235
17.1 Streams and Delayed Evaluation......Page 237
17.2 An Expert System Shell in Lisp......Page 241
Exercises......Page 250
18.1 Semantic Networks and Inheritance in Lisp......Page 251
18.2 Object-Oriented Programming Using CLOS......Page 255
18.3 CLOS Example: A Thermostat Simulation......Page 262
Exercises......Page 268
19.1 Learning: The ID3 Algorithm......Page 269
19.2 Implementing ID3......Page 277
Exercises......Page 284
20 Lisp: Final Thoughts......Page 285
Part IV: AI Programming in Java......Page 287
21.1 Introduction to O-O Representation and Design......Page 291
21.2 Object-Orientation......Page 292
21.3 Classes and Encapsulation......Page 293
21.4 Polymorphism......Page 294
21.5 Inheritance......Page 295
21.6 Interfaces......Page 298
21.7 Scoping and Access......Page 300
21.8 The Java Standard Library......Page 301
21.9 Conclusions: Designing in Java......Page 302
Exercises......Page 303
22.1 Abstraction and Generality in Java......Page 305
22.2 Search Algorithms......Page 306
21.3 Abstracting Problem States......Page 310
22.4 Traversing the Problem Space......Page 313
22.5 Putting the Framework to Use......Page 318
Exercises......Page 321
23.1 Introduction to the Task......Page 323
23.2 A Review of the Predicate Calculus and Unification......Page 325
23.3 Building a Predicate Calculus Problem Solver in Java......Page 328
23.4 Design Discussion......Page 338
23.5 Conclusion: Mapping Logic into Objects......Page 340
Exercises......Page 341
24.2 Reasoning in Logic as Searching an And/Or Graph......Page 343
24.3 The Design of a Logic-Based Reasoning System......Page 347
24.4 Implementing Complex Logic Expressions......Page 348
24.5 Logic-Based Reasoning as And/Or Graph Search......Page 353
24.6 Testing the Reasoning System......Page 364
24.7 Design Discussion......Page 366
Exercises......Page 368
25.1 Introduction: Expert Systems......Page 369
25.2 Certainty Factors and the Unification Problem Solver......Page 370
25.3 Adding User Interactions......Page 376
25.4 Design Discussion......Page 378
Exercises......Page 379
26.2 JESS......Page 381
26.3 Other Expert System Shells......Page 382
26.4 Using Open Source Tools......Page 383
27.2 Representing Knowledge as Decision Trees......Page 385
27.3 A Decision Tree Induction Program......Page 388
27.4 ID3: An Information Theoretic Tree Induction Algorithm......Page 403
Exercises......Page 406
28.2 The Genetic Algorithm: A First Pass......Page 407
28.3 A GA Implementation in Java......Page 411
Exercises......Page 419
29.1 Java Machine Learning Software......Page 421
30.1 Chart Parsing: An Introduction......Page 423
30.2 The Earley Parser: Components......Page 424
30.3 The Earley Parser: Java Code......Page 426
30.4 The Completed Parser......Page 432
30.5 Generating Parse Trees from Charts and Grammar Rules (Advanced Section)......Page 437
Exercises......Page 440
31.2 LingPipe from the University of Pennsylvania......Page 441
31.3 The Stanford Natural Language Processing Group......Page 443
31.4 Sun’s Speech API......Page 444
Part V: Conclusion: Model Building and the Master Programmer......Page 447
32.1 Language Paradigm-Based Abstractions and Idioms......Page 449
32.2 Programming as a Tool for Exploring Problem Domains......Page 451
32.3 Programming as a Social Activity......Page 453
32.4 Final Thoughts......Page 455
Bibliography......Page 457
Index......Page 461