Efficient computation control in concurrent logic languages

Many interesting applications of concurrent logic languages require the ability to initiate, monitor, and control computations. Two approaches to the implementation of these control functions have been proposed: one based on kernel support and the other on program transformation. The efficiency of the two approaches has not previously been compared. This paper presents an implementation scheme based on kernel support, applicable to both uniprocessor and multiprocessor architectures. Experimental studies on a uniprocessor show the scheme to be more efficient than equivalent program transformations. Analysis of a multiprocessor implementation shows that the scheme imposes little communication and computation overhead.     

Dynamic slicing of concurrent specification languages

Dynamic slicing is a technique to extract the part of the program (called slice) that influences or is influenced, in a particular execution, by a given point of interest in the source code (called slicing criterion). Since a single execution is considered, the technique often uses a trace of this execution to analyze data and control dependencies. In this work we present the first formulation and implementation of dynamic slicing in the context of CSP. Most of the ideas presented can be directly applied to other concurrent specification languages such as Promela or CCS, but we center the discussion and the implementation on CSP. We base our technique on a new data structure to represent CSP computations called track. A track is a data structure which represents the sequence of expressions that have been evaluated during the computation, and moreover, it is labeled with the location of these expressions in the specification. The implementation of a dynamic slicer for CSP is useful for debugging, program comprehension, and program specialization, and it is also interesting from a theoretical perspective because CSP introduces difficulties such as heavy concurrency and non-determinism, synchronizations, frequent absence of data dependence, etc.     

Vectorial languages and linear temporal logic

Determining for a given deterministic complete automaton the sequence of visited states while reading a given word is the core of important problems with automata-based solutions, such as approximate string matching. The main difficulty is to do this computation efficiently. Considering words as vectors and working on them using vectorial operations allows to solve the problem faster than using local operations.

In this paper, we show first that the set of vectorial operations needed by an algorithm representing a given automaton depends on the language accepted by the automaton. We give precise characterizations for star-free, solvable and regular languages using vectorial algorithms. We also study classes of languages associated with restricted sets of vectorial operations and relate them with languages defined by fragments of linear temporal logic.

Finally, we consider the converse problem of constructing an automaton from a given vectorial algorithm. As a byproduct, we show that the satisfiability problem for some extensions of LTL characterizing solvable and regular languages is PSPACE-complete.     

Programming languages and systems security

Modern research and development has produced various language-level supports for secure systems design. Safe languages provide a flexible and reliable foundation on which to build. Language-based security abstractions provide systems programmers with an effective means of defining and enforcing security models. Controlled language-execution models can impose fine-grained and powerful restrictions on code at varying levels of trust. Arguably, the most popular modern general-purpose languages, Java and C#, bear witness to the importance of programming language safety and security, being both safe and endowed with sophisticated security models. Research into these topics is ongoing, but perhaps the most important current task is the integration of modern language security technologies (much more efficient and effective than past technologies) with realistic systems design.     

Programming languages for distributed applications

