This is one of the few texts that combines three essential theses in the study of logic programming: the logic that gives logic programs their unique character: the practice of programming effectively using the logic; and the efficient implementation of logic programming on computers. The book begins with a gentle introduction to logic programming using a number of simple examples, followed by a concise and self-contained account of the logic behind Prolog programming. This leads to a discussion of methods of writing programs so that the process of deriving anwers from them is as efficient as possible. The techniques are illustrated by practical examples and the final part of the book explains how logic programming can be implented efficiently. It includes source code for a small but Complete Prolog implementation written in Pascal. The implementation is capable of running all the programs presented in the book, and is available via the Internet
Author(s): Spivey J.M.
Series: Prentice-Hall international series in computer science
Edition: free web version (1996)
Publisher: Prentice Hall
Year: 2008
Language: English
Pages: 259
City: London ; New York
Cover
Title Page
Table of Contents
Preface
1 Introduction
1.1 Introducing logic programming
2 Programming with relations
3 Recursive structures
3.1 Lists
3.2 Deriving facts about append
3.3 More relations on lists
3.4 Binary trees
4 The meaning of logic programs
4.1 Syntax
4.2 Truth tables
4.3 Adding functions and variables
4.4 Substitutions
5 Inference rules
5.1 Substitution and ground resolution
5.2 Refutation
5.3 Completeness
6 Unification and resolution
6.1 Unification
6.2 Resolution
6.3 Derivation trees and the lifting lemma
6.4 Completeness of resolution
7 SLD–resolution and answer substitutions
7.1 Linear resolution
7.2 SLD–resolution
7.3 Search trees
7.4 Answer substitutions
8 Negation as failure
8.1 Negation in goals
8.2 Negation in programs
8.3 Semantics of negation
9 Searching problems
9.1 Representing the problem
9.2 Avoiding cycles
9.3 Bounded and breadth-first search
10 Parsing
10.1 Arithmetic expressions
10.2 Difference lists
10.3 Expression trees
10.4 Grammar rules in Prolog
11 Evaluating and simplifying expressions
11.1 Evaluating expressions
11.2 Simplifying expressions
12 Hardware simulation
13 Program transformation
13.1 Unfolding and symbolic execution
13.2 Fold–unfold transformation
13.3 Improving the reverse program
14 About picoProlog
14.1 The picoProlog language
14.2 Built-in relations
14.3 The cut symbol
14.4 Implementation overview
15 Implementing depth-first search
15.1 Depth-first search
15.2 Representing the goal list
15.3 Representing goals
15.4 Answer substitutions
15.5 Depth-first search revisited
15.6 Choice points
15.7 Choosing representations
16 Representing terms and substitutions
16.1 Representing terms
16.2 Substitutions
16.3 Renaming
16.4 Printing terms
16.5 The trail
16.6 Unification
17 Implementation notes
17.1 Macros
17.2 String handling
17.3 Memory allocation
17.4 Symbol table
17.5 Lexical analysis
17.6 Syntax analysis
17.7 Trail
17.8 Unification
17.9 Interpreter
17.10 Built-in relations
17.11 Main program
18 Interpreter optimizations
18.1 Garbage collection
18.2 Indexing
18.3 Tail recursion
18.4 A concluding example
19 In conclusion
Further reading
A Answers to the exercises
B Using an ordinary Prolog system
C PicoProlog source code
D Cross-reference listing
Index
