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