A relational language for parallel programming

ABSTRACT

A parallel program often defines a relation not a function. The program constrains the output to lie in some relation R to the input, but the particular output produced during a computation can depend on the time behaviour of component processes. This suggests the use of a relational language as an applicative language for parallel programming. The Horn clause subset of predicate logic is a relational language with an established procedural interpretation for non-deterministic sequential computations [Kowalski 1974]. In this paper we modify and extend that interpretation to define a special purpose parallel evaluator.

REFERENCES

• 1: Clark K.L. {1979}, Predicate logic as a computational formalism. Draft monograph, Dept. of Computing, Imperial College, London.
• 2: Clark K.L., McCabe F.G. and Gregory S. {1981}, IC-Prolog reference manual. Research report, Dept. of Computing, Imperial College, London.
• 3: Dausmann M., Persch G. and Winterstein G. {1979}, Concurrent logic. In Proc. 4th Workshop on AI, Bad Honnef.
• 4: Edsger Wybe Dijkstra, A Discipline of Programming, Prentice Hall PTR, Upper Saddle River, NJ, 1997
• 5: van Emden M.H., de Lucena G.J. and Silva H. de M. {1981}, Predicate logic as a language for parallel programming. Research report, Dept. of Computer Science, Univ. of Waterloo, Ontario.
• 6: Daniel P. Friedman , David S. Wise, An indeterminate constructor for applicative programming, Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.245-250, January 28-30, 1980, Las Vegas, Nevada [doi>10.1145/567446.567470]
• 7: 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]
• 8: Hogger C.J. {1980}, Logic representation of a concurrent algorithm. Research report, Dept. of Civil Engineering, Imperial College, London.
• 9: Kahn G. and MacQueen D.B. {1977}, Coroutines and networks of parallel processes. In Proc. IFIP Congress 77, North Holland, Amsterdam, 993-998.
• 10: Kowalski R.A. {1974}, Predicate logic as programming language. In Proc. IFIP Congress 74, North Holland, Amsterdam, 569-574.
• 11: Robert Kowalski, Logic for problem-solving, North-Holland Publishing Co., Amsterdam, The Netherlands, 1986
• 12: MacQueen D.B. {1979}, Models for distributed computing. Rapport de Recherche 351, INRIA, France.
• 13: George Milne , Robin Milner, Concurrent Processes and Their Syntax, Journal of the ACM (JACM), v.26 n.2, p.302-321, April 1979 [doi>10.1145/322123.322134]
• 14: J. A. Robinson, A Machine-Oriented Logic Based on the Resolution Principle, Journal of the ACM (JACM), v.12 n.1, p.23-41, Jan. 1965 [doi>10.1145/321250.321253]
• 15: Warren D.H.D. {1977}, Implementing Prolog - compiling predicate logic programs. Research reports 39, 40, Dept. of AI, Edinburgh Univ.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Applicative (functional) languages

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.1 Specifying and Verifying and Reasoning about Programs
          Subjects: Logics of programs

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Predicate logic

General Terms:
Languages, Performance, Theory, Verification