Parallel programming with logic languages: A survey

Formal properties of logic languages are largely studied; however, their impact on the practice of software design and programming is currently minimal. In this paper we survey some interesting representatives of the family of logic languages aiming at comparing the different capabilities they offer for designing and programming parallel systems. The logic languages Prolog, Aurora, Flat Concurrent Prolog, Parlog, GHC, and DeltaProlog were chosen, because a suitable set of relevant examples has been published, mostly by the language designers themselves. A number of sample programs is used to expose and compare the languages with respect to their object oriented programming capabilities for multiprocess coordination, interprocess communication, and resource management. Special attention is devoted also to metaprogramming as well, seen as a useful technique for specifying and building the operating environments of the languages themselves. The paper ends with a discussion on positive and negative features found comparing these languages, and indicates some guidelines to be followed in the design of new logic languages.     

The languages FCP(:) and FCP(:,?)

The language FCP(:,?) is the outcome of attempts to integrate the best of several flat concurrent logic programming languages, including Flat GHC, FCP (↓, |) and Flat Concurrent Prolog, in a single consistent framework. FCP(:) is a subset of FCP(:, ?), which is a variant of FPP(↓, |) and employs concepts of the concurrent constraint framework of cc(↓, |). FCP(:, ?) is a language which is strong enough to accommodate all useful concurrent logic programming techniques, including those which rely on atomic test unification and read-only variables, yet incorporates the weaker languages mentioned as subsets. This allows the programmer to remain within a simple subset of the language such as Flat GHC when the full power of atomic unification or read-only variables is not needed.     

Meta-interpreters and partial evaluation in Parlog

Since logic programs are executable specifications, the main concern of logic programming, producing efficient programs, is tangential to the mainstream of formal methods. A fashionable automatic transformation technique for producing efficient programs, partial evaluation, applied to the concurrent logic programming language Parlog is discussed.     

Parallel branch-and-bound search in Parlog

The concurrent logic languages, of which Parlog is one, have been promoted as a new generation of software languages specifically designed for parallel programming. This paper investigates their application to a search problem commonly used as an illustration of artificial intelligence techniques, the 8-puzzle. It notes that programs written in the concurrent logic languages which do not pay attention to the parallelism can fall into two possible traps: either there is little real parallelism in them due to data dependencies, or there is too much parallelism and any practical architecture will be overwhelmed. A solution which controls the parallelism using user-defined priorities is proposed. This solution has the advantage of being architecture-independent.     

: A distributed real-time logic language

This paper presents a new language that integrates the real-time and distributed paradigms within the framework of a concurrent logic language. Concurrent logic languages (CLLs) are capable of expressing concurrence, communication and nondeterminism in a natural way. That is, the intrinsic parallel semantics of the concurrent logic languages makes them well-suited for distributed programming. The proposed language is particularly suitable for loosely coupled systems and it contains mechanisms for distributed and real-time process control. A new execution model for concurrent logic languages is presented, which enables efficient distributed execution and real-time control. The model is introduced by giving an operational semantics for the language and the new model's implementation is discussed, including the definition of a new abstract machine and its implementation on a network of Unix workstations. Although the sequential core is not optimized, some previous results are discussed, showing the feasibility of the language's execution model for distributed real-time systems. The language is currently being used as the kernel language for a distributed simulation and validation tool for communication protocols.     

Predicates and pixels

This paper explores the possibilities of programming with graphical representations of logic programs. Two example programs are given in the concurrent logic language FGDC but many languages based on rewrite rules would be suitable for the same treatment. A graphical syntax promises to make programming in suitable ultra high level languages easier and more intuitive.     

: A distributed real-time logic language

This paper presents a new language that integrates the real-time and distributed paradigms within the framework of a concurrent logic language. Concurrent logic languages (CLLs) are capable of expressing concurrence, communication and nondeterminism in a natural way. That is, the intrinsic parallel semantics of the concurrent logic languages makes them well-suited for distributed programming. The proposed language is particularly suitable for loosely coupled systems and it contains mechanisms for distributed and real-time process control. A new execution model for concurrent logic languages is presented, which enables efficient distributed execution and real-time control. The model is introduced by giving an operational semantics for the language and the new model's implementation is discussed, including the definition of a new abstract machine and its implementation on a network of Unix workstations. Although the sequential core is not optimized, some previous results are discussed, showing the feasibility of the language's execution model for distributed real-time systems. The language is currently being used as the kernel language for a distributed simulation and validation tool for communication protocols.     

A garbage collection algorithm for shared memory parallel processors

