BRAVE: An OR-Parallel dialect of Prolog and its Application
to Artificial Intelligence
T.J.Reynolds and
P. Kefalas
Abstract: We present the Brave system which
consists of the simple Horn-clause language Brave, a dialect of Prolog
designed for OR-parallel execution, plus meta-Brave, which contains the
extra-logical features and executes sequentially. Pure Brave has been stripped
of Prolog’s assert and retract, control features like cut and side-effect
predicates like write. Meta-Brave features enable compatibility with existing
Prolog. Brave allows programmers to exploit an available parallel machine
by writing programs in a declarative style which enables easy parallelisation.
Meta-Brave also features a number of directives which allow algorithmic
knowledge about a domain to be stated independently from the Brave application
program. These include informing as to what sort of partial results should
be remembered (lemmas), instructing on which goals can be pruned as they
must fail and modifying the selection rule from depth-first to breadth-first
or best-first. We show how this combination of features makes the Brave
system specially suited to writing clear programs for search problems in
Artificial Intelligence. Results are presented for the performance of well-known
algorithms including parallel branch-and-bound and game-tree search with
alpha-beta pruning, obtained using a multi-processor simulator written
in C.
Keywords: Prolog, OR-Parallelism, Memoisation, Branch &
Bound Searchm Alpha-Beta Pruning
Appeared in: Proc. of the 1st and 2nd Intern. Conf. in Logic
Programming in Soviet Union, Lecture Notes in Artificial Intelligence,
vol.592, pp 415-432, Springer-Verlag, Irkutsk 1990 and Leningrad 1991
Available: Hardcopy on request from the authors. .
Back
to Dept. of Computer Science, CITY Liberal Studies
Back
to Petros Kefalas home page