Much progress has been made in distributed computing in the areas of distribution structure, open computing, fault tolerance, and security. Yet, writing distributed applications remains difficult because the programmer has to manage models of these areas explicitly. A major challenge is to integrate the four models into a coherent development platform. Such a platform should make it possible to cleanly separate an application’s functionality from the other four concerns. Concurrent constraint programming, an evolution of concurrent logic programming, has both the expressiveness and the formal foundation needed to attempt this integration. As a first step, we have designed and built a platform that separates an application’s functionality from its distribution structure. We have prototyped several collaborative tools with this platform, including a shared graphic editor whose design is presented in detail. The platform efficiently implements Distributed Oz, which extends the Oz language with constructs to express the distribution structure and with basic primitives for open computing, failure detection and handling, and resource control. Oz appears to the programmer as a concurrent object-oriented language with dataflow synchronization. Oz is based on a higher-order, state-aware, concurrent constraint computation model. Seif Haridi, Ph.D.: He received his Ph.D. in computer science in 1981 from the Royal Institute of Technology, Sweden. After spending 18 months at IBM T. J. Watson Research Center, he moved to the Swedish Institute of Computer Science (SICS) to form a research lab on logic programming and parallel systems. Dr. Haridi is currently the research director of the Swedish Institute of Computer Science. He has been an active researcher in the area of logic and constraint programming and parallel processing since the beginning of the eighties. His earlier work includes contributions to the design of SICStus Prolog, various parallel Prolog systems and a class of scalable cache-coherent multiprocessors known as Cache-Only Memory Architecture (COMA). During the nineties most of his work focused on the design of multiparadigm programming systems based on Concurrent Constraint Programming (CCP). Currently, he is interested in programming systems and software methodology for distributed and agent-based applications. Peter Van Roy, Ph.D.: He obtained an engineering degree from the Vrije Universiteit Brussel (1983), Masters and Ph.D. degrees from the University of California at Berkeley (1984, 1990), and the Habilitation à Diriger des Recherches from Paris VII Denis Diderot (1996). He has made major contributions to logic language implementation. His research showed for the first time that Prolog can be implemented with the same execution efficiency as C. He was principal developer or codeveloper of Aquarius Prolog, Wild_Life, Logical State Threads, and FractaSketch. He joined the Oz project in 1994 and is currently working on Distributed Oz. His research interests are motivated by the desire to provide increased expressivity and efficiency to application developers. Per Brand: He is a researcher at the Swedish Institute of Computer Science. He has previously worked on the design and implementation of OR-parallel Prolog (the Aurora project) and optimized compilation techniques for Concurrent Constraint Programming Languages (in particular, AKL). He has been a member of the Distributed Oz design team since the project began. His research interests are focused on techniques, languages, and methodology for distributed programming. Christian Schulte: He studied computer science at the University of Karlsruhe, Germany, from 1987 to 1992 where he received his diploma. Since 1992 he has been a member of the Programming Systems Lab at DFKI. He is one of the principal designers of Oz. His research interests include design, implementation, and application of concurrent and distributed programming languages as well as constraint programming.     

Programming languages for use in safety-related applications

Programmable electronic systems are being used in almost all application sectors to perform non-safety and increasingly to perform safety functions as well. Although software-based solutions are usually superior to hardwired ones for reasons of efficiency and flexibility, there is a certain reluctance of the certification authorities when it comes to licensing computer-based systems which are classified as safety critical. Despite many attempts to overcome problems of software safety (IEC 61508, IEC 880, VDE 0801, IDS 00-55, RTCA/DO-178), up to now neither precise guidelines supporting the software development process are available, nor are there serious efforts being made to develop programming languages dedicated to the implementation of safety critical functions. To improve this unsatisfactory situation, i.e. to meet both economic and safety requirements, it is necessary to design appropriate language concepts with consequent regard to safety aspects. Accordingly, four subsets of a real time language suitable for the implementation of safety-related systems are proposed, whose definitions fulfil the respective requirements of the four safety integrity levels.     

Computational complexity and constraint logic programming languages

We give a complexity analysis of a variety of languages across the spectrum of the CLP scheme. By varying the logic and memory management, the role of the constraints and the role of the logic can be measured. The analysis clarifies the relation between linear/integer programming and constraint logic programming. We also determine how the power of constraints can easily lead to undecidable queries in Datalog languages with constraints. This work is motivated in large part by the problems of efficient implementation of CLP languages and the concomitant need for low level constraint languages.Research partially supported by PSC-CUNY Grant 669287.Research partially supported by NSF Grant IRI-8902511.     

Programming languages for fifth generation computers

Fifth Generation languages and computers, for use in the 1990's, may be based on significantly different concepts than traditional computing. There are four major categories of computing, each consisting of a programming style and corresponding computer. These are: procedural languages (and control flow computers); object-oriented languages (and actor computers); functional languages (and data flow or reduction computers); and logic languages (and logic computers). In the future any of these categories of languages may become “main-stream” programming styles. In this paper we briefly present these novel programming languages and examine their advantages and disadvantages for programming.     

Database query languages and functional logic programming

