Verification Condition Generator (VCG) tools have been effective in simplifying the task of proving programs correct. However, in the past these VCG tools have in general not themselves been mechanically proven, so any proof using and depending on these VCGs might not be sound. In our work, we define and rigorously prove correct a VCG tool within the HOL theorem proving system, for a standard while-loop language, with one new feature not usually treated: expressions with side effects. Starting from a structural operational semantics of this programming language, we prove as theorems the axioms and rules of inference of a Hoare-style axiomatic semantics, verifying their soundness. This axiomatic semantics is then used to define and prove correct a VCG tool for this language. Finally, this verified VCG is applied to an example program to verify its correctness.

The capabilities needed in an Ada debugger are discussed in light of the language's tasking constructs, and the design for a debugger is presented which operates in concert with a single-processor Ada interpreter. This debugger design demonstrates the extensions to sequential debugging techniques that are necessary to handle concurrency, and shows that significant debugging functionality can be provided even without the inclusion of automatic error diagnosis methods. The issues considered include isolation of effects and display of the full dynamic execution status, both of which are essential to diagnosis of concurrent programs.>

Aspect of the interaction between compiler theory and practice is addressed. Presented is a technique for the syntax-directed specification of compilers together with a method for proving the correctness of their parse-driven implementations. The subject matter is presented in an order-algebraic framework; while not strictly necessary, this approach imposes beneficial structure and modularity on the resulting specifications and implementation correctness proofs. Compilers are specified using an order-algebraic definition of attribute grammars. A practical class of compiler implementations is considered, consisting of those driven by LR( k ) or LL( k ) parsers which cause a sequence of translation routine activations to modify a suitably initialized collection of data structures (called a translation environment). The implementation correctness criterion consists of appropriately comparing, for each source program, the corresponding object program (contained in the final translation environment) produced by the compiler implementation to the object program dictated by the compiler specification. Provided that suitable intermediate assertions (called translation invariants ) are supplied, the program consisting of the (parse-induced) sequence of translation routine activations can be proven partially correct via standard inductive assertion methods.

This paper presents a formulation, within the framework of initial algebra semantics, of Knuthian semantic systems (K-systems) which contain both synthesized and inherited attributes. This formulation permits a precise definition of K-systems, and combines their intuitive appeal with the theoretical power of algebraic methods. The basic approach consists of algebraically specifying the semantic portion of a given K-system, converting this K-system into another equivalent one which contains only synthesized attributes, and then defining the new equivalent K-system by means of an algebraic formulation. The practical implications of the algebraic definition of K-systems are discussed, and the combined use of Knuth's original formulation and the algebraic approach for the development of semantic definitions is advocated.

Several topics of theoretical and practical importance to the field of translator writing systems are presented in this paper. These are

This paper discusses essential difficulties in calculating mean path lengths on a directed graph model of computations. This study was part of a larger study of a priori scheduling of computer programs in a parallel processing environment. Efficient approximations to mean processing time (mean path length) of programs in such an environment are given.

This paper concerns itself with the modeling of computations and systems and the generation of a priori estimates of expected computation time for given problems on given processing systems. In particular, methods are discussed for determining the probabilities of reaching vertices in a graph model of computations.

This paper reports results of experiments on models of computational sequences and models of computer systems. The validity of these models is a step in the evolution of methods for prediction of complex computer system performance. A graph model representing computational sequences was implemented and mapped onto a model of computer systems using programmable assignment and sequencing strategies. An approximate procedure for a priori estimation of path length (computation time) through an assigned graph was checked against more conventional simulation. The graph model was also perturbed to probe sensitivity of estimates of operation times, cycle factors, and branching probabilities. Problems arising in numerical weather prediction, X-ray analysis, nuclear modeling, and graph computations were transformed into acyclic directed graphs and have undergone computer analysis. Effectiveness of parallel processing, convergence properties of the successive approximation assignment and sequencing procedure, sensitivity to input parameter variation, the cost in computer time of the graph analysis, and comparison with more conventional SIMSCRIPT simulation are presented. The reduction in time required to obtain an estimate of path length compared to conventional simulation is found to range from a little less than 102to more than 104. Computational tests indicate that additional factors may be gained without severe loss in validity of the approximation.

This paper discusses cyclic to acyclic transformations performed on graphs representing computational sequences. Such transformations are critical to the development of models of computations and computer systems for performance prediction. The nature of cycles in computer programs for parallel processors is discussed. Transformations are then developed which replace cyclic graph structures by mean-value equivalent acyclic structures. The acyclic equivalents retain the noncyclic part of the structure in the original graph by evaluating a multiplicative factor associated with the mean time required for each vertex execution in the original graph. Bias introduced in the acyclic approximation is explored.