ISSN:
1573-7640
Keywords:
Stream AND-parallelism
;
don’t-know nondeterminism
;
intelligent backtracking
;
strong and precise modes
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract We present the first backtracking algorithm for stream AND-parallel logic programs. It relies on compile-time knowledge of the dataflow graph of each clause to let it figure out efficiently which goals to kill or restart when a goal fails. This crucial information, which we derive from mode declarations, was not available at compile-time in any previous stream AND-parallel system. We show that modes can increase the precision of the backtracking algorithm, though our algorithm allows this precision to be traded off against overhead on a procedure-by-procedure and call-by-call basis. The modes also allow our algorithm to handle efficiently programs that manipulate partially instantiated data structures and an important class of programs with circular dependency graphs. On code that does not need backtracking, the efficiency of our algorithm approaches that of the committed-choice languages; on code that does need backtracking its overhead is comparable to that of the independent AND-parallel backtracking algorithms.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02427851
Permalink
