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 compatability 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 alphabeta pruning, obtained using a multi-processor simulator written in C.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
R.A. Finkel, J.P. Fishburn. “Parallelism in alpha-beta Search”. Artificial Intelligence 19, pages 89–106, 1982
S. Haridi, P. Brand. “ANDORRA Prolog — An Integration of Prolog and Committed Choice Languages”. Proceedings of the FGCS'88 Conference, ICOT, pages 745–754, 1988
B. Hausman, A. Ciepielewski, A. Calderwood. “Cut and Side Effects in Or-Parallel Prolog”. Proceedings of the FGCS'88 Conference, ICOT, pages 831–840, 1988
D.E. Knuth, R.W. Moore. “An Analysis of alpha-beta Pruning”. Artificial Intelligence 6, pages 293–326, 1975
T.H. Lai, S. Sahni. “Anomalies in Parallel Branch and Bound Algorithms”. Communications of the ACM, Vol. 27, pages 594–602, 1984
J.W.Lloyd. “Directions for Meta-Programming”. Proceedings of the FGCS '88 Conference, ICOT, pages 609–617, 1988
E. Lusk et al., D.H.D. Warren et. al, S. Haridi et al. “The Aurora OR-Parallei Prolog System”. Proceedings of the FGCS '88 Conference, ICOT, pages 819–830, 1988
L. Naish. “Negation and Control in Prolog”. G. Goos and J. Hartmanis (ed.), LNCS 238, Springer-Verlag, 1985
M. Newborn. “A Parallel Search Chess Program”. Proceedings of the ACM Annual Conference, ACM, New York, pages 272–277, 1985
S.L. Peyton Jones, C. Clack, J. Salkild, M. Hardie. “GRIP — a high-performance architecture for parallel graph reduction”. Proceedings of the IFIP Conference on Functional Programming Languages and Computer Architecture, Portland, G. Kahn (ed.), LNCS 274, SpringerVerlag, pages 98–112, 1987
T.J. Reynolds, A.J. Beaumont, A.S.K. Cheng, S.A. Delgado-Rannauro, L.A. Spacek. “BRAVE-A Parallel Logic Language for Artificial Intelligence”. Future Generations Computer Systems 4, North-Holland, pages 69–75, 1988
P. Van Hentenryck. “Parallel Constraint Satisfaction in Logic Programming: Preliminary results of CHIP within PEPSys”, In Logic Programming, Proceedings of the 6th International Conference on Logic Programming, Lisbon, MIT Press, pages 165–180, 1989
D.H.D.Warren. “An Abstract Prolog Instruction Set”, Technical Report TN-309, SRI, October 1983
D.H.D.Warren. “The SRI model for OR-Parallel Execution of Prolog. Abstract Design and Implementation Issues”. In the IEEE Computer Society Press (ed.), Proceedings of the 1987 Symposium on Logic Programming, pages 46–53, IEEE, September 1987
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1992 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Reynolds, T.J., Kefalas, P. (1992). Brave: An OR-parallel dialect of Prolog and its application to artificial intelligence. In: Voronkov, A. (eds) Logic Programming. Lecture Notes in Computer Science, vol 592. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-55460-2_31
Download citation
DOI: https://doi.org/10.1007/3-540-55460-2_31
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-55460-8
Online ISBN: 978-3-540-47083-0
eBook Packages: Springer Book Archive