In spite of its. practical importance, the Boyer-Moore string-matching algorithm has hardly been studied in the context of partial evaluation. We show how to derive the search stage of a variant of this algorithm usin...
详细信息
In spite of its. practical importance, the Boyer-Moore string-matching algorithm has hardly been studied in the context of partial evaluation. We show how to derive the search stage of a variant of this algorithm using "disjunctive" partial deduction. (C) 2003 Published by Elsevier B.V.
As critical computer systems continue to grow in complexity, the task of showing that they execute correctly becomes more difficult. For this reason, research in software engineering has turned to formal methods, i.e....
详细信息
As critical computer systems continue to grow in complexity, the task of showing that they execute correctly becomes more difficult. For this reason, research in software engineering has turned to formal methods, i.e., rigorous approaches to demonstrating the correctness of software systems. Unfortunately, the formal methods currently used in the design of concurrent systems do not provide any mechanisms for specifying and reasoning about the mapping of software to hardware. As a result, architectural constraints, even though they play an important role in the design process, are left out of the formal framework. In this paper, we show how to state architectural constraints in a formal notation, how to prove that programs are allocated correctly to the underlying architecture, and how to factor architectural considerations into a program derivation process which uses a mixture of specification and program refinements. The approach is illustrated by the derivation of two related programs that solve the same problem but are designed to work on distinct architectures.
We show how to derive imperative programs for relation-based discrete structures by combining relational calculus and the Dijkstra-Gries method. Three examples are given, viz. Warshall's algorithm for transitive c...
详细信息
We show how to derive imperative programs for relation-based discrete structures by combining relational calculus and the Dijkstra-Gries method. Three examples are given, viz. Warshall's algorithm for transitive closures, a breadth-first-search reachability algorithm, and an algorithm for spanning trees. (C) 1999 Elsevier Science Inc. All rights reserved.
Adaptation rules adapt the pre-post specification of a procedure to contexts where it is called. Such rules are important for practical reasons and necessary for completeness for languages with recursive procedures. A...
详细信息
Adaptation rules adapt the pre-post specification of a procedure to contexts where it is called. Such rules are important for practical reasons and necessary for completeness for languages with recursive procedures. A sharp rule is one that gives the weakest precondition with respect to a given postcondition. A number of rules have been proposed, most unsound or incomplete or non-sharp. Using refinement algebra, we clarify and extend the applicability of previously proposed sharp rules for total correctness and show how further rules may be found. (C) 2001 Elsevier Science B.V. All rights reserved.
We bridge the gap between compositional evaluators and abstract machines for the lambda-calculus, using closure conversion, transformation into continuation-passing style, and defunctionalization of continuations. Thi...
详细信息
We bridge the gap between compositional evaluators and abstract machines for the lambda-calculus, using closure conversion, transformation into continuation-passing style, and defunctionalization of continuations. This article is a followup, of our article at PPDP 2003, where we consider call by name and call by value. Here, however, we consider call by need. We derive a lazy abstract machine from an ordinary call-by-need evaluator that threads a heap of updatable cells. In this resulting abstract machine, the continuation fragment for updating a heap cell naturally appears as an 'update marker', an implementation technique that was invented for the Three Instruction Machine and subsequently used to construct lazy variants of Krivine's abstract machine. Tuning the evaluator leads to other implementation techniques such as unboxed values. The correctness of the resulting abstract machines is a corollary of the correctness of the original evaluators and of the program transformations used in the derivation. (C) 2004 Elsevier B.V. All rights reserved.
This paper describes a formal approach to developing concurrent rule-based programs. Our program derivation strategy starts with a formal specification of the problem. Specification refinement is used to generate an i...
详细信息
This paper describes a formal approach to developing concurrent rule-based programs. Our program derivation strategy starts with a formal specification of the problem. Specification refinement is used to generate an initial version of the program. program refinement is then applied to produce a highly concurrent and efficient version of the same program. Techniques for deriving concurrent programs through either specification or program refinement have been described in previous literature. The main contribution of this paper consists of extending the applicability of these techniques to rule-based programs. The derivation process is supported by a powerful proof logic, a logic that recently has been extended to cover rule-based programs. The presentation centers around a rigorous and systematic derivation of a concurrent rule-based solution to a classic problem.
Formal calculations can contribute successfully to a better understanding of the structure of a proof, both in programming and in "classical" mathematics. This is illustrated by means of a few examples. (C) ...
详细信息
Formal calculations can contribute successfully to a better understanding of the structure of a proof, both in programming and in "classical" mathematics. This is illustrated by means of a few examples. (C) 2001 Elsevier Science B.V. All rights reserved.
The initial algebra semantics of nested datatypes was proved to be valid in a wide class of categories. There is a unique morphism from each initial functional algebra to any other functional algebra. folds are standa...
详细信息
The initial algebra semantics of nested datatypes was proved to be valid in a wide class of categories. There is a unique morphism from each initial functional algebra to any other functional algebra. folds are standard operators in functional programming and satisfy fusion laws that are useful for program transformation. Asemantic for second order nested datatypes were used so that generalized folds could also be defined in second order datatypes.
The classical specification formalism involving pre- and postconditions expressed in program variables cannot directly be applied to the specification of classes, interfaces, components, and design patterns, since the...
详细信息
The classical specification formalism involving pre- and postconditions expressed in program variables cannot directly be applied to the specification of classes, interfaces, components, and design patterns, since the program variables involved are mostly invisible outside of (dynamically selected) implementation code. A more useful specification formalism, operating at the problem domain level rather than at the implementation level, is proposed and it is shown how this can be used for Dijkstra-style derivation of object-oriented code. (C) 2001 Elsevier Science B.V. All rights reserved.
We present an algorithm for multiple-precision floating-point multiplication. The conventional algorithms based on the fast Fourier transform (FFT) multiply two n-bit numbers to obtain a 2n-bit result. In multiple-pre...
详细信息
We present an algorithm for multiple-precision floating-point multiplication. The conventional algorithms based on the fast Fourier transform (FFT) multiply two n-bit numbers to obtain a 2n-bit result. In multiple-precision floating-point multiplication, we need only the returned result whose precision is equal to the multiple-precision floating-point number. We show that the overall arithmetic operations for FFT-based multiple-precision floating-point multiplication are reduced by decomposition of the full-length multiplication into shorter-length multiplication. (c) 2004 Elsevier Inc. All rights reserved.
暂无评论