Prolog programs are often inefficient: execution corresponds to a depth-first traversal of an AND/OR graph; traversing subgraphs in another order can be less expensive. It is shown how the reordering of clauses within Prolog predicates, and especially of goals within clauses, can prevent unnecessary search. The characterization and detection of restrictions on reordering is discussed. A system of calling modes for Prolog, geared to reordering, is proposed, and ways to infer them automatically are discussed. The information needed for safe reordering is summarized, and which types can be inferred automatically and which must be provided by the user are considered. An improved method for determining a good order for the goals of Prolog clauses is presented and used as the basis for a reordering system.>

The authors show how reordering of Prolog clauses, and especially goals, can prevent unnecessary search. They characterize the restrictions on reordering and show how they may be detected. They design a system of calling modes for Prolog, geared to reordering and discuss ways to infer them automatically. They present an improved method for determining a good goal order for Prolog clauses, and use it 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.>