Correctness proofs of CSP programs

In a research report we have proposed an axiomatic semantics for the language of communicating sequential processes (CSP) of Hoare (1978). In this paper, we use the axiomatic semantics to prove the correctness of a number of CSP programs.     

Compositional verification of sequential programs with procedures

We present a method for algorithmic, compositional verification of control-flow-based safety properties of sequential programs with procedures. The application of the method involves three steps: (1) decomposing the desired global property into local properties of the components, (2) proving the correctness of the property decomposition by using a maximal model construction, and (3) verifying that the component implementations obey their local specifications. We consider safety properties of both the structure and the behaviour of program control flow. Our compositional verification method builds on a technique proposed by Grumberg and Long that uses maximal models to reduce compositional verification of finite-state parallel processes to standard model checking. We present a novel maximal model construction for the fragment of the modal μ-calculus with boxes and greatest fixed points only, and adapt it to control-flow graphs modelling components described in a sequential procedural language. We extend our verification method to programs with private procedures by defining an abstraction, presented as an inlining transformation. All algorithms have been implemented in a tool set automating all required verification steps. We validate our approach on an electronic purse case study.     

Combinator evaluation of functional programs with logical variables

A technique is presented that brings logical variables into the scope of the well-known Turner method for normal order evaluation of functional programs by S, K, I combinator graph reduction. This extension is illustrated bySASL+LV, an extension of Turner's languageSASL in which arbitrary expressions serve as formal parameters, and parameter passage is done by unification. The conceptual and practical advantages of such an extension are discussed, as well as semantic pitfalls that arise from the attendant weakening of referential transparency. Only five new combinators (LV, BV, FN, FB and UNIFY) are introduced. The resulting object code is fully upward compatible in the sense that previously compiledSASL programs remain executable with unchanged semantics. However,read-only variable usage inSASL+LV programs requires amultitasking extension of the customary stack-based evaluation method. Mechanisms are presented for managing this multitasking on both single and multiprocessor systems. Finally, directions are mentioned for applying this technique to implementations involving larger granularity combinators, and fuller semantic treatment of logical variables (e.g. accommodation of failing unifications).Research was supported in part by the Marcus Wallenberg Foundation.Research supported in part by grant CCR-8704778 from the National Science Foundation, and by an unrestricted gift from Telefonaktiebolaget LM Ericsson, Stockholm.     

Efficient global sensitivity analysis with correlated variables

Existing methods for the computation of global sensitivity indices are challenged by both number of input-output samples required and the presence of dependent or correlated variables. First, a methodology is developed to increase the efficiency of sensitivity computations with independent variables by incorporating optimal space-filling quasi-random sequences into an existing importance sampling-based kernel regression sensitivity method. Two prominent situations where parameter correlations cannot be ignored, however, are (1) posterior distributions of calibrated parameters and (2) transient, coupled simulations. Therefore, the sensitivity methodology is generalized to dependent variables allowing for efficient post-calibration sensitivity analyses using input-output samples obtained directly from Bayesian calibration. These methods are illustrated using coupled, aerothermal simulations where it is observed that model errors and parameter correlations control the sensitivity estimates until coupling effects become dominant over time.     

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.     

Organizing programs without classes

All organizational functions carried out by classes can be accomplished in a simple and natural way by object inheritance in classless languages, with no need for special mechanisms. A single model—dividing types into prototypes and traits—supports sharing of behavior and extending or replacing representations. A natural extension, dynamic object inheritance, can model behavioral modes. Object inheritance can also be used to provide structured name spaces for well-known objects. Classless languages can even express class-based encapsulation. These stylized uses of object inheritance become instantly recognizable idioms, and extend the repertory of organizing principles to cover a wider range of programs.This work has been generously supported by National Science Foundation Presidential Young Investigator Grant # CCR-8657631, and by Sun Microsystems, IBM, Apple Computer, Cray Laboratories, Tandem Computers, NCR, Texas Instruments, and DEC.     

Regression for ordinal variables without underlying continuous variables

