Abstract:
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.
Bibtex Entry:
@inproceedings{DRRS:ICLP93, author = {Steven Dawson and C. R. Ramakrishnan and I. V. Ramakrishnan and R. Sekar}, title = {Extracting Determinacy in Logic Programs}, booktitle = {International Conference on Logic Programming}, publisher = {MIT Press}, pages = {424--438}, year = {1993} }
| Full Paper: | [pdf] |
C. R. Ramakrishnan
(cram@cs.sunysb.edu)