An Introduction to Logic Programming Through Prolog

Description

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 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