Breadth-first execution

This package implements breadth-first execution of predicates. This may be useful in search problems when a proof procedure is needed that will find all solutions (even if it may still loop for some failures). This is in contrast with the default depth-first search, which may loop in some cases even if there are correct answers to a given query. This library is also useful when experimenting with pure programs as well as when teaching logic programming, for illustrating the expected theoretical results that should be expected from the declarative semantics (see for example the slides in http://www.cliplab.org/proglog).

It is important to realize, however, that the improved behaviour of breadth first execution comes at a high (exponential!) price in terms of both time ad memory. This library allows the programmer to control this overhead by selecting which predicates will be executed in breadth-first mode and which predicates in depth-first mode. More concretely, predicates written with operators '<-'/1 (facts) and '<-'/2 (clauses) are executed using breadth-first search, while predicates using the standard syntax will be executed depth-first.

The following example implements two versions of a predicate meant to succeed if two nodes of a directed graph are connected. The chain/2 predicate (which will be executed depth-first) loops without finding the connection between a and d, while the bfchain/2 predicate (which will be executed breadth-first) will find the connection correctly:

:- module(chain, _, [bf]).

test(bf) :- bfchain(a,d).
test(df) :- chain(a,d).   % loops!

bfchain(X,X) <- .
bfchain(X,Y) <- arc(X,Z), bfchain(Z,Y).

chain(X,X).
chain(X,Y) :- arc(X,Z), chain(Z,Y).

arc(a,b).
arc(a,d).
arc(b,c).
arc(c,a).

A second package, 'bf/bfall', allows executing all the predicates in a given module in breadth-first mode. In this case, predicates should be written using the standard syntax. This is useful to be able to switch easily between depth-first and breadth-first execution (e.g., for testing purposes) for all predicates in a given module without having to modify the program. The following program (written in standard syntax) runs breadth-first:

:- module(chain_bfall, _, ['bf/bfall']).

test :- chain(a,d).

chain(X,X).
chain(X,Y) :- arc(X,Z), chain(Z,Y).

arc(a,b).
arc(a,d).
arc(b,c).
arc(c,a).

There is another version, package 'bf/af', which ensures AND-fairness by goal shuffling. This reduces the number of cases in which an execution that is a failure loops instead (infinite failures) at a small additional cost. For example, by using 'bf/af' the following code correctly answers “no” when executing test/0:

:- module(sublistapp, [test/0, sublistapp/2], ['bf/af']).

:- push_prolog_flag(unused_pred_warnings, no).

test :- sublistapp([a], [b]).

sublistapp(S, L) <- append(_, S, Y), append(Y, _, L).

append([], L, L) <- .
append([X|Xs], L, [X|Ys]) <- append(Xs, L, Ys).

:- pop_prolog_flag(unused_pred_warnings).

There is also a package 'bf/bfall' which again allows executing all the predicates in a given module in breadth-first, and-fair mode, where also all predicates should be written using the standard syntax. This package offers (at a cost, of course) very nice results for many programs, and is used extensively in programming courses by the Ciao developers.

Finally, it should be noted that a separate library, id, implements iterative-deepening search, which can in many cases be a better alternative to breadth-first search, since it achieves the same improvement in the completeness results in many cases at a greatly reduced execution cost (but the enumeration order of solutions is not as nice, and that is why these packages are very attractive for prototyping and teaching).