Functional logic programming is a paradigm which integrates functional and logic programming. It is based on the use of rewriting rules for defining programs, and rewriting for goal solving. In this context, goals, usually, consist of equality (and, sometimes, inequality) constraints, which are solved in order to obtain answers, represented by means of substitutions. On the other hand, database programming languages involve a data model, a data definition language and, finally, a query language against the data defined according to the data model. To use functional logic programming as a database programming language, (1) we will propose a data model involving the main features adopted from functional logic programming (for instance, handling of partial and infinite data), (2) we will use conditional rewriting rules as data definition language, and finally, (3) we will deal with equality and inequality constraints as query language. Moreover, as most database systems, (4) we will propose an extended relational calculus and algebra, which can be used as alternative query languages in this framework. Finally, (5) we will prove that three alternative query languages are equivalent.     

Sequential versus concurrent languages of labeled conflict-freePetri nets

For structurally deterministic labeled conflict-free Petri nets (PNs), we show that two PNs have identical sequential languages if and only if their concurrent languages are identical as well, and whether a given labeled conflict-free PN is structurally deterministic or not can be checked in polynomial time. We also investigate a number of language-related problems in supervisory control theory for this class of PNs. As it turns out, the properties of controllability, observability, and normality in the sequential framework coincide with that in the concurrent framework     

Continuation compilation for concurrent logic programming

A new and powerful approach to threading is proposed, that is designed to improve the responsiveness of concurrent logic programs for distributed, real-time AI applications. The technique builds on previously proposed scheduling techniques to improve responsiveness by synchronously passing control and data directly from a producer to a consumer. Furthermore, synchronous transfer of data requires less buffering and so less garbage is produced. Arguments are also passed in registers, further reducing overheads.     

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.     

Compile-time granularity analysis for parallel logic programming languages

The paper describes a simple compiler analysis method for determining the “weight” of procedures in parallel logic programming languages. Using Flat Guarded Horn Clauses (FGHC) as an example, the analysis algorithm is described. Consideration of weights has been incorporated in the scheduler of a real-parallel FGHC emulator running on the Sequent Symmetry multiprocessor. Alternative demand-distribution methods are discussed, includingoldest-first andheaviest-first distributions. Performance measurements, collected from a group of non-trivial benchmarks on eight processors, show that the new schemes donot perform significantly faster than conventional distribution methods. This result is attributed to a combination of factors overshadowing the benefits of the new method: high system overheads, the low cost of spawning a goal on a shared memory multiprocessor, and the increase in synchronization caused by the new methods. Directions of further research are discussed, indicating where further speedup can be attained.     

A lingua franca for concurrent logic programming

Two of the more important concurrent logic programming languages with nonflat guards are GHC and Parlog. They balance the requirements of having clean semantics and providing good control facilities rather differently, and their respective merits are compared and contrasted. Since concurrent logic programming would benefit from both, but neither language is able to express all the programs expressible in the other language, a lingua franca of these languages is defined and justified. A method is given for translating GHC and Parlog to and from it. The method preserves the arities and execution conditions of each clause. It enables a lingua franca implementation to support both languages transparently, and to provide a simple concurrent logic programming language suitable for programming in its own right     

A survey of concurrent object‐oriented languages

During the last decade object‐oriented programming has grown from marginal influence into widespread acceptance. During the same period, progress in hardware and networking has changed the computing environment from sequential to parallel. Multi‐processor workstations and clusters are now quite common. Unnumbered proposals have been made to combine both developments. Always the prime objective has been to provide the advantages of object‐oriented software design at the increased power of parallel machines. However, combining both concepts has proven to be notoriously difficult. Depending on the approach, often key characteristics of either the object‐oriented paradigm or key performance factors of parallelism are sacrificed, resulting in unsatisfactory languages. This survey first recapitulates well‐known characteristics of both the object‐oriented paradigm and parallel programming, and then marks out the design space of possible combinations by identifying various interdependencies of key concepts. The design space is then filled with data points: for 111 proposed languages we provide brief characteristics and feature tables. Feature tables, the comprehensive bibliography, and web‐addresses might help in identifying open questions and preventing re‐inventions. Copyright © 2000 John Wiley & Sons, Ltd.