On the call-by-value CPS transform and its semantics

We investigate continuations in the context of idealized call-by-value programming languages. On the semantic side, we analyze the categorical structures that arise from continuation models of call-by-value languages. On the syntactic side, we study the call-by-value continuation-passing transformation as a translation between equational theories. Among the novelties are an unusually simple axiomatization of control operators and a strengthened completeness result with a proof based on a delaying transform.     

Preprocessing embedded actions

Some parser generators allow the user to attach actions, consisting of executable code, to syntax rules. Actions are usually in the local programming language, so they are simply copied into the generated parser. However, we show two situations in which it is convenient to allow actions to be in a different notation. A preprocessor is used to translate such notations into the local programming language. A preprocessor must know where to find actions and how to translate them. We show how these two activities can be programmed separately. Often, the user only has to worry about the second part: once the parser generator is known, the placement of the actions is known as well, so routines for finding actions can be separately compiled and linked in. Examples in the paper are based on the parser generator Yacc, but the approach is not limited to Yacc, or even to parser generators. Certain compositions of syntax-directed translations can be implemented by preprocessing actions.     

Grammar semantics, analysis and parsing by abstract interpretation

We study abstract interpretations of a fixpoint protoderivation semantics defining the maximal derivations of a transitional semantics of context-free grammars akin to pushdown automata. The result is a hierarchy of bottom-up or top-down semantics refining the classical equational and derivational language semantics and including Knuth grammar problems, classical grammar flow analysis algorithms and parsing algorithms.     

On the Codd semantics of SQL nulls

Theoretical models used in database research often have subtle differences with those occurring in practice. One particular mismatch that is usually neglected concerns the use of marked nulls to represent missing values in theoretical models of incompleteness, while in an SQL database these are all denoted by the same syntactic

object. It is commonly argued that results obtained in the model with marked nulls carry over to SQL, because SQL nulls can be interpreted as Codd nulls, which are simply marked nulls that do not repeat. This argument, however, does not take into account that even simple queries may produce answers where distinct occurrences of

do in fact denote the same unknown value. For such queries, interpreting SQL nulls as Codd nulls would incorrectly change the semantics of query answers. To use results about Codd nulls for real-life SQL queries, we need to understand which queries preserve the Codd interpretation of SQL nulls. We show, however, that the class of relational algebra queries preserving Codd interpretation is not recursively enumerable, which necessitates looking for sufficient conditions for such preservation. Those can be obtained by exploiting the information provided by NOT NULL constraints on the database schema. We devise mild syntactic restrictions on queries that guarantee preservation, do not limit the full expressiveness of queries on databases without nulls, and can be checked efficiently.     

Refunctionalization at work

We present the left inverse of Reynolds’ defunctionalization and we show its relevance to programming and to programming languages. We propose two methods to transform a program that is almost in defunctionalized form into one that is actually in defunctionalized form, and we illustrate them with a recognizer for Dyck words and with Dijkstra’s shunting-yard algorithm.     

Operational semantics of the Java Card Virtual Machine

We present the operational semantics of Carmel, a language that models the Java Card Virtual Machine Language. We define a small-step relation between program configurations, including rules for exception handling, array objects and subroutines. We also include the basic structures needed to model object ownership and the Java Card firewall.     

Strongly reducing variants of the Krivine abstract machine

We present two variants of the Krivine abstract machine that reduce lambda-terms to full normal form. We give a proof of their correctness by interpreting their behaviour in the λ σ-calculus. This article is an extended version of a paper presented at the ‘Lisp and Functional Programming’ Conference in 1990 and the work was done at Ecole Normale Supérieure between 1989 and 1991.     

The semantics of the combination of atomized statements and parallel choice

In this paper we define a uniform language that is an extension of the language underlying the process algebraPA. One of the main extensions of this language overPA is given by so-called atomizing brackets. If we place these brackets around a statement then we treat this statement as an atomic action. Put differently, these brackets remove all interleaving points. We present a transition system for the language and derive its operational semantics. We show that there are several options for defining a transition system such that the resulting operational semantics is a conservative extension of the semantics forPA. We define a semantic domain and a denotational model for the language. Next we define a closure operator on the semantic domain and show how to use this closure operator to derive a fully abstract denotational semantics. Then the algebraic theory of the language is considered. We define a collection of axioms and a term rewrite system based on these axioms. Using this term rewrite system we are able to identify normal forms for the language. It is shown that these axioms capture the denotational equality. It follows that if two terms are provably equal then they have the same operational semantics. Finally, we show how to extend the axiomatization in order to axiomatize its operational equivalence.     

