通过Prolog介绍逻辑编程

The chapters of this book can be grouped into four parts, each developing different themes from the theory, application and implementation of logic programming. Chapters 1 to 3 introduce the ideas of logic programming; writing programs by defining relations, combining relations to define new ones, recursion in data and programs. The exposition here is mainly by example, and many topics are touched upon that are explored fully in later parts of the book. Chapters 4 to 8 develop the ‘logical’ theme by presenting the semantics of logic programs and developing the inference system of SLD–resolution that is the logical basis of Prolog implementations. This is the most mathematical part of the book, and develops in miniature the standard theory of mathematical logic, including proofs that various inference systems for Horn clause logic are sound and complete. Chapters 9 to 13 present more practical topics, from the formulation of graph-searching problems so that they can be solved by Prolog’s simple search strategy, to applications of logic programming in parsing, algebraic simplification and simulating hardware circuits. The final part of the book, in Chapters 14 to 18, picks up where the sec- ond part left off. It explains how SLD–resolution can be implemented efficiently by machine, using the conventional technology of Prolog implementation. These chapters describe the functioning of an actual interpreter for a Prolog subset, and the complete source code for this interpreter is included as Appendix C of this book. The presentation in this part of the book is based on stepwise refinement of data representations. The account begins with a simple implementation of depth-first search that uses abstract data types like sequences, terms and substitutions with corresponding abstract operations. Later chapters explain how these abstract data types can be implemented using the concrete data types provided by a machine. exposition here is mainly by example, and many topics are touched upon that are explored fully in later parts of the book. Chapters 4 to 8 develop the ‘logical’ theme by presenting the semantics of logic programs and developing the inference system of SLD–resolution that is the logical basis of Prolog implementations. This is the most mathematical part of the book, and develops in miniature the standard theory of mathematical logic, including proofs that various inference systems for Horn clause logic are sound and complete. Chapters 9 to 13 present more practical topics, from the formulation of graph-searching problems so that they can be solved by Prolog’s simple search strategy, to applications of logic programming in parsing, algebraic simplification and simulating hardware circuits. The final part of the book, in Chapters 14 to 18, picks up where the sec- ond part left off. It explains how SLD–resolution can be implemented efficiently by machine, using the conventional technology of Prolog implementation. These chapters describe the functioning of an actual interpreter for a Prolog subset, and the complete source code for this interpreter is included as Appendix C of this book. The presentation in this part of the book is based on stepwise refinement of data representations. The account begins with a simple implementation of depth-first search that uses abstract data types like sequences, terms and substitutions with corresponding abstract operations. Later chapters explain how these abstract data types can be implemented using the concrete data types provided by a machine.