Keith Clark
Abstract
PARLOG is a logic programming language in the sense that nearly every definition and query can be read as a sentence of predicate logic. It differs from PROLOG in incorporating parallel modes of evaluation. For reasons of efficient implementation, it distinguishes and separates and-parallel and or-parallel evaluation.
PARLOG relations are divided into two types: single-solution relations and all-solutions relations. A conjunction of single-solution relation calls can be evaluated in parallel with shared variables acting as communication channels for the passing of partial bindings. Only one solution to each call is computed, using committed choice nondeterminism.
A conjunction of all-solutions relation calls is evaluated without communication of partial bindings, but all the solutions may be found by an or-parallel exploration of the different evaluation paths. A set constructor provides the main interface between single-solution relations and all-solutions relations.
This paper is a tutorial introduction to PARLOG. It assumes familiarity with logic programming. Categories and Subject Descriptors: D.l.l [Programming Techniques]: Applicative (Functional)
- 1 BOWEN, D. L., BYRD, L., PEREIRA, F. C. N., PEREIRA, L. M., AND WARREN, D. H. D. DECsystem-10 Prolog user's manual. Dept. of Artificial Intelligence, Univ. of Edinburgh, Nov. 1982.Google Scholar
- 2 BROOA, K., AND GREGORY, S. PARLOG for discrete event simulation. In Proceedings of the 2nd International Logic Programming Conference (Uppsala, July 1984), 301-312.Google Scholar
- 3 CIEPIELEWSKI, A. Towards a computer architecture for or-parallel execution of logic programs. PhD thesis, TRITA-CS-8401, Dept. of Computer Systems, Royal Institute of Technology, Stockholm, May 1984.Google Scholar
- 4 CLARK, K.L. Negation as failure. In Logic and Databases, H. Gallaire and J. Minker, Eds., Plenum Press, New York, 1978.Google ScholarCross Ref
- 5 CLARK, K. L., AND GREGORY, S. A relational language for parallel programming. In Proceedings of the 1981 ACM Conference on Functional Programming Languages and Computer Architecture (Portsmouth, N.H., Oct. 1981), 171-178. Google ScholarDigital Library
- 6 CLARK, K. L., AND GREGORY, S. PARLOG: A parallel logic programming language. Res. rep. DOC 83/5, Dept. of Computing, Imperial College, London, May 1983.Google Scholar
- 7 CLARK, K. L., AND GREGORY, S. Notes on systems programming in PARLOG. In Proceedings of the International Conference on Fifth Generation Computer Systems (Tokyo, Nov. 1984), 299-306.Google Scholar
- 8 CLARK, K. L., AND GREGORY, S. Notes on the implementation of PARLOG. J. Logic Program. 2, 1 (Apr. 1985), 17-42.Google ScholarCross Ref
- 9 CLARK, K. L., AND MCCABE, F. G. micro-PROLOG: Programming in Logic. Prentice-Hall, Englewood Clift~, N.J., 1984. Google ScholarDigital Library
- 10 CLARK, K. L., MCCABE, F. G., AND GREGORY, S. IC-PROLOG language features. In Logic Programming, K. L. Clark and S-A. Tarnlund, Eds., Academic Press, London, 1982, 253-266.Google Scholar
- 11 CLARK, I4{. L., AND TARNLUND, S-A. A first-order theory of data and programs. In Proceedings of the 1FIP Congress 77 (1977), 939-944.Google Scholar
- 12 CLOCKS1N, W. F., AND MELLISH, C.S. Programming in Prolog. Springer-Verlag, New York, 1981. Google ScholarDigital Library
- 13 CONERY, J.S. The AND/OR process model for parallel interpretation of logic programs. PhD thesis, Tech. rep 204, Dept. of Information and Computer Science, Univ. of California, Irvine, June 1983. Google ScholarDigital Library
- 14 CONERY, J. S., AND K1BLER, D.F. Parallel interpretation of logic programs. In Proceedings of the 198I ACM Conference on Functional Programming Languages and Computer Architecture (Portsmouth, N.H., Oct. 1981), 163-170. Google ScholarDigital Library
- 15 DARLINGTON, J., AND REEVE, M.J. ALICE: A multiprocessor reduction machine. In Proceedings of the 1981 ACM Conference on Functional Programming Languages and Computer Architecture (Portsmouth, N.H., Oct. 1981), 65-75. Google ScholarDigital Library
- 16 DEGROOT, D. Restricted and-parallelism. In Proceedings of the International Conference on Fifth Generation Computer Systems (Tokyo, Nov. 1984), 471-478.Google Scholar
- 17 DIJKSTRA, E.W. A Discipline of Programming. Prentice-Hall, Englewood Cliffs, N.J., 1976. Google ScholarDigital Library
- 18 FRIEDMAN, D. P., AND WISE, D.S. CONS should not evaluate its arguments. In Proceedings of the 3rd International Colloquium on Automata, Languages and Programming, Edinburgh University Press, 1976.Google Scholar
- 19 GRE(;OR~, S. How to use PARLOG. Unpublished report, Dept. of Computing, Imperial College, London, Aug. 1984.Google Scholar
- 20 GREGORY, S. Implementing PARLOG on the Abstract PROLOG Machine. Res. rep. DOC 84/23, Dept. of Computing, Imperial College, London, Aug. 1984.Google Scholar
- 21 GREGORY, S. Design, application, and implementation of a parallel logic programming language. PhD thesis, Dept. of Computing, hnperial College, London, Sept. 1985.Google Scholar
- 22 GREGORY, S. The Sequential PARLOG Machine. Res. rep. (in preparation), Dept. of Computing, Imperial College, London, 1985.Google Scholar
- 23 GREGORY, S., NEELY, R., AND RINGWOOD, G.A. PARLOG for specification, verification, and simulation. In Proceedings of the 7th International Symposium on Computer Hardware Description Languages and their Applications (Tokyo, Aug. 1985), 139-148.Google Scholar
- 24 HANSSON, A., HARIDI, S., AND TARNLUND, S-A. Properties of a logic programming language. In Logic Programming, K. L. Clark and S-A. Tarnlund, Eds., Academic Press, London, 1982, 267-280.Google Scholar
- 25 HENDERSON, P. Purely functional operating systems. In Functional Programming and its Applications, J. Darlington, P. Henderson, and D. Turner, Eds., Cambridge University Press, 1982.Google Scholar
- 26 HENDERSON, P., AND MORRIS, J. $. A lazy evaluator. In Proceedings of the 3rdACM Symposium on Principles of Programming Languages ( Jan. 1976), 95-103. Google ScholarDigital Library
- 27 HOARE, C. A. R. Communicating sequential processes. Commun. ACM 21, 8 (Aug. 1978), 666-677. Google ScholarDigital Library
- 28 HOGGER, C.J. Concurrent logic programming. In Logic Programming, K. L. Clark and S-A. Tarnlund, Eds., Academic Press, London, 1982, 199-211.Google Scholar
- 29 HOGGER, C.J. Introduction to Logic Programming. Academic Press, London, 1984. Google ScholarDigital Library
- 30 KAHN, G., AND MACQUEEN, D.B. Coroutines and networks of parallel processes. In Proceedings of the IFIP Congress 77 (1977), 993-998.Google Scholar
- 31 KAHN, K.M. A primitive for the control of logic programs. In Proceedings of the 1984 IEEE International Symposium on Logic Programming (Atlantic City, N.J., Feb. 1984), 242-251.Google Scholar
- 32 KASIr, S., KOHLI, M., AND MINKER, J. PRISM: A parallel inference system for problem solving. In Proceedings of the Logic Programming Workshop 83 (Portugal, June 1983), 123-152.Google Scholar
- 33 KOWALSK!, R.A. Predicate logic as programming language. In Proceedings of the IFIP Congress 74 (1974), 569-574.Google Scholar
- 34 KOWALSKI, R.A. Logic for Problem Solving. North-Holland, New York, 1979. Google ScholarDigital Library
- 35 KOWALSKI, R.A. Logic programming. In Proceedings of the IFIP Congress 83 (1983), 133-145.Google Scholar
- 36 LEVY, J. A unification algorithm for Concurrent Prolog. In Proceedings of the 2nd International Logic Programming Conference (Uppsala, July 1984), 333-341.Google Scholar
- 37 MATSUMOTO, Y. On parallel parsing. Res. Rep., Dept. of Computing, Imperial College, London, 1985.Google Scholar
- 38 McCABE, F.G. Abstract PROLOG machine--a specification. Res. rep. DOC 83/12, Dept. of Computing, hnperial College, London, June 1984.Google Scholar
- 39 MIEROWSKY, C. Design and implementation of Flat Concurrent Prolog. MSc thesis, Dept. of Applied Mathematics, Weizmann Institute of Science, Rehovot, Nov. 1984.Google Scholar
- 40 MIYAZAKi, T., TAKEUCH!, A., AND CHIKAYAMA, T. A sequential implementation of Concurrent Prolog based on the shallow binding scheme. In Proceedings of the IEEE Symposium on Logic Programming (Boston, Mass., July 1985), 110-118.Google Scholar
- 41 MOENS, E., AND YU, B. Implementation of PARLOG on the Warren Machine. Tech. rep., Dept. of Computer Science, Univ. of British Columbia, Vancouver, 1985.Google Scholar
- 42 MOSS, C. D.S. Computing with sequences. In Proceedings of the Logic Programming Workshop 83 (Portugal, June 1983), 623-630.Google Scholar
- 43 MOTO-OKA, T., TANAKA, H., A1DA, H., H1RATA, K., AND MARUYAMA, T. The architecture of a parallel inference engine--PIE. In Proceedings of the International Conference on Fifth Generation Computer Systems (Tokyo, Nov. 1984), 479-488.Google Scholar
- 44 POLLARD, C.H. Parallel execution of Horn clause programs. PhD thesis. Dept. of Computing, Imperial College, London, 1981.Google Scholar
- 45 REEVE, M.J. A BNF description of the ALICE Compiler Target Language. Unpublished rep., Dept. of Computing, Imperial College, London, Mar. 1985.Google Scholar
- 46 SCHWARZ, J. Using annotations to make recursion equations behave. Res. rep. 43, Dept. of Artificial Intelligence, Univ. of Edinburgh, 1977.Google Scholar
- 47 SHAPIRO, E.Y. A subset of Concurrent Prolog and its interpreter. Tech. rep. TR-003, ICOT, Tokyo, Feb. 1983.Google Scholar
- 48 SHAPIRO, E.Y. Systems programming in Concurrent Prolog. In Proceedings of the 11th ACM Symposium on Principles of Programming Languages (Salt Lake City, Utah, Jan. 1984). Google ScholarDigital Library
- 49 SHAPmO, E. Y., ANb MIEROWSKY, C. Fair, biased, and self-balancing merge operators. In Proceedings of the 1984 IEEE International Symposium on Logic Programming (Atlantic City, N.J., Feb. 1984), 83-90.Google Scholar
- 50 TAKEUCHI, A., AND FURUKAWA, $. Interprocess communication in Concurrent Prolog. In Proceedings of the Logic Programming Workshop 83 (Portugal, June 1983), 171-185.Google Scholar
- 51 TURNER, D.A. The semantic elegance of applicative languages. In Proceedings of the 1981 ACM Conference on Functional Programming Languages and Computer Architecture (Portsmouth, N.H., Oct. 1981), 85-92. Google ScholarDigital Library
- 52 UEDA, K. Guarded Horn Clauses. Tech. rep. TR-103, ICOT, Tokyo, June 1985.Google Scholar
- 53 UEDA, K. Concurrent Prolog reexamined. Tech. rep. TRy102 (in preparation), ICOT, Tokyo, 1985.Google Scholar
- 54 WARREN, D. H.D. Logic programming and compiler writing. In Softw. Pract. Exper. 10 (1980), 97-125.Google ScholarCross Ref
- 55 WARREN, D. H.D. An abstract Prolog instruction set. Tech. note 309, SRI International, Menlo Park, Calif., Oct. 1983.Google Scholar
Index Terms
- PARLOG: parallel programming in logic
Recommendations
Parallel logic programming systems
Parallelizing logic programming has attracted much interest in the research community, because of the intrinsic OR- and AND-parallelisms of logic programs. One research stream aims at transparent exploitation of parallelism in existing logic programming ...
Data parallel logic programming in &ACE
SPDP '95: Proceedings of the 7th IEEE Symposium on Parallel and Distributeed Processing&ACE is a high performance parallel Prolog system developed at the Laboratory for Logic, Databases, and Advanced Programming that exploits and-parallelism from Prolog programs. &ACE was developed to exploit MIMD parallelism. However, SPMD parallelism ...
Reviews
Jiri Zlatuska
This paper presents a tutorial introduction to PARLOG, an extensive generalization of PROLOG into a language incorporating parallel modes of evaluation and introducing a number of constructs enabling efficient implementation. PARLOG is a logic programming language in the sense that nearly every definition and query can be read as a sentence of predicate logic. For reasons of efficient implementation, it distinguishes and separates and-paral- lel and or-parallel evaluation and introduces classification of procedure parameters to input and output ones by mode declarations. The concept of input and output modes makes the language not satisfy the ideas of “pure” logic programming. Instead, it enables the language to express the interprocess communication constraints in a very nice way and to obtain a language that is conceptually clean and easy to implement efficiently. The paper extensively discusses various concepts embodied into PARLOG and illustrates them using lots of examples. First, PARLOG and-parallelism is described introducing the concept of shared variables acting as communication channels between the processes, enabling easy realization of various communication modes (such as stream communication or back communication; or, e.g., conversion of eager evaluation to lazy evaluation, etc.). Waiting for a value of a shared variable is the means of process synchronization in PARLOG. Single-solution relation calls are evaluated in parallel, using committed choice nondeterminism: a candidate clause for the reduction is one which “read-only” matches with the call on all its input arguments and which has a successfully terminating guard. Parallel search can also be constrained to force a PROLOG-style sequential search. All-solution relations are provided using normal PROLOG-style sequences of clauses without mode declarations or guards, using special set constructors. These enable implementation by an or-parallel, rather than backtracking, evaluation. The metacall feature of PARLOG is described, being more general than the metacall feature of PROLOG. It reports the succeed/fail results of the call and allows the evaluation of the call to be suspended or prematurely terminated. The PARLOG metacall primitive is also shown to be an ideal tool for implementing a UNIX-style operating system for PARLOG in PARLOG. Finally, an account of the history of PARLOG is given, and the relationship of PARLOG with other work on parallel logic programming (especially with Concurrent PROLOG and Guarded Horn Clauses) is examined. The paper is clearly written, easy to read, and contains a lot of suitable examples thoroughly illustrating the notions being introduced. It presents excellent ideas by putting together concepts from various fields of computer science, such as logic programming, concurrent programming, and applicative languages. However, not only theorists will find it interesting, because it presents a clean, complete, and ready-to-use language, which should suit all the practical needs of parallel logic programming. I suppose the paper to be a real must for everybody who is interested in new ideas concerning logic programming or parallel programming.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments