Determinacy and determinacy analysis.
Patricia Munday Hill, Andy King · Kent Academic Repository (University of Kent) · 1997
One attractive, unique feature of logic programming languages is their ability to succinctly and declaratively express search. The alternatives of a search can be specified by a set of clauses defining the same predicate. By backtracking, considering in turn each of these clauses, the different alternatives are explored until a solution (if it exists) is found. However, though backtracking is essential for predicates that deploy search, typically, many predicates of the programs are deterministic, and most queries to the program have no more than one solution. Providing for non-determinism can slow down the execution of a program on a uni-processor and limit the scope for parallel execution on a multi-processor. As a consequence, programmers are often forced to resort to the non-logical features of the language to ensure any determinacy is fully exploited. A number of papers on determinacy and its detection have been published. However, because of the diversity of applications for dete...