A data-dependency-based intelligent backtracking scheme for PROLOG

AbstractThis paper presents a scheme for intelligent backtracking in PROLOG programs. Rather than doing the analysis of unification failures, this scheme chooses backtrack points by doing the analysis of data dependency between literals. The other data-dependency-based methods previously developed cannot be easily incorporated in Warren's abstract machine, and are not able to perform across-the-clause backtracking intelligently. Our scheme overcomes all these defects. For many problems this scheme is just as effective as intelligent backtracking schemes based upon (more accurate) analysis of unification failure, and yet incurs small space and time over- head. To demonstrate the usefulness of our scheme, we have modified a simulator of Warren's abstract machine to incorporate our intelligent backtracking scheme, and have evaluated its performance on a number of problems