Complexity of semi-stable and stage semantics in argumentation frameworks

In this work, we answer two questions about the complexity of semi-stable semantics for abstract argumentation frameworks: we show -completeness for the problem of deciding whether an argument is skeptically accepted, and respectively, -completeness for the problem of deciding whether an argument is credulously accepted under the semi-stable semantics. Furthermore, we extend these complexity bounds to the according decision problems for stage semantics and discuss two approaches towards tractability.     

On Probabilistic Techniques for Data Flow Analysis

We present a semantics-based technique for analysing probabilistic properties of imperative programs. This consists in a probabilistic version of classical data flow analysis. We apply this technique to pWhile programs, i.e programs written in a probabilistic version of a simple While language. As a first step we introduce a syntax based definition of a linear operator semantics (LOS) which is equivalent to the standard structural operational semantics of While. The LOS of a pWhile program can be seen as the generator of a Discrete Time Markov Chain and plays a similar role as a collecting or trace semantics for classical While. Probabilistic Abstract Interpretation techniques are then employed in order to define data flow analyses for properties like Parity and Live Variables.     

A cognitive semantics for the association construct

The unified modelling language (UML), besides its traditional use in describing software artifacts, is increasingly being used for conceptual modelling, the activity of describing an application domain. For models to be clear and unambiguous, every construct of the modelling language must have well-defined semantics, which is its mapping to elements of the semantic domain. When used for conceptual modelling, the semantic domain of UML is the application domain, as perceived by the modeller. Modellers perceive and structure their perceptions using cognitive concepts. This paper proposes a mapping of the UML association construct to those concepts. Implications for the use of the association construct for conceptual modelling are derived, a UML profile for conceptual modelling is presented, along with the results of a case study using the semantics and profile.

A practical study of semi-automatic OSI protocol implementation

Communication protocols form a language which can be recognized by extended finite automata, and compiler generating tools can help with its implementation. This paper presents a project for implementing the ISO OSI layers which are most relevant to LANs. Taking advantage of modular and repetitive OSI architecture, a layer implementation model is proposed, introducing sharp distinctions between protocol layer-dependent and independent modules, so that the implementation effort can be largely reduced. It is also shown that layer-dependent modules can be generated automatically by using software tools developed for compiler construction. It is assumed that the protocols to be implemented have already been verified and validated in their abstract forms using other techniques, since these aspects are not covered by the method proposed. Measures of program sizes and execution speeds obtained following the approach proposed are reported; they show that most of the layer code can be produced by automatic tools and the overall software complexity enables the OSI architecture to be implemented for single-board microcomputers.     

A fully abstract semantics of classes for Object-Z

This paper presents a fully abstract semantics of classes for the object oriented formal specification language Object-Z. Such a semantics includes no unnecessary syntactic details and, hence, describes a class in terms of the external behaviour of its objects only. The semantics, based on an extension of existing process models, defines a notion of behavioural equivalence which is stronger than that of CSP and weaker than that of CCS.     

A timed semantics of Orc

Orc is a kernel language for structured concurrent programming. Orc provides three powerful combinators that define the structure of a concurrent computation. These combinators support sequential and concurrent execution, and concurrent execution with blocking and termination.Orc is particularly well-suited for task orchestration, a form of concurrent programming with applications in workflow, business process management, and web service orchestration. Orc provides constructs to orchestrate the concurrent invocation of services while managing time-outs, priorities, and failures of services or communication.Our previous work on the semantics of Orc focused on its asynchronous behavior. The inclusion of time or the effect of delay on a computation had not been modeled. In this paper, we define an operational semantics of Orc that allows reasoning about delays, which are introduced explicitly by time-based constructs or implicitly by network delays. We develop a number of identities among Orc expressions and define an equality relation that is a congruence. We also present a denotational semantics in which the meaning of an Orc program is a set of traces, and show that the two semantics are equivalent.     

Declarative semantics of transactions in ORM

