A language-independent proof system for full program equivalence

Two programs are fully equivalent if, for the same input, either they both diverge or they both terminate with the same result. Full equivalence is an adequate notion of equivalence for programs written in deterministic languages. It is useful in many contexts, such as capturing the correctness of program transformations within the same language, or capturing the correctness of compilers between two different languages. In this paper we introduce a language-independent proof system for full equivalence, which is parametric in the operational semantics of two languages and in a state-similarity relation. The proof system is sound: a proof tree establishes the full equivalence of the programs given to it as input. We illustrate it on two programs in two different languages (an imperative one and a functional one), that both compute the Collatz sequence. The Collatz sequence is an interesting case study since it is not known whether the sequence terminates or not; nevertheless, our proof system shows that the two programs are fully equivalent (even if we cannot establish termination or divergence of either one).     

A Hoare-like verification system for a language with an exception handling mechanism

This paper presents a Hoare-like system for the language _exc containing typical statements, recursive procedures and an exception handling mechanism. The exception handling mechanism supports both termination and resumption as handler responses to an exception The semantics of the language is defined by a copy rule. The Hoare-like system is based on the system defined in Olderog (1981) for an Algol-like language. It is relatively complete for programs with a finite -index ( stands for a copy rule). The example of a correctness proof fo a simple program is presented.     

Safety verification of Ada programs using software fault trees

The software fault-tree analysis technique is explained. It is then extended to allow its use on a more complex language involving such features as concurrency and exception handling. Ada is used as the example language because many safety-critical projects are using or planning to use Ada. It also contains complex, real-time programming facilities found in other languages used in these types of projects. Software fault-tree analysis uses failure-mode templates to generate the fault tree. The templates provided can be used to define the procedures for applying the technique to programs written in most other declarative languages. To explain the use of the templates an example Ada program, for a traffic-light-control system, is analyzed. The cost and practicality of the method and its implications for software reuse are assessed. The application of the safety analysis procedures to requirements modeling and specification languages is considered     

Testing and verification aspects of Pascal-like languages

This paper addresses aspects of programming language design that affect the ease with which programs written in a language can be subjected to systematic testing and/or program verification. The discussion focuses of Pascal and on several languages that have been derived primarily from Pascal, particularly Euclid and PLAIN. Specific language issues addressed include translation-time checking, program readability, flow of control, support for program modularity, data flow, and program immutability. The relative ease of validating such programs is then determined by the style in which the programs are written. The paper presents some guidelines for writing programs in Pascal-like languages for testability and verifiability.     

An axiomatic proof technique for parallel programs I

Summary A language for parallel programming, with a primitive construct for synchronization and mutual exclusion, is presented. Hoare's deductive system for proving partial correctness of sequential programs is extended to include the parallelism described by the language. The proof method lends insight into how one should understand and present parallel programs. Examples are given using several of the standard problems in the literature. Methods for proving termination and the absence of deadlock are also given.This research was partially supported by National Science Foundation grant GJ-42512.     

一种异常处理机制的设计与实现

异常处理是一种用来检测异常并时其进行处理的技术。异常处理机制已作为现代程序设计语言的一个重要的特性被广泛地采纳，以增强系统运行的可靠性，提高软件的健壮性。对异常处理在程序语言的实现进行了一般性研究，分析比较几种异常处理机制及其实现方法，提出了一种新的异常处理机制的实现方法。     

Java异常处理策略研究

异常处理机制是程序设计语言的重要标志之一,在程序设计过程中用来处理程序运行中的异常。传统的程序设计语言里异常处理较为繁杂。Java是一种面向对象的程序设计语言,且引入了异常处理机制。合理完备的异常处理可以增强程序运行的可靠性、提高软件的健壮性,可以较为快速地确定错误的位置。文章分析了Java异常处理的逻辑,阐述了异常类、异常处理机制以及异常处理方法,提出了异常处理的一些策略。综合运用这些策略可以使编程人员编写出更加简洁、高效的程序代码。     

A Program Logic for Bytecode

Program logics for bytecode languages such as Java bytecode or the .NET CIL can be used to apply Proof-Carrying Code concepts to bytecode programs and to verify correctness properties of bytecode programs. This paper presents a Hoare-style logic for a sequential bytecode kernel language similar to Java bytecode and CIL. The logic handles object-oriented features such as inheritance, dynamic method binding, and object structures with destructive updates, as well as unstructured control flow with jumps. It is sound and complete.     

