Efficient evaluation of normal logic programs
Terrance Swift · 1994
An accident of implementation may be responsible for the fact that Logic Programming, Deductive Databases and Non-Monotonic Reasoning are different subfields. Logic Programming views logic as a programming language-- implemented through Prolog or an extension of Prolog. The Deductive Database community regards logic as a database language, often implemented using a variant of magic sets as a basis for implementation. Finally the field of Non-Monotonic Reasoning studies non-classical logics of interest to Artificial Intelligence or other applications. However, there are currently few engines powerful enough to implement Non-Monotonic Reasoning for practical programs. Recent formulations of tabling methods have the potential to unify these subfields. This thesis explores how to efficiently implement one such method: SLG. Previous formulations of SLG do not make explicit the search strategy for an evaluation, or consider trade-offs between alternate search strategies. To bring out these features, an operational semantics for SLG, SLGO, is defined which makes explicit algorithms for completion and other operations. This formalism allows proofs of correctness of algorithms upon which the SLG-WAM is based, as well as proofs of termination for programs of boundedterm size. The modelling of search strategy is also powerful enough to derive preliminary results for the cut/0 operator as extended to SLG, and for combining SLG and SLDNF using Existential Negation. Based on the SLGO search strategy, Part 2 describes the SLG-WAM, an engine which evaluates SLG for stationary stratified programs, and integrates SLG with full Prolog functionality, including the cut, findall, and meta-predicates. Data structures and instructions of the SLG-WAM are described in detail. The SLG-WAM is in fact the engine for the XSB system, and has been installed in hundreds of sites around the world. Part three analyzes the SLG-WAM and compares its performance with the WAM and