Computing With Logic: Logic Programming With Prolog

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