|
Unnecessary backtracking is a principal source of inefficiency in Prolog execution. To
avoid the overhead of the general backtracking mechanism, determinate programs should be
executed deterministically. Even for programs that are not determinate, failure should be
identified early so as to minimize time spent in useless computation. One way to achieve
this is by identifying conditions under which a predicate will succeed and checking this
condition even before calling the predicate. We present a novel method to infer success
conditions of predicates. Unlike previous approaches that rely on cuts or use a
limited notion of test predicates, we propagate the conditions to detect determinacy,
enabling us to handle a much larger class of programs. Since the conditions are propagated
explicitly, the power of the method can be readily increased by increasing the
expressiveness of these conditions.
|