Publications
1986
-
-
(1986) Journal of Logic Programming. 3, 2, p. 157-184 Abstract
This paper reports on the experience of implementing Shiloach and Vishkin's parallel Maxflow algorithm [7] in Concurrent PROLOG. The major difficulties in this endeavor were understanding the algorithm, which is intricate, and adapting it to the computational model of Concurrent PROLOG. In spite of the difficulties, we were able to produce a Concurrent PROLOG program that implements the algorithm and achieves the expected complexity bounds. The lack of destructive assignment in the logic program's computation model prevents PROLOG from being an efficient implementation language for many sequential algorithms. Our main conclusion is that, in concurrent algorithms, message passing is a powerful substitute for destructive assignment. It is therefore possible to write efficient Concurrent PROLOG implementations of concurrent algorithms.
-
(1986) International Journal of Parallel Programming. 15, 3, p. 245-275 Abstract
Flat Concurrent Prolog is a simple, practical, concurrent programming language which has an efficient uniprocessor implementation. This paper describes an initial parallel implementation of the language; it consists of an interpreter implemented on an Intel iPSC Hypercube. The parallel execution of concurrent logic programming languages involves many nontrivial implementation problems. Some of these problems are well known and have been treated extensively in the literature. The most difficult task is to integrate problem solutions in a coherent and efficient manner. The algorithm presented has been useful in providing insights into the major problems and includes a number of novel ideas to simplify implementation. It does not attempt to solve all the problems involved but rather provides a workable basis for current and future research. The algorithm is under ongoing refinement, simplification and improvement.
-
(1986) Fundamentals of Artificial Intelligence. Jorrand P. & Bibel W.(eds.). Vol. 232. p. 277-313 (trueLecture Notes in Computer Science). Abstract
Concurrent Prolog is a logic programming language designed for concurrent programming and parallel execution. It is a process oriented language, which embodies dataflow synchronization and guarded-command indeterminacy as its basic control mechanisms.The paper outlines the basic concepts and definition of the language, and surveys the major programming techniques that emerged out of three years of its use. The history of the language development, implementation, and applications to date is reviewed. Details of the performance of its compiler and the functionality of Logix, its programming environment and operating system, are provided.
-
(1986) New Generation Computing. 4, 2, p. 211-216 Abstract
Multiway dynamic mergers with constant delay are an essential component of a parallel logic programming language. Previous attempts to defined efficient mergers have required complex optimising compilers and run-time support.This paper proposes a simple technique to implement mergers efficiently. The technique requires an additional data type and the definition of an operation on it. The operation allows multiple processes to access a stream without incurring the cost of searching for the end of stream. It is specified in Concurrent Prolog and is used to define multiple assignment variables using a monitor.The technique forms the basis for stream merging in Logix, a practical programming environment written in Flat Concurrent Prolog.
-
-
(1986) International Conference on Logic Programming. Shapiro E.(eds.). Vol. 225. p. 283-297 (trueLecture Notes in Computer Science). Abstract
This paper suggests a general method for compiling OR-parallelism into AND-parallelism. An interpreter for an AND/OR-parallel language written in the AND-parallel subset of the language induces a source-to-source transformation from the full language into the AND-parallel subset. This transformation can be identified and implemented as a special purpose compiler or applied using a general purpose partial evaluator.The method is demonstrated to compile a variant of Concurrent Prolog into an AND-parallel subset of the language called Flat Concurrent Prolog (FCP). It is also shown applicable to the compilation of OR-parallel Prolog to FCP. The transformation identified is simple and efficient. The performance of the method is discussed in the context of programming examples. These compare well with conventionally compiled Prolog programs.
-
(1986) Third International Conference on Logic Programming. Shapiro E.(eds.). Berlin, Heidelberg: . Vol. 225. p. 544-551 (trueLecture Notes in Computer Science). Abstract
Most Prolog textbooks are based on gradual presentation of Prolog's concepts, as well as some concepts from logic. We think that this order of presentation used in most books is inadequate for readers with little prior experience with logic, mathematics or programming. In this paper we introduce a new approach for teaching Prolog to these \u201cnaive\u201d users. Within our framework, the order of concept introduction is based upon the order used in teaching logic: from propositions to predicates. We believe that this approach will ease the difficulties encountered by newcomers to Prolog, and will provide a good basis for better understanding of logic, programming, data-base theory, and perhaps also other relevant disciplines.The choice of Prolog as a first programming language is also discussed, and we argue that it is a better choice than conventional languages in the same sense that those languages are considered better than machine languages. This claim however should be empirically verified.