Concurrent constraint programming

ABSTRACT

This paper presents a new and very rich class of (concurrent) programming languages, based on the notion of computing with partial information, and the concomitant notions of consistency and entailment.1 In this framework, computation emerges from the interaction of concurrently executing agents that communicate by placing, checking and instantiating constraints on shared variables. Such a view of computation is interesting in the context of programming languages because of the ability to represent and manipulate partial information about the domain of discourse, in the context of concurrency because of the use of constraints for communication and control, and in the context of AI because of the availability of simple yet powerful mechanisms for controlling inference, and the promise that very rich representational/programming languages, sharing the same set of abstract properties, may be possible. To reflect this view of computation, [Sar89] develops the cc family of languages. We present here one member of the family, cc(↓, →) (pronounced “cc with Ask and Choose”) which provides the basic operations of blocking Ask and atomic Tell and an algebra of behaviors closed under prefixing, indeterministic choice, interleaving, and hiding, and provides a mutual recursion operator. cc(↓, →) is (intentionally!) very similar to Milner's CCS, but for the radically different underlying concept of communication, which, in fact, provides a general—and elegant—alternative approach to “value-passing” in CCS. At the same time it adequately captures the framework of committed choice concurrent logic programming languages. We present the rules of behavior for cc agents, motivate a notion of “visible action” for them, and develop the notion of c-trees and reactive congruence analogous to Milner's synchronization trees and observational congruence. We also present an equational characterization of reactive congruence for Finitary cc(↓, →).

REFERENCES

