An abstract machine for tabled execution of fixed-order stratified logic programs
- 1 May 1998
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Programming Languages and Systems
- Vol. 20 (3) , 586-634
- https://doi.org/10.1145/291889.291897
Abstract
SLG resolution uses tabling to evaluate nonfloundering normal logic pr ograms according to the well-founded semantics. The SLG-WAM, which forms the engine of the XSB system, can compute in-memory recursive queries anorder of magnitute fasterthan current deductive databases. At the same time, the SLG-WAM tightly intergrates Prolog code with tabled SLG code, and executes Prolog code with minimal overhead compared to the WAM. As a result, the SLG-WAM brings to logic programming important termination and complexity properties of deductive databases. This article describes the architecture of the SLG-WAM for a powerful class of programs, the class offixed-order dynamically stratified programs. We offer a detailed description of the algorithms, data structures, and instructions that the SLG-WAM adds to the WAM, and a performance analysis of engine overhead due to the extensions.Keywords
This publication has 14 references indexed in Scilit:
- Efficient model checking using tabled resolutionPublished by Springer Nature ,1997
- Implementation of tabled evaluation with delaying in PrologIEEE Transactions on Knowledge and Data Engineering, 1997
- Tabled evaluation with delaying for general logic programsJournal of the ACM, 1996
- The limits of fixed-order computationPublished by Springer Nature ,1996
- Efficient top-down computation of queries under the well-founded semanticsThe Journal of Logic Programming, 1995
- Modular stratification and magic sets for Datalog programs with negationJournal of the ACM, 1994
- Negation as failure using tight derivations for general logic programsThe Journal of Logic Programming, 1989
- Foundations of Logic ProgrammingPublished by Springer Nature ,1987
- Memory Performance of Prolog ArchitecturesPublished by Springer Nature ,1987
- OLD resolution with tabulationPublished by Springer Nature ,1986