Execution of logic programs by iterative-deepening A* SLD-tree search

The depth-first search strategy used by PROLOG is supplemented by depth-first iterative-deepening A*, which is complete, i.e. it always succeeds in executing a correct program if enough time and space is available. Iterative-deepening A* is only used for predicates that can be executed faster with iterative-deepening A* instead of depth-first.Since standard iterative-deepening A* is quadratic instead of linear for trees with much one way branching, e.g. most SLD-trees, extrapolation is used to determine a suitable bound on the evaluation function values of nodes that are to be expanded during an iteration. The number of inferences is further reduced by pruning rules such as cutting when the next literal to be evaluated is an alphabetic variant of a literal for which evaluation has failed previously.An advantage of the suggested search strategy is that many more programs can be executed with reasonable efficiency. The main disadvantage is that the programmer either must specify explicitly which strategy to use for a given predicate or provide examples so that the best strategy can be inferred automatically.