A framework for specifying, prototyping, and reasoning about computational systems

This thesis concerns the development of a framework that facilitates the design and analysis of formal systems. Specifically, this framework is intended to provide (1) a specification language which supports the concise and direct description of a system based on its informal presentation, (2) a mechanism for animating the specification language so that descriptions written in it can quickly and effectively be turned into prototypes of the systems they are about, and (3) a logic for proving properties of descriptions provided in the specification language and thereby of the systems they encode. A defining characteristic of the proposed framework is that it is based on two separate but closely intertwined logics. One of these is a specification logic that facilitates the description of computational structure while the other is a logic that exploits the special characteristics of the specification logic to support reasoning about the computational behavior of systems that are described using it. Both logics embody a natural treatment of binding structure by using the λ-calculus as a means for representing objects and by incorporating special mechanisms for working with such structure. By using this technique, they lift the treatment of binding from the object language into the domain of the relevant meta logic, thereby allowing the specification or analysis components to focus on the more essential logical aspects of the systems that are encoded. One focus of this thesis is on developing a rich and expressive reasoning logic that is of use within the described framework. This work exploits a previously developed capability of definitions for embedding recursive specifications into the reasoning logic; this notion of definitions is complemented by a device for a case-analysis style reasoning over the descriptions they encode. Use is also made of a special kind of judgment called a generic judgment for reflecting object language binding into the meta logic and thereby for reasoning about such structure. Existing methods have, however, had a shortcoming in how they combine these two devices. Generic judgments lead to the introduction of syntactic objects called nominal constants into formulas and terms. The manner in which such objects are introduced often ensures that they satisfy certain properties which are necessary to take note of in the reasoning process. Unfortunately, this has heretofore not been possible to do. To overcome this problem, we introduce a special binary relation between terms called nominal abstraction and show this can be combined with definitions to encode the desired properties. The treatment of definitions is further enriched by endowing them with the capability of being interpreted inductively or co-inductively. The resulting logic is shown to be consistent and examples are presented to demonstrate its richness and usefulness in reasoning tasks. This thesis is also concerned with the practical application of the logical machinery it develops. Specifically, it describes an interactive, tactic-style theorem prover called Abella that realizes the reasoning logic. Abella embodies the use of lemmas in proofs and also provides intuitively well-motivated tactics for inductive and co-inductive reasoning. The idea of reasoning using two-levels of logic is exploited in this context. This form of reasoning, pioneered by McDowell and Miller, embeds the specification logic explicitly into the reasoning logic and then reasons about particular specifications through this embedding. The usefulness of this approach is demonstrated by showing that general properties can be proved about the specification logic and then used as lemmas to simplify the overall reasoning process. We use these ideas together with Abella to develop several interesting and challenging proofs. The examples considered include ones in the recently proposed POPLmark challenge and a formalization of Girard’s proof of strong normalization for the simply-typed λ-calculus. We also explore the notion of adequacy that relates theorems proved using Abella to the properties of the object systems that are ultimately of primary interest. (Abstract shortened by UMI.)