We exploit the idea of proving properties of an abstract machine by using a corresponding semantic style that better suits the purpose. In a previous work we introduced a calculus of closures and proved by program derivation that it corresponds to a slightly optimised open-terms version of Pierre Crégut's full-reducing Krivine machine KN. In this work we prove that this calculus (and KN by correspondence) simulates in lockstep the standard and complete normal-order strategy (i.e. leftmost reduction to normal form) of the pure lambda calculus. The simulation is witnessed by a substitution function from closures to pure terms. Lockstep simulation is stronger than the known proof that KN is complete, for in the pure lambda calculus there are complete but non-standard strategies. The proof of lockstep simulation proceeds by straightforward structural induction thanks to how KN's parameters-as-levels and index-alignment properties are carried into the calculus' deterministic reduction relation, allowing `balanced derivations' where the nesting level under lambda at which reduction is taking place remains constant at both sides of a reduction. Lexical adjustments at binding lookup, on-the-fly alpha-conversion, or recursive traversals (as in the locally nameless representation) are unnecessary. The proof's lemmata constitute a recipe for carrying parameters-as-levels, index alignment, and balanced derivations to other calculi and machines. The whole proof, including the closure calculus and normal-order, has been mechanised in the Coq proof assistant and is available online. This work amends the framework for environment machines of Biernacka and Danvy, adding a missing full-reducing open-terms closure calculus, machine, and lockstep simulation proof via a substitution function.
We present a declarative framework for the compilation of constraint logic programs into variable-free relational theories which are then executed by rewriting. This translation provides an algebraic formulation of the abstract syntax of logic programs. Logic variables, unification, and renaming apart are completely elided in favor of manipulation of variable-free relation expressions. In this setting, term rewriting not only provides an operational semantics for logic programs, but also a simple framework for reasoning about program execution. We prove the translation sound, and the rewriting system complete with respect to traditional SLD semantics.
Concurrent systems are hard to program, and ensuring quality by means of traditional testing techniques is often very hard as errors may not show up easily and reproducing them is hard. In previous work, we have advocated a model-driven approach to the analysis and design of concurrent, safety-critical systems. However, to take full advantage of these techniques, they must be supported by code generation schemes for concrete programming languages. Ideally, this translation should be traceable, automated and should support the verification of the generated code. In our work, we consider the problem of generating a concurrent Java component from a high-level model of inter-process interaction (i.e., communication + synchronization). We call our formalism shared resources. From the model, which can be represented in mathematical notation or written as a Java interface annotated using an extension of JML, a Java component can be obtained by a semiautomatic translation. We describe how to obtain shared memory (using a priority monitors library) and message passing (using the JCSP library) implementations. Focusing on inter-process interaction for formal development is justified by several reasons, e.g., mathematical models are language-independent and allow to analyze certain concurrency issues, such as deadlocks or liveness properties prior to code generation. Also, the Java components produced from the shared resource model will contain all the concurrency-related language constructs, which are often responsible for many of the errors in concurrent software. We follow a realistic approach where the translation is semiautomatic (schemata for code generation) and the programmer still retains the power of coding or modifying parts of the code for the resource. The code thus obtained is JML-annotated Java with proof obligations that help with code traceability and verification of safety and liveness properties. As the code thus obtained is not automatically correct, there is still the need to verify its conformance to the original specs. We illustrate the methodology by developing a concurrent control system and verifying the code obtained using the KeY program verification tool. We also show how KeY can be used to find errors resulting from a wrong use of the templates.
This file was generated by bibtex2html 1.98.