The formal definition of a real-time language

Summary This paper presents the formal definition of TOMAL (Task-Oriented Microprocessor Applications Language), a programming language intended for real-time systems running on small processors. The formal definition addresses all aspects of the language. Because some modes of semantic definition seem particularly well-suited to certain aspects of a language, and not as suitable for others, the formal definition employs several complementary modes of definition.The primary definition is axiomatic and is employed to define most statements of the language. Simple, denotational (but not lattice-theoretic) semantics complement the axiomatic semantics to define type-related features, such as binding of names to types, data type coercions, and evaluation of expressions. Together, the axiomatic and denotational semantics define all features of the sequential language. An operational definition is used to define real-time execution, and to extend the axiomatic definition to account for all aspects of concurrent execution. Semantic constraints, sufficient to guarantee conformity of a program with the axiomatic definition, can be checked by analysis of a TOMAL program at compilation.     

Two Congruent Semantics for Prolog with CUT

The development of a formal semantics for a given programming language can proceed in several stages,At each stage we give an alternative semantic definition of the language,and each definition embodies successively more and more implementation details.Then we formulate and prove at each stage the congruence conditions between successive definitions in the sequence.This paper presents two formal semantics for Prolog with “cut” and shows the congruence condition between them.     

Two-level grammar as an implementable metalanguage for axiomatic semantics

Two-level grammars can define the syntax and the operational semantics of programming languages and these definitions are directly executable by interpretation. In this paper it is shown that axiomatic semantics can also be defined using a two-level grammar with the result being a partially automatic program verification system accomplished within the framework of a language definition. These results imply that a programming language can be defined operationally and axiomatically together in complementary definitions as advocated by Hoare and Lauer. Because two-level grammars are executable, these complementary definitions accomplish a system for interpreting and verifying programs.     

Toward the Next Generation of Data Modeling Tools

This paper describes the Update Protocol Model (UPM), a formal language for the expression of database update semantics. UPM has been used primarily to capture and communicate in a precise and uniform notation the plethora of database semantics described by a variety of "fourth generation" models, many of which are imprecise when it comes to update semantics. Several computing trends–knowledge-based expert systems, distributed database management systems, and new applications based on higher order semantic models–point to the need for modeling techniques beyond that which current data models such as the relational and entity-relationship models provide.     

Cardinality constraints in semantic data models

Constraints are central to the notion of a semantic data model. How well a model captures constraints affects its power and viability as a semantic data model. Cardinality constraints are an important subclass of general constraints. In this paper we provide formal definitions for cardinality constraints of several semantic models, as described in the literature. We construct a partial ordering of these constraints that shows the relative power expressed by each cardinality constraints. We discuss our results and offer possible extensions to contemporary cardinality constraint definitions. Our contributions include a collection and formal definition of existing cardinality constraints, a partial ordering of this set, and recommendations for cardinality constraint mechanisms in semantic data models.     

Constructing language processors with algebra combinators

Modular Monadic Semantics (MMS) is a well-known mechanism for structuring modular denotational semantic definitions for programming languages. The principal attraction of MMS is that families of language constructs can be independently specified and later combined in a mix-and-match fashion to create a complete language semantics. This has proved useful for constructing formal, yet executable, semantics when prototyping languages. In this work we demonstrate that MMS has an additional software engineering benefit. In addition to composing semantics for various language constructs, we can use MMS to compose various differing semantics for the same language constructs. This capability allows us to compose and reuse orthogonal language tasks such as type checking and compilation. We describe algebra combinators, the principal vehicle for achieving this reuse, along with a series of applications of the technique for common language processing tasks.     

Specifications and an implementation of the type-ambiguity problem in pascal

Certain ambiguities in the definition of Pascal imperil the portability of Pascal programs. Specifications and an implementation of alternative interpretations are presented. Context-free grammars augmented with guarded commands are demonstrated as a notation for specifying the static context-sensitive constraints of programming languages. Most of the advantages of context-free grammars are preserved and yet the potential range of the syntactic definition component has been extended to encompass all static constraints. Context-sensitive syntax typically tends to either clutter the semantic definition component or (as with type equivalence in Pascal) result in undesirable implementor-dependent decisions. An implementation of a CFG-based parser that automatically checks for the defined context-sensitive constraints is also described. In addition stepwise abstraction is introduced as a practical technique for communicating formal programming language definitions.     

面向对象编程体裁中继承机制语义的Γ_(γω)理论描述:多重继承

_(γω)理论是一种一阶数学理论,它融合γω演算与谓词演算于一体.本文运用_(γω)理论来描述面向对象编程体裁(00PP)中一种多重继承机制的语义,它象公理语义一样抓住了(语义)问题的本质._(γω)理论在这里起了公理语义学的作用.这种语义描述简明得象Prolog程序一样,并且可望得到多层次多体裁编程语言Lyusia的支持,变得可执行的,从而可用作验证程序正确性.     

A comparative study of two formal semantics of the SIGNAL language

