Object oriented programming in Concurrent Prolog

It is shown that the basic operations of object-oriented programming languages — creating an, object, sending and receiving messages, modifying an object’s state, and forming class-superclass hierarchies — can be implemented naturally in Concurrent Prolog. In addition, a new object-oriented programming paradigm, called incomplete messages, is presented. This paradigm subsumes stream communication, and greatly simplifies the complexity of programs defining communication networks and protocols for managing shared resources. Several interesting programs are presented, including a multiple-window manager. All programs have been developed and tested using the Concurrent Prolog interpreter described in.¹⁾     

Flat Concurrent Prolog on transputers

Flat Concurrent Prolog (FCP) is a general purpose logic programming language designed for concurrent programming and parallel execution. Staring with a concise introduction of the language and its underlying computational model we describe how to implement a distributed FCP interpreter on a transputer environment using OCCAM. Basic techniques we used for exploiting and controlling parallelism are explained in terms of an abstract architecture. The result of mapping this abstract model on transputers is presented as concrete architecture. Substantial design issues are considered in detail.     

Serialization of process reduction in Concurrent Prolog

Unlike most other logic programming languages. Concurrent Prolog⁵⁾ does not include a sequential-AND operator to enforce serial goal (process) reduction. However, sequential process reduction is still possible using existing constructs. In a number of published programming examples it is achieved with the “commit” operator. Such programs may not execute as described, but instead encounter deadlock. In this paper several examples of this are presented, the cause of the problem is diagnosed, and a solution suggested. This paper also deals with sequential process reduction in more general terms. The methods available to achieve serialization involving commit and read-only variable references are analyzed and compared. The potential for incorporating sequential-AND into the language is also addressed.     

Multiway merge with constant delay in Concurrent Prolog

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.     

A parallel implementation of Flat Concurrent Prolog

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.     

Bounded MSC communication

Message sequence charts (MSCs) and high-level message sequence charts (HMSCs) are popular formalisms for the specification of communication protocols between asynchronous processes. An important concept in this context is the size of the communication buffers used between processes. Since real systems impose limitations on the capacity (or speed) of communication links, we ask whether a given HMSC can be implemented with respect to a given buffer size imposed by the environment. We introduce four different measures for buffer sizes and investigate for each of these measures the complexity of deciding whether a given MSC (or HMSC, or nested MSC) satisfies a given bound on the buffer size. The complexity of these problems varies between the classes P, NP, and coNP.     

Data-flow based execution mechanisms of Parallel and Concurrent Prolog

Study attempts to show that our machine architecture based on the data flow model is suitable for two types of logic programming languages with different aims: one is Parallel Prolog and the other is Concurrent Prolog. The data flow model can naturally implement parallel computation, and it has close similarity to these languages. Unification and nondeterministic control, two basic functions of these languages, are represented by data flow graphs and interpreted by the machine. Several representations of variables, that facilitate the development of parallel unification and nondeterministic control mechanisms for these languages, the unification and control primitives needed to execute these languages on this architecture are presented.     

CARMEL-2: A second generation VLSI architecture for Flat Concurrent Prolog

CARMEL-2 is a high performance VLSI uniprocessor, tuned forFlat Concurrent Prolog (FCP). CARMEL-2 shows almost 5-fold speedup over its predecessor, CARMEL-1, and it achieves 2,400 KLIPS executingappend. This high execution rate was gained as a result of an optimized design, based on an extensive architecture-oriented execution analysis of FCP, and the lessons learned with CARMEL-1. CARMEL-2 is a RISC processor in its character and performance. The instruction set includes only 29 carefully selected instructions. The 10 special instructions, the prudent implementation and pipeline scheme, as well as sophisticated mechanisms such as intelligent dereference, distinguish CARMEL-2 as a RISC processor for FCP.     

Concurrent communication and synchronization mechanisms

The concepts of process and guarded command have become the basic building blocks in concurrent programming language design. In this paper we deal with many of the proposed communication and synchronization primitives and we compare them from the perspective of their implementability. Our evaluation treats four basic criteria: the length of synchronization, process termination, deadlock and protocol complexity.     

Concurrent communication in high-speed wide area networks

