Declarative Logic Programming : Theory, Systems, and Applications

The idea of this book grew out of a symposium that was held at Stony Brook in September 2012 in celebration of David S.Warren's fundamental contributions to Computer Science and the area of Logic Programming in particular. Logic Programming (LP) is at the nexus of Knowledge Representation, Artificial Intelligence, Mathematical Logic, Databases, and Programming Languages. It is fascinating and intellectually stimulating due to the fundamental interplay among theory, systems, and applications brought about by logic. Logic programs are more declarative in the sense that they strive to be logical specifications of "what" to do rather than "how" to do it, and thus they are high-level and easier to understand and maintain. Yet, without being given an actual algorithm, LP systems implement the logical specifications automatically. Several books cover the basics of LP but focus mostly on the Prolog language with its incomplete control strategy and non-logical features. At the same time, there is generally a lack of accessible yet comprehensive collections of articles covering the key aspects in declarative LP. These aspects include, among others, well-founded vs. stable model semantics for negation, constraints, object-oriented LP, updates, probabilistic LP, and evaluation methods, including top-down vs. bottom-up, and tabling. For systems, the situation is even less satisfactory, lacking accessible literature that can help train the new crop of developers, practitioners, and researchers. There are a few guides onWarren's Abstract Machine (WAM), which underlies most implementations of Prolog, but very little exists on what is needed for constructing a state-of-the-art declarative LP inference engine. Contrast this with the literature on, say, Compilers, where one can first study a book on the general principles and algorithms and then dive in the particulars of a specific compiler. Such resources greatly facilitate the ability to start making meaningful contributions quickly. There is also a dearth of articles about systems that support truly declarative languages, especially those that tie into first-order logic, mathematical programming, and constraint solving. LP helps solve challenging problems in a wide range of application areas, but in-depth analysis of their connection with LP language abstractions and LP implementation methods is lacking. Also, rare are surveys of challenging application areas of LP, such as Bioinformatics, Natural Language Processing, Verification, and Planning. The goal of this book is to help fill in the previously mentioned void in the LP literature. It offers a number of overviews on key aspects of LP that are suitable for researchers and practitioners as well as graduate students. The following chapters in theory, systems, and applications of LP are included. Cover Title Page Copyright Page Dedication Page Table of Contents Preface PART I THEORY Chapter 1 Datalog: Concepts, History, and Outlook 1.1 Introduction 1.2 The Emergence of Datalog 1.3 Coining “Datalog” 1.4 Extensions to Datalog 1.5 Evaluation Techniques 1.6 Early Datalog and Deductive Database Systems 1.7 The Decline and Resurgence of Datalog 1.8 Current Systems and Comparison 1.9 Conclusions Acknowledgments References Chapter 2 An Introduction to the Stable and Well-Founded Semantics of Logic Programs 2.1 Introduction 2.2 Terminology, Notation, and Other Preliminaries 2.3 The Case of Horn Logic Programs 2.4 Moving Beyond Horn Programs—An Informal Introduction 2.5 The Stable Model Semantics 2.6 The Well-Founded Model Semantics 2.7 Concluding Remarks Acknowledgments References Chapter 3 A Survey of Probabilistic Logic Programming 3.1 Introduction 3.2 Languages with the Distribution Semantics 3.3 Defining the Distribution Semantics 3.4 Other Semantics for Probabilistic Logics 3.5 Probabilistic Logic Programs and Bayesian Networks 3.6 Inferencing in Probabilistic Logic Programs 3.7 Discussion Acknowledgments References PART II SYSTEMS Chapter 4 WAM for Everyone: A Virtual Machine for Logic Programming 4.1 Introduction 4.2 The Run-Time Environment of a Traditional Procedural Language 4.3 Deterministic Datalog 4.4 Deterministic Prolog 4.5 Nondeterministic Prolog 4.6 Last Call Optimization 4.7 Indexing 4.8 Environment Trimming 4.9 Features Required for Full Prolog 4.10 WAM Extensions for Tabling 4.11 Concluding Remarks Acknowledgments References Chapter 5 Predicate Logic as a Modeling Language: The IDP System 5.1 Introduction 5.2 FO(ID, AGG, PF, T), the Formal Base Language 5.3 IDP as a Knowledge Base System 5.4 The IDP Language 5.5 Advanced Features 5.6 Under the Hood 5.7 In Practice 5.8 Related Work 5.9 Conclusion References Chapter 6 SolverBlox: Algebraic Modeling in Datalog 6.1 Introduction 6.2 Datalog 6.3 LogicBlox and LogiQL 6.4 Mathematical Programming with LogiQL 6.5 The Traveling Salesman Problem (TSP) Test Case 6.6 Conclusions and Future Work References PART III APPLICATIONS Chapter 7 Exploring Life: Answer Set Programming in Bioinformatics 7.1 Introduction 7.2 Biology in a Nutshell 7.3 Answer Set Programming in a Nutshell 7.4 Phylogenetics 7.5 Haplotype Inference 7.6 RNA Secondary Structure Prediction 7.7 Protein Structure Prediction 7.8 Systems Biology 7.9 Other Logic Programming Approaches 7.10 Conclusions Acknowledgments References Chapter 8 State-Space Search with Tabled Logic Programs 8.1 Introduction 8.2 Finite-State Model Checking 8.3 Infinite-State Model Checking 8.4 Simple Planning via Tabled Search 8.5 Discussion Acknowledgments References Chapter 9 Natural Language Processing with (Tabled and Constraint) Logic Programming 9.1 Introduction 9.2 Tabling, LP, and NLP 9.3 Tabled Logic Programming and Definite Clause Grammars 9.4 Using Extra Arguments for Linguistic Information 9.5 Assumption Grammars: DCGs Plus Global Memory 9.6 Constraint Handling Rules and Their Application to Language Processing 9.7 Hypothetical Reasoning with CHR and Prolog: Hyprolog 9.8 A Note on the Usefulness of Probabilistic Logic Programming for Language Processing 9.9 Conclusion References Chapter 10 Logic Programming Applications: What Are the Abstractions and Implementations? 10.1 Introduction 10.2 Logic Language Abstractions 10.3 Join and Database-Style Queries 10.4 Recursion and Inductive Analysis 10.5 Constraint and Combinatorial Search 10.6 Further Extensions, Applications, and Discussion 10.7 Related Literature and Future Work Acknowledgments References Index Biographies

