Proving termination of GHC programs

A transformational approach for proving termination of parallel logic programs such as GHC programs is proposed. A transformation from GHC programs to term rewriting systems is developed; it exploits the fact that unifications in GHC-resolution correspond to matchings. The termination of a GHC program for a class of queries is implied by the termination of the resulting rewrite system. This approach facilitates the applicability of a wide range of termination techniques developed for rewrite systems in proving termination of GHC programs. The method consists of three steps: (a) deriving moding information from a given GHC program, (b) transforming the GHC program into a term rewriting system using the moding information, and finally (c) proving termination of the resulting rewrite system. Using this method, the termination of many benchmark GHC programs such as quick-sort, merge-sort, merge, split, fair-split and append, etc., can be proved. This is a revised and extended version of Ref. 12). The work was partially supported by the NSF Indo-US grant INT-9416687 Kapur was partially supported by NSF Grant nos. CCR-8906678 and INT-9014074. M. R. K. Krishna Rao, Ph.D.: He currently works as a senior research fellow at Griffith University, Brisbane, Australia. His current interests are in the areas of logic programming, modular aspects and noncopying implementations of term rewriting, learning logic programs from examples and conuterexamples and dynamics of mental states in rational agent architectures. He received his Ph.D in computer science from Tata Institute of Fundamental Research (TIFR), Bombay in 1993 and worked at TIFR and Max Planck Institut für Informatik, Saarbrücken until January 1997. Deepak Kapur, Ph.D.: He currently works as a professor at the State University of New York at Albany. His research interests are in the areas of automated reasoning, term rewriting, constraint solving, algebraic and geometric reasoning and its applications in computer vision, symbolic computation, formal methods, specification and verification. He obtained his Ph.D. in Computer Science from MIT in 1980. He worked at General Electric Corporate Research and Development until 1987. Prof. Kapur is the editor-in-chief of the Journal of Automated Reasoning. He also serves on the editorial boards of Journal of Logic Programming, Journal on Constraints, and Journal of Applicable Algebra in Engineering, Communication and Computer Science. R. K. Shyamasundar, Ph.D.: He currently works as a professor at Tata Institute of Fundamental Research (TIFR), Bombay. His current intersts are in the areas of logic programming, reactive and real time programming, constraint solving, formal methods, specification and verification. He received his Ph.D in computer science from Indian Institute of Science, Bangalore in 1975 and has been a faculty member at Tata Institute of Fundamental Research since then. He has been a visiting/regular faculty member at Technological University of Eindhoven, University of Utrecht, IBM TJ Watson Research Centre, Pennsylvania State University, University of Illinois at Urbana-Champaign, INRIA and ENSMP, France. He has served on (and chaired) Program Committees of many International Conferences and has been on the Editorial Committees.     

Proving termination of nonlinear command sequences

We describe a simple and efficient algorithm for proving the termination of a class of loops with nonlinear assignments to variables. The method is based on divergence testing for each variable in the cone-of-influence of the loop’s condition. The analysis allows us to automatically prove the termination of loops that cannot be handled using previous techniques. We also describe a method for integrating our nonlinear termination proving technique into a larger termination proving framework that depends on linear reasoning.     

Proving termination of context-sensitive rewriting by transformation

Context-sensitive rewriting (CSR) is a restriction of rewriting that forbids reductions on selected arguments of functions. With CSR, we can achieve a terminating behavior with non-terminating term rewriting systems, by pruning (all) infinite rewrite sequences. Proving termination of CSR has been recently recognized as an interesting problem with several applications in the fields of term rewriting and programming languages. Several methods have been developed for proving termination of CSR. Specifically, a number of transformations that permit treating this problem as a standard termination problem have been described. The main goal of this paper is to contribute to a better comprehension and practical use of transformations for proving termination of CSR. We provide new completeness results regarding the use of the transformations in two restricted (but relevant) settings: (a) proofs of termination of canonical CSR and (b) proofs of termination of CSR by using transformations together with simplification orderings. We have also made an experimental evaluation of the transformations, which complements the theoretical analysis from a practical point of view. This leads to new hierarchies of the transformations which are useful to guide their practical use when implementing tools for proving termination of CSR.     

Proving programs correct through refinement

Summary Program proving must be made applicable to all stages of program development. In particular, in the design phase, proving could prevent a program development based on erroneous or inconsistent design decisions, with its associated high cost of debugging. Furthermore, the proving activity itself would benefit from an early application in the development cycle of a program, because the proof of a program design seems to be simpler than the proof of the final, perhaps optimized, program. The Fisher-Galler algorithm will be used as an example for demonstrating the proof of a program design. An algebraic specification technique is used for describing the design. Details of the proof will be discussed.     

Computing change and specificity with equational logic programs

