A structural operational semantics for an Edison-like language (1)

A structural operational semantics for Edison. 1—an Edison-like language—is given. The static and dynamic (operational) semantics for various declarations and statements contained in this type of languages have been carefully studied by using a structural operational approach. The method used here can be generalised to cover more complicated concurrent programming languages. The paper is divided into two parts. In the first part, an abstract syntax of Edison. 1 is introduced and the static semantics of it is studied. In the second part, an operational (dynamic) semantics of Edison. 1 is given.     

Temporal Semantics for Concurrent M M

Concurrent is a programming language based on the notion of concurrent, communicating objects, where each object directly executes a specification given in temporal logic, and communicates with other objects using asynchronous broadcast message-passing. Thus, Concurrent represents a combination of the direct execution of temporal specifications, together with a novel model of concurrent computation. In contrast to the notions of predicates as processes and stream parallelism seen in concurrent logic languages, Concurrent represents a more coarse-grained approach, where an object consists of a set of logical rules and communication is achieved by the evaluation of certain types of predicate. Representing concurrent systems as groups of such objects provides a powerful tool for modelling complex reactive systems. In order to reason about the behaviour of Concurrent systems, we requir a suitable semantics. Being based upon executable temporal logic, objects in isolation have an intuitive semantics. However, the addition of both operational constraints upon the object's execution and global constraints provided by the asynchronous model of concurrency and communication, complicates the overall semantics of networks of objects. It is this, more complex, semantics that we address here, where temporal semantics for varieties of Concurrent are provided.     

An axiomatic semantics for the synchronous language Gentzen

We propose an axiomatic semantics for the synchronous language Gentzen, which is an instantiation of the paradigm Timed Concurrent Constraint Programming proposed by Saraswat, Jagadeesan and Gupta. We view Gentzen as a prototype of the class of state-oriented synchronous languages, since it offers the basic constructs that are shared by the languages in the class. Since synchronous concurrency cannot be simulated by arbitrary interleaving, we cannot exploit “head normal forms”, on which axiomatic theories for asynchronous process calculi are based. We suggest how axiomatic semantics for other state-oriented synchronous languages can be obtained by expressing constructs of such languages in terms of Gentzen constructs.     

SystemJ: A GALS language for system level design

In this paper we present the syntax, semantics, and compilation of a new system-level programming language called SystemJ. SystemJ is a multiclock language supporting the Globally Asynchronous Locally Synchronous (GALS) model of computation. The synchronous reactive (SR) model is used for synchronous parts of the modelled system, and those parts, which represent individual clock-domains, are coupled asynchronously each to the other on the top-level of system design. SystemJ is based on Java language, which is used to describe “instantaneous” data transformations. Hence, SystemJ is well suited for both software-based embedded and distributed systems. SystemJ offers effective modelling of (1) data transformations through the power of Java, (2) control and synchronous concurrency through the SR paradigm and (3) asynchronous concurrency through clock domains and rendezvous. The language is based on semantics that is amenable to efficient code generation and partial automatic verification. The SystemJ micro-step semantics provide asynchronous and synchronous extensions over the semantics of other SR languages such as Esterel and provide an ideal platform for efficient software implementation.     

A continuous semantics for unbounded nondeterminism

Nondeterminism is introduced into an ordinary iterative programming language by treating procedure calls as nondeterministic assignment statements. The effect of such assignment statements is assumed to be determined solely by the entry-exit specifications of the corresponding procedures. The nondeterminism which this approach yields is not necessarily bounded. The paper discusses the problem of defining a denotational semantic for programming languages with this kind of, possibly unbounded, nondeterminism. As an additional constraint, the semantics is required to be continuous, in the sense that the underlying semantic algebra is continuous. It is shown how such a continuous semantics for unbounded nondeterminism can be derived from a simple operational semantics based on program execution trees.     

PTSC: probability, time and shared-variable concurrency

Complex software systems typically involve features like time, concurrency and probability, where probabilistic computations play an increasing role. It is challenging to formalize languages comprising all these features. In this paper, we integrate probability, time and concurrency in one single model, where the concurrency feature is modelled using shared-variable-based communication. The probability feature is represented by a probabilistic nondeterministic choice, probabilistic guarded choice and a probabilistic version of parallel composition. We formalize an operational semantics for such an integration. Based on this model we define a bisimulation relation, from which an observational equivalence between probabilistic programs is investigated and a collection of algebraic laws are explored. We also implement a prototype of the operational semantics to animate the execution of probabilistic programs.     

A residualizing semantics for the partial evaluation of functional logic programs

Recent proposals for multi-paradigm declarative programming combine the most important features of functional, logic and concurrent programming into a single framework. The operational semantics of these languages is usually based on a combination of narrowing and residuation. In this paper, we introduce a non-standard, residualizing semantics for multi-paradigm declarative programs and prove its equivalence with a standard operational semantics. Our residualizing semantics is particularly relevant within the area of program transformation where it is useful, e.g., to perform computations during partial evaluation. Thus, the proof of equivalence is a crucial result to demonstrate the correctness of (existing) partial evaluation schemes.     

simpA: An agent-oriented approach for programming concurrent applications on top of Java