Advanced exception handling mechanisms

It is no longer possible to consider exception handling as a secondary issue in language design, or even worse, a mechanism added after the fact via a library approach. Exception handling is a primary feature in language design and must be integrated with other major features, including advanced control flow, objects, coroutines, concurrency, real-time, and polymorphism. Integration is crucial as there are both obvious and subtle interactions between exception handling and other language features. Unfortunately, many exception handling mechanisms work only with a subset of the features and in the sequential domain. A framework for a comprehensive, easy to use, and extensible exception handling mechanism is presented for a concurrent, object-oriented environment. The environment includes language constructs with separate execution stacks, e.g. coroutines and tasks, so the exception environment is significantly more complex than the normal single-stack situation. The pros and cons of various exception features are examined, along with feature interaction with other language mechanisms. Both exception termination and resumption models are examined in this environment, and previous criticisms of the resumption model, a feature commonly missing in modern languages, are addressed     

Deductive Synthesis of Numerical Simulation Programs from Networks of Algebraic and Ordinary Differential Equations

Scientists and engineers face recurring problems of constructing, testing and modifying numerical simulation programs. The process of coding and revising such simulators is extremely time-consuming, because they are almost always written in conventional programming languages. Scientists and engineers can therefore benefit from software that facilitates construction of programs for simulating physical systems. Our research adapts the methodology of deductive program synthesis to the problem of constructing numerical simulation codes. We have focused on simulators that can be represented as second order functional programs composed of numerical integration and root extraction routines. We have developed a system that uses first order Horn logic to synthesize numerical simulators built from these components. Our approach is based on two ideas: first, we axiomatize only the relationship between integration and differentiation. We neither attempt nor require a complete axiomatization of mathematical analysis. Second, our system uses a representation in which functions are reified as objects. Function objects are encoded as lambda expressions. Our knowledge base includes an axiomatization of term equality in the lambda calculus. It also includes axioms defining the semantics of numerical integration and root extraction routines. We use depth bounded SLD resolution to construct proofs and synthesize programs. Our system has successfully constructed numerical simulators for computational design of jet engine nozzles and sailing yachts, among others. Our results demonstrate that deductive synthesis techniques can be used to construct numerical simulation programs for realistic applications.     

Program logic and equivalence in the presence of garbage collection

It is generally thought that reasoning about programs in memory safe, garbage collected languages is much easier than in languages where the programmer has more explicit control over memory. Paradoxically, existing program logics are based on a low-level view of storage that is sensitive to the presence or absence of unreachable cells, and Reynolds has pointed out that the Hoare triples derivable in these logics are even incompatible with garbage collection. We present a study of a small language whose operational semantics includes a rule for reclaiming garbage. Our main results include an analysis of propositions that are garbage insensitive, and full abstraction results connecting partial and total correctness to two natural notions of observational equivalence between programs.     

A programming language engineered for beginners

As the complexity and size of programs increase, the programmer is challenged with the task of organizing his program in a manner which will enhance intellectual manageability. Thus, the structure and style are critical in regards to writing programs and verifying their correctness. In recent years, considerable emphasis has been placed on the correctness of programs and techniques for engineering them to be correct. However, more emphasis should be placed on designing languages which facilitate constructing correct programs. In an effort to partially address this problem, a language is described which permits users the convenient development of well-structured programs that are easy to read and understand, easy to correct (debug) and modify, and easy to verify the correctness of the program. The language presented permits the use of decision tables for expressing complex logic.     

Aspects preserving properties