• Abr89: S. Abramsky. Tutorial on concurrency. Presented at 1989 POPL, January 1989.
• AK84: Hassan Ait-Kaci, A lattice theoretic approach to computation based on a calculus of partially ordered type structures (property inheritance, semantic nets, graph unification), 1984
• BFL85: Ronald J. Brachman, Richard E. Fikes, and Hector J. Levesque. Readings in Knowledge Repre. senation, chapter KRYPTON: A functional approach to Knowledge Representation, pages 411 -429. Morgan Kaufmann Publishers, 1985.
• BHR84: S. D. Brookes , C. A. R. Hoare , A. W. Roscoe, A Theory of Communicating Sequential Processes, Journal of the ACM (JACM), v.31 n.3, p.560-599, July 1984 [doi>10.1145/828.833]
• BIM88: B. Bloom , S. Istrail , A. R. Meyer, Bisimulation can't be traced, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.229-239, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73580]
• CG86: Keith Clark , Steve Gregory, PARLOG: parallel programming in logic, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.1, p.1-49, Jan. 1986 [doi>10.1145/5001.5390]
• CM88: K. Mani Chandy, Parallel program design: a foundation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• Dav83: Martin Davis. Automation of Reasoning: Clas. sical papers on computational logic, chapter The prehistory and early history of automated deduction. Springer Verlag, 1983.
• dBK88: J.W. de Bakker and J.N. Kok. Uniform abstraction, atomicity and contractions in the comparative semantics of Concurrent Prolog. In Proceedings of the Fifth Generation Computer Systems Conference, December 1988.
• Dij76: Edsger Wybe Dijkstra, A Discipline of Programming, Prentice Hall PTR, Upper Saddle River, NJ, 1997
• DvH+88: M. Dincbas, P. van Hentenryck, H. Simonis F. Berthier. The constraint logic programming language CHIP. In Proceedings of the FGCS Conference, November 1988.
• FT89a: Ion Foster and Steve Taylor. Strand: A practical parallel programming language, in North American Logic Programming Conference, 1989.
• FT89b: Ian Foster , Stephen Taylor, Strand: new concepts in parallel programming, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• GCLS88: Rob Gerth, Mike Codish, Yossi Lichtenstein, and Ehud Shapiro. A fully abstract denotational semantics for Flat Concurrent Prolog. ia LICS 88, 1988.
• GMS89: HaJm Gaifman, Michael 2I. Ma.her, and Ehud Shapiro. Reactive behavior semantics for concurrent constraint logic programs. In North American Logic Programming Con/erence, October 1989. To appear.
• Gre87: Steve Gregory, Parallel logic programming in PARLOG: the language and its implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• Hen88: Matthew Hennessy, Algebraic theory of processes, MIT Press, Cambridge, MA, 1988
• JL87: J. Jaffar , J.-L. Lassez, Constraint logic programming, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.111-119, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41635]
• JLL: J. Jaffar, J-.L. Lassez, and C. Lassez. Constraint logic programming: Tutorial. It~EE SLP 87 Tutorial.
• Kah89: Kenneth Kahn. Objects- a fresh look. In Proceedings of the European Conference on Object- Oriented Programming, pages 207-224. Cambridge University Press, July 1989.
• KYSK88: S. Kliger, E. Yardeni, E. Shapiro, and K. Kahn. The language FCP(:,?). In Conference on Fifth Generation Computer Systems, December 1988.
• Llo84: J. W. Lloyd, Foundations of logic programming, Springer-Verlag New York, Inc., New York, NY, 1984
• Mah87: Michael Maher. Logic semantics for a class of committed-choice programs. In 4th International Conference on Logic Programming. MIT Press, May 1987.
• Mah88: Michael Maher. Complete axiomatizations of the algebras of finite, rational and infinite trees. Technical report, IBM T.J. Watson Research Center, 1988.
• Mil83: Robin Milner. Calculi for synchrony and asynchrony. Theoretical Computer Science, 25:267 - 310, 1983.
• Mil84: Robin Milner, Lectures on a Calculus for Communicating Systems, Seminar on Concurrency, Carnegie-Mellon University, p.197-220, July 09-11, 1984
• MR88: Alan Mackworth and Ray Reiter. The logic of depiction. Technical report, University of British Columbia, October 1988.
• OH86: E R Olderog , C A R Hoare, Specification-oriented semantics for communicating processes, Acta Informatica, v.23 n.1, p.9-66, April 1986 [doi>10.1007/BF00268075]
• Sar85: Vijay A. Saraswat, Partial correctness semantics for CP [ , | , &], Proceedings of the Fifth Conference on Foundations of Software Technology and Theoretical Computer Science, p.347-368, December 16-18, 1985
• Sar87a: Vijay A. Sara.swat. Compiling CP(t, I, &) on top of Prolog. Technical Report CMU-CS- 87-174, Computer Science Department, Carnegie Mellon University, October 1987.
• Sar87b: V. A. Saraswat, The concurrent logic programming language CP: Definition and operational semantics, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.49-62, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41630]
• Sar88: Vijay A. Saraswat. A somewhat logical formulation of CLP synchronization primitives. In Proceedings of LP 88. MIT Press, August 1988.
• Sar89: Vijay A. Saraswat, Concurrent constraint programming, MIT Press, Cambridge, MA, 1993
• Sha83: Ehud Shapiro. A subset of Concurrent Prolog and its interpreter. Technical Report CS83-06, Weizmann Institute, 1983.
• Smo88: Gert Smolka. A feature logic with subsorts. Technical Report Lilog Report 33, IBM Deutschland, May 1988.
• SRng: Vijay A. Sara.swat and Martin Rinard. Concurrent constraint programming. Technical report, Xerox PARC, forthcoming.
• Str89: Strand Software Technologies Inc. Strand 88 Users Manual, June 1989.
• SWKS88: Vijay A. Saraswat , Kenneth Kahn , David Weinbaum, Detecting stable properties of networks in concurrent logic programming languages, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.210-222, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62582]
• Ued85: K Ueda. Guarded horn clauses. Technical Report TR-103, IGOT Technical report, June 1985.
• Ued86: K. Ueda. Guarded Horn Clauses. PhD thesis, University of Tokyo, 1986.
• UF88: K. Ueda and K. Furukawa. Tranformation rules for GtIC programs. In 3d International Conference on Fifth Generation Computer Systems, 1988.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.2 SOFTWARE ENGINEERING
        D.2.10 Design**
            Subjects: Methodologies**
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Design, Languages, Theory