Читать книгу Declarative Logic Programming - Michael Kifer - Страница 8

Preface

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 on Warren’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.

Part I: Theory

1. “Datalog: Concepts, History, and Outlook” by David Maier, K. Tuncay Tekle, Michael Kifer, and David S. Warren.

This chapter is a comprehensive survey of the main concepts of Datalog, an LP language for data processing. The study of Datalog was one of the early drivers of more declarative approaches to LP. Some aspects of Datalog are covered in greater depth than others, but the bibliography at the end of the chapter can be relied upon to help fill in the details.

2. “An Introduction to the Stable and Well-Founded Semantics of Logic Programs” by Miroslaw Truszczynski.

The theory underlying modern LP is based on two different logical semantics: the stable model semantics and the well-founded semantics, leading to two different declarative paradigms. The stable model semantics defines the meaning of an LP program as a set of two-valued models and is a leading approach in LP to solving combinatorial problems. The well-founded semantics always yields a single, possibly three-valued, model and is popular with knowledge representation systems that focus on querying. This chapter provides a rigorous yet accessible introduction to both semantics.

3. “A Survey of Probabilistic Logic Programming” by Fabrizio Riguzzi and Theresa Swift.

Integration of probabilistic and logic reasoning is of great importance to modern Artificial Intelligence. This chapter provides a uniform introduction, based on what is called distribution semantics, to a number of leading approaches to such integration.

Part II: Systems

4. “WAM for Everyone: A Virtual Machine for Logic Programming” by David S. Warren.

This chapter is an introduction to Warren’s Abstract Machine (WAM), the primary technology underlying modern LP systems. Unlike previous expositions of WAM, this chapter also describes tabling, one of the main breakthroughs that occurred since D.H.D. Warren developed the original WAM in 1970’s.

5. “Predicate Logic as a Modeling Language: The IDP System” by Broes De Cat, Bart Bogaerts, Maurice Bruynooghe, Gerda Janssens, and Marc Denecker.

IDP is a language and system that supports classical predicate logic extended with inductive definitions as rules, and with aggregation, functions, and types. It promotes a declarative semantics of logic programs and allows a single logical specification to be used in multiple different reasoning tasks to solve a range of problems. This chapter gives an overview of the IDP language and system.

6. “SolverBlox: Algebraic Modeling in Datalog” by Conrado Borraz-Sánchez, Diego Klabjan, Emir Pasalic, and Molham Aref.

LogiQL extends Datalog with aggregation, reactive rules, and constraints to support transactions in a database and software development platform called LogicBlox. This chapter introduces LogiQL and shows how it can be used to specify and solve mixed-integer linear optimization problems by adding simple declarations.

Part III: Applications

7. “Exploring Life: Answer Set Programming in Bioinformatics” by Alessandro Dal Palù, Agostino Dovier, Andrea Formisano, and Enrico Pontelli.

This chapter surveys applications of declarative LP in Bioinformatics, including in Genomics studies, Systems Biology, and Structural studies. The necessary biological background is provided when necessary. The applications selected for this survey all rely on the Answer Set Programming paradigm.

8. “State-Space Search with Tabled Logic Programs” by C. R. Ramakrishnan.

Model checking and planning are two important and challenging classes of problems that require extensive search through the possible states of systems. This chapter gives an overview of both types of problems as applications of LP. It focuses on tabling as an effective technique for improving the performance of state space search.

9. “Natural Language Processing with (Tabled and Constraint) Logic Programming” by Henning Christiansen and Verónica Dahl.

Natural language processing (NLP) was the original motivation for the development of Prolog, the most popular logic-based language. This chapter is an overview of the applications of LP to NLP, primarily based on definite clause grammars.

10. “Logic Programming Applications: What Are the Abstractions and Implementations?” by Yanhong A. Liu.

LP is used in many areas and contexts but the applicability of LP needs to be understood in more fundamental ways. This chapter gives an overview of LP applications, classifying them based on three key abstractions and their corresponding implementations. The abstractions are join, recursion, and constraint. The corresponding implementations are for-loops, fixed points, and backtracking.

Acknowledgments

Congratulations to the chapter authors for the well-thought-out surveys—all written specifically for this book. Each contribution was carefully reviewed, with at least four reviews per chapter. We are deeply grateful to the reviewers for the time and effort dedicated to perfecting the book material. Many thanks to the Editor-in-Chief of ACM Books series, M. Tamer Özsu, for his support, and to Diane Cerra of Morgan & Claypool for her help, guidance, and patience throughout the process. We were lucky to have an expert production team: Paul Anagnostopoulos of Windfall Software, who masterfully typeset this book; Sara Kreisman of Rambling Rose Press, who copyedited the pesky typos out of existence; Brent Beckley of Morgan & Claypool, who designed the beautiful and artsy cover; and Christine Kiilerich, also of Morgan & Claypool, who helped with many publication tasks.

We also acknowledge the support of NSF under grants CCF-0964196, CCF-1248184, CCF-1414078, and IIS-1447549; and of ONR under grant N000141512208.