This text is appropriate for a senior or first-year graduate course on logic
programming. It concentrates on the formal semantics of logic programs, automatic theorem-
proving techniques, and efficient implementation of logic languages. It is also an
excellent reference for the computer professional wishing to do self-study on the
fundamentals of logic programming. We have included numerous examples to
illustrate all the major concepts and results. No other text deals with implementation
in as much detail. Other discussions of implementation techniques do not explain
and develop the relationship between interpreter (or compiler) behavior and
resolution theorem proving. We stress that connection throughout.
Author(s): David Maier, David S. Warren
Publisher: AW
Year: 1988
Language: English
Pages: 559
Cover
Title Page
Copyright Page
Dedication Page
Preface
Introduction
Table of Contents
Part I Prolog and Propositional Logic
Chapter 1 Computing with Propositional Logic
1.1. Representing Knowledge in Proplog
1.1.1. Computer Science Requirements Example
1.1.2. Fabric Example
1.2. Evaluating Proplog Programs
1.2.1. Bottom-up Evaluation
1.2.2. A Simple Bottom-up Interpreter
1.2.3. Top-down Evaluation
1.2.4. A Simple Top-down Interpreter
1.3. Proplog as a Declarative Component in a Procedural System
1.3.1. Traffic Light Example
1.3.2. Fabric Identification Program
1.4. Exercises
1.5. Comments and Bibliography
Chapter 2 Propositional Logic
2.1. Propositional Logic for Proplog
2.1.1. What Is a Logic?
2.1.2. Formal Syntax of Proplog
2.1.2.1. Parsing Proplog Programs
2.1.3. Semantics for Proplog
2.1.4. Deduction in Proplog
2.2. Full Propositional Logic
2.2.1. Syntax of Propositional Logic
2.2.2. Semantics for Propositional Logic
2.3. Deduction in Propositional Logic
2.3.1. Resolution in Propositional Logic
2.3.2. Limiting Choice in Resolution
2.4. Horn Clauses
2.4.1. If
2.4.2. Horn Clause Syntax
2.4.3. Resolution with Horn Clauses
2.4.4. Search Strategies
2.5. Negation and the Closed World Assumption
2.6. Exercises
2.7. Comments and Bibliography
Chapter 3 Improving the Proplog Interpreter
3.1. Indexing Clauses
3.2. Lazy Concatenation
3.3. Exercises
3.4. Comments and Bibliography
Part II Datalog and Predicate Logic
Chapter 4 Computing with Predicate Logic
4.1. Why Proplog Is Too Weak
4.2. Pasta or Popovers
4.3. A Simple Datalog Interpreter
4.4. Separating Noodles from Muffins
4.5. Answers
4.6. An Example of Recursion
4.7. Informal Semantics for Datalog
4.8. Procedural Extensions to Datalog
4.8.1. Negation-as-Failure
4.8.2. Numbers, Comparisons, and Arithmetic
4.9. Datalog and Databases
4.10. Exercises
4.11. Comments and Bibliography
Chapter 5 Predicate Logic
5.1. Predicate Logic for Datalog
5.1.1. Formal Syntax of Datalog
5.1.2. Semantics for Datalog
5.2. Full Predicate Logic
5.2.1. Syntax of Predicate Logic
5.2.2. Semantics for Predicate Logic
5.3. Deduction in Predicate Logic
5.3.1. Special Forms
5.3.2. If
5.4. Herbrand Interpretations
5.4.1. Herbrand's Theorem
5.5. Resolution in Predicate Logic
5.5.1. Correctness of Resolution
5.5.2. Completeness of Resolution
5.6. Horn Clauses
5.7. Exercises
5.8. Comments and Bibliography
Chapter 6 Improving the Datalog Interpreter
6.1. Representations
6.2. Naive Datalog Interpreter
6.3. Delayed Copying and Application
6.4. Delayed Composition of Substitutions
6.5. Avoiding Copies Altogether
6.5.1. Applying Substitutions in the Matching Routine
6.5.2. Structure Sharing for Code
6.6. Simplifying Local Substitutions
6.7. Binding Arrays
6.7.1. Looking Back
6.8. Implementing Evaluable Predicates
6.9. Exercises
6.10. Comments and Bibliography
Part III Prolog and Functional Logic
Chapter 7 Computing with Functional Logic
7.1. Evaluating Arithmetic Expressions Using Datalog
7.2. Adding Structures to Datalog
7.3. A Simple Prolog Interpreter
7.4. Evaluating Expression Trees
7.5. Informal Semantics for Prolog
7.6. Lists
7.6.1. List Syntax
7.6.2. Difference Lists
7.6.3. Transitive Closure with Cycles
7.6.4. An Extended Example: Poker
7.7. Exercises
7.8. Comments and Bibliography
Chapter 8 Prolog Evaluable Predicates
8.1. Prolog Pragmatics
8.1.1. Documentation Conventions
8.2. Input/Output
8.3. Call
8.4. Controlling Backtracking: The Cut
8.5. Arithmetic
8.6. Control Convenience
8.7. Metaprogramming Features
8.7.1. Term Testing and Comparison
8.7.2. Structure Manipulation
8.8. Lists of All Answers
8.9. Modifying the Program
8.10. Exercises
8.11. Comments and Bibliography
Chapter 9 Functional Logic
9.1. Functional Logic for Prolog
9.1.1. Formal Syntax of Prolog
9.1.2. Semantics for Prolog
9.2. Full Functional Logic
9.2.1. Syntax of Functional Logic
9.2.2. Semantics for Functional Logic
9.3. Deduction in Functional Logic
9.3.1. Special Forms and Skolem Functions
9.4. Herbrand Interpretations
9.4.1. Herbrand's Theorem
9.5. Resolution in Functional Logic
9.6. Answers
9.7. Model Elimination
9.8. Horn Clauses
9.9. Exercises
9.10. Comments and Bibliography
Chapter 10 Improving the Prolog Interpreter
10.1. Representations
10.2. Naive Prolog Interpreter
10.3. Delayed Copying and Application
10.4. Delayed Composition of Substitutions
10.5. Avoiding Copies Altogether
10.5.1. Applying Substitutions in the Matching Routine
10.5.2. Structure Sharing for Code
10.5.2.1. Structure Sharing for Terms
10.5.2.2. Copy on Use for Terms
10.5.2.3. Comparison of Methods
10.6. Binding Arrays
10.7. Implementing Model Elimination with Prolog Techniques
10.8. Exercises
10.9. Comments and Bibliography
Chapter 11 Interpreter Optimizations and Prolog Compilation
11.1. Activation Records
11.2. Including Variable Bindings in the Stack Frame
11.3. Backtrack Points
11.4. Implementing Evaluable Predicates
11.5. Reclaiming Deterministic Frames
11.5.1. Deterministic Frames with Structure Sharing
11.6. Indexing
11.7. Last Call and Tail Recursion Optimizations
11.8. Compiling Prolog
11.8.1. The Warren Prolog Engine
11.8.2. WPE Instructions
11.8.3. Allocating Binding Frames
11.8.4. A Complete Datalog Example
11.8.5. Temporary Variables
11.8.6. Nondeterminism
11.8.7. Terms in Clauses
11.8.7.1. Terms in the Body
11.8.7.2. Terms in the Head
11.8.8. Final Literal Optimization
11.8.9. Trimming Environments
11.9. Exercises
11.10. Comments and Bibliography
Chapter 12 An Example
12.1. Universal Scheme Query Languages
12.2. The PIQUE Query Language
12.3. Implementing PIQUE in Prolog
12.3.1. Representing the Database Scheme and Data
12.3.2. PIQUE Scanner
12.3.3. PIQUE Parser
12.3.4. PIQUE Translator
12.3.5. Optimizations of Simple Queries
12.3.6. Compound Queries
12.3.7. Programming in Prolog
12.4. Exercises
Appendix: Possible Course Project
Index
