Go to the first, previous, next, last section, table of contents.

Breadth-first execution

Author(s): Daniel Cabeza, Manuel Carro.

Version: 1.11#222 (2004/5/24, 13:8:7 CEST)

Version of last change: 1.5#143 (2000/5/12, 13:54:34 CEST)

This package implements breadth-first execution of predicates. Predicates written with operators '<-'/1 (facts) and '<-'/2 (clauses) are executed using breadth-first search. This may be useful in search problems when a complete proof procedure is needed. An example of code would be: 

- 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).

There is another version, called bf/af, which ensures AND-fairness by goal shuffling. This version correctly says "no" executing the following test: 

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

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).

Usage and interface (bf)

Known bugs and planned improvements (bf)

Go to the first, previous, next, last section, table of contents.