Aspect Oriented Programming can arbitrarily distort the semantics of programs. In particular, weaving can invalidate crucial safety and liveness properties of the base program. In this article, we identify categories of aspects that preserve some classes of properties. Specialized aspect languages are then designed to ensure that aspects belong to a specific category and, therefore, that woven programs will preserve the corresponding properties.Our categories of aspects, inspired by Katz’s, comprise observers, aborters, confiners and weak intruders. Observers introduce new instructions and a new local state but they do not modify the base program’s state and control-flow. Aborters are observers which may also abort executions. Confiners only ensure that executions remain in the reachable states of the base program. Weak intruders are confiners between two advice executions. These categories (along with two others) are defined formally based on a language independent abstract semantics framework. The classes of preserved properties are defined as subsets of LTL for deterministic programs and CTL* for non-deterministic ones. We can formally prove that, for any program, the weaving of any aspect in a category preserves any property in the related class.We present, for most aspect categories, a specialized aspect language which ensures that any aspect written in that language belongs to the corresponding category. It can be proved that these languages preserve the corresponding classes of properties by construction. The aspect languages share the same expressive pointcut language and are designed w.r.t. a common imperative base language.Each category and language is illustrated by simple examples. The appendix provides semantics and two instances of proofs: the proof of preservation of properties by a category and the proof that all aspects written in a language belong to the corresponding category.     

Renaming Detection

Finding changed identifiers is important for understanding the difference between two versions of a program and for detecting and resolving conflicts while merging variants of a program together. Standard practice for differencing and merging relies on line based techniques that do not recognize renamed identifiers. The design and implementation of a tool to automatically detect renamed identifiers between two versions of a program is presented. The system uses an abstract representation of language constructs to enable language awareness without introducing language dependence. Modules for Java and Scheme have been written. The detector works with multiple file pairs, taking into account renamings that span several files. A case study is presented that demonstrates proof of concept. The detector is part of a suite of intelligent differencing and merging programs that exploit the static semantics of programming languages.     

NDAUTO：An Experimental Software Automation System

This paper describer the design and implementation of an experimental software automation system(NDAUTO).By combining the transformational and procedural approaches in software gutomation,the system can tansform software unctional specifications written in a graphical specification language GSPEC to executable programs sutomatically,The equivalence between a specification and its corresponding program can be guaranteed by the system,and the correctness of the specification can also be validated.The main new points of the work lie in the design of the specification languange,the transformation mechanism and the correctness validation of the specification.     

一种基于规则的语言的公理语义

为了准确描述离散事件控制系统对象之间的逻辑关系和编写控制程序,提出了一种基于规则的语言——逻辑规则描述语言（LRDL）。用EBNF给出了LRDL的语法定义,基于Hoare逻辑的公理系统,形式化地给出并证明了LRDL的公理语义,为用LRDL编写的程序的正确性证明提供了理论依据。     

Static analysis of logical languages with deferred update semantics

Static analysis of declarative languages deals with the detection, at compile time, of program properties that can be used to better understand the program semantics and to improve the efficiency of program evaluation. In logical update languages, an interesting problem is the detection of conflicting updates, inserting and deleting the same fact, for transactions based on set-oriented updates and active rules. In this paper, we investigate this topic in the context of the U-Datalog language, a set-oriented update language for deductive databases, based on a deferred semantics. We first formally define relevant properties of U-Datalog programs, mainly related to update conflicts. Then, we prove that the defined properties are decidable and we propose an algorithm to detect such conditions. Finally, we show how the proposed techniques can be applied to other logical update languages. Our results are based on the concept of labeling and query-tree.     

Performance analysis of GAME: A generic automated marking environment

This paper describes the Generic Automated Marking Environment (GAME) and provides a detailed analysis of its performance in assessing student programming projects and exercises. GAME has been designed to automatically assess programming assignments written in a variety of languages based on the “structure” of the source code and the correctness of the program’s output. Currently, the system is able to mark programs written in Java, C++ and the C language. To use the system, instructors are required to provide a simple “marking schema” for each given assessment item, which includes pertinent information such as the location of files and the model solution. In this research, GAME has been tested on a number of student programming exercises and assignments and its performance has been compared against that of a human marker. An in-depth statistical analysis of the comparison is presented, providing encouraging results and directions for employing GAME as a tool for teaching and learning.     

Static and Dynamic Characteristics of XPL Programs

One use of performance measurement techniques is in the study of operational characteristics of programs written in high-level programming languages. Information derived from such studies can be used to construct benchmark programs and synthetic workloads,^1,2detect inefficiencies in programming language implementation, and suggest possible improvements in the design of computers.^3,9,10Our main interest is in the latter area: the discovery of primitive operations, implied by the semantics of a programming language, that can be added to the firmware or hardware of a computer to improve overall system performance. These computer architecture optimization techniques have been applied in several studies^3,9and have been used commercially to design efficient pseudo machines for the Burroughs B1700.^10,12