More and more aspects of concurrency and concurrent programming are becoming part of mainstream programming and software engineering, due to several factors such as the widespread availability of multi-core/parallel architectures and Internet-based systems. This leads to the extension of mainstream object-oriented programming languages and platforms-Java is a main example-with libraries providing fine-grained mechanisms and idioms to support concurrent programming, in particular for building efficient programs. Besides this fine-grained support, a main research goal in this context is to devise higher-level, coarse-grained abstractions that would help building concurrent programs, as pure object-oriented abstractions help building large component-based programs. To this end, in this paper we present simpA, a Java-based framework that provides programmers with agent-oriented abstractions on top of the basic OO layer, as a means to organize and structure concurrent applications. We first describe the application programming interface (API) and annotation framework provided to Java programmers for building simpA applications, and then we discuss the main features of the approach from a software engineering point of view, by showing some programming examples. Finally, we define an operational semantics formalizing the main aspects of this programming model.     

A fully abstract model for the exchange of information in multi-agent systems

In this paper,¹ we present a semantic theory for the exchange of information in multi-agent systems. We consider the multi-agent programming language agent communication programming language, which integrates the paradigms of concurrent constraint programming and communicating sequential processes ( ). The constraint programming techniques are used to represent and process information, whereas the synchronous communication mechanism from is generalised to enable the exchange of information. The semantics of the language, which is based on a generalisation of traditional failure semantics, is shown to be fully abstract with respect to observing of each terminating computation its final global store of information.     

Asynchronous communication model based on linear logic

We propose a new framework called ACL for concurrent computation based on linear logic. ACL is a kind oflinear logic programming framework, where its operational semantics is described in terms ofproof construction in linear logic. We also give a model-theoretic semantics based onphase semantics, a model of linear logic. Our framework well captures concurrent computation based on asynchronous communication. It will, therefore, provide us with a new insight into other models of asynchronous concurrent computation from alogical point of view. We also expect ACL to become a formal framework for analysis, synthesis and transformation of concurrent programs by the use of techniques for traditional logic programming. ACL's attractive features for concurrent programming paradigms are also discussed.     

Step semantics for “true” concurrency with recursion

We present a variety of denotational linear time semantics for a language with recursion and true concurrency in a form of synchronous co-operation, which in the literature is known as step semantics. We show that this can be done by a generalization of known results for interleaving semantics. A general method is presented to define semantical operators and denotational semantics in the Smyth powerdomain of streams. With this method, first a naive and then more sophisticated semantics for synchronous co-operation are developed, which include such features as interleaving and synchronization. Then we refine the semantics to deal with a bounded number of processors, subatomic actions, maximal parallelism and a real-time operator. Finally, it is indicated how to apply these ideas to branching-time models, where it becomes possible to analyze deadlock behaviour as well as a form of true concurrency. John-Jules Meyer received his Master's degree in Mathematics in 1979 from the University of Leiden, and his Ph.D. degree in 1985 from the Free University Amsterdam. He is currently a Professor of Theoretical Computer Science, both at the Free University Amsterdam and at the University of Nijmegen. His current research interests include semantics of programming languages and logics for computer science, in particular artifical intelligence. Erik de Vink received the M.S. degree in Mathematics from the University of Amsterdam. He is currently a Junior Researcher at the Department of Mathematics and Computer Science of the Free University Amsterdam. At the moment his main research concerns the semantics of concurrent and logic programming languages.     

A temporal programming model with atomic blocks based on projection temporal logic

Atomic blocks, a high-level language construct that allows programmers to explicitly specify the atomicity of operations without worrying about the implementations, are a promising approach that simplifies concurrent programming. On the other hand, temporal logic is a successful model in logic programming and concurrency verification, but none of existing temporal programming models supports concurrent programming with atomic blocks yet. In this paper, we propose a temporal programming model (αPTL) which extends the projection temporal logic (PTL) to support concurrent programming with atomic blocks. The novel construct that formulates atomic execution of code blocks, which we call atomic interval formulas, is always interpreted over two consecutive states, with the internal states of the block being abstracted away. We show that the framing mechanism in projection temporal logic also works in the new model, which consequently supports our development of an executive language. The language supports concurrency by introducing a loose interleaving semantics which tracks only the mutual exclusion between atomic blocks. We demonstrate the usage of αPTL by modeling and verifying both the fine-grained and coarse-grained concurrency.     

一个并发对象演算

由于缺乏一个为人们接受的描述并发对象系统语义的形式化模型,开发面向对象程序设计语言的开发受到了很大的制约,为了给并发面向对象程序设计定义一个公共的语义框架,人们分别以π演算和ａｃｔｏｒ模型为基础进行了研究。     

: 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 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.     

The logic of message-passing

Message-passing is a key ingredient of concurrent programming. The purpose of this paper is to describe the equivalence between the proof theory, the categorical semantics, and term calculus of message-passing. In order to achieve this we introduce the categorical notion of a linear actegory and the related polycategorical notion of a poly-actegory. Not surprisingly the notation used for the term calculus borrows heavily from the (synchronous) π-calculus. The cut-elimination procedure for the system provides an operational semantics.     

Probabilistic bisimulations for quantum processes

Modeling and reasoning about concurrent quantum systems is very important for both distributed quantum computing and quantum protocol verification. As a consequence, a general framework formally describing communication and concurrency in complex quantum systems is necessary. For this purpose, we propose a model named qCCS. It is a natural quantum extension of classical value-passing CCS which can deal with input and output of quantum states, and unitary transformations and measurements on quantum systems. The operational semantics of qCCS is given in terms of probabilistic labeled transition system. This semantics has many different features compared with the proposals in the available literature in order to describe the input and output of quantum systems which are possibly correlated with other components. Based on this operational semantics, the notions of strong probabilistic bisimulation and weak probabilistic bisimulation between quantum processes are introduced. Furthermore, some properties of these two probabilistic bisimulations, such as congruence under various combinators, are examined.