|Publication Type||Journal Article|
|Year of Publication||1997|
|Authors||Hill PM, King A|
|Journal||Journal of Programming Languages|
|Keywords||abstract interpretation, determinacy analysis, logic programming, mode analysis, software verification, static analysis|
One unique feature of logic languages is their ability to succinctly and declaratively express non-determinacy and hence search. In logic programming, alternatives can be specified by a set of sentences defining the same predicate. By backtracking, considering in turn each of these sentences, these alternatives can be explored until a solution (if one exists) is found. However, though backtracking is essential for certain parts of a program, typically, many predicates are deterministic, and most queries to a program have no more than one solution. Providing for non-determinacy 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. This paper reformulates the determinacy definitions in a uniform framework; identifying and contrasting the different approaches. Techniques for detecting and exploiting determinacy are also reviewed together with some directions for future research.