Recent deductive approaches to reasoning about action and chance allow us to model objects and methods in a deductive framework. In these approaches, inheritance of methods comes for free, whereas overriding of methods is unsupported. In this paper, we present an equational logic framework for objects, methods, inheritance and overriding of methods. Overriding is achieved via the concept of specificity, which states that more specific methods are preferred to less specific ones. Specificity is computed with the help of negation as failure. We specify equational logic programs and show that their completed versions behave as intended. Furthermore, we prove that SLDENF-resolution is complete if the equational theory is finitary, the completed programs are consistent and no derivation flounders or is infinite. Moreover, we give syntactic conditions which guarantee that no derivation flounders or is infinite. Finally, we discuss how the approach can be extended to reasoning about the past in the context of incompletely specified objects or situations. It will turn out that constructive negation is needed to solve these problems.     

Proving termination of normalization functions for conditional expressions

Boyer and Moore have discussed a function that puts conditional expressions into normal form [1]. It is difficult to prove that this function terminates on all inputs. Three termination proofs are compared: (1) using a measure function, (2) in domain theory using LCF, (3) showing that its recursion relation, defined by the pattern of recursive calls, is well-founded. The last two proofs are essentially the same though conducted in markedly different logical frameworks. An obviously total variant of the normalize function is presented as the computational meaning of those two proofs.A related function makes nested recursive calls. The three termination proofs become more complex: termination and correctness must be proved simultaneously. The recursion relation approach seems flexible enough to handle subtle termination proofs where previously domain theory seemed essential.     

Proving termination of (conditional) rewrite systems

In this paper an important problem in the domain of term rewriting, the termination of (conditional) rewrite systems, is dealt with. We show that in many applications, well-founded orderings on terms which only make use of syntactic information of a rewrite systemR, do not suffice for proving termination ofR. Indeed sometimes semantic information is needed to orient a rewrite rule. Therefore we integrate a semantic interpretation of rewrite systems and terms into a well-founded ordering on terms: the notion ofsemantic ordering is the first main contribution of this paper. The use and usefulness of the semantic ordering in proving termination is illustrated by means of some realistic examples.Furthermore the concept of semantic information induces a novel approach for proving termination inconditional rewrite systems. The idea is to employ not only semantic information contained in the terms that are to be compared, but also extra (semantic) information contained in the premiss of the conditional equation in which the terms appear. This leads to our second contribution in the termination problem area: the notion ofcontextual ordering andcontextual semantic ordering. Thecontextual approach allows to prove termination of conditional rewrite systems where all classical partial orderings would fail.     

Proving pointer programs in higher-order logic

Building on the work of Burstall, this paper develops sound modelling and reasoning methods for imperative programs with pointers: heaps are modelled as mappings from addresses to values, and pointer structures are mapped to higher-level data types for verification. The programming language is embedded in higher-order logic. Its Hoare logic is derived. The whole development is purely definitional and thus sound. Apart from some smaller examples, the viability of this approach is demonstrated with a non-trivial case study. We show the correctness of the Schorr–Waite graph marking algorithm and present part of its readable proof in Isabelle/HOL.     

Type-based termination of generic programs

Instances of a polytypic or generic program for a concrete recursive type often exhibit a recursion scheme that is derived from the recursion scheme of the instantiation type. In practice, the programs obtained from a generic program are usually terminating, but the proof of termination cannot be carried out with traditional methods as term orderings alone, since termination often crucially relies on the program type. In this article, it is demonstrated that type-based termination using sized types handles such programs very well. A framework for sized polytypic programming is developed which ensures (type-based) termination of all instances.     

Proving properties of Pascal programs in MIZAR 2

Summary In this paper we present the so called natural semantics for a subset of Pascal programming language. A set of sentences of first order predicate calculus defines the meaning of the Pascal language constructs. The meaning of a specific program is defined separately by another set of sentences which can be generated automatically. Both these sets together constitute axiomatics of a theory, called the theory of a specific program. The axiomatics is built in such a way that its logical consequences describe all the computational processes defined by the program. Proofs of properties for two small programs are discussed in detail. These properties and their proofs are recorded in the MIZAR 2 language — a computer formalization of predicate calculus. MIZAR 2 proof checker was used to verify the proofs.     

The clean termination of iterative programs

Summary The paper is devoted to a program-correctness concept which captures partial correctness, termination (nonlooping) and clean termination (nonabortion). The underlying proof method offers a one-stage proof of all the three properties. This method is proved consistent and algebraically complete. It is first discussed for the general case of arbitrary possibly nondeterministic iterative programs. Next, this case is restricted to arbitrary deterministic iterative programs and finally to structured programs. The presented approach is compared with partial correctness, total correctness and weakest precondition methods. The concluding example shows the verification of an arithmetical program in machine-bounded arithmetics. As a side effect of the verification procedure one finds input boundary conditions which guarantee clean termination.This paper was prepared when the author was visiting the Department of Computer Science of the Technical University of Denmark in Lyngby.     

The clean termination of Pascal programs