This paper describes a technique for adapting the Morris sliding garbage collection algorithm to execute on parallel machines with shared memory. The algorithm is described within the framework of an implementation of the parallel logic language Parlog. However, the algorithm is a general one and can easily be adapted to parallel Prolog systems and to other languages. The performance of the algorithm executing a few simple Parlog benchmarks is analyzed. Finally, it is shown how the technique for parallelizing the sequential algorithm can be adapted for a semi-space copying algorithm.     

A new external reference management and distributed unification for KL1

This paper describes a new external reference management scheme for KL1, a committed choice logic programming language based on GHC. The significance of the new scheme is that it realizes incremental inter-processor garbage collection. Previous distributed implementations of committed choice languages had not seriously addressed inter-processor garbage collection. Incremental inter-precessor garbage collection is realized by the Weighted Export Counting (WEC). It is a first attempt to use the weighted reference counting technique in logic programming language implementation, and is also new in that it has introduced export and import tables for making independent local garbage collection possible and reducing the number of inter-processor read requests. The problems with exhaustion of reference counts and indirect exportation are discussed. Since the binding order rule adopted in our previous implementation for avoiding creation of reference loops is insufficient in the presence of indirect exportation, a new binding order rule is introduced. We prove that avoidance of reference loops is guaranteed and also prove that the unification procedure always terminates for non-circular structures.     

Heuristic search in PARLOG using replicated worker style parallelism

Most concurrent logic programming languages hide the distribution of processes among physical processors from the programmer. For parallel applications based on heuristic search, however, it is important for the programmer to accurately control this distribution. With such applications, an inferior distribution strategy easily leads to enormous search overheads, thus decreasing speedup on parallel hardware.

To solve this problem, various language extensions for concurrent logic languages have been proposed, such as mapping notations and priorities. We present an alternative approach that does not require any new language features. Our solution is to use the replicated workers paradigm in a concurrent logic language (PARLOG). This paradigm has thus far mainly been used in parallel procedural languages, such as Linda and Orca. We show that it is just as useful for logic languages. We have implemented two parallel applications, the Traveling Salesman Problem and alpha-beta search, using this approach. Also, we have done some performance measurements of these programs on a multiprocessor. These experiments show that significant speedups can be obtained in this way.     

Moded flat GHC and its message-oriented implementation technique

Concurrent processes can be used both for programming computation and for programming storage. Previous implementations of Flat GHC, however, have been tuned for computation-intensive programs, and perform poorly for storage-intensive programs (such as programs implementing reconfigurable data structures using processes and streams) and demand-driven programs. This paper proposes an optimization technique for programs in which processes are almost always suspended. The technique compiles unification for data transfer into message passing. Instead of reducing the number of process switching operations, the technique optimizes the cost of each process switching operation and reduces the number ofcons operations for data buffering. The technique is based on a mode system which is powerful enough to analyze bidirectional communication and streams of streams. The mode system is based on mode constraints imposed by individual clauses rather than on global dataflow analysis, enabling separate analysis of program modules. The introduction of a mode system into Flat GHC effectively subsets Flat GHC; the resulting language is calledModed Flat GHC. Moded Flat GHC programs enjoy two important properties under certain conditions: (1) reduction of a goal clause retains the well-modedness of the clause, and (2) when execution terminates, all the variables in an initial goal clause will be bound to ground terms. Practically, the computational complexity of all-at-once mode analysis can be made almost linear with respect to the sizen of the program and the complexity of the data structures used, and the complexity of separate analysis is higher only by O(logn) times. Mode analysis provides useful information for debugging as well. Benchmark results show that the proposed technique well improves the performance of storage-intensive programs and demand-driven programs compared with a conventional native-code implementation. It also improves the performance of some computation-intensive programs. We expect that the proposed technique will expand the application areas of concurrent logic languages.     

Lingual and non-lingual safety training methodology effectiveness: Does language of origin impact effectiveness