Several techniques exist nowadays for continuous (i.e. numerical) data analysis and modeling. However, although part of the information gathered by companies, statistical offices and other institutions is numerical, a large part of it is represented using categorical variables in ordinal or nominal scales. Techniques for model building on categorical data are required to take advantage of such a wealth of information. In this paper, current approaches to regression for ordinal data are reviewed and a new proposal is described which has the advantage of not assuming any latent continuous variable underlying the dependent ordinal variable. Estimation in the new approach can be implemented using genetic algorithms. An artificial example is presented to illustrate the feasibility of the proposal.     

Estimation of global sensitivity indices for models with dependent variables

A novel approach for estimation variance-based sensitivity indices for models with dependent variables is presented. Both the first order and total sensitivity indices are derived as generalizations of Sobol? sensitivity indices. Formulas and Monte Carlo numerical estimates similar to Sobol? formulas are derived. A copula-based approach is proposed for sampling from arbitrary multivariate probability distributions. A good agreement between analytical and numerical values of the first order and total indices for considered test cases is obtained. The behavior of sensitivity indices depends on the relative predominance of interactions and correlations. The method is shown to be efficient and general.     

Studies in the theory of algebraic models of programs with procedures

Algebraic models of programs with procedures extend algebraic models of programs that are free of procedures (simple models of programs). A specific feature of both types of models is that they are built for some formalization of software programs. Models of programs are intended for studying functional equivalence of formalized programs and constructing wide sets of equivalent transformations of programs. Two basic problems in the theory of algebraic models of programs are the equivalence problem and the problem of building complete systems of equivalent transformations. An increasing interest in models of programs with procedures is due to the abundance of results obtained for simple models of programs. The most suitable model of programs with procedures is a gateway model. A remarkable feature of these models is that every such model is induced by some simple model of programs. This paper gives a survey of the latest results obtained for gateway models of programs.     

A simulation-and-regression approach for stochastic dynamic programs with endogenous state variables

We investigate the optimum control of a stochastic system, in the presence of both exogenous (control-independent) stochastic state variables and endogenous (control-dependent) state variables. Our solution approach relies on simulations and regressions with respect to the state variables, but also grafts the endogenous state variable into the simulation paths. That is, unlike most other simulation approaches found in the literature, no discretization of the endogenous variable is required. The approach is meant to handle several stochastic variables, offers a high level of flexibility in their modeling, and should be at its best in non time-homogenous cases, when the optimal policy structure changes with time. We provide numerical results for a dam-based hydropower application, where the exogenous variable is the stochastic spot price of power, and the endogenous variable is the water level in the reservoir.     

Arbitration without common modifiable variables

Summary The binary arbitration problem (or, the problem of mutual exclusion between two competitors) is the problem of preventing two competitors from simultaneously possessing the same token. A solution to this problem is presented together with a formal correctness proof. The solution is specific in that it combines the absence of common modifiable variables with the absence of auxiliary activities. Hence, its implementation does not require an arbiter on a lower level or a degree of concurrency of more than two. The solution is generalized for any arbitrary number of competitors by applying the binary solution in a binary arbitration tree.     

Quantification without variables in connectionism

Connectionist attention to variables has been too restricted in two ways. First, it has not exploited certain ways of doing without variables in the symbolic arena. One variable-avoidance method, that of logical combinators, is particularly well established there. Secondly, the attention has been largely restricted to variables in long-term rules embodied in connection weight patterns. However, short-lived bodies of information, such as sentence interpretations or inference products, may involve quantification. Therefore short-lived activation patterns may need to achieve the effect of variables. The paper is mainly a theoretical analysis of some benefits and drawbacks of using logical combinators to avoid variables in short-lived connectionist encodings without loss of expressive power. The paper also includes a brief survey of some possible methods for avoiding variables other than by using combinators.This work was supported in part by grant AFOSR-88-0215 from the Air Force Office of Scientific Research, to Barnden, and grant NAGW-1592 under the Innovative Research Program of the NASA Office of Space Science and Applications, to Barnden and C.A. Fields.     

Practical considerations of global and local variables

