PARLOG: parallel programming in logic

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)

REFERENCES

• 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.
• 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.
• 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.
• 4: CLARK, K.L. Negation as failure. In Logic and Databases, H. Gallaire and J. Minker, Eds., Plenum Press, New York, 1978.
• 5: Keith L. Clark , Steve Gregory, A relational language for parallel programming, Proceedings of the 1981 conference on Functional programming languages and computer architecture, p.171-178, October 18-22, 1981, Portsmouth, New Hampshire, United States [doi>10.1145/800223.806776]
• 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.
• 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.
• 8: CLARK, K. L., AND GREGORY, S. Notes on the implementation of PARLOG. J. Logic Program. 2, 1 (Apr. 1985), 17-42.
• 9: K. L Clark , F. G McCabe, Micro-PROLOG: programming in logic, Prentice-Hall, Inc., Upper Saddle River, NJ, 1984
• 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.
• 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.
• 12: W. F. Clocksin , C. S. Mellish, Programming in Prolog, Springer-Verlag New York, Inc., New York, NY, 1987
• 13: John Simpson Conery, The and/or process model for parallel interpretation of logic programs, 1983
• 14: John S. Conery , Dennis F. Kibler, Parallel interpretation of logic programs, Proceedings of the 1981 conference on Functional programming languages and computer architecture, p.163-170, October 18-22, 1981, Portsmouth, New Hampshire, United States [doi>10.1145/800223.806775]
• 15: John Darlington , Mike Reeve, ALICE a multi-processor reduction machine for the parallel evaluation CF applicative languages, Proceedings of the 1981 conference on Functional programming languages and computer architecture, p.65-76, October 18-22, 1981, Portsmouth, New Hampshire, United States [doi>10.1145/800223.806764]
• 16: DEGROOT, D. Restricted and-parallelism. In Proceedings of the International Conference on Fifth Generation Computer Systems (Tokyo, Nov. 1984), 471-478.
• 17: Edsger Wybe Dijkstra, A Discipline of Programming, Prentice Hall PTR, Upper Saddle River, NJ, 1997
• 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.
• 19: GRE(;OR~, S. How to use PARLOG. Unpublished report, Dept. of Computing, Imperial College, London, Aug. 1984.
• 20: GREGORY, S. Implementing PARLOG on the Abstract PROLOG Machine. Res. rep. DOC 84/23, Dept. of Computing, Imperial College, London, Aug. 1984.
• 21: GREGORY, S. Design, application, and implementation of a parallel logic programming language. PhD thesis, Dept. of Computing, hnperial College, London, Sept. 1985.
• 22: GREGORY, S. The Sequential PARLOG Machine. Res. rep. (in preparation), Dept. of Computing, Imperial College, London, 1985.
• 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.
• 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.
• 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.
• 26: Peter Henderson , James H. Morris, Jr., A lazy evaluator, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.95-103, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811543]
• 27: C. A. R. Hoare, Communicating sequential processes, Communications of the ACM, v.21 n.8, p.666-677, Aug. 1978 [doi>10.1145/359576.359585]
• 28: HOGGER, C.J. Concurrent logic programming. In Logic Programming, K. L. Clark and S-A. Tarnlund, Eds., Academic Press, London, 1982, 199-211.
• 29: Christopher John Hogger, Introduction to logic programming, Academic Press Professional, Inc., San Diego, CA, 1984
• 30: KAHN, G., AND MACQUEEN, D.B. Coroutines and networks of parallel processes. In Proceedings of the IFIP Congress 77 (1977), 993-998.
• 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.
• 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.
• 33: KOWALSK!, R.A. Predicate logic as programming language. In Proceedings of the IFIP Congress 74 (1974), 569-574.
• 34: Robert Kowalski, Logic for problem-solving, North-Holland Publishing Co., Amsterdam, The Netherlands, 1986
• 35: KOWALSKI, R.A. Logic programming. In Proceedings of the IFIP Congress 83 (1983), 133-145.
• 36: LEVY, J. A unification algorithm for Concurrent Prolog. In Proceedings of the 2nd International Logic Programming Conference (Uppsala, July 1984), 333-341.
• 37: MATSUMOTO, Y. On parallel parsing. Res. Rep., Dept. of Computing, Imperial College, London, 1985.
• 38: McCABE, F.G. Abstract PROLOG machine--a specification. Res. rep. DOC 83/12, Dept. of Computing, hnperial College, London, June 1984.
• 39: MIEROWSKY, C. Design and implementation of Flat Concurrent Prolog. MSc thesis, Dept. of Applied Mathematics, Weizmann Institute of Science, Rehovot, Nov. 1984.
• 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.
• 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.
• 42: MOSS, C. D.S. Computing with sequences. In Proceedings of the Logic Programming Workshop 83 (Portugal, June 1983), 623-630.
• 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.
• 44: POLLARD, C.H. Parallel execution of Horn clause programs. PhD thesis. Dept. of Computing, Imperial College, London, 1981.
• 45: REEVE, M.J. A BNF description of the ALICE Compiler Target Language. Unpublished rep., Dept. of Computing, Imperial College, London, Mar. 1985.
• 46: SCHWARZ, J. Using annotations to make recursion equations behave. Res. rep. 43, Dept. of Artificial Intelligence, Univ. of Edinburgh, 1977.
• 47: SHAPIRO, E.Y. A subset of Concurrent Prolog and its interpreter. Tech. rep. TR-003, ICOT, Tokyo, Feb. 1983.
• 48: Ehud Shapiro, Systems programming in concurrent prolog, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.93-105, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800520]
• 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.
• 50: TAKEUCHI, A., AND FURUKAWA, $. Interprocess communication in Concurrent Prolog. In Proceedings of the Logic Programming Workshop 83 (Portugal, June 1983), 171-185.
• 51: D. A. Turner, The semantic elegance of applicative languages, Proceedings of the 1981 conference on Functional programming languages and computer architecture, p.85-92, October 18-22, 1981, Portsmouth, New Hampshire, United States [doi>10.1145/800223.806766]
• 52: UEDA, K. Guarded Horn Clauses. Tech. rep. TR-103, ICOT, Tokyo, June 1985.
• 53: UEDA, K. Concurrent Prolog reexamined. Tech. rep. TRy102 (in preparation), ICOT, Tokyo, 1985.
• 54: WARREN, D. H.D. Logic programming and compiler writing. In Softw. Pract. Exper. 10 (1980), 97-125.
• 55: WARREN, D. H.D. An abstract Prolog instruction set. Tech. note 309, SRI International, Menlo Park, Calif., Oct. 1983.

INDEX TERMS

Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Applicative (functional) languages
          Nouns: PARLOG; Prolog
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Logic programming

General Terms:
Design, Languages