Determinacy and Determinacy Analysis

Title
Publication TypeJournal Article
Year of Publication1997
AuthorsHill PM, King A
JournalJournal of Programming Languages
Volume5
Pagination135–171
ISSN0963-9306
Keywordsabstract interpretation, determinacy analysis, logic programming, mode analysis, software verification, static analysis
Abstract

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.