The idea of this book grew out of a symposium that was held at Stony Brook in September 2012 in celebration of David S.Warren's fundamental contributions to Computer Science and the area of Logic Programming in particular.

Logic Programming (LP) is at the nexus of Knowledge Representation, Artificial Intelligence, Mathematical Logic, Databases, and Programming Languages. It is fascinating and intellectually stimulating due to the fundamental interplay among theory, systems, and applications brought about by logic. Logic programs are more declarative in the sense that they strive to be logical specifications of "what" to do rather than "how" to do it, and thus they are high-level and easier to understand and maintain. Yet, without being given an actual algorithm, LP systems implement the logical specifications automatically.

Several books cover the basics of LP but focus mostly on the Prolog language with its incomplete control strategy and non-logical features. At the same time, there is generally a lack of accessible yet comprehensive collections of articles covering the key aspects in declarative LP. These aspects include, among others, well-founded vs. stable model semantics for negation, constraints, object-oriented LP, updates, probabilistic LP, and evaluation methods, including top-down vs. bottom-up, and tabling.

For systems, the situation is even less satisfactory, lacking accessible literature that can help train the new crop of developers, practitioners, and researchers. There are a few guides onWarren’s Abstract Machine (WAM), which underlies most implementations of Prolog, but very little exists on what is needed for constructing a state-of-the-art declarative LP inference engine. Contrast this with the literature on, say, Compilers, where one can first study a book on the general principles and algorithms and then dive in the particulars of a specific compiler. Such resources greatly facilitate the ability to start making meaningful contributions quickly. There is also a dearth of articles about systems that support truly declarative languages, especially those that tie into first-order logic, mathematical programming, and constraint solving.

LP helps solve challenging problems in a wide range of application areas, but in-depth analysis of their connection with LP language abstractions and LP implementation methods is lacking. Also, rare are surveys of challenging application areas of LP, such as Bioinformatics, Natural Language Processing, Verification, and Planning.

The goal of this book is to help fill in the previously mentioned void in the LP literature. It offers a number of overviews on key aspects of LP that are suitable for researchers and practitioners as well as graduate students. The following chapters in theory, systems, and applications of LP are included.

Logic Programming (LP) is at the nexus of knowledge representation, AI, mathematical logic, databases, and programming languages. It allows programming to be more declarative, by specifying "what" to do instead of "how" to do it. This field is fascinating and intellectually stimulating due to the fundamental interplay among theory, systems, and applications brought about by logic. Several books cover the basics of LP but they focus mostly on the Prolog language. There is generally a lack of accessible collections of articles covering the key aspects of LP, such as the well-founded vs. stable semantics for negation, constraints, object-oriented LP, updates, probabilistic LP, and implementation methods, including top-down vs. bottom-up evaluation and tabling. For systems, the situation is even less satisfactory, lacking expositions of LP inference machinery that supports tabling and other state-of-the-art implementation techniques. There is also a dearth of articles about systems that support truly declarative languages, especially those that tie into first-order logic, mathematical programming, and constraint programming. Also rare are surveys of challenging application areas of LP, such as bioinformatics, natural language processing, verification, and planning, as well as analysis of LP applications based on language abstractions and implementations methods. The goal of this book is to help fill in the previously mentioned void in the LP literature. It offers a number of overviews on key aspects of LP that are suitable for researchers and practitioners as well as graduate students