A study of several of the proof of correctness methods is presented. In particular, the form of induction used is explored in detail. A relational semantic model for programming languages is introduced and its relatio...
详细信息
A study of several of the proof of correctness methods is presented. In particular, the form of induction used is explored in detail. A relational semantic model for programming languages is introduced and its relation to predicate transformers is explored. A rather elementary viewpoint is taken in order to expose, as simply as possible, the basic differences of the methods and the underlying principles involved. These results were obtained by attempting to thoroughly understand the "subgoal induction" method.
We present through the algorithmic language DHL (Dijkstra-Hehner language), a practical approach to a simple first order theory based on calculational logic, unifying Hoare and Dijkstra's iterative style of progra...
详细信息
We present through the algorithmic language DHL (Dijkstra-Hehner language), a practical approach to a simple first order theory based on calculational logic, unifying Hoare and Dijkstra's iterative style of programming with Hehner's recursive predicative programming theory, getting the "best of the two worlds" and without having to recur in any way to higher-order approaches such as predicate transformers, Hoare logic, fixed-point or relational theory.
An assertion language for data structures is presented, leading to the following results: formal semantics of operations on data structures are given in terms of the weakest precondition formula for assignment stateme...
详细信息
An assertion language for data structures is presented, leading to the following results: formal semantics of operations on data structures are given in terms of the weakest precondition formula for assignment statements; input/output specifications for data-structure manipulating algorithms can be stated with precision; there is a clear relationship between the output specification and intermediate assertions; and knowledge about standard types of data structures can be schematized. These ideas are illustrated on an algorithm to reverse the arcs on a one-way linked list, and on a threaded tree example.
The common framework for formalizing state-transition computation models we present is based on a general theory for studying the interrelationship of specifications, programs, computation, and program correctness. We...
详细信息
The common framework for formalizing state-transition computation models we present is based on a general theory for studying the interrelationship of specifications, programs, computation, and program correctness. We establish a necessary and sufficient condition for program correctness for this class of computation models and demonstrate framework application by formalizing, as its instances, two concrete examples of state-transition computation models - NAT and D-rule. We compare their correct-program spaces by introducing the embedding mapping concept.
Described in this paper is a program-analysis method that can be used to effectively determine the logical structure of a program, explicate the computation a program will perform, and show the equivalence of programs...
详细信息
Many approaches proposed in the literature for proving the correctness of unfold/fold transformations of logic programs make use of measures associated with program clauses. When from a program P (1) we derive a progr...
详细信息
Many approaches proposed in the literature for proving the correctness of unfold/fold transformations of logic programs make use of measures associated with program clauses. When from a program P (1) we derive a program P (2) by applying a sequence of transformations, suitable conditions on the measures of the clauses in P (2) guarantee that the transformation of P (1) into P (2) is correct, that is, P (1) and P (2) have the same least Herbrand model. In the approaches proposed so far, clause measures are fixed in advance, independently of the transformations to be proved correct. In this paper we propose a method for the automatic generation of clause measures which, instead, takes into account the particular program transformation at hand. During the application of a sequence of transformations we construct a system of linear equalities and inequalities over nonnegative integers whose unknowns are the clause measures to be found, and the correctness of the transformation is guaranteed by the satisfiability of that system. Through some examples we show that our method is more powerful and practical than other methods proposed in the literature. In particular, we are able to establish in a fully automatic way the correctness of program transformations which, by using other methods, are proved correct at the expense of fixing in advance sophisticated clause measures.
Thom Fruhwirth presented a short, elegant, and efficient Prolog program for the n queens problem. However, the program may be seen as rather tricky and one may not be convinced about its correctness. This paper explai...
详细信息
Thom Fruhwirth presented a short, elegant, and efficient Prolog program for the n queens problem. However, the program may be seen as rather tricky and one may not be convinced about its correctness. This paper explains the program in a declarative way and provides proofs of its correctness and completeness. The specification and the proofs are declarative, that is they abstract from any operational semantics. The specification is approximate, it is unnecessary to describe the program's semantics exactly. Despite the program works on non-ground terms, this work employs the standard semantics, based on logical consequence and Herbrand interpretations. Another purpose of the paper is to present an example of precise declarative reasoning about the semantics of a logic program.
Relative correctness is the property of a program to be more-correct than another with respect to a given specification. Whereas the traditional definition of (absolute) correctness divides candidate program into two ...
详细信息
Relative correctness is the property of a program to be more-correct than another with respect to a given specification. Whereas the traditional definition of (absolute) correctness divides candidate program into two classes (correct, and incorrect), relative correctness arranges candidate programs on the richer structure of a partial ordering. In other venues we discuss the impact of relative correctness on program derivation, and on program verification. In this paper, we discuss the impact of relative correctness on program testing;specifically, we argue that when we remove a fault from a program, we ought to test the new program for relative correctness over the old program, rather than for absolute correctness. We present analytical arguments to support our position, as well as an empirical argument in the form of a small program whose faults are removed in a stepwise manner as its relative correctness rises with each fault removal until we obtain a correct program.
A set of test data T for a program P is reliable if it reveals that P contains an error whenever P is incorrect. If a set of tests T is reliable and P produces the correct output for each element of T then P is a corr...
详细信息
暂无评论