Environment, Health and Safety (EHS) trainings are used by global industries to mitigate risks and are often provided in a lingua franca (often English). This research investigated a strategy for overcoming language barriers associated with performance, comprehension, and training effectiveness. Non-linguistic (e.g., EU's Napo animated trainings) and English language (ENG) versions of EHS training were compared for effectiveness with native English language participants (L1), non-native English language participants (L2), and non-English language participants (L0).In the 1st study, 102 L1 & L2 U.S. employees completed one of the two trainings and were assessed on their reaction to and comprehension of the training. For this study, ENG was more effective and preferred by both language groups and this may be due to the workers' English proficiency and the number of channels of communication provided by the training medium. In the 2nd study, 78 L0 Brazilian and Chinese employees completed trainings and were assessed identically to the 1st study. For these participants, Napo training was more effective and preferred by both groups and this was likely because ENG L0 trainees had no channels for processing the information versus Napo's single channel of information. Interestingly, Brazilians in the ENG group outperformed their Chinese counterparts. Conversely, Chinese in the Napo group outperformed Brazilians in the Napo group.Though these findings are somewhat intuitive, they are extremely important for two reasons: 1) there is remarkable dearth of empirical research regarding the effects of the use of lingua franca for safety training. 2) Even though the idea of using lingua franca for training with L0 workers may seem obvious, there are a large number of international companies that use this for their EHS training. The findings from this study may provide a more effective and affordable method for some of these companies’ safety training needs.     

Towards the uniform implementation of declarative languages

Current implementation techniques for functional languages differ considerably from those for logic languages. This complicates the development of flexible and efficient abstract machines that can be used for the compilation of declarative languages combining concepts of functional and logic programming. We propose an abstract machine, called the JUMP-machine, which systematically integrates the operational concepts needed to implement the functional and logic programming paradigm. The use of a tagless representation for heap objects, which originates from the Spineless Tagless G-machine, supports the integration of different concepts. In this paper, we provide a functional logic kernel language and show how to translate it into the abstract machine language of the JUMP-machine. Furthermore, we define the operational semantics of the machine language formally and discuss the mapping of the abstract machine to concrete machine architectures. We tested the approach by writing a compiler for the functional logic language GTML. The obtained performance results indicate that the proposed method allows to implement functional logic languages efficiently.     

Relating state-based and process-based concurrency through linear logic (full-version)

This paper has the purpose of reviewing some of the established relationships between logic and concurrency, and of exploring new ones.Concurrent and distributed systems are notoriously hard to get right. Therefore, following an approach that has proved highly beneficial for sequential programs, much effort has been invested in tracing the foundations of concurrency in logic. The starting points of such investigations have been various idealized languages of concurrent and distributed programming, in particular the well established state-transformation model inspired by Petri nets and multiset rewriting, and the prolific process-based models such as the π-calculus and other process algebras. In nearly all cases, the target of these investigations has been linear logic, a formal language that supports a view of formulas as consumable resources. In the first part of this paper, we review some of these interpretations of concurrent languages into linear logic and observe that, possibly modulo duality, they invariably target a small semantic fragment of linear logic that we call LV^obs.In the second part of the paper, we propose a new approach to understanding concurrent and distributed programming as a manifestation of logic, which yields a language that merges those two main paradigms of concurrency. Specifically, we present a new semantics for multiset rewriting founded on an alternative view of linear logic and specifically LV^obs. The resulting interpretation is extended with a majority of linear connectives into the language of ω-multisets. This interpretation drops the distinction between multiset elements and rewrite rules, and considerably enriches the expressive power of standard multiset rewriting with embedded rules, choice, replication, and more. Derivations are now primarily viewed as open objects, and are closed only to examine intermediate rewriting states. The resulting language can also be interpreted as a process algebra. For example, a simple translation maps process constructors of the asynchronous π-calculus to rewrite operators. The language of ω-multisets forms the basis for the security protocol specification language MSR 3. With relations to both multiset rewriting and process algebra, it supports specifications that are process-based, state-based, or of a mixed nature, with the potential of combining verification techniques from both worlds. Additionally, its logical underpinning makes it an ideal common ground for systematically comparing protocol specification languages.     

Linearity Analysis of Concurrent Logic Programs

Automatic memory management and the hiding of the notion of pointers are the prominent features of symbolic processing languages. They make programming easy and guarantee the safety of memory references. For the memory management of linked data structures, copying garbage collection is most widely used because of its simplicity and desirable properties. However, if certain properties about runtime storage allocation and the behavior of pointers can be obtaind by static analysis, a compiler may be able to generate object code closer to that of procedural programs. In the fields of parallel, distributed and real-time computation, it is highly desirable to be able to identify data structures in a program that can be managed without using garbage collection. To this end, this paper proposes a framework of linearity analysis for a concurrent logic language Moded Flat GHC, and proves its basic property. The purpose of linearity analysis is to distinguish between fragments of data structures that may be referenced by two or more pointers and those that cannot be referenced by two or more pointers. Data structures with only one reader are amenable to compile-time garbage collection or local reuse. The proposed framework of linearity analysis is constraint-based and involves both equality and implicational constraints. It has been implemented as part of klint v2, a static analyzer for KL1 programs.     

Instant replay debugging of concurrent logic programs

One problem with debugging (committed choice) concurrent logic programs is that their behaviour may be non-deterministic, in that successive executions of the same program may produce different results. We describe a scheme, based on the ‘Instant Replay’ scheme developed for more conventional parallel languages, that allows us to reproduce the execution behaviour of a concurrent logic program on subsequent executions, so that the execution may be examined for debugging purposes. The properties of concurrent logic programming languages allow us to simplify our scheme greatly. We have demonstrated our scheme with KLIC, and KL1 on the PIM multiprocessors, but it can also be applied to other committed choice concurrent logic programming languages.