Fisher advocates that all variables should be made global to programs and subprograms in order to increase the maintainability and to reduce the problems with subprogram linkages, among other things. The fallacies of Fisher's arguments are shown and the advantages and necessity of using local variables are discussed. It is argued that, from a practical point of view, the use of local variables improves the comprehensibility and the time and space efficiency of programs, as well as makes correctness proofs easier and recursion possible.     

Nondeterministic flowchart programs with recursive procedures: Semantics and correctness II

In the second part of this work, we formulate a new inductive assertion method applying to the class of nondeterministic flowchart programs with recursive procedures studied in part 1. Using results on unfolding proved in part 1, we prove that this method is sound and complete with a finite number of assertions. We study four notions of correctness: two notions of partial correctness (existential and universal) and the corresponding notions of total correctness. We also formalize two notions of extension and equivalence (existential and universal) in the second-order predicate calculus.     

Nondeterministic flowchart programs with recursive procedures: semantics and correctness I

In this paper, we study some aspects of the semantics of nondeterministic flowchart programs with recursive procedures. In the first part of this work we provide the operational semantics of programs using the concept of an execution tree. We propose a new definition of the semantics of a non-deterministic recursive program as a mapping from the input domain to the set of execution trees determined by the program. Using this new concept, we prove that every nondeterministic flowchart program with recursive procedures can be unfolded into a semantically equivalent infinite pure flowchart (without procedures). This result is applied in the second part of this work to prove the soundness of an inductive assertion method which is also complete with a finite number of assertions (contrary to De Bakker and Meertens's method [11]).     

A direct solution approach to fuzzy mathematical programs with fuzzy decision variables

In this paper, a direct solution approach is presented for solving fuzzy mathematical programming problems with fuzzy decision variables. In the proposed approach, a fuzzy ranking procedure for fuzzy numbers and a meta-heuristic algorithm is employed. A basic example is presented in the paper. It has been observed that fuzzy mathematical programs with fuzzy decision variables can be solved effectively by employing direct solution approaches which are based on fuzzy ranking procedures and meta-heuristics.     

Evolving computer programs without subtree crossover

An evolutionary programming procedure is used for optimizing computer programs in the form of symbolic expressions. Six tree mutation operators are proposed. Recombination operators such as crossover are not included. The viability and efficiency of the method is extensively investigated on a set of well-studied problems. The evidence indicates that the technique is not only viable but is indeed capable of evolving good computer programs. The results compare well with other evolutionary methods that rely on crossover to solve the same problems     

Proving correctness of coroutines without history variables

We examine the question of whether history variables are necessary in formal proofs of correctness for coroutines. History variables are special variables, which are added to a program to facilitate its proof by recording the sequence of states reached by the program during a computation; after the proof has been completed the history variables may be deleted. The use of such variables in correctness proofs was first suggested by Clint [CL73] in a paper entitled Program Proving: Coroutines; subsequently, history variables have been used by Owicki [OW76a] and Howard [HO75] in verifying concurrent programs and by Apt [APT77] in verifying sequential programs. We argue that recording the entire history of a computation in a single set of variables can actually complicate a correctness proof and should be avoided if possible. We propose a modification of Clint's axiom system and a strategy for constructing proofs that eliminates the need for history variables in verifying simple coroutines. Examples (including Clint's program Histo) are given to illustrate this technique of verifying coroutines, and our axiom system is shown to be sound and relatively complete with respect to an operational semantics for coroutines. Finally, we discuss extensions of the coroutine concept for which history variables do appear to be needed; we also discuss the question of whether such variables are necessary in verifying concurrent programs.The preparation of this paper was supported by NSF Grant MCS-75-08146.     

Testing and debugging distributed programs using global predicates

Testing and debugging programs are more involved in distributed systems than in uniprocessor systems because of the presence of the communication medium and the inherent concurrency. Past research has established that predicate testing is an approach that can alleviate some of the problems in this area. However, checking whether a general predicate is true in a particular distributed execution appears to be a computationally hard problem. This paper considers a class of predicates called conjunctive form predicates (CFP) that is quite useful in distributed program development, but can be tested efficiently. We develop fully-distributed algorithms to test CFP's, prove that these algorithms are correct, and analyze them for their message complexity. The analysis shows that our techniques incur a fairly low overhead on the distributed system