In order to specify databases completely at the conceptual level, conceptual database specification languages should contain a data definition (sub)language (DDL), for specifying data structures (+constraints), a data retrieval (sub)language (DRL), for specifying queries, as well as a (declarative) data manipulation (sub)language (DML), for specifying transactions.Object Role Modeling (ORM) is a powerful method for designing and querying database models at the conceptual level. By means of verbalization the application is also described in natural language as used by domain experts, for communication and validation purposes. ORM currently comprises a DDL and a DRL (ConQuer). However, the ORM-method does not yet contain an expressive DML for specifying transactions at the conceptual level.In an earlier paper we designed a syntactic extension of the ORM-method with a DML for specifying transactions at the conceptual level in a purely declarative way. For all transactions we proposed syntaxes, verbalizations, and diagrams. However, we did not give a formal semantics then.The purpose of this paper is to add a clear, formal and purely declarative semantics to the proposed ORM-transactions. The paper also formally defines rollbacks and illustrates everything with examples (including a solution to a well-known transaction specification problem). The extension of ORM with an expressive set of completely declaratively specified transactions makes ORM complete as a database specification method at the conceptual level.     

The computational complexity of ideal semantics

We analyse the computational complexity of the recently proposed ideal semantics within both abstract argumentation frameworks (afs) and assumption-based argumentation frameworks (abfs). It is shown that while typically less tractable than credulous admissibi-lity semantics, the natural decision problems arising with this extension-based model can, perhaps surprisingly, be decided more efficiently than sceptical preferred semantics. In particular the task of finding the unique ideal extension is easier than that of deciding if a given argument is accepted under the sceptical semantics. We provide efficient algorithmic approaches for the class of bipartite argumentation frameworks and, finally, present a number of technical results which offer strong indications that typical problems in ideal argumentation are complete for the class of languages decidable by polynomial time algorithms allowed to make non-adaptive queries to a C oracle, where C is an upper bound on the computational complexity of deciding credulous acceptance: C=np for afs and logic programming (lp) instantiations of abfs; for abfs modelling default theories.     

Inductive inference of logic programs based on algebraic semantics

In this paper we present a new inductive inference algorithm for a class of logic programs, calledlinear monadic logic programs. It has several unique features not found in Shapiro’s Model Inference System. It has been proved that a set of trees isrational if and only if it is computed by a linear monadic logic program, and that the rational set of trees is recognized by a tree automaton. Based on these facts, we can reduce the problem of inductive inference of linear monadic logic programs to the problem of inductive inference of tree automata. Further several efficient inference algorithms for finite automata have been developed. We extend them to an inference algorithm for tree automata and use it to get an efficient inductive inference algorithm for linear monadic logic programs. The correctness, time complexity and several comparisons of our algorithm with Model Inference System are shown.     

Functional semantics of programs with exceptions

Linguistic mechanisms for exception handling facilitate the production of reliable software and play an important role in fault tolerant computing. This paper describes the functional semantics of a Pascal-like language which supports exception handling and data abstraction. A program with exceptions is considered as having a standard semantics, as well as an exceptional semantics for each exception that may be signaled during its execution. Standard functional semantics methods provide rules to obtain the function representing the standard semantics. In this paper, we provide rules to determine the functions representing the exceptional semantics. We also describe a method for specifying and verifying the correctness of implementation of data types with exceptions.     

Edge-to-cloud sensing and actuation semantics in the industrial Internet of Things

There are billions of devices worldwide deployed, connected, and communicating to other systems. Sensors and actuators, which can be stationary or movable devices. These Edge devices are considered part of the Internet of Things (IoT) devices, which can be referred to as a tier of the Computing Continuum paradigm. There are two main concerns at stake in the success of this ecosystem. The interoperability between devices and systems is the first. Mainly, because most of them communicate uniquely and differently from each other, leading to heterogeneous data. The second issue is the lack of decision-making capacity to conduct actuations, such as communicating through different computing tiers based on latency constraints due to a certain measured factor. In this article, we propose an ontology to improve device interoperability in the IoT. In addition, we also explain how to ease data communication between Computing Continuum devices, providing tools to enhance data management and decision-making. A use case is also presented, using the automotive industry, where quickness in maneuver determination is key to avoid accidents. It is exemplified using two Raspberry Pi devices, connected using different networks and choosing the appropriate one depending on context-aware conditions.