Dynamic reordering of alternatives for definite logic programs

摘要

Due to their highly declarative nature and efficiency, tabled logic programming systems have been applied to solving many complex problems. Tabled logic programming is essential for extending traditional logic programming with tabled resolution. In this paper, we propose a new tabled resolution scheme, called dynamic reordering of alternatives (DRA) resolution, for definite logic programs. The scheme keeps track of the type of the subgoals during resolution; if the subgoal in the current resolvent is a variant of a former tabled subgoal, tabled answers are used to resolve the subgoal; otherwise, program clauses are used similar to SLD resolution. Program clauses leading to variant subgoals at runtime are dynamically reordered for further computation until the subgoals are completely evaluated. DRA resolution allows query evaluation to be performed in a depth-first, left-to-right traversal order similar to Prolog-typed SLD resolution, thus yielding a simple technique for incorporating tabled resolution in traditional logic programming systems. We show the correctness of DRA resolution.