Declarative Logic Programming

Yanhong Annie Liu, Michael Kifer

Description

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.

Table of Contents: Preface / PART I THEORY / 1. Datalog: Concepts, History, and Outlook / 2. An Introduction to the Stable and Well-Founded Semantics of Logic Programs / 3. A Survey of Probabilistic Logic Programming / PART II SYSTEMS / 4. WAM for Everyone: A Virtual Machine for Logic Programming / 5. Predicate Logic as a Modeling Language: The IDP System / 6. SolverBlox: Algebraic Modeling in Dialog / PART III APPLICATIONS / 7. Exploring Life: Answer Set Programming in Bioinformatics / 8. State-Space Search with Tabled Logic Programs / 9. Natural Language Processing with (Tabled and Constraint) Logic Programming / 10. Logic Programming Applications: What Are the Abstractions and Implementations? / Index / Biographies

Sujets

• Computer Science
• Computers
• Informatique

Informations

• Publié par: Association for Computing Machinery and Morgan & Claypool Publishers
• Date de parution: 19 septembre 2018
• Nombre de lectures: 0
• EAN13: 9781970001983
• Langue: English
• Poids de l'ouvrage: 12 Mo

Extrait

Declarative Logic Programming
ACM Books
Editor in Chief
M. Tamer zsu, University of Waterloo
ACM Books is a new series of high-quality books for the computer science community, published by ACM in collaboration with Morgan Claypool Publishers. ACM Books publications are widely distributed in both print and digital formats through booksellers and to libraries (and library consortia) and individual ACM members via the ACM Digital Library platform.
Declarative Logic Programming: Theory, Systems, and Applications
Editors: Michael Kifer, Stony Brook University
Yanhong Annie Liu, Stony Brook University
2018
The Handbook of Multimodal-Multisensor Interfaces, Volume 2: Signal Processing, Architectures, and Detection of Emotion and Cognition
Editors: Sharon Oviatt, Monash University
Bj rn Schuller, University of Augsburg and Imperial College London
Philip R. Cohen, Monash University
Daniel Sonntag, German Research Center for Artificial Intelligence (DFKI)
Gerasimos Potamianos, University of Thessaly
Antonio Kr ger, German Research Center for Artificial Intelligence (DFKI)
2017
The Sparse Fourier Transform: Theory and Practice
Haitham Hassanieh, University of Illinois at Urbana-Champaign
2018
The Continuing Arms Race: Code-Reuse Attacks and Defenses
Editors: Per Larsen, Immunant, Inc .
Ahmad-Reza Sadeghi, Technische Universit t Darmstadt
2018
Frontiers of Multimedia Research
Editor: Shih-Fu Chang, Columbia University
2018
Shared-Memory Parallelism Can Be Simple, Fast, and Scalable
Julian Shun, University of California, Berkeley
2017
Computational Prediction of Protein Complexes from Protein Interaction Networks
Sriganesh Srihari, The University of Queensland Institute for Molecular Bioscience
Chern Han Yong, Duke-National University of Singapore Medical School
Limsoon Wong, National University of Singapore
2017
The Handbook of Multimodal-Multisensor Interfaces, Volume 1: Foundations, User Modeling, and Common Modality Combinations
Editors: Sharon Oviatt, Incaa Designs
Bj rn Schuller, University of Passau and Imperial College London
Philip R. Cohen, Voicebox Technologies
Daniel Sonntag, German Research Center for Artificial Intelligence (DFKI)
Gerasimos Potamianos, University of Thessaly
Antonio Kr ger, German Research Center for Artificial Intelligence (DFKI)
2017
Communities of Computing: Computer Science and Society in the ACM
Thomas J. Misa, Editor, University of Minnesota
2017
Text Data Management and Analysis: A Practical Introduction to Information Retrieval and Text Mining
ChengXiang Zhai, University of Illinois at Urbana-Champaign
Sean Massung, University of Illinois at Urbana-Champaign
2016
An Architecture for Fast and General Data Processing on Large Clusters
Matei Zaharia, Stanford University
2016
Reactive Internet Programming: State Chart XML in Action
Franck Barbier, University of Pau, France
2016
Verified Functional Programming in Agda
Aaron Stump, The University of Iowa
2016
The VR Book: Human-Centered Design for Virtual Reality
Jason Jerald, NextGen Interactions
2016
Ada s Legacy: Cultures of Computing from the Victorian to the Digital Age
Robin Hammerman, Stevens Institute of Technology
Andrew L. Russell, Stevens Institute of Technology
2016
Edmund Berkeley and the Social Responsibility of Computer Professionals
Bernadette Longo, New Jersey Institute of Technology
2015
Candidate Multilinear Maps
Sanjam Garg, University of California, Berkeley
2015
Smarter Than Their Machines: Oral Histories of Pioneers in Interactive Computing
John Cullinane, Northeastern University; Mossavar-Rahmani Center for Business and Government, John F. Kennedy School of Government, Harvard University
2015
A Framework for Scientific Discovery through Video Games
Seth Cooper, University of Washington
2014
Trust Extension as a Mechanism for Secure Code Execution on Commodity Computers
Bryan Jeffrey Parno, Microsoft Research
2014
Embracing Interference in Wireless Systems
Shyamnath Gollakota, University of Washington
2014
Declarative Logic Programming
Theory, Systems, and Applications
Michael Kifer
Stony Brook University
Yanhong Annie Liu
Stony Brook University
ACM Books #20
Copyright 2018 by the Association for Computing Machinery and Morgan Claypool Publishers
All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means-electronic, mechanical, photocopy, recording, or any other except for brief quotations in printed reviews-without the prior permission of the publisher.
Designations used by companies to distinguish their products are often claimed as trademarks or registered trademarks. In all instances in which Morgan Claypool is aware of a claim, the product names appear in initial capital or all capital letters. Readers, however, should contact the appropriate companies for more complete information regarding trademarks and registration.
Declarative Logic Programming: Theory, Systems, and Applications
Michael Kifer, Yanhong Annie Liu, editors
books.acm.org
www.morganclaypoolpublishers.com
ISBN: 978-1-97000-199-0 hardcover
ISBN: 978-1-97000-196-9 paperback
ISBN: 978-1-97000-197-6 eBook
ISBN: 978-1-97000-198-3 ePub
Series ISSN: 2374-6769 print 2374-6777 electronic
DOIs:
10.1145/3191315 Book
10.1145/3191315.3191316 Preface
10.1145/3191315.3191317 Chapter 1
10.1145/3191315.3191318 Chapter 2
10.1145/3191315.3191319 Chapter 3
10.1145/3191315.3191320 Chapter 4
10.1145/3191315.3191321 Chapter 5
10.1145/3191315.3191322 Chapter 6
10.1145/3191315.3191323 Chapter 7
10.1145/3191315.3191324 Chapter 8
10.1145/3191315.3191325 Chapter 9
10.1145/3191315.3191326 Chapter 10
10.1145/3191315.3191327 Index
A publication in the ACM Books series, #20
Editor in Chief: M. Tamer zsu, University of Waterloo
Area Editor: Yanhong Annie Liu, Stony Brook University
This book was typeset in Arnhem Pro 10/14 and Flama using ZzTEX.
First Edition
10 9 8 7 6 5 4 3 2 1
To David Scott Warren, for his groundbreaking work on principles and systems for logic programming
Contents
Preface
PART I THEORY
Chapter 1 Datalog: Concepts, History, and Outlook
David Maier, K. Tuncay Tekle, Michael Kifer, David S. Warren
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
Miroslaw Truszczynski
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
Fabrizio Riguzzi, Theresa Swift
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
David S. Warren
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
Broes De Cat, Bart Bogaerts, Maurice Bruynooghe, Gerda Janssens, Marc Denecker
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
Conrado Borraz-S nchez, Diego Klabjan, Emir Pasalic, Molham Aref
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
Alessandro Dal Pal , Agostino Dovier, Andrea Formisano, Enrico Pontelli
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
C. R. Ramakrishnan
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
Henning Christiansen, Ver nica Dahl
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 Abstrac