The SLG-WAM: A search-efficient engine for well-founded evaluation of normal logic programs.

摘要

We investigate ways of bringing systems based on ideas from logic programming closer to the ideals of the paradigm. We conservatively extend Prolog implementations to overcome their susceptibility to infinite loops, and their unacceptable performance caused by repeated subcomputations. Moreover, we improve the expressive power of systems whose query language is based on logical rules with negation by supporting evaluation of queries according to the well-founded semantics. We focus on how to achieve these ambitious goals without sacrificing the search-efficiency of the evaluation strategy, or the performance of the underlying abstract machine.;Higher-level issues related to the search-efficiency of evaluation strategies for the well-founded semantics are addressed by proving a bound on the non-determinism required by the computation rule. Lower-level issues that are sometimes overlooked, albeit necessary for the efficient evaluation of practical programs (and in many cases today for relevance of research in computer science), are addressed by developing the SLG-WAM, an abstract machine for the efficient evaluation of normal programs according to the well-founded semantics. The SLG-WAM conservatively extends the standard basis of Prolog implementations to include features that are necessary to support the enhanced functionality.;We believe that the SLG-WAM can serve as a conceptual framework for future implementation efforts aiming to incorporate into one system ideas from logic programming, deductive databases, and non-monotonic reasoning.;The work was done in the framework of the XSB system, various aspects of which are also briefly described.