The axiomatic definition of PASCAL takes no account of the finite bounds of real computers. It is proposed that the bounds of differing machines may be accounted for in the PASCAL definition by the use of an axiom schema with machine dependent parameters. If these parameters are available to the program prover and to the program it is possible to prove the clean termination of a program on a particular bounded machine. The use of a parameterised definition for all PASCAL machines, means that clean termination can be guaranteed over a range of machines. In particular a programmer may prove his program against a set of bounds chosen for ease of proof, as long as the implemented machine is larger.     

Proving total correctness of nondeterministic programs in infinitary logic

Summary It is shown how the weakest precondition approach to proving total correctness of nondeterministic programs can be formalized in infinitary logic. The weakest precondition technique is extended to hierarchically structured programs by adding a new primitive statement for operational abstraction, the nondeterministic assignment statement, to the guarded commands of Dijkstra. The infinitary logic L ₁ is shown to be strong enough to express the weakest preconditions for Dijkstra's guarded commands, but too weak for the extended guarded commands. Two possible solutions are considered: going to the essentially stronger infinitary logic L ₁₁ and restricting the power of the nondeterministic assignment statement in a way which allows the weakest preconditions to be expressed in L ₁.     

Efficient automata‐driven pattern‐matching for equational programs

We propose a practical technique to compile left‐to‐right pattern‐matching of prioritised overlapping function definitions in equational languages to a matching automaton from which efficient code can be derived. First, a matching table is constructed using a compilation method similar to the technique that YACC employs to generate parsing tables. The matching table obtained allows for the pattern‐matching process to be performed without any backtracking. Then, the known information about right sides of the equations is inserted in the matching table in order to speed‐up the pattern‐matching process. Most of the discussion assumes that the processed pattern set is left‐linear, the non‐linear case being handled by an additional pass following the matching stage. Copyright © 1999 John Wiley & Sons, Ltd.     

Compositional operational semantics for Prolog programs

To relate operational semantics of logic programs to its declarative semantics, we have to rely on SLD-trees. But this form of operational semantics does not make it easy to relate execution behaviour to program structure. The reason is that the traversal of SLD-trees decomposes in a way that is different from the decomposition (which is by disjunction and conjunction) of programs. We propose SLD-contours, a variant of SLD-trees, that are, like programs, built up out of simpler components by means of disjunction and conjunction. The traversal of SLD-trees carries over to the traversal of SLD-contours in such a way that the trace events of the Box Model (Try, Succeed, Retry, Fail) are reproduced in the same way as during the execution of the program. ThusSLD-contours relate the trace more closely to the program than SLD-trees. SLD-contours specify the trace more completely than the Box Model does.     

Symbolic decision procedure for termination of linear programs

Tiwari proved that the termination of a class of linear programs is decidable in Tiwari (Proceedings of CAV’04. Lecture notes in computer science, vol 3114, pp 70–82, 2004). The decision procedure proposed therein depends on the computation of Jordan forms. Thus, people may draw a wrong conclusion from this procedure, if they simply apply floating-point computation to compute Jordan forms. In this paper, we first use an example to explain this problem, and then present a symbolic implementation of the decision procedure. Thus, the rounding error problem is therefore avoided. Moreover, we also show that the symbolic decision procedure is as efficient as the numerical one given in Tiwari (Proceedings of CAV’04. Lecture notes in computer science, vol 3114, pp 70–82, 2004). The complexity of former is max{O(n ⁶), O(n ^m+3)}, while that of the latter is O(n ^m+3), where n is the number of variables of the program and m is the number of its Boolean conditions. In addition, for the case when the characteristic polynomial of the assignment matrix is irreducible, we design a more efficient symbolic algorithm whose complexity is max(O(n ⁶), O(mn ³)).     

命令式程序终止性验证方法综述

作为软件完全正确性的重要组成部分,程序终止性受到越来越多的关注。旨在跟踪国内外针对命令式程序的终止性验证方法,调研该领域的最新研究成果,同时提出解决该问题的建议性方法框架,对命令式程序终止性研究提供有意义的帮助。给出了程序终止性问题的定义,介绍了已有的数值程序、堆操作程序终止性验证方法,并分别进行了分析与对比。总结了当前研究中存在的难点与热点问题,给出了一种基于模型检验的C程序终止性验证框架,该框架可以作为研究命令式程序终止性的基本框架。     

Transformational methodology for proving termination of logic programs

A methodology for proving the termination of well-moded logic programs is developed by reducing the termination problem of logic programs to that of term rewriting systems. A transformation procedure is presented to derive a term rewriting system from a given well-moded logic program such that the termination of the derived rewrite system implies the termination of the logic program for all well-moded queries under a class of selection rules. This facilitates applicability of a vast source of termination orderings proposed in the literature on term rewriting, for proving termination of logic programs. The termination of various benchmark programs has been established with this approach. Unlike other mechanizable approaches, the proposed approach does not require any preprocessing and works well, even in the presence of mutual recursion. The transformation has also been implemented as a front end to Rewrite Rule Laboratory (RRL) and has been used in establishing termination of nontrivial Prolog programs such as a prototype compiler for ProCoS, PL₀ language.