Determinacy and Determinacy Analysis

Publication TypeJournal Article
Year of Publication1997
AuthorsHill PM, King A
JournalJournal of Programming Languages
Keywordsabstract 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.

We are a passionate team of experts. Do not hesitate to let us have your feedback:
You may be surprised to discover just how much your suggestions matter to us.