The Art of Prolog, Second Edition: Advanced Programming Techniques (Logic Programming)

Front matter......Page 2
Table of Contents......Page 6
Figures......Page 12
Programs......Page 16
Series Foreword......Page 24
Foreword......Page 26
Preface......Page 30
Preface to First Edition......Page 34
Introduction......Page 40
I Logic Programs......Page 48
1.1 Facts......Page 50
1.2 Queries......Page 51
1.3 The Logical Variable, Substitutions, and Instances......Page 52
1.4 Existential Queries......Page 53
1.5 Universal Facts......Page 54
1.6 Conjunctive Queries and Shared Variables......Page 55
1.7 Rules......Page 57
1.8 A Simple Abstract Interpreter......Page 61
1.9 The Meaning of a Logic Program......Page 64
1.10 Summary......Page 66
2.1 Simple Databases......Page 68
2.2 Structured Data and Data Abstraction......Page 74
2.3 Recursive Rules......Page 78
2.4 Logic Programs and the Relational Database Model......Page 81
2.5 Background......Page 83
3.1 Arithmetic......Page 84
3.2 Lists......Page 95
3.3 Composing Recursive Programs......Page 104
3.4 Binary Trees......Page 111
3.5 Manipulating Symbolic Expressions......Page 117
3.6 Background......Page 123
4.1 Unification......Page 126
4.2 An Abstract Interpreter for Logic Programs......Page 130
4.3 Background......Page 137
5.1 Semantics......Page 140
5.2 Program Correctness......Page 144
5.3 Complexity......Page 147
5.4 Search Trees......Page 149
5.5 Negation in Logic Programming......Page 152
5.6 Background......Page 154
II The Prolog Language......Page 156
6.1 The Execution Model of Prolog......Page 158
6.2 Comparison to Conventional Programming Languages......Page 163
6.3 Background......Page 166
7.1 Rule Order......Page 168
7.2 Termination......Page 170
7.3 Goal Order......Page 172
7.4 Redundant Solutions......Page 175
7.5 Recursive Programming in Pure Prolog......Page 178
7.6 Background......Page 186
8.1 System Predicates for Arithmetic......Page 188
8.2 Arithmetic Logic Programs Revisited......Page 191
8.3 Transforming Recursion into Iteration......Page 193
8.4 Background......Page 201
9.1 Type Predicates......Page 202
9.2 Accessing Compound Terms......Page 206
9.3 Background......Page 213
10 Meta-Logical Predicates......Page 214
10.1 Meta-Logical Type Predicates......Page 215
10.2 Comparing Nonground Terms......Page 219
10.3 Variables as Objects......Page 221
10.4 The Meta-Variable Facility......Page 224
10.5 Background......Page 225
11.1 Green Cuts: Expressing Determinism......Page 228
11.2 Tail Recursion Optimization......Page 234
11.3 Negation......Page 237
11.4 Red Cuts: Omitting Explicit Conditions......Page 241
11.5 Default Rules......Page 245
11.6 Cuts for Efficiency......Page 247
11.7 Background......Page 251
12.1 Input/Output......Page 254
12.2 Program Access and Manipulation......Page 258
12.3 Memo-Functions......Page 260
12.4 Interactive Programs......Page 262
12.5 Failure-Driven Loops......Page 268
12.6 Background......Page 270
13.1 Programming Style and Layout......Page 272
13.2 Reflections on Program Development......Page 274
13.3 Systematizing Program Construction......Page 277
13.4 Background......Page 283
III Advanced Prolog Programming Techniques......Page 286
14.1 Generate-and-Test......Page 288
14.2 Don't-Care and Don't-Know Nondeterminism......Page 302
14.3 Artificial Intelligence Classics: ANALOGY, ELIZA, and McSAM......Page 309
14.4 Background......Page 319
15.1 Difference-Lists......Page 322
15.2 Difference-Structures......Page 330
15.3 Dictionaries......Page 332
15.4 Queues......Page 336
15.5 Background......Page 339
16.1 All-Solutions Predicates......Page 340
16.2 Applications of Set Predicates......Page 344
16.3 Other Second-Order Predicates......Page 353
16.4 Background......Page 356
17.1 Interpreters for Finite State Machines......Page 358
17.2 Meta-Interpreters......Page 362
17.3 Enhanced Meta-Interpreters for Debugging......Page 370
17.4 An Explanation Shell for Rule-Based Systems......Page 380
17.5 Background......Page 393
18.1 Unfold/Fold Transformations......Page 396
18.2 Partial Reduction......Page 399
18.3 Code Walking......Page 405
18.4 Background......Page 412
19.1 Definite Clause Grammars......Page 414
19.2 A Grammar Interpreter......Page 419
19.3 Application to Natural Language Understanding......Page 421
19.4 Background......Page 427
20.1 Searching State-Space Graphs......Page 428
20.2 Searching Game Trees......Page 440
20.3 Background......Page 446
IV Applications......Page 448
21.1 Mastermind......Page 450
21.2 Nim......Page 454
21.3 Kalah......Page 459
21.4 Background......Page 462
22.1 Developing the System......Page 468
22.2 Background......Page 477
23.1 An Overview of Equation Solving......Page 478
23.2 Factorization......Page 487
23.3 Isolation......Page 488
23.4 Polynomial......Page 491
23.5 Homogenization......Page 493
23.6 Background......Page 496
24.1 Overview of the Compiler......Page 498
24.2 The Parser......Page 505
24.3 The Code Generator......Page 509
24.4 The Assembler......Page 514
24.5 Background......Page 517
A Operators......Page 518
References......Page 522
Index......Page 536