Using inspections to investigate program correctness

An approach to inspections is proposed that would emphasize the search for correctness. It would hold up to scrutiny to not only what is on the page, but also the thought behind the representation. Inspectors would investigate how the program developed, looking for evidence of disciplined methods in its construction, adequate consideration of the error domain, and the program's ability to withstand years of use and inevitable change. An example inspection is given that uses a program developed according to IBM's design methods. The inspection presents the arguments as a series of questions that the inspectors would ask the author and themselves     

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.     

Axiomatic approach to total correctness of programs

Summary We present here an axiomatic approach which enables one to prove by formal methods that his program is totally correct (i.e., it terminates and is logically correct—does what it is supposed to do). The approach is similar to Hoare's approach [3] for proving that a program is partially correct (i.e., that whenever it terminates it produces correct results). Our extension to Hoare's method lies in the possibility of proving both correctness and termination by one unified formalism. One can choose to prove total correctness by a single step, or by incremental proof steps, each step establishing more properties of the program.     

An approach to a unified theory of grammar and L forms

We present one approach within which the dissimilar developments of the grammar form and the L form theories can be unified. Our results also shed light on the inherent differences of parallel and sequential rewriting.     

Multilevel structured program designs and correctness proving

A mathematical model of a program specification and design language is considered. A system of axioms is proposed for proving formulas interpreted as assertions of logical consistency of specifications. The results provide a mathematical foundation for the development of MSPD tools.Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 98–107, September–October, 1991.     

An architectural approach to improved program maintainability

A programming standard is described, with the emphasis on the visual aspects of the final product rather than on how the programs are engineered.     

基于程序正确性的演算方法

为了使开发出的程序更具有可靠性,研究了两种正确性验证的演算方法,Dijkstra的最弱前置谓词变换法和Hoare的公理化方法.针对于Hoare公理化方法证明中的前置条件难以寻找的问题,提出了将这两种演算方法结合使用的方法.对最弱前置谓词变换法的过程进行分析,确定了最弱前置谓词算法的准确性.将最弱前置谓词应用到公理化方法中,即把最弱前置谓词变换法求出的前置谓词作为公理化方法的前置条件.通过一个具体实例,详细说明了其验证过程,并证明了该方法的有效性.     

A correctness proof of an indenting program

The correctness of an indenting program for Pascal is proved at an intermediate level of rigour. The specifications of the program are given in the companion paper.¹ The program is approximately 330 lines long and consists of four modules: io, lex, stack and indent. We prove first that the individual procedures contained in these modules meet their specifications as given by the entry and exit assertions. A global proof of the main routine then establishes that the interaction between modules is such that the main routine meets the specification of the entire program. We argue that correctness proofs at the level of rigour used here serve very well to transfer one's understanding of a program to others. We believe proofs at this level should become commonplace before more formal proofs can take over to reduce traditional testing to an inconsequential place.     

Constraint-based correctness proofs for logic program transformations

Many approaches proposed in the literature for proving the correctness of unfold/fold transformations of logic programs make use of measures associated with program clauses. When from a program P ₁ we derive a program P ₂ by applying a sequence of transformations, suitable conditions on the measures of the clauses in P ₂ guarantee that the transformation of P ₁ into P ₂ is correct, that is, P ₁ and P ₂ have the same least Herbrand model. In the approaches proposed so far, clause measures are fixed in advance, independently of the transformations to be proved correct. In this paper we propose a method for the automatic generation of clause measures which, instead, takes into account the particular program transformation at hand. During the application of a sequence of transformations we construct a system of linear equalities and inequalities over nonnegative integers whose unknowns are the clause measures to be found, and the correctness of the transformation is guaranteed by the satisfiability of that system. Through some examples we show that our method is more powerful and practical than other methods proposed in the literature. In particular, we are able to establish in a fully automatic way the correctness of program transformations which, by using other methods, are proved correct at the expense of fixing in advance sophisticated clause measures.     

A functional correctness model of program verification

A model whose verification conditions depend only on elementary symbolic execution of a trace table is presented. The method is applied to rather simple programs. However, even in large complex implementations, the techniques can be applied informally to determine the functionality of complex interactions. The technique is easy to learn (it is used in a freshman computer science course) and lends itself to automation     

An approach to effortless construction of program animations

Program animation systems have not been as widely adopted by computer science educators as we might expect from the firm belief that they can help in enhancing computer science education. One of the most notable obstacles to their adoption is the considerable effort that the production of program animations represents for the instructor. We present here an approach to reduce such a workload based on the automatic generation of visualizations and animations. The user may customize them in a user-friendly way to construct more expressive program animations. These operations are carried out by means of a user-friendly manipulation based on the metaphor of office documents. We have applied this approach to the functional paradigm by extending the WinHIPE programming environment. Finally, we report on the successful results of an evaluation performed to measure its ease of use.     

An elementary state space approach to RH optimal control

This paper presents a new elementary approach to the H-infinity optimal control problem. No knowledge about function spaces is needed to derive the solutions. Only a few results in linear system theory, some matrix manipulations and the classical Cauchy integral theorem are used.     

Data structures and program correctness: Bridging the gap

An assertion language for data structures is presented, leading to the following results: formal semantics of operations on data structures are given in terms of the weakest precondition formula for assignment statements; input/output specifications for data-structure manipulating algorithms can be stated with precision; there is a clear relationship between the output specification and intermediate assertions; and knowledge about standard types of data structures can be schematized. These ideas are illustrated on an algorithm to reverse the arcs on a one-way linked list, and on a threaded tree example.     

A unified approach to smoothing formulas

Based on various approaches, several different solutions to the smoothing problem have been given. The relationships between these solutions are not immediate, although they solve the same problem. Making use of a certain framework from scattering theory, we derive two families of solutions, with equations evolving forwards and backwards in time, respectively. Within these families three major previous approaches are obtained as special cases, and their relationships are clarified. The set of solutions also contains as a fourth special case a (new) backwards analog of the innovations solution. The Mayne-Fraser two-filter formula belongs to the set of backwards solutions, and within this framework certain difficulties with its interpretation can be resolved.     

A unified approach to layout wirability

We consider the problem of wiring planar knock-knee mode layouts. We present a systematic approach to this problem and develop a unified framework that also applies to layouts using grids that are more general than the usual square grid, and determine all possible grids that satisfy some natural regularity criteria. We develop some specific techniques for wiring of layouts in the square grid. As one of the applications of these techniques, we give a simple characterization of two-layer wirability of an arbitrary layout.On leave from the Institute of Computer Science, Polish Academy of Sciences, P.O. Box 22, 00-901 Warsaw, Poland. W. Lipski tragically died on May 30, 1985.The work of F. P. Preparata was supported in part by the Semiconductor Research Corporation under Contract SRC RSCH 84-06-049.     

A unified approach to pattern recognition

The paper is an outline of a new approach to pattern recognition developed by the author. A fuller introduction to the approach will appear soon.⁽¹⁾ Within the proposed framework the two principal approaches to pattern recognition—vector and syntactic—are unified.