The concurrent language, Shared Prolog

ABSTRACT

Shared Prolog is a new concurrent logic language. A Shared Prolog system is composed of a set of parallel agents that are Prolog programs extended by a guard mechanism. The programmer controls the granularity of parallelism, coordinating communication and synchronization of the agents via a centralized data structure. The communication mechanism is inherited from the blackboard model of problem solving. Intuitively, the granularity of the logic processes to be elaborated in parallel is large, while the resources shared on the blackboard can be very fined grained. An operational semantics for Shared Prolog is given in terms of a distributed model. Through an abstract notion of computation, the kinds of parallelism supported by the language, as well as properties of infinite computations, such as local deadlocks, are studied. The expressiveness of the language is shown with respect to the specification of two classes of applications: metaprogramming and blackboard systems.

REFERENCES

• 1: AMBRIOLA, V., CIANCARINI, P., CORRADINI, A., AND DE FRANCESCO, N. Towards innovative software engineering environments. Tech. Rep. 6/88, Dipartimento di Informatica, Universit~ di Pisa, 1988, p. 24.
• 2: Isabelle Attali , Paul Franchi-Zannettacci, Inference system environment for Ada, Proceedings of the Ada-Europe International Conference on Ada-components: libraries and tools, p.3-18, November 1987, Stockholm, Sweden
• 3: BALZER, R. Living in the next generation operating system. In Proceedings of IFIP86. IFIP, 1986, pp. 283-291.
• 4: Roberto Bisiani , Alessandro Forin, Multilanguage Parallel Programming of Heterogeneous Machines, IEEE Transactions on Computers, v.37 n.8, p.930-945, August 1988 [doi>10.1109/12.2245]
• 5: K A Bowen, Meta-level programming and knowledge representation, New Generation Computing, v.3 n.4, p.359-383, 1985 [doi>10.1007/BF03037077]
• 6: BROGI~ A., FILIPPI~ R.~ GASPARI~ M., AND TURINI~ F. An expert system 1or data fusion based on a blackboard architecture. In Proceedings of the 8th International Workshop on Expert Systems and their Application (Avignon, France). 1988, pp. 147-166.
• 7: Antonio Brogi , Roberto Gorrieri, A Distributed, Net Oriented Semantics for Delta Prolog, Proceedings of the International Joint Conference on Theory and Practice of Software Development, Volume 1: Advanced Seminar on Foundations of Innovative Software Development I and Colloquium on Trees in Algebra and Programming, p.162-177, March 13-17, 1989
• 8: Randal E. Bryant , Jack B. Dennis, Concurrent programming, Proceedings of the 14th IBM Computer SCience Symposium on Operating Systems Engineering, p.426-451, October 01, 1980
• 9: CARRIERO, N., AND GELERNTER, D. Coordination languages and their significance. Tech. Rep. DCS TR.RR716, Yale Umversity, New Havem Conn. June 1989.
• 10: Nicholas Carriero , David Gelernter, Linda in context, Communications of the ACM, v.32 n.4, p.444-458, April 1989 [doi>10.1145/63334.63337]
• 11: CIANCARINI, P. Specifying and prototyping software engmeering environments. Ph.D. dissertation (in Italian), Universit~ di Pisa, Pisa, Italy, 1988.
• 12: CLARK, K. Negation as failure. In Logic and Data Bases, Gallaire and Minker, Eds. Plenum, New York, 1978, pp. 293-322.
• 13: 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]
• 14: CLARK, K., AND GREGORY, S. Parlog and Prolog umted. In Proceedings of the 4th International Conference on Logic Programming (Melbourne, Australia). 1987, pp. 927-961.
• 15: 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]
• 16: Andrew Davison, Blackboard system in Polka, International Journal of Parallel Programming, v.16 n.5, p.401-424, October 1987 [doi>10.1007/BF01407904]
• 17: Pierpaolo Degano , Ugo Montanari, Concurrent histories: a basis for observing distributed systems, Journal of Computer and System Sciences, v.34 n.2-3, p.422-461, April/June 1987 [doi>10.1016/0022-0000(87)90032-8]
• 18: ENGLEMORE, R., AND MORGAN, T., Eds. Blackboard OEvstems. Addison-Wesley, Reading, Mass., 1988.
• 19: Lee D. Erman , Frederick Hayes-Roth , Victor R. Lesser , D. Raj Reddy, The Hearsay-II Speech-Understanding System: Integrating Knowledge to Resolve Uncertainty, ACM Computing Surveys (CSUR), v.12 n.2, p.213-253, June 1980 [doi>10.1145/356810.356816]
• 20: FOSTER, I. Logic operating systems: Desxgn msues. In Proceedings of the 4th Internatmnal Logtc Programming Con/erence (Melbourne, Australia). 1987, pp. 910-926.
• 21: David Gelernter, Generative communication in Linda, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.1, p.80-112, Jan. 1985 [doi>10.1145/2363.2433]
• 22: David Gelernter, Multiple Tuple Spaces in Linda, Proceedings of the Parallel Architectures and Languages Europe, Volume II: Parallel Languages, p.20-27, June 12-16, 1989
• 23: GERTH, R., CODISH, M., LICHTENSTEIN, Y., AND SHAPIRO, E.Y. Fully abstract denotational semantms for concurrent Prolog. In Proceedmgs of the Conference on Log~c m Computer Science. 1988, pp. 320-335.
• 24: C. A. R. Hoare, Communicating sequential processes, Prentice-Hall, Inc., Upper Saddle River, NJ, 1985
• 25: Ph Jorrand, Term rewriting as a basis for the design of a functional and parallel programming language. A case study: the language FP2, Fundamentals of artificial intelligence: an advanced course, Springer-Verlag New York, Inc., New York, NY, 1986
• 26: KAHN, K., AND MILLER, M. Comments on "Linda in Context." Commun. ACM 10, 5 (May 1989), 1240 1258.
• 27: J. W. Lloyd, Foundations of logic programming; (2nd extended ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 28: Robin Milner, A proposal for standard ML, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.184-197, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802035]
• 29: Penny Nii, The blackboard model of problem solving, AI Magazine, v.7 n.2, p.38-53, Summer 1986
• 30: PLOTKIN, G. A structural approach to operational semantics. Tech. Rep., Aarhus University, 1981.
• 31: SARASWAT. V.A. GHC: Operatlonal semantics, problems and relationship with CP(Q, I, &). In Proeeedings of the 1987 International Symposium on Logic Programming. IEEE Computer Society Press, Los Angeles, 1987, pp. 347 358.
• 32: 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]
• 33: SHAFER, G. A Mathematical Theory of Evidence. Princeton University Press, Princeton, N.J., 1976.
• 34: E. Shapiro, A subset of Concurrent Prolog and its interpreter, Concurrent Prolog, MIT Press, Cambridge, MA, 1988
• 35: SHAPIRO, E.Y. Embedding Linda and other joys of concurrent logic programming. Commun. ACM 33, 10 (Oct. 1989), 1240-1258.
• 36: Ehud Shapiro, The family of concurrent logic programming languages, ACM Computing Surveys (CSUR), v.21 n.3, p.413-510, Sep. 1989 [doi>10.1145/72551.72555]
• 37: Akikazu Takeuchi , Koichi Furukawa, Parallel logic programming languages, Proceedings on Third international conference on logic programming, p.242-254, September 1986, London, United Kingdom
• 38: Kazunori Ueda, Guarded horn clauses, Proceedings of the 4th conference on Logic programming '85, p.168-179, August 1986, Tokyo, Japan

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics
      D.3.2 Language Classifications
          Subjects: Concurrent, distributed, and parallel languages

  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

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

General Terms:
Languages, Theory

Keywords:
blackboard, distributed programming, languages for distributed programming, logic programming, metainterpretation, parallel programming, transition systems