The family of concurrent logic programming languages

ABSTRACT

Concurrent logic languages are high-level programming languages for parallel and distributed systems that offer a wide range of both known and novel concurrent programming techniques. Being logic programming languages, they preserve many advantages of the abstract logic programming model, including the logical reading of programs and computations, the convenience of representing data structures with logical terms and manipulating them using unification, and the amenability to metaprogramming. Operationally, their model of computation consists of a dynamic set of concurrent processes, communicating by instantiating shared logical variables, synchronizing by waiting for variables to be instantiated, and making nondeterministic choices, possibly based on the availability of values of variables. This paper surveys the family of concurrent logic programming languages within a uniform operational framework. It demonstrates the expressive power of even the simplest language in the family and investigates how varying the basic synchronization and control constructs affect the expressiveness and efficiency of the resulting languages. In addition, the paper reports on techniques for sequential and parallel implementation of languages in this family, mentions their applications to date, and relates these languages to the abstract logic programming model, to the programming language PROLOG, and to other concurrent computational models and programming languages.

REFERENCES

• 1: ACKERMAN, W. B. 1982. Data flow languages. Computer 15, 2 (Feb.), 15-25.
• 2: Sudhir Ahuja , Nicholas Carriero , David Gelernter, Linda and friends, Computer, v.19 n.8, p.26-34, Aug. 1986 [doi>10.1109/MC.1986.1663305]
• 3: ALl, K. A. M. 1986a. Or-parallel execution of Prolog on a multi-sequential machine. SICS Tech. Rep. Swedish Instit. of Computer Science.
• 4: ALl, K. A. M. 1986b. Or-parallel execution of Horn clause programs based on the WAM and shared control information. SiCS Tech. Rep. Swedish Instit. of Computer Science.
• 5: ALKALAJ, L, AND SHAPIRO, E. 1988. An architectural model for a Flat Concurrent Prolog processor. In Proceedings of the 5th International Conference Symposium on Logic Programming, K. Bowen and R. A. Kowalski, Eds. MIT Press, Cambridge, Mass., pp. 1277-1297.
• 6: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 7: BAGE, G., AND LINDSTROM, G. 1988. Committed choice functional programming. In Proceedings of the International Conference on Fifth Generation Computer Systems. ICOT, Tokyo, pp. 666-674.
• 8: BAHGAT, R., AND GRECORY, S. 1989. Pandora: Nondeterministic parallel logic programming. In Proceedings of the 6th International Conference on Logic Programming (Lisbon, Portugal). MIT Press, Cambridge, Mass.
• 9: or BAKKER, J. W., AND KOK, J. N. 1988. Uniform abstraction, atomicity and contractions in the comparative semantics of Concurrent Prolog. In Proceedings of the International Conference on Fifth Generation Computer Systems. ICOT, Tokyo, pp. 347-355.
• 10: BARON, U., CHASSIN DE KERGOMMEAUX, J., HAIL- PERIN, M., RATCLIFFE, M., ROBERT, P., SYRE, J.-C., AND WESTPHAL, H. 1988. The parallel ECRC Prolog system PEPSys: An overview and evaluation results. In Proceedings of the International Conference on Fifth Generation Computer Systems. ICOT, Tokyo, pp. 841-850.
• 11: BOWEN, D. L., BYRD, L., PEREIRA, L. M., PEREIRA, F. C. N., AND WARREN, D. H. D. 1981. PROLOG on the DECSystem-10 User's Manual. Tech. Rep., Dept. of Artificial Intelligence, Univ. of Edinburgh, Scotland.
• 12: CARLSSON, M. 1987. Freeze, indexing, and other implementation issues in the WAM. In Proceedings of the 4th International Conference on Logic Programming, J.-L. Lassez, Ed. MIT Press, Cambridge, Mass., pp. 40-58.
• 13: 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]
• 14: K. M. Chandy , J. Misra, A paradigm for detecting quiescent properties in distributed computations, Logics and models of concurrent systems, Springer-Verlag New York, Inc., New York, NY, 1989
• 15: K. Mani Chandy, Parallel program design: a foundation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 16: K. Mani Chandy , Leslie Lamport, Distributed snapshots: determining global states of distributed systems, ACM Transactions on Computer Systems (TOCS), v.3 n.1, p.63-75, Feb. 1985 [doi>10.1145/214451.214456]
• 17: CHIKAYAMA, T., AND KIMURA, Y. 1987. Multiple reference management in Flat GHC. In Proceedings of the 4th International Conference on Logic Programming, J.-L. Lassez, Ed. MIT Press, Cambridge, Mass., pp. 276-293.
• 18: CHIKAYAMA, T., SATO, H., AND MIYAZAKI, T. 1988. Overview of the paralle inference machine operating system (PIMOS). In Proceedings of the International Conference on Fifth Generation Computer Systems. ICOT, Tokyo, pp. 230-251.
• 19: CLARK, K. L. 1979. Predicate logic as a computational formalism. Res. Rep. DOC 79/59, Dept. of Computing, Imperial College, London.
• 20: 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]
• 21: CLARK, K. L., AND GREGORY, S. 1984a. Notes on systems programming in PARLOG. In Proceedings of the International Conference on Fifth Generation Computer Systems. ICOT, Tokyo, pp. 299-306.
• 22: CLARK, K. L., AND GREGORY, S. 1984b. Notes on the implementation of PARLOG. Res. Rep. DOC 84/16, Dept. of Computing, Imperial College, London. Also in J. Logic Program. 2, I (1985), 17-42.
• 23: 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]
• 24: CLARK, K. L., AND GREGORY, S. 1987. PARLOG and PROLOG united. In Proceedings of the 4th International Conference on Logic Programming, J.-L. Lassez, Ed. MIT Press, Cambridge, Mass., pp. 927-961.
• 25: CLARK, K. L., AND T:4RNLUND, S.-A. 1977. A firstorder theory of data and programs. In Information Processing 77, B. Gilchrist, Ed. North-Holland, Amsterdam, pp. 939-944.
• 26: CLARK, K. L., MCCABE, F. G., AND GREGORY, S. 1982. IC-PROLOG--Language features. In Logic Programming, K. L. Clark and S.-A. T~irnlund, Eds. Academic Press, London, pp. 253-266.
• 27: CLOCKSIN, W. R., AND ALSHAWI, H. 1986. A method for efficiently executing Horn clause programs using multiple processors. Tech. Rep., Dept. of Computer Science, Cambridge, Univ., Cambridge.
• 28: M. Codish , E. Shapiro, Compiling OR-parallelism into AND-parallelism, New Generation Computing, v.5 n.1, p.45-61, April 1987 [doi>10.1007/BF03037457]
• 29: J. Gallagher , Michael Codish , E. Y. Shapiro, Using safe approximations of fixed points for analysis of logic programs, Meta-programming in logic programming, MIT Press, Cambridge, MA, 1989
• 30: Alain Colmerauer, Opening the Prolog III universe, BYTE, v.12 n.9, p.177-182, Aug. 1987
• 31: Gerardo Costa , Colin Stirling, Weak and strong fairness in CCS, Information and Computation, v.73 n.3, p.207-244, June 1987 [doi>10.1016/0890-5401(87)90013-7]
• 32: CRAMMOND, J. 1985. A comparative study of unification algorithms for Or-parallel execution of logic languages. In Proceedings of the IEEE International Conference on Parallel Processing. IEEE, New York, pp. 131-138.
• 33: James Alexander Crammond, Implementation of committed choice logic languages on shared memory multiprocessors, 1988
• 34: DAVlSON, A. Polka: A PARLOG object oriented language. Dept. of Computing, Imperial College, London, 1988.
• 35: Doug DeGroot , Gary Lindstrom, Logic programming: functions, relations, and equations, Prentice-Hall, Inc., Upper Saddle River, NJ, 1986
• 36: DIJKSTRA, E. W. 1971. Hierarchical ordering of sequential processes. Acta Inf. I, 115-138.
• 37: Edsger W. Dijkstra, Guarded commands, nondeterminacy and formal derivation of programs, Communications of the ACM, v.18 n.8, p.453-457, Aug. 1975 [doi>10.1145/360933.360975]
• 38: Edsger Wybe Dijkstra, A Discipline of Programming, Prentice Hall PTR, Upper Saddle River, NJ, 1997
• 39: DIJKSTRA, E. W., AND SCHOLTEN, C. S. 1980. Termination detection for diffusing computations. Inf. Process. Lett. I 1, 1, 1-4.
• 40: M. H. Van Emden , R. A. Kowalski, The Semantics of Predicate Logic as a Programming Language, Journal of the ACM (JACM), v.23 n.4, p.733-742, Oct. 1976 [doi>10.1145/321978.321991]
• 41: VAN EMDEN, M. H., AND DE LUCENA, G. J. 1982. Predicate logic as a language for parallel programming. In Logic Programming, K. L. Clark and S.-A. T~rnlund, Eds. Academic Press, London.
• 42: ERSHOV, A. P., ET AL., EDS. 1987. Special issue: Selected papers from the Workshop on Partial Evaluation and Mixed Computation. New Generation Comput. 6, 2-3.
• 43: FALASCHI, M., AND LEVI, G. 1988. Finite failures and partial computations in concurrent logic languages. In Proceedings of the International Conference on Fifth Generation Computer Systems. ICOT, Tokyo, pp. 364-373.
• 44: FALASCHI, M., LEVl, G., MARTELLI, M., AND PALA- MIDESSI, G. 1988. A new declarative semantics for logic languages. In Proceedings of the Fifth International Conference Symposium on Logic Programming, K. Bowen and R. A. Kowalski, Eds. MIT Press, Cambridge, Mass., pp. 993-1005.
• 45: FOSTER, I. 1987. Efficient metacontrol in parallel logic programming. Res. Rep. PAR 87/18, Dept. of Computing, Imperial College, London.
• 46: FOSTER, I. 1988a. Parallel implementation of PAR- LOG. In Pro~ceedings of the International Conference on Parallel Processing.
• 47: FOSTER, I. 1988b. PARLOG as a systems programming language. Ph.D. thesis, Dept. of Computing, Imperial College, London.
• 48: Ian Foster , Stephen Taylor, Flat parlog: a basis for comparison, International Journal of Parallel Programming, v.16 n.2, p.87-125, April 1987 [doi>10.1007/BF01379097]
• 49: Nissim Francez, Fairness, Springer-Verlag New York, Inc., New York, NY, 1986
• 50: FRANCEZ, N., AND RODEH, M. 1982. Achieving distributed termination without freezing. IEEE Trans. Softw. Eng. SE-8, 3, 359-385.
• 51: FRIEDMAN, D. P., AND WTSE, D. S. 1978. Aspects of applicative programming for parallel processing. IEEE Trans. Comput. C-27, 4, 289-296.
• 52: Daniel P. Friedman , David S. Wise, An Approach to Fair Applicative Multiprogramming, Proceedings of the International Sympoisum on Semantics of Concurrent Computation, p.203-225, July 02-04, 1979
• 53: 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]
• 54: K. Fuchi , K. Furukawa, The role of logic programming in the fifth generation computer project, New Generation Computing, v.5 n.1, p.3-28, April 1987 [doi>10.1007/BF03037455]
• 55: FURUKAWA, K., AND UEDA, K. 1985. GHC process fusion by program transformation. In Proceedings of the 2nd Conference on Japan Society of Software Science and Technology. pp. 89-92.
• 56: FURUKAWA, K., OKUMURA, A., AND MURAKAMI, M. 1987. Unfolding rules for GHC programs. In Proceedings of the Workshop on Partial and Mixed Computation, D. Bjorner et al., Eds.
• 57: FUTAMURA, Y. 1971. Partial evaluation of computation process--An approach to a compilercompiler. Syst. Comput. Controls 2, 5, 721-728.
• 58: H. Gaifman , E. Shapiro, Fully abstract compositional semantics for logic programs, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.134-142, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75289]
• 59: H. Gaifman , E. Shapiro, Proof theory and semantics of logic programs, Proceedings of the Fourth Annual Symposium on Logic in computer science, p.50-62, June 1989, Pacific Grove, California, United States
• 60: GAWMAN, H., MAHER, M. J., AND SHAPIRO, E. 1989. Reactive behavior semantics for concurrent constraint logic languages, In Proc. 1989, North American Conf. on Logic Programming, Lusk, E., and Overbeck, R., Eds., MIT Press.
• 61: C, ALLAGHER, J. 1983. An approach to the control of logic programs. Ph.D. thesis, Dept. of Computer Science, Trinity College, Dublin.
• 62: GALLAGHER, J. 1986. Transforming logic programs by specialising interpreters. In Proceedings of the 7th European Conference on Artificial Intelligence (Brighton, U.K.). pp. 109-122.
• 63: J. Gallagher , M. Codish , E. Shapiro, Specialisation of Prolog and FCP programs using abstract interpretation, New Generation Computing, v.6 n.2-3, p.159-186, March-April 1988 [doi>10.1007/BF03037136]
• 64: GERTH, R., COOISH, M, LICHTENSTEIN, Y., AND SHAPIRO, E. 1988. Fully abstract denotational semantics for Flat Concurrent Prolog. In Proceedings of the IEEE Symposium on Logic in Computer Science. IEEE, New York, pp. 320-333.
• 65: Steve Gregory, Parallel logic programming in PARLOG: the language and its implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 66: GREGORY, S., NEELY, R., AND RINGWOOD, G. A. 1985. PARLOG for specification, verification and simulation. In Proceedings of the 7th International Symposium on Computer Hardware Description Languages and their Applications, C. J. Koomen and T. Moto-Oka, Eds. Elsevier North- Holland, New York, pp. 139-148.
• 67: S. Gregory , I. T Foster , A. D. Burt , G. A. Ringwood, An abstract machine for the implementation of PARLOG on uniprocessors, New Generation Computing, v.6 n.4, p.389-420, Feb. 1989 [doi>10.1007/BF03037448]
• 68: Robert H. Halstead, Jr., MULTILISP: a language for concurrent symbolic computation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.4, p.501-538, Oct. 1985 [doi>10.1145/4472.4478]
• 69: David Harel, Algorithmics: the spirit of computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 70: D. Harel , A. Pnueli, On the development of reactive systems, Logics and models of concurrent systems, Springer-Verlag New York, Inc., New York, NY, 1989
• 71: HARIDI, S., AND BRAND, P. 1988. ANDORRA PrologmAn integration of Prolog and committed choice languages. In Proceedings of the International Conference on Fifth Generation Computer Systems. ICOT, Tokyo, pp. 745-754.
• 72: HARPER, R., MACQUEEN, D., AND MILNER, R. 1986. Standard ML. Tech. Rep. ECS-LFCS-86-2, Univ. of Edinburgh, Scotland.
• 73: HARSAT, A., AND GINOSAR, R. 1987. CARMEL--A VLSI architecture for Flat Concurrent Prolog. EE PUB. Tech. Rep., Dept. of Computer Science, Technion, Haifa.
• 74: HARSAT, A., AND GINOSAR, R. 1988. CARMEL-2: A second generation VLSI architecture for Flat Concurrent Prolog. In Proceedings of the International Conference on Fifth Generation Compurer Systems. ICOT, Tokyo, pp. 962-969.
• 75: L Hellerstein , E Shapiro, Implementing parallel algorithms in concurrent prolog: The maxiflow experience, Journal of Logic Programming, v.3 n.2, p.157-184, July 1986 [doi>10.1016/0743-1066(86)90021-X]
• 76: HENOERSON, P. 1982. Purely functional operating systems. In Functional Programming and Its Applications, J. Darlington, P. Henderson, and D. Turner, Eds. Cambridge University Press, New York.
• 77: HEWITT, C. 1973. A universal, modular Actor formalism for artificial intelligence. In Proceedings of the International Joint Conference on Artificial Intelligence.
• 78: Carl Hewitt, The challenge of open systems: current logic programming methods may be insufficient for developing the intelligent systems of the future, BYTE, v.10 n.4, p.223-242, April 1985
• 79: HILL, R. 1974. LUSH-resolution and its completeness. DCL Memo 78, Dept. of Artificial Intelligence, Univ. of Edinburgh, Scotland.
• 80: HIRATA, M. 1986a. Letter to the editor. SIGPLAN Not. (May), 16-17.
• 81: HIRATA, M. 1986b. Programming language Doc and its self-description, or, X---X is considered harmful. In Proceedings of the 3rd Conference of Japan Society of Software Science and Technology. pp. 69-72.
• 82: HIRATA, M. 1987. Parallel list processing language Oc and its self-description. Comput. Softw. 4, 3, 41-64. (In Japanese.)
• 83: M. Hirsch , W. Silverman , E. Shapiro, Computation control and protection in the Logix system, Concurrent Prolog: collected papers, MIT Press, Cambridge, MA, 1988
• 84: C. A. R. Hoare, Monitors: an operating system structuring concept, Communications of the ACM, v.17 n.10, p.549-557, Oct. 1974 [doi>10.1145/355620.361161]
• 85: 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]
• 86: C. A. R. Hoare, Communicating sequential processes, Prentice-Hall, Inc., Upper Saddle River, NJ, 1985
• 87: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 88: A. Houri , E. Shapiro, A sequential abstract machine for flat Concurrent Prolog, Concurrent Prolog: collected papers, MIT Press, Cambridge, MA, 1988
• 89: ICHIYOSHI, N., MIYAZAKI, T., AND TAKI, K. 1987. A distributed implementation of Flat GHC on the Multi-PSI. In Proceedings of the 4th International Conference on Logic Programming, J.-L. Lassez, Ed. MIT Press, Cambridge, Mass., pp. 257-275.
• 90: Inmos Corp, Occam Programming Manual, Prentice Hall Trade, 1984
• 91: 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]
• 92: JOHNSON, S. D. 1981. Circuits and systems: Implementing communications with streams. Tech. Rep. 116, Computer Science Dept., Indiana Univ.
• 93: KAHN, K. 1989. Objects: A fresh look, Procedings of ECOOP, European Conference on Object Oriented Programming, Nottingham, England, July.
• 94: KAHN, G., AND MACQUEEN, D. 1977. Coroutines and networks of parallel processes. In Information Processing 77, Proceedings of the IFIP Congress, B. Gilchrist, Ed. North-Holland, Amsterdam, pp. 993-998.
• 95: KAHN, $., SILVERMAN, W., AND SHAPIRO, E. 1988. Logic programs with implicit variables. Unpublished.
• 96: Kenneth Kahn , Eric Dean Tribble , Mark Miller , Daniel G. Bobrow, Vulcan: logical concurrent objects, Research directions in object-oriented programming, MIT Press, Cambridge, MA, 1987
• 97: KIMURA, Y., AND CHIKAYAMA, T. 1987. An abstract KL1 machine and its instruction set. In Proceedings of the iEEE Symposium on Logic Programming (San Francisco, Calif.). IEEE, New York, pp. 468-477.
• 98: KISHIMOTO, M., ET AL. 1987. An evaluation of the FGHC via practical application programs. ICOT Tech. Rep. TR-232, Institute for New Generation Computer Technology, Tokyo.
• 99: KLIGER, S., AND SHAPIRO, E. 1988. A decision tree compilation algorithm for FCP(} ,:,?). in Proceedings of the 5th International Conference Symposium on Logic Programming, K. Bowen and R. A. Kowalski, Eds. MIT Press, Cambridge, Mass., pp. 1315-1336.
• 100: KLIGER, S., YARDENI, E., KAHN, K., AND SHAPIRO, E. 1988. The language FCP(:,?). In Proceedings of the International Conference on Fifth Generation Computer Systems. ICOT, Tokyo, pp. 763- 773.
• 101: Robert Kowalski, Logic for problem-solving, North-Holland Publishing Co., Amsterdam, The Netherlands, 1986
• 102: KUNG, H. T. 1982, Why systolic architectures? Computer 15, 1, 37-46.
• 103: KUSALIK, A. j. 1984. Bounded-wait merge in Shapiro's Concurrent Prolog. New Generation Comput. 1, 12, 157-169.
• 104: Ten-Hwang Lai, Termination detection for dynamically distributed systems with non-first-in-first-out communication, Journal of Parallel and Distributed Computing, v.3 n.4, p.577-599, December 1, 1986 [doi>10.1016/0743-7315(86)90015-8]
• 105: LAM, M., AND GREGORY, S. 1987. PARLOG and ALICE: A marriage of convenience. In Proceedings of the 4th International Conference on Logic Programming, J.-L. Lassez, Ed. MIT Press, Cambridge, Mass., pp. 294-310.
• 106: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 107: J.-L. Lassez , M. J. Maher , K. Marriott, Unification revisited, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 108: Lrvl, G. 1988. Models, unfolding rules and fixpoint semantics. In Proceedings of the 5th International Conference Symposium on Logic Programming, K. Bowen and R. A. Kowalski, Eds. MIT Press, Cambridge, Mass., pp. 1649-1665.
• 109: LEVI, G., AND PALAMIDESSI, C. 1987. An approach to the declarative semantics of synchronization in logic languages. In Proceedings of the 4th international Conference on Logic Programming, J.-L. Lassez, Ed. MIT Press, Cambridge, Mass., pp. 877-893.
• 110: LEVi, G., AND SARDU, G. 1987. Partial evaluation of meta-programs in a multiple world's logic language. In Workshop on Partial Evaluation and Mixed Computation, D. Bjorner, A. P. Ershov, and N. D. Jones, Eds.
• 111: LEVY, J. 1984. A unification algorithm for Concurrent Prolog. In Proceedings of the 2nd International Conference on Logic Programming, S.-A. T~irnlund, Ed. (Uppsala, Sweden). Pp. 333-341.
• 112: Jacob Levy, A GHC abstract machine and instruction set, Proceedings on Third international conference on logic programming, p.157-171, September 1986, London, United Kingdom
• 113: LEVY, J. 1988. Concurrent Prolog and related lan~ guages. Ph.D. thesis, Dept. of Computer Science, The Weizmann Institute of Science, Rehovot, Israel.
• 114: LEVY, J., AND FRIEDMAN, N. 1986. Concurrent Prolog implementations--two new schemes. Tech. Rep. CS86-13, Dept. of Computer Science, The Weizmann Institute of Science, Rehovot, Israel.
• 115: J. Levy , E. Shapiro, Translation of safe GHC and safe Concurrent Prolog to FCP, Concurrent Prolog: collected papers, MIT Press, Cambridge, MA, 1988
• 116: J. Levy , E. Shapiro, CFL—A concurrent functional language embedded in a concurrent logic programming environment, Concurrent Prolog: collected papers, MIT Press, Cambridge, MA, 1988
• 117: Yossi Lichtenstein , Ehud Shapiro, Concurrent algorithmic debugging, Proceedings of the 1988 ACM SIGPLAN and SIGOPS workshop on Parallel and distributed debugging, p.248-260, May 05-06, 1988, Madison, Wisconsin, United States
• 118: Y. Lichtenstein , M. Codish , E. Shapiro, Representation and enumeration of flat Concurrent Prolog computations, Concurrent Prolog: collected papers, MIT Press, Cambridge, MA, 1988
• 119: LICHTENSTEIN, Y., AND SHAPIRO, E. 1988. Abstract algorithmic debugging. In Proceedings of the 5th International Conference and Symposium on Logic Programming, K. Bowen and R. A. Kowalski, Eds. MIT Press, Cambridge, Mass., pp. 1315-1336.
• 120: J. W. Lloyd, Foundations of logic programming; (2nd extended ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 121: LUSK, E., BUTLER, R., DISZ, T., OLSON, R., OVER- BEEK, R., STEVENS, R., WARREN, D. H. D., CALD- ERWOOD, A., SZEREDI, P., HARIDI, S., BRAND, P., CARLSSON, M., CIEPIELEWSKI, A., AND HAUSMAN, B. 1988. The Aurora Or-Parallel Prolog system. In Proceedings of the International Conference on Fifth Generation Computer Systems. ICOT, Tokyo, pp. 819-830.
• 122: M. J. Maher, Equivalences of logic programs, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 123: MAHER, M. J. 1987b. Logic semantics for a class of committed-choice programs. In Proceedings of the 4th International Conference on Logic Programming, J.-L. Lassez, Ed. MIT Press, Cambridge, Mass., pp. 858-876.
• 124: Z Manna , Amir Pnueli, Specification and Verification of Concurrent Programs by For-All Automata, Stanford University, Stanford, CA, 1988
• 125: MATTERN, F. 1987. Algorithms for distributed termination detection. Distrib. Comput. 2, 161-175.
• 126: MIEROWSKY, C., TAYLOR, S., SHAPIRO, E., LEVY, J., AND SArRA, S. 1985. The design and implementation of Flat Concurrent Prolog. Tech. Rep. CS85-09, Dept. of Computer Science, The Weizmann Institute of Science, Rehovot, Israel.
• 127: R. Milner, A Calculus of Communicating Systems, Springer-Verlag New York, Inc., Secaucus, NJ, 1982
• 128: Jayadev Misra, Distributed discrete-event simulation, ACM Computing Surveys (CSUR), v.18 n.1, p.39-65, March 1986 [doi>10.1145/6462.6485]
• 129: MIYAZAKI, T., TAKEUCHI, A., AND CHIKAYAMA, W. 1985. A sequential implementation of Concurrent Prolog based on the shallow binding scheme. In IEEE Symposium on Logic Programming, IEEE, New York, pp. 110-118. (Also Chap. 37 in {Shapiro 1987a}.)
• 130: MURAKAMI, M. 1988. A declarative semantics of parallel logic programs with perpetual processes. In Proceedings of the International Conference on Fifth Generation Computer Systems. ICOT, Tokyo, pp. 374-381.
• 131: NAISH, L. 1984. MU-Prolog 3.1db Reference Manual. Intern. Memo., Dept. of Computer Science, Univ. of Melbourne, Melbourne, Australia.
• 132: Bruce Jay Nelson, Remote procedure call, 1981
• 133: Martin Nilsson , Hidehiko Tanaka, -FLENG Prolog- the language which turns supercomputers into parallel Prolog machines, The 5th Conference on Logic programming '86, p.170-179, July 1987, Tokyo, Japan
• 134: M. Nilsson , H. Tanaka, The art of building a parallel logic programming system, Proceedings of the 6th Conference on Logic programming '87, p.95-105, July 1988, Tokyo, Japan
• 135: NILSSON, M., AND TANAKA, H. 1988a. Massively parallel implementation of Flat GHC on the connection machine. In Proceedings of the International Conference on Fifth Generation Computer Systems. ICOT, Tokyo, pp. 1031-1040.
• 136: NILSSON, M., AND TANAKA, H. 1988b. A Flat GHC Implementation for supercomputers. In Proceedings of the 5th International Conference Symposium on Logic Programming, K. Bowen and R. A. Kowalski, Eds. MIT Press, Cambridge, Mass., pp. 1337-1350.
• 137: OHKi, M., ET AL. 1987. An object-oriented programming language based on a parallel logic programming language KL1. ICOT Tech. Rep. TR-222, Institute for New Generation Computer Technology, Tokyo.
• 138: OKABE, Y., AND YAJIMA, S. 1988. Parallel computational complexity of logic programs and alternating turing machines. In Proceedings of the International Conference on Fifth Generation Computer Systems. ICOT, Tokyo, pp. 356-363.
• 139: OKUMURA, A., AND MATSUMOTO, Y. 1987. Parallel programming with layered streams. In Proceedings of the IEEE Symposium on Logic Programming (San Francisco, Calif.). IEEE, New York, pp. 224-231.
• 140: PEREIRA, L. M., AND NASR, R. 1984. Delta-Prolog: A distributed logic programming language. In Proceedings of the International Conference on Fifth Generation Computer Systems. ICOT, Tokyo, pp. 283-291.
• 141: PICCA, R., BELLONE, J., AND LEVY, J. 1987. Orparallel And-interleaving execution of Concurrent Prolog. Tech. Rep. CS87-07, Dept. of Computer Science, The Weizmann Institute of Science, Rehovot, Israel.
• 142: A Pnueli, Applications of temporal logic to the specification and verification of reactive systems: a survey of current trends, Current trends in concurrency. Overviews and tutorials, Springer-Verlag New York, Inc., New York, NY, 1986
• 143: Raghu Ramakrishnan , Abraham Silberschatz, Annotations for distributed programming in logic, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.255-262, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512668]
• 144: RECHES, E., GUDES, E., AND SHAPIRO, E. 1988. Parallel access to a distributed database and its implementation in Flat Concurrent Prolog. Tech. Rep. CS88-11, Dept. of Computer Science, The Weizmann Institute of Science, Rehovot, Israel.
• 145: G. A. Ringwood, Parlog86 and the dining logicians, Communications of the ACM, v.31 n.1, p.10-25, Jan. 1988 [doi>10.1145/35043.35044]
• 146: RINGWOOD, G. A. 1987. Pattern-directed, Markovian, linear, guarded definite clause resolution. Dept. of Computing, Imperial College, London.
• 147: 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]
• 148: SArRA, S. 1986. Partial evaluation of Concurrent Prolog and its implications. M.S. thesis and Tech. Rep. CS86-24, Dept. of Computer Science, The Weizmann Institute of Science, Rehovot, israel.
• 149: SAFRA, S., AND SHAPIRO, E. 1986. Meta-interpreters for real. In Information Processing 86. North- Holland, Amsterdam, pp. 271-278. (Also Chap. 25 in {Shapiro 1987a}.)
• 150: 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
• 151: SARASWAT, V. A. 1986. Problems with Concurrent Prolog. Tech. Rep. 86-100, Dept. of Computer Science, Carnegie-Mellon Univ., Pittsburgh, Pa.
• 152: V. A. Saraswat, Merging many streams efficiently: The importance of atomic commitment, Concurrent Prolog, MIT Press, Cambridge, MA, 1988
• 153: SARASWAT, V. A. 1987b, A compiler of CP(~,{,&) on top of Prolog. Tech. Rep. CS-87-174, Dept. of Computer Science, Carnegie-Mellon Univ., Pittsburgh, Pa.
• 154: 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]
• 155: SARASWAT, V. A. 1987d. The language GHC: Operational semantics, problems and relationship with CP{~,I }. In Proceedings of the IEEE Symposium on Logic Programming (San Francisco, Calif.). IEEE, New York, pp. 347-358.
• 156: SARASWAT, V. A. 1988a. A somewhat logical formulation of CLP synchronization primitives. In Proceedings of the 5th International Conference Symposium on Logic Programming, K. Bowen and R. A. Kowalski, Eds. MIT Press, Cambridge, Mass., pp. 1298-1314.
• 157: Vijay Anand Saraswat , Dana S. Scott, Concurrent constraint programming languages, 1989
• 158: 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]
• 159: Ehud Y. Shapiro, Algorithmic Program DeBugging, MIT Press, Cambridge, MA, 1983
• 160: SHAPIRO, E. 1983b. A subset of Concurrent Prolog and its interpreter. ICOT Tech, Rep. TR-003, Institute for New Generation Computer Technology, Tokyo. (Also Chap. 2 in {Shapiro 1987a}.)
• 161: Ehud Y. Shapiro, Alternation and the computational complexity of logic programs, Journal of Logic Programming, v.1 n.1, p.19-33, June 1984 [doi>10.1016/0743-1066(84)90021-9]
• 162: SHAPIRO, E. 1984b. Systolic programming: A paradigm of parallel processing. In Proceedings of the International Conference on Fifth Generation Computer Systems. ICOT, Tokyo, pp. 458-471. (Also Chap. 7 in {Shapiro 1987a}.)
• 163: Ehud Shapiro, Concurrent Prolog: A progress report, Computer, v.19 n.8, p.44-58, Aug. 1986 [doi>10.1109/MC.1986.1663307]
• 164: E. Shapiro, Concurrent prolog: collected papers, MIT Press, Cambridge, MA, 1987
• 165: E. Shapiro, Or-parallel Prolog in flat Concurrent Prolog, Concurrent Prolog: collected papers, MIT Press, Cambridge, MA, 1988
• 166: SHAPIRO, E. 1989. Embedding Linda and other joys of concurrent logic programming. Tech. Rep. CS- 89-07, Dept. of Computer Science, The Weizmann Institute of Science, Rehovot, Israel.
• 167: SHAPIRO, E., AND MIER0WSKY, C. 1984. Fair, biased, and self-balancing merge operators: Their specification and implementation in Concurrent Prolog. New Generation Comput. 2, 3, 221-240. (Also Chap. 14 in {Shapiro 1987a}.)
• 168: E Shapiro , S Safra, Multiway merge with constant delay in concurrent Prolog, New Generation Computing, v.4 n.2, p.211-216, 1986 [doi>10.1007/BF03037442]
• 169: SHAPIRO, E., AND TAKEUCHI, A. 1983. Objectoriented programming in Concurrent Prolog. New Generation Comput. 1, 1, 25-49. (Also Chap. 29 in {Shapiro 1987a}.)
• 170: W. Silverman , M. Hirsch , A. Houri , E. Shapiro, The Logix system user manual version 1.21, Concurrent Prolog: collected papers, MIT Press, Cambridge, MA, 1988
• 171: STERLING, L. S., AND SHAPIRO, E. 1986. The Art of Protog. MIT Press, Cambridge, Mass.
• 172: SUZUKI, N. 1986. Experience with specification and verification of complex computer using Concurrent Prolog. In Logic Programming and Its Applications, D. H. D. Warren and M. van Caneghem, Eds. Ablex, New Jersey, pp. 188-209.
• 173: SZOKE, D. 1987. Distributed Flat Concurrent Prolog on a network architecture. M.S. thesis, Dept. of Computer Science, The Weizmann Institute of Science, Rehovot, Israel.
• 174: TAKEDA, Y., NAKASHIMA, H., MASUDA, K., CHIKA- YAMA, T., AND TAKI, K. 1988. A load balancing mechanism for large scale multiprocessor systems and its implementation. In Proceedings of the International Conference on Fifth Generation Computer Systems. ICOT, Tokyo, pp. 978-986.
• 175: TAKEUCHI, A. 1983. How to solve it in Concurrent Prolog.
• 176: A. Takeuchi, Algorithm debugging of GHC programs and its implementation in GHC, Concurrent Prolog: collected papers, MIT Press, Cambridge, MA, 1988
• 177: TAKEUCHI, A., AND FURUKAWA, g. 1985. Boundedbuffer communication in Concurrent Prolog. New Generation Comput. 3, 2, 145-155. (Also Chap. 18 in {Shapiro 1987a}.)
• 178: TAKEUCHI, A., AND FURUKAWA, K. 1986. Partial evaluation of Prolog programs and its application to meta-programming. In Information Processing 86. North-Holland, Amsterdam, pp. 415-420.
• 179: TAKEUCHI, A., ET AL. 1987. A description language with AND/OR parallelism for concurrent systems and its stream-based realization. ICOT Tech. Rep. TR-229, Institute for New Generation Computer Technology, Tokyo.
• 180: TAMAKI, H. 1985. A distributed unification scheme for systolic programs. In Proceedings of the International Conference on Parallel Processing. Pp. 552-559.
• 181: J. Tanaka, A simple programming system written in GHC and its reflective operations, Proceedings of the seventh conference on Logic programming '88, p.108-121, September 1989, Tokyo, Japan
• 182: TANAKA, J. 1988b. Meta-interpreters and reflective operations in GHC. In Proceedings of the International Conference on Fifth Generation Computer Systems. ICOT, Tokyo, pp. 774-783.
• 183: Jiro Tanaka , Kazunori Ueda , Toshihiko Miyazaki , Akikazu Takeuchi , Yuji Matsumoto , Koichi Furukawa, Guarded horn clauses and experiences with parallel logic programming, Proceedings of 1986 ACM Fall joint computer conference, p.948-954, November 1986, Dallas, Texas, United States
• 184: TAYLOR, H. 1988a. Localizing the GHC suspension test. In Proceedings of the 5th International Conference Symposium on Logic Programming, K. Bowen and R. A. Kowalski, Eds. MIT Press, Cambridge, Mass., pp. 1257-1271.
• 185: TAYLOR, S. 1988b. Parallel logic programming techniques. Ph.D. thesis, Dept. of Computer Science, The Weizmann Institute of Science, Rehovot, Israel.
• 186: TAYLOR, $., AND FOSTER, I. 1988. Strand language reference manual. Tech. Rep. PAR 88/10, Dept. of Computing, Imperial College, London.
• 187: TAYLOR, S., AND SHAPIRO, E. 1988. An improved parallel algorithm for Flat Concurrent Prolog. Tech. Rep. CS88-09, Dept. of Computer Science, The Weizmann Institute of Science, Rehovot, Israel.
• 188: Stephen Taylor , Evyatar Av-Ron , Ehud Shapiro, A layered method for process and code mapping, New Generation Computing, v.5 n.2, p.185-205, Oct. 1987 [doi>10.1007/BF03037398]
• 189: Stephen Taylor , Shmuel Safra , Ehud Shapiro, A parallel implementation of flat concurrent prolog, International Journal of Parallel Programming, v.15 n.3, p.245-275, June 1986 [doi>10.1007/BF01414556]
• 190: S. Taylor , R. Shapiro , E. Shapiro, FCP: a summary of performance results, Proceedings of the third conference on Hypercube concurrent computers and applications, p.1364-1373, January 1989, Pasadena, California, United States [doi>10.1145/63047.63092]
• 191: Stephen Taylor , Lisa Hellerstein , Shmuel Safra , Ehud Shapiro, Notes on the complexity of systolic programs, Journal of Parallel and Distributed Computing, v.4 n.3, p.250-265, June 1, 1987 [doi>10.1016/0743-7315(87)90036-0]
• 192: TICK, E. 1988. A performance comparison of Andand Or-parallel logic programming architectures. ICOT Tech. Rep. TR-421, Institute for New Generation Computer Technology, Tokyo.
• 193: TRIBBLE, E. D., MILLER, M. S., KAHN, K., BOBROW, D. G., AND ABBOTT, C. 1987. Channels: A generalization of streams. In Proceedings of the 4th International Conference of Logic Programming, J.-L. Lassez, Ed. MIT Press, Cambridge, Mass., pp. 839-857. (Also Chap. 17 in {Shapiro 1987a}.)
• 194: UCHIDA, S., TAKI, K., NAKASHiMA, K., GOTO, A., AND CHiKAYAMA, T. 1988. Research and development of the parallel inference system in the intermediate stage of the FGCS project. In Proceedings of the International Conference on Fifth Generation Computer Systems. ICOT, Tokyo, pp. 16-36.
• 195: VEDA, K. 1985. Concurrent Prolog re-examined. ICOT Tech. Rep. TR-102, Institute for New Generation Computer Technology, Tokyo.
• 196: VEDA, K. 1986a. Guarded Horn Clauses. Ph.D. thesis, Information Engineering Course, Univ. of Tokyo, Tokyo.
• 197: Kazunori Ueda, Guarded horn clauses, Proceedings of the 4th conference on Logic programming '85, p.168-179, August 1986, Tokyo, Japan
• 198: VEDA, K. 1986c. Guarded Horn Clauses: A parallel logic programming language with the concept of a guard. ICOT Tech. Rep. TR-208, Institute for New Generation Computer Technology, Tokyo (revised in 1987). (Also in Nivat, M., and Fuchi, K., Eds. 1988. Programming of Future Generation Computers. North-Holland, Amsterdam, pp. 441-456.)
• 199: K. Ueda, Making exhaustive search programs deterministic, New Generation Computing, v.5 n.1, p.29-44, April 1987 [doi>10.1007/BF03037456]
• 200: UEDA, K. 1987b. Making exhaustive search programs deterministic, Part II. ICOT Tech. Rep. TR-249, institute for New Generation Computer Technology, Tokyo.
• 201: VEDA, K. 1989. Parallelism in logic programming. In Proceedings of the IFiP Congress.
• 202: UEDA, $., AND CHIKAYAMA, T. 1985. Concurrent Prolog compiler on top of Prolog. In Proceedings of the IEEE Symposium on Logic Programming. pp. 119-126.
• 203: VEDA, $., AND FURUKAWA, $. Transformation rules for GHC programs. In Proceedings of the International Conference on Fifth Generation Computer Systems. ICOT, Tokyo, pp. 582-591.
• 204: Phil Vasey, Qualified answers and their application to transformation, Proceedings on Third international conference on logic programming, p.425-432, September 1986, London, United Kingdom
• 205: WARREN, D. H. D. 1983. An abstract Prolog instruction set. Tech. Rep. 309, Artificial Intelligence Center, SRI International, Menlo Park, Calif.
• 206: D. H. D. Warren, Or-parallel execution models of prolog, II and Colloquium on Functional and Logic Programming and Specifications (CFLP) on TAPSOFT '87: Advanced Seminar on Foundations of Innovative Software Development, p.243-259, March 1987, Pisa, Italy
• 207: WEINBAUM, D., AND SHAPIRO, E. 1987. Hardware description and simulation using Concurrent Prolog. In Proceedings of CHDL '87. Elsevier Science Publishing, pp. 9-27. (Also Chap. 36 in {Shapiro 1987a}.)
• 208: YANG, R. 1986. A parallel logic programming language and its implementation. Ph.D. thesis, Dept. of Computer Science, Keio Univ., Keio.
• 209: Rong Yang , Hideo Aiso, P-Prolog: a parallel logic programming language based on exclusive relation, Proceedings on Third international conference on logic programming, p.255-269, September 1986, London, United Kingdom
• 210: E. Yardeni , E. Shapiro, A type system for logic programs, Concurrent Prolog: collected papers, MIT Press, Cambridge, MA, 1988

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Very high-level languages
          Nouns: Prolog
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures; Control structures

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Alternation and nondeterminism; Parallelism and concurrency
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Operational semantics
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

General Terms:
Algorithms, Design, Languages, Performance, Theory