SIGNAL is a part of the synchronous languages family, which are broadly used in the design of safety-critical real-time systems such as avionics, space systems, and nuclear power plants. There exist several semantics for SIGNAL, such as denotational semantics based on traces (called trace semantics), denotational semantics based on tags (called tagged model semantics), operational semantics presented by structural style through an inductive definition of the set of possible transitions, operational semantics defined by synchronous transition systems (STS), etc. However, there is little research about the equivalence between these semantics. In this work, we would like to prove the equivalence between the trace semantics and the tagged model semantics, to get a determined and precise semantics of the SIGNAL language. These two semantics have several different definitions respectively, we select appropriate ones and mechanize them in the Coq platform, the Coq expressions of the abstract syntax of SIGNAL and the two semantics domains, i.e., the trace model and the tagged model, are also given. The distance between these two semantics discourages a direct proof of equivalence. Instead, we transformthem to an intermediate model, which mixes the features of both the trace semantics and the tagged model semantics. Finally, we get a determined and precise semantics of SIGNAL.     

基于UML类图的模糊时空数据建模

模糊性广泛存在于时空应用领域,现有的时空数据模型缺乏描述和表达模糊时空对象内在机制和语义关系的能力。通过研究模糊时空数据语义,给出了模糊时空数据模型的形式化定义,在此基础上对UML类图进行扩展,提出一种模糊时空UML数据模型,并用例子说明本文所提模糊时空数据模型的可用性。     

A model for the formal definition of programming languages

An operational model which allows the complete formal definition of the full syntax and, particularly, semantics of programming languages is described. Both its syntactic and semantic parts are based on so-called linked-forest manipulation systems which allow the definition of mappings on forests. The idea of “linking” is crucial for the given model, we represent not only abstract programs but also intermediate states of our system (abstract computer) by labelled forests with pointers.     

A structured approach to static semantics correctness

An approach to the correctness proof of static semantics with respect to the standard semantics of a programming language is presented, where correctness means that the properties of the language described by the static semantics, such as type checking, are consistent with the standard semantics. The standard and static semantics are given in a denotational style in terms of some basic domains and domain constructors, which, together with suitable operations, are used to describe fundamental semantic concepts. The domains have different meaning in the two semantics and the static semantics correctness proof is carried out by devising a set of suitable functions between them. We show that the correctness proof can be greatly simplified by structuring the semantics definitions, and we illustrate that by applying the methodology to a simple imperative language. In the example the derivation of a static checking algorithm from the static semantics is described.     

Non-deterministic data types: models and implementations

Summary The model theoretic basis for (abstract) data types is generalized from algebras to multi-algebr as in order to cope with non-deterministic operations. A programming oriented definition and a model theoretic criterion (called simulation) for implementation of data types are given. To justify the criterion w.r.t. the definition, an abstract framework linking denotational semantics of programming languages and model theory of data types is set up. A set of constraints on a programming language semantics are derived which guarantee that simulation implies implementation. It is argued that any language supporting data abstraction does fulfill these constraints. As an example a simple but expressive language L is defined and it is formally proved that L does conform to these restrictions.     

A layered semantics for a parallel object-oriented language

We develop a denotational semantics for POOL, a parallel object-oriented programming language. The main contribution of this semantics is an accurate mathematical model of the most important concept in object-oriented programming: the object. This is achieved by structuring the semantics in layers working at three different levels: for statements, objects and programs. For each of these levels we define a specialized mathematical domain of processes, which we use to assign a meaning to each language construct. This is done in the mathematical framework of complete metric spaces. We also define operators that translate between these domains. At the program level we give a precise definition of the observable input/output behaviour of a particular program, which could be used at a later stage to decide the issue of full abstractness. We illustrate our semantic techniques by first applying them to a toy language similar to CSP.This paper describes work done in ESPRIT Basic Research Action 3020,Integration.     

A Rewriting Logic Approach to Operational Semantics (Extended Abstract)

This paper shows how rewriting logic semantics (RLS) can be used as a computational logic framework for operational semantic definitions of programming languages. Several operational semantics styles are addressed: big-step and small-step structural operational semantics (SOS), modular SOS, reduction semantics with evaluation contexts, and continuation-based semantics. Each of these language definitional styles can be faithfully captured as an RLS theory, in the sense that there is a one-to-one correspondence between computational steps in the original language definition and computational steps in the corresponding RLS theory. A major goal of this paper is to show that RLS does not force or pre-impose any given language definitional style, and that its flexibility and ease of use makes RLS an appealing framework for exploring new definitional styles.     

A rewriting logic approach to operational semantics

This paper shows how rewriting logic semantics (RLS) can be used as a computational logic framework for operational semantic definitions of programming languages. Several operational semantics styles are addressed: big-step and small-step structural operational semantics (SOS), modular SOS, reduction semantics with evaluation contexts, continuation-based semantics, and the chemical abstract machine. Each of these language definitional styles can be faithfully captured as an RLS theory, in the sense that there is a one-to-one correspondence between computational steps in the original language definition and computational steps in the corresponding RLS theory. A major goal of this paper is to show that RLS does not force or pre-impose any given language definitional style, and that its flexibility and ease of use makes RLS an appealing framework for exploring new definitional styles.     

一个并发对象演算

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

Typical examples of using the atoment language

Atoment is a domain-specific language of executable specifications applied to describe methods and techniques of program verification. In this paper, a series of typical examples of using the Atoment language covering program models; the operational, transformational, and axiomatic semantics; and the formal specification of programming languages is presented.