Distributed speculative execution for reliability and fault tolerance: an operational semantics

This paper examines the use of speculations, a form of distributed transactions, for improving the reliability and fault tolerance of distributed systems. A speculation is defined as a computation that is based on an assumption that is not validated before the computation is started. If the assumption is later found to be false, the computation is aborted and the state of the program is rolled back; if the assumption is found to be true, the results of the computation are committed. The primary difference between a speculation and a transaction is that a speculation is not isolated—for example, a speculative computation may send and receive messages, and it may modify shared objects. As a result, processes that share those objects may be absorbed into a speculation. We present a syntax, and an operational semantics in two forms. The first one is a speculative model, which takes full advantage of the speculative features. The second one is a nonspeculative, nondeterministic model, where aborts are treated as failures. We prove the equivalence of the two models, demonstrating that speculative execution is equivalent to failure-free computation.     

A rewriting logic framework for operational semantics of membrane systems

Existing results in membrane computing refer mainly to P systems’ characterization of Turing computability, also to some polynomial solutions to NP-complete problems by using an exponential workspace created in a “biological way”. In this paper we define an operational semantics of a basic class of P systems, and give two implementations of the operational semantics using rewriting logic. We present some results regarding these implementations, including two operational correspondence results, and discuss why these implementations are relevant in order to take advantage of good features of both structural operational semantics and rewriting logic.     

Linking operational semantics and algebraic semantics for a probabilistic timed shared-variable language

Complex software systems typically involve features like time, concurrency and probability, with probabilistic computations playing an increasing role. However, it is currently challenging to formalize languages incorporating all those features. Recently, the language PTSC has been proposed to integrate probability and time with shared-variable concurrency (Zhu et al. (2006, 2009) [51] and [53]), where the operational semantics has been explored and a set of algebraic laws has been investigated via bisimulation. This paper investigates the link between the operational and algebraic semantics of PTSC, highlighting both its theoretical and practical aspects.The link is obtained by deriving the operational semantics from the algebraic semantics, an approach that may be understood as establishing soundness of the operational semantics with respect to the algebraic semantics. Algebraic laws are provided that suffice to convert any PTSC program into a form consisting of a guarded choice or an internal choice between programs, which are initially deterministic. That form corresponds to a simple execution of the program, so it is used as a basis for an operational semantics. In that way, the operational semantics is derived from the algebraic semantics, with transition rules resulting from the derivation strategy. In fact the derived transition rules and the derivation strategy are shown to be equivalent, which may be understood as establishing completeness of the operational semantics with respect to the algebraic semantics.That theoretical approach to the link is complemented by a practical one, which animates the link using Prolog. The link between the two semantics proceeds via head normal form. Firstly, the generation of head normal form is explored, in particular animating the expansion laws for probabilistic interleaving. Then the derivation of the operational semantics is animated using a strategy that exploits head normal form. The operational semantics is also animated. These animations, which again supports to claim soundness and completeness of the operational semantics with respect to the algebraic, are interesting because they provide a practical demonstration of the theoretical results.     

Bialgebras for structural operational semantics: An introduction

Bialgebras and distributive laws are an abstract, categorical framework to study various flavors of structural operational semantics. This paper aims to introduce the reader to the basics of bialgebras for operational semantics, and to sketch the state of the art in this research area.     

Deriving a compiler from an operational semantics written in VDL

This paper addresses the issue of compiler correctness. The approach taken is to systematically construct a correct compiler for a language from a formal semantic definition of the language. For this purpose, an operational semantics of a language is chosen as the basis for the approach. That is, the compiler for a language is derived from an interpreter of the language. The derivation process uses the notion of mixed computation proposed by Ershov. Briefly stated, one begins interpreting and when a primitive state changing instruction is about to be executed, the instruction is emitted as code instead. The correctness of all compilers produced by the method is guaranteed by proving the derivation rules correct. This proof is a one-time task for each specification language. The specification language studied in this paper is the Vienna Definition Language (VDL). The object code generated by the compiler is in an intermediate language close to an assembly language. Therefore, the translation from the intermediate language into the assembly language should be straightforward.     

