BRAVE: AN OR-PARALLEL LOGIC LANGUAGE AND ITS APPLICATION TO SEARCH PROBLEMS IN ARTIFICIAL INTELLIGENCE
Πέτρος Κεφαλάς · 1991
This thesis presents extensions to the language Brave, an OR-parallel dialect of Prolog, to enable coding of Artificial Intelligence algorithms.The upgraded language, Brave89, consists of two parts: Brave, which performs an all-solutions OR-parallel search and meta-Brave, which establishes control over the search.Brave features a conditional construction and a single solution predicate.Higher order predicates are also introduced in order to facilitate expansion and collection of lists.Two types of clause terminators are employed to direct sequential and parallel exploration of OR-choices.They are otherwise semantically transparent, only affecting the order in which solutions are produced.Meta-Brave takes the form of directives.Independent subproofs may learn of each other's results by means of a special database which contains selectively published information in the form of lemmas.A lemma directive says which results should be lemmaed.A prune directive allows subproofs to be failed on the basis of lemmaed information.Another directive may alter the proof strategy to other than the default multiple depth-first.The performance of Brave89 is evaluated using two simulators: one written in Prolog, one in C.These implement the Brave89 non-deterministic rewrite machine.A practical tool is developed to display the behaviour of the OR-parallel execution.The requirements of AI programs are analysed and a number of algorithms coded, showing how the various language features are utilised.Running the programs on the simulators shows that there is good scope for OR-parallelism.The language features chosen for Brave89 are also shown to be sufficient to re-express many successful AI algorithms in a new parallel paradigm.