Efficient reordering of Prolog programs

Abstract

Redundant search often makes Prolog programs inefficient. Prolog execution corresponds to a depth-first traversal of an AND/OR graph; often a large subgraph will be searched successfully, with failure resulting from a subsequent small one. It is shown how reordering of Prolog clauses and especially goals can prevent unnecessary search. The restrictions on reordering are characterized and how they may be detected is shown. A new system of calling modes for Prolog, geared to reordering, and a system for inferring them automatically are designed. An improved method for determining a good goal order for Prolog clauses is presented, and it is used as the basis for a reordering system, showing how it can be guided by information about modes and restrictions to generate reordered Prolog that behaves correctly.