Shallow Backtracking in Prolog Programs
Micha Meier · 2015
The efficiency of Prolog compilers is increasing rapidly but the Prolog programs still cannot compete with traditional languages when executing simple conditionals. In this paper we present a possibility to increase Prolog performance by exploiting the shallow backtracking. Shallow backtracking is initiated when a call fails to unify with the head of a clause and it backtracks to another clause in the same procedure, as opposed to deep backtracking which requires going back in the search tree and trying an alternative of a previous goal. We introduce modified OR-level instructions and data management and discuss the impact on performance of Prolog programs. III 1 Introduction One of the outstanding features of Prolog is the ability to yield multiple solutions of a procedure call by backtracking to a previous OR-node and trying another, not yet explored alternative. One of Prolog's drawbacks is that backtracking is the only means to solve a failure of any kind, even a failure of a sim...