A performance metric called receptivity is introduced for quantifying the degree of concurrent communication possible in high-speed wide area networks (WAN's). Given a stochastic demand pattern model, receptivity is defined to be the probability that all requested connections can be established concurrently. Because calculation of the exact value of receptivity is shown to (generally) have an exponential complexity, an analytic estimate for its value is derived. The derived estimate is dependent on network parameters such as the number of links, link capacity values, and a weighted hop distance metric (which depends on the topological structure of the network and its relationship to parameter values of the stochastic model for the demand patterns). The derived estimate for the proposed metric compares reasonably well with simulated values for several asymmetric topological structures ranging from planar meshes to random graphs. The utility of the estimate is twofold. First, it can be computed quickly, i.e., in polynomial time. Second, its simple analytic form provides the network architect with insight into some of the inherent limitations and consequences associated with topological design choices for high-speed WAN's     

Bounds on buffer overflow probabilities in communication systems

A model to analyze the buffer behaviour in a multiplexor is derived, based on the analogy between the buffer occupancy in a discrete time model of multiplexing and the waiting time of a GI/G/1 queueing system.The bounding techniques developed earlier by Kingman and Ross are extended to the discrete time model. Simple and useful bounds are obtained for the buffer overflow probabilities under general assumptions concerning incoming message traffic characteristics. Numerical examples are presented and compared with other methods.     

用Prolog写Prolog

本文介绍一个用Prolog书写的Prolog系统,简称为PiPs。该系统是一个按照解释方式实现的语言处理系统的雏型。全文共分两大部分。前一部分介绍了PiPs本身的结构:首先介绍建立PiPs所需的Prolog谓词,接着介绍PiPs的处理概要,用户接口,执行系统,对应谓词。后一部分,通过四个例子介绍了如何使用PiPs来扩充Prolog的功能。     

Fair,biased, and self-balancing merge operators: Their specification and implementation in Concurrent Prolog

The problem of allowing a dynamically changing set of processes fair access to a shared resource is considered, in the context of communication-stream based systems. It is argued that fair binary merge operators alone cannot solve this problem satisfactorily. Two solutions are proposed. One employs binary merge operators with a programmable bias; the other binary and ternary fair merge operators capable of self-balancing, using the concept of 2–3 trees. A Concurrent Prolog implementation of these operators is described. The implementation of the self-balancing merge operators illustrates the expressive power of incomplete messages, a programming technique that supports messages that contain communication channels as arguments. In the course of implementing the self-balancing merge operator, it was necessary to develop a distributed variant of the 2–3 tree deletion algorithm.     

Prolog III

Prolog III is available from PrologIA Luminy, Case 919 13288, Marseille Cedex 09, France. Tel: +33 91 26 86 36. Prices (French francs): Sun 3, 70 000; Sparc 100 000; Mac Plus/SE 30 000; Mac SE 30/II38 000; IBM PC 386 38 000. Prices exclude VAT. Universities are entitled to a 60% discount and research centres to 30%. Systems are also available for HP9000 (series 300 and series 800), VAX and DECstation.     

Regular corecursion in Prolog

Corecursion is the ability of defining a function that produces some infinite data in terms of the function and the data itself, as supported by lazy evaluation. However, in languages such as Haskell strict operations fail to terminate even on infinite regular data, that is, cyclic data.Regular corecursion is naturally supported by coinductive Prolog, an extension where predicates can be interpreted either inductively or coinductively, that has proved to be useful for formal verification, static analysis and symbolic evaluation of programs.In this paper we use the meta-programming facilities offered by Prolog to propose extensions to coinductive Prolog aiming to make regular corecursion more expressive and easier to program with.First, we propose a new interpreter to solve the problem of non-terminating failure as experienced with the standard semantics of coinduction (as supported, for instance, in SWI-Prolog). Another problem with the standard semantics is that predicates expressed in terms of existential quantification over a regular term cannot directly defined by coinduction; to this aim, we introduce finally clauses, to allow more flexibility in coinductive definitions.Then we investigate the possibility of annotating arguments of coinductive predicates, to restrict coinductive definitions to a subset of the arguments; this allows more efficient definitions, and further enhance the expressive power of coinductive Prolog.We investigate the effectiveness of such features by showing different example programs manipulating several kinds of cyclic values, ranging from automata and context free grammars to graphs and repeating decimals; the examples show how computations on cyclic values can be expressed with concise and relatively simple programs.The semantics defined by these vanilla meta-interpreters are an interesting starting point for a more mature design and implementation of coinductive Prolog.