A Standard Model—Theoretic Approach to Operational Semmantics of Recursiv Programs

In this paper we try to introduce a new approach to operational semantics of recursive programs by using ideas in the“priority method”which is a fundamental tool in Recursion Theory.In lieu of modelling partial functions by introducing undefined values in a traditional approach,we shall define a priority derivation tree for every term,and by respecting thr rule“attacking the subtem of the highest priority first”we define transition relations,computation sequences etc.directly based on a standard interpretation whic includes no undefined value in its domain,Finally,we prove that our new approach generates the same opeational semantics as the traditional one.It is also pointed out that we can use our strategy oto refute a claim of Loeckx and Sieber that the opperational semantics of recursive programs cannot be built based on predicate logic.     

基于Handel—C语言的FPGA设计

对于以ISO／ANSI—C为基础的程序设计语言Handel—C，可利用Celoxiea DK设计工具将Handel—C的源代码编译成能直接针对FPGA目标的网表(Netlist)，而无需VHDL／Verilog的中间步骤，最后利用FPGA布线工具直接将Netlist下载到FPGA上。文中在分析Handel—C语言的FPGA开发流程的基础上，将Handel—C与VHDL设计进行对比分析，揭示了Handel—C在电路算法级设计方面的优势，而且设计效率也大大提高。     

A compact fixpoint semantics for term rewriting systems

This work is motivated by the fact that a “compact” semantics for term rewriting systems, which is essential for the development of effective semantics-based program manipulation tools (e.g. automatic program analyzers and debuggers), does not exist. The big-step rewriting semantics that is most commonly considered in functional programming is the set of values/normal forms that the program is able to compute for any input expression. Such a big-step semantics is unnecessarily oversized, as it contains many “semantically useless” elements that can be retrieved from a smaller set of terms. Therefore, in this article, we present a compressed, goal-independent collecting fixpoint semantics that contains the smallest set of terms that are sufficient to describe, by semantic closure, all possible rewritings. We prove soundness and completeness under ascertained conditions. The compactness of the semantics makes it suitable for applications. Actually, our semantics can be finite whereas the big-step semantics is generally not, and even when both semantics are infinite, the fixpoint computation of our semantics produces fewer elements at each step. To support this claim we report several experiments performed with a prototypical implementation.     

Typed operational semantics for higher-order subtyping

Bounded operator abstraction is a language construct relevant to object oriented programming languages and to ML2000, the successor to Standard ML. In this paper, we introduce , a variant of F_<:^ω with this feature and with Cardelli and Wegner’s kernel Fun rule for quantifiers. We define a typed-operational semantics with subtyping and prove that it is equivalent with , using logical relations to prove soundness. The typed-operational semantics provides a powerful and uniform technique to study metatheoretic properties of , such as Church–Rosser, subject reduction, the admissibility of structural rules, and the equivalence with the algorithmic presentation of the system that performs weak-head reductions.Furthermore, we can show decidability of subtyping using the typed-operational semantics and its equivalence with the usual presentation. Hence, this paper demonstrates for the first time that logical relations can be used to show decidability of subtyping.     

Executable structural operational semantics in Maude

This paper describes in detail how to bridge the gap between theory and practice when implementing in Maude structural operational semantics described in rewriting logic, where transitions become rewrites and inference rules become conditional rewrite rules with rewrites in the conditions, as made possible by the new features in Maude 2. We validate this technique using it in several case studies: a functional language Fpl (evaluation and computation semantics), an imperative language WhileL (evaluation and computation semantics), Kahn’s functional language Mini-ML (evaluation or natural semantics), Milner’s CCS (with strong and weak transitions), and Full LOTOS (including ACT ONE data type specifications). In addition, on top of CCS we develop an implementation of the Hennessy–Milner modal logic for describing local capabilities of processes, and for LOTOS we build an entire tool where Full LOTOS specifications can be entered and executed (without user knowledge of the underlying implementation of the semantics). We also compare this method based on transitions as rewrites with another one based on transitions as judgements.     

Compositional operational semantics for Prolog programs

To relate operational semantics of logic programs to its declarative semantics, we have to rely on SLD-trees. But this form of operational semantics does not make it easy to relate execution behaviour to program structure. The reason is that the traversal of SLD-trees decomposes in a way that is different from the decomposition (which is by disjunction and conjunction) of programs. We propose SLD-contours, a variant of SLD-trees, that are, like programs, built up out of simpler components by means of disjunction and conjunction. The traversal of SLD-trees carries over to the traversal of SLD-contours in such a way that the trace events of the Box Model (Try, Succeed, Retry, Fail) are reproduced in the same way as during the execution of the program. ThusSLD-contours relate the trace more closely to the program than SLD-trees. SLD-contours specify the trace more completely than the Box Model does.     

A structured operational semantics for UML-statecharts

The Unified Modeling Language (UML) has gained wide acceptance in very short time because of its variety of well-known and intuitive graphical notations. However, this comes at the price of an unprecise and incomplete semantics definition. This insufficiency concerns single UML diagram notations on their own as well as their integration. In this paper, we focus on the notation of UML-statecharts. Starting with a precise textual syntax definition, we develop a precise structured operational semantics (SOS) for UML-statecharts. Besides the support of interlevel transitions and in contrast to related work, our semantics definition supports characteristic UML-statechart features like the history mechanism as well as entry and exit actions. Initial submission: 19 February 2002 / Revised submission: 28 October 2002 Published online: 2 December 2002     

Algebraic and operational semantics of specifications allowing exceptions and errors

The specification of abstract data types requires the possibility to treat exceptions and errors. We present an approach allowing all forms of error handling: error introduction, error propagation and error recovery. The algebraic semantics of our method and a new correctness criterion are given. We also introduce an operational semantics of a subclass of our specifications which coincides with the algebraic semantics.     

基于Handel-C的软硬件协同验证方法

针对数字集成电路中传统IP验证方法效率不高的问题,提出了一种新的IP验证方法。该方法以OpenGL-ES中坐标变换算法为例,利用Handel-C对其进行建模并用FPGA实现。最后与软件测试平台进行了协同验证。验证结果表明,对复杂的验证模块而言,该方法和传统的Modelsim仿真对比,在速度上具有明显的优势。     

A Hardware Implementation of a Genetic Programming System Using FPGAs and Handel-C

This paper presents an implementation of Genetic Programming using a Field Programmable Gate Array. This novel implementation uses a high level language to hardware compilation system, called Handel-C, to produce a Field Programmable Logic Array capable of performing all the functions required of a Genetic Programming System. Two simple test problems demonstrate that GP running on a Field Programmable Gate Array can outperform a software version of the same algorithm by exploiting the intrinsic parallelism available using hardware, and the geometric parallelisation of Genetic Programming.     

Compositionality of Hennessy–Milner logic by structural operational semantics

This paper presents a method for the decomposition of HML formulas. It can be used to decide whether a process algebra term satisfies a HML formula, by checking whether subterms satisfy certain formulas, obtained by decomposing the original formula. The method uses the structural operational semantics of the process algebra. The main contribution of this paper is the extension of an earlier decomposition method for the De Simone format from the Ph.D. thesis of Larsen in 1986, to more general formats.     

The connection between an event structure semantics and an operational semantics forTCSP

The relation between an operational interleaving semantics forTSCP based on a transition system and a compositional true concurrency semantics based on event structures is studied. In particular we extend the consistency result of Goltz and Loogan [15] forTCSP processes without recursion to the general case. Thus we obtain for everyTCSP processP that its operational meaningO(P) and the interleaving behaviourO( M3P3) which is derived from the event structureM3P3 associated withP are bisimilar.