A pointer logic and certifying compiler

Proof-Carrying Code brings two big challenges to the research field of programming languages. One is to seek more expressive logics or type systems to specify or reason about the properties of low-level or high-level programs. The other is to study the technology of certifying compilation in which the compiler generates proofs for programs with annotations. This paper presents our progress in the above two aspects. A pointer logic was designed for PointerC (a C-like programming language) in our research. As an extension of Hoare logic, our pointer logic expresses the change of pointer information for each statement in its inference rules to support program verification. Meanwhile, based on the ideas from CAP (Certified Assembly Programming) and SCAP (Stack-based Certified Assembly Programming), a reasoning framework was built to verify the properties of object code in a Hoare style. And a certifying compiler prototype for PointerC was implemented based on this framework. The main contribution of this paper is the design of the pointer logic and the implementation of the certifying compiler prototype. In our certifying compiler, the source language contains rich pointer types and operations and also supports dynamic storage allocation and deallocation.     

Automated verification of pointer programs in pointer logic

Reasoning about pointer programs is difficult and challenging, while their safety is critical in software engineering. Storeless semantics pioneered by Jonkers provides a method to reason about pointer programs. However, the representation of memory states in Jonkers’ model is costly and redundant. This paper presents a new framework under a more efficient storeless model for automatically verifying properties of pointer programs related to the correct use of dynamically allocated memory such as absence of null dereferences, absence of dangling dereferences, absence of memory leaks, and preservation of structural invariants. The introduced logic-Pointer Logic, is developed to achieve such goals. To demonstrate that Pointer Logic is a useful storeless approach to verification, the Schorr-Waite tree-traversal algorithm which is always considered as a key test for pointer formalizations was verified via our analysis. Moreover, an experimental tool-plcc was implemented to automatically verify a number of non-trivial pointer programs.     

Most specific logic programs

More specific versions of definite logic programs are introduced. These are versions of a program in which each clause is further instantiated or removed and which have an equivalent set of successful derivations to those of the original program, but a possibly increased set of finitely failed goals. They are better than the original program because failure in a non-successful derivation may be detected more quickly. Furthermore, information about allowed variable bindings which is hidden in the original program may be made explicit in a more specific version of it. This allows better static analysis of the program's properties and may reveal errors in the original program. A program may have several more specific versions but there is always a most specific version which is unique up to variable renaming. Methods to calculate more specific versions are given and it is characterized when they give the most specific version.     

On connections and higher-order logic

This is an expository introduction to an approach to theorem proving in higher-order logic based on establishing appropriate connections between subformulas of an expanded form of the theorem to be proved. Expansion trees and expansion proofs play key roles.This is an extended version of a lecture presented to the 8th International Conference on Automated Deduction in Oxford, England on 27 July 1986. This material is based upon work supported by the National Science Foundation under grants DCR-8402532 and CCR-8702699.     

Making default inferences from logic programs

The relationship between Reiter's default logic and general logic programs, which may contain negative subgoals in rule bodies, has been discussed in the literature by translating logic programs to default logic theories. Here, we present a method to translate some default logic theories to general logic programs, and study the extensions of default logic theories with the stable model semantics of logic programming. Based on the translation method, we show that another semantics of logic programming, the well-founded semantics, can be used to define a new version of default logic, which is more cautious than the original one. This enables the existing proof procedures for the well-founded semantics to perform default inference. We also study the property of cumulative monotonicity for both default logic theories and general logic programs under the two different semantics. As a direct application of the translation method, logic programs can be used to make default inference for semantic networks with exceptions. La relation entre la logique par défaut de Reiter et les programmes logiques généraux, qui peuvent comporter des sous-buts négatifs dans les ensembles de règies, a déjàété discutée en traduisant les programmes logiques en théories de la logique par défaut. Dans cet article, les auteurs proposent une méthode pour traduire certaines théories de la logique par defaut en programmes logiques généraux et étudient les extensions des theories de la logique par defaut avec la sémantique de modéle stable de la programmation logique. En se basant sur la méthode de traduction, les auteurs démontrent qu'une autre sémantique de la programmation logique, la sémantique bien fondée, peut ětre utilisée pour définir une nouvelle version de la logique par défaut, qui est plus prudente que la première. Cela permet aux procédures de preuve existantes de la sémantique bien fondée d' effectuer l' inférence par défaut. Les auteurs examinent également les caracteristiques de la monotonicité cumulative pour les theories de la logique par défaut et les programmes logiques généraux selon les deux différentes sémantiques. Une application directe de la méthode de traduction est la possibilityé d' utiliser les programmes logiques pour effectuer de l' inférence par défaut pour les réseaux sémantiques avec exceptions.     

Verification conditions for source-level imperative programs

This paper is a systematic study of verification conditions and their use in the context of program verification. We take Hoare logic as a starting point and study in detail how a verification conditions generator can be obtained from it. The notion of program annotation is essential in this process. Weakest preconditions and the use of updates are also studied as alternative approaches to verification conditions. Our study is carried on in the context of a While language. Important extensions to this language are considered toward the end of the paper. We also briefly survey modern program verification tools and their approaches to the generation of verification conditions.     

Equivalent logic programs and symmetric homogeneous forms of logic programs with equality

This article introduces the notion of CAS-equivalent logic programs: logic programs with identical correct answer substitutions. It is shown that the notions CAS-equivalence, refutational equivalence, and logical equivalence do not coincide in the case of definite clause logic programs. Least model criteria for refutational and CAS-equivalence are suggested and their correctness is proved. The least model approach is illustrated by two proofs of CAS-equivalence. It is shown that the symmetric extension of a logic program subsumes the symmetry axiom and the symmetric homogeneous form of a logic program with equality subsumes the symmetry, transitivity, and predicate substitutivity axioms of equality. These results contribute towards the goal of building equality into standard Prolog without introducing additional inference rules.     

Stable and extension class theory for logic programs and default logics

The stable model semantics (cf. Gelfond and Lifschitz [1]) for logic programs suffers from the problem that programs may not always have stable models. Likewise, default theories suffer from the problem that they do not always have extensions. In such cases, both these formalisms for non-monotonic reasoning have an inadequate semantics. In this paper, we propose a novel idea-that of extension classes for default logics, and of stable classes for logic programs. It is shown that the extension class and stable class semantics extend the extension and stable model semantics respectively. This allows us to reason about inconsistent default theories, and about logic programs with inconsistent completions. Our work extends the results of Marek and Truszczynski [2] relating logic programming and default logics.     

On Local Stratifiability of Logic Prograns and Databases

In this paper,we deal with the problem of verifying local stratifiability of logic programs and databases presented by Przymusinski.Necessary and sufficient condition for the local stratifiability of logic programs are presented and algorithms of performing the verification are developed.Finally,we prove that a database D B containing clauses with disjunctive consequents can be easily converted into a logic program P such that D B is locally statified iff P is locally stratified.