Systems programming in concurrent prolog

ABSTRACT

Concurrent Prolog [28] combines the logic programming computation model with guarded-command indeterminacy and dataflow synchronization. It will form the basis of the Kernel Language [21] of the Parallel Inference Machine [36], planned by Japan's Fifth Generation Computers Project. This paper explores the feasibility of programming such a machine solely in Concurrent Prolog (in the absence of a lower-level programming language), by implementing in it a representative collection of systems programming problems.

REFERENCES

• 1: Arvind , J. Dean Brock, Streams and Managers, Proceedings of the 14th IBM Computer SCience Symposium on Operating Systems Engineering, p.452-465, October 01, 1980
• 2: Daniel G. Bobrow and Mark Stefik The LOOPS Manual (preliminary version), Memo KB-VLSI-81-13, Xerox PARC. 1983.
• 3: Keith L. Clark and Stan-Ake Tarnlund, A first-order theory of data and programs, in Information Processing 77, B. Gilechrist (ed.), pp.939-944, North-Holland, 1977.
• 4: 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]
• 5: Keith L. Clark and Steve Gregory PARLOG: A Parallel Logic Programming Language Research report DOC 83/5, Department of Computing, Imperial College of Science and Technology, May 1983.
• 6: J.R. Ellis, N. Mishkin, and S.R. Wood Tools: an Environment for Timeshared Computing an Programming, Research Report 232, Department of Computer Science, Yale University, 1982.
• 7: Edsger Wybe Dijkstra, A Discipline of Programming, Prentice Hall PTR, Upper Saddle River, NJ, 1997
• 8: 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]
• 9: K. Furukawa, A. Takeuchi, and S. Kunifuji Mandala: A Knowledge Programming Language on Concurrent Prolog, ICOT Technical Memorandum TM-0028 (in Japanese), 1983.
• 10: David Gelenter A Note on Systems Programming in Concurrent Prolog, Unpublished manuscript, Yale University, 1983.
• 11: Peter Henderson Purely Functional Operating Systems in Functional Programming and its Applications, P. Henderson and D.A. Turner (eds.), Cambridge University Press, 1982.
• 12: Hideki Hirakawa Chart Parsing in Concurrent Prolog, ICOT Technical Report TR-008, 1983.
• 13: Hideki Hirakawa et al. Implementing an Or-Parallel Optimizing Prolog System (POPS) in Concurrent Prolog, ICOT Technical Report TR-020, 1983.
• 14: Carl C. Hewitt A universal modular Actor formalism for artificial intelligence. In Proceedings of the Third International Joint Conference on Artificial Intelligence, IJCAI, 1973.
• 15: Lisa Hellerstein and Ehud Shapiro Algorithmic Programming in Concurrent Prolog: the MAXFLOW experience. Technical Report CS83-12, Department of Applied Mathematics, The Weizmann Institute of Science, 1983.
• 16: 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]
• 17: R.C. Holt, G.S. Graham, E.D. Lazowska, and M.A. Scott Structured Programming with Operating Systems Applications Addison Wesley, 1978.
• 18: Daniel H. H. Ingalls, The Smalltalk-76 programming system design and implementation, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.9-16, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512762]
• 19: Robert M. Keller, Gary Lindstrom, and Elliot I. Organic Rediflow: a multiprocessing architecture combining reduction with data-flow. Unpublished manuscript, Department of Computer Science, University of Utah, 1983.
• 20: H. Jan Komorowski, Partial evaluation as a means for inferencing data structures in an applicative language: a theory and implementation in the case of prolog, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.255-267, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582181]
• 21: S. Kunifuji et al. Conceptual Specification of the Fifth Generation Kernel Language Version 1 (preliminary draft) ICOT Technical Memorandum TM-0028, 1983.
• 22: H.T. Kung Let's Design Algorithms for VLSI Systems, Technical Report CMU-CS-79-151, Department of Computer Science, Carnegie-Mellon University, 1979.
• 23: T. Moto-Oka et at. Challenge for knowledge information processing systems (preliminary report on fifth generation computer systems) In Proceedings of International Conference on Fifth Generation Computer Systems, pages 1-85, JIPDEC, 1981.
• 24: Danny Dolev, Maria Klawe and Michael Rodeh An O(nlogn) Uni-directional distributed algorithm for extrema finding in a circle, Journal of Algorithm 3, pages 245-260, 1982.
• 25: Erik Sandewall, Programming in an Interactive Environment: the ``Lisp'' Experience, ACM Computing Surveys (CSUR), v.10 n.1, p.35-71, March 1978 [doi>10.1145/356715.356719]
• 26: Avner Shafrir and Ehud Shapiro Distributed Programming in Concurrent Prolog, Technical Report CS83-12, Department of Applied Mathematics, The Weizmann Institute of Science, 1983.
• 27: Ehud Y. Shapiro, Algorithmic Program DeBugging, MIT Press, Cambridge, MA, 1983
• 28: Ehud Shapiro A Subset of Concurrent Prolog and its Interpreter, Technical Report TR-003, ICOT—Institute for New Generation Computer Technology, 1983. Also available as Technical Report CS83-06, Department of Applied Mathematics, The Weizmann Institute of Science.
• 29: Ehud Shapiro, Fair, Biased, and Self-Balancing Merge Operators: Their Specification and Implementation in Concurrent Prolog, Technical Report CS83-12, Department of Applied Mathematics, The Weizmann Institute of Science, 1983.
• 30: Ehud Shapiro and Akikazu Takeuchi Object Oriented Programming In Concurrent Prolog, Journal of New Generation Computing Volume 1, Number 1, 1983.
• 31: Yossi Shiloach , Uzi Vishkin, An O(n2 log n) parallel max-flow algorithm, Journal of Algorithms, v.3 n.2, p.128-146, Feb. 1982 [doi>10.1016/0196-6774(82)90013-X]
• 32: Guy L Steele , Gerald J Sussman, The Art of the Interpreter or, The Modularity Complex (Parts Zero, One, and Two), Massachusetts Institute of Technology, Cambridge, MA, 1978
• 33: Nohirisa Suzuki 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), Lawrence Erlbaum Press, To appear.
• 34: A. Takeuchi and K. Furukawa Interprocess Communication in Concurrent Prolog, in Proc. Logic Programming Workshop 83, pp. 171-185, Albufeira, Portugal, June 1983. Also ICOT Technical Report TR-006, 1983.
• 35: Hisao Tamaki and Taisuke Sato A Transformation System for Logic Programs which Preserves Equivalence, ICOT Technical Report TR-018, 1983.
• 36: Shunichi Uchida, Inference machine: From sequential to parallel, Proceedings of the 10th annual international symposium on Computer architecture, p.410-416, June 13-17, 1983, Stockholm, Sweden

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.6 Logic Programming

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Concurrent Prolog

General Terms:
Languages, Performance