We provide an approach to formally analyze the computational behavior of coroutines in logicprograms and to compile these computations into new programs, not requiring any support for coroutines. the problem was alre...
详细信息
ISBN:
(纸本)9783319178226;9783319178219
We provide an approach to formally analyze the computational behavior of coroutines in logicprograms and to compile these computations into new programs, not requiring any support for coroutines. the problem was already studied near to 30 years ago, in an analysis and transformation technique called Compiling Control. However, this technique had a strong ad hoc flavor: the completeness of the analysis was not well understood and its symbolic evaluation was also very ad hoc. We show how Abstract Conjunctive Partial Deduction, introduced by Leuschel in 2004, provides an appropriate setting to redefine Compiling Control. Leuschel's framework is more general than the original formulation, it is provably correct, and it can easily be applied for simple examples. We also show that the Abstract Conjunctive Partial Deduction framework needs some further extension to be able to deal with more complex examples.
the traditional stepwise refinement basedprogram derivation methodologies are primarily top-down. Strictly following the top-down program derivation approach may require backtracking resulting in rework. Moreover, th...
详细信息
ISBN:
(纸本)9783319274362;9783319274355
the traditional stepwise refinement basedprogram derivation methodologies are primarily top-down. Strictly following the top-down program derivation approach may require backtracking resulting in rework. Moreover, the top down approach does not directly help in suggesting the next course of action in case of a failed derivation attempt. In this work we seamlessly incorporate a bottom up assumption propagation technique into a primarily top down derivation methodology. We present new tactics for back-propagating the assumptions made during the top-down phase. these tactics help in reducing the guesswork during the derivations. We have implemented these tactics in a program derivation system. Withthe help of simple examples, we show how this approach is useful for avoiding backtracking thereby simplifying the derivations.
Among other objectives, rewriting programs serves as a useful technique to improve numerical accuracy. However, this optimization is not intuitive and this is why we switch to automatic transformation techniques. We a...
详细信息
ISBN:
(纸本)9783319274362;9783319274355
Among other objectives, rewriting programs serves as a useful technique to improve numerical accuracy. However, this optimization is not intuitive and this is why we switch to automatic transformation techniques. We are interested in the optimization of numerical programs relying on the IEEE754 floating-point arithmetic. In this article, our main contribution is to study the impact of optimizing the numerical accuracy of programs on the time required by numerical iterative methods to converge. To emphasize the usefulness of our tool, we make it optimize several examples of numerical methods such as Jacobi's method, Newton-Raphson's method, etc. We show that significant speedups are obtained in terms of number of iterations, time and flops.
A pattern t, i.e., a term possibly with variables, denotes the set (language) [t] of all its ground instances. In an untyped setting, symbolic operations on finite sets of patterns can represent Boolean operations on ...
详细信息
ISBN:
(纸本)9783319274362;9783319274355
A pattern t, i.e., a term possibly with variables, denotes the set (language) [t] of all its ground instances. In an untyped setting, symbolic operations on finite sets of patterns can represent Boolean operations on languages. But for the more expressive patterns needed in declarative languages supporting rich type disciplines such as subtype polymorphism untyped pattern operations and algorithms break down. We show how they can be properly defined by means of a signature transformation Sigma bar right arrow Sigma(#) that enriches the types of S. We also show that this transformation allows a systematic reduction of the first-order logic properties of an initial order-sorted algebra supporting subtype-polymorphic functions to equivalent properties of an initial many-sorted (i.e., simply typed) algebra. this yields a new, simple proof of the known decidability of the first-order theory of an initial order-sorted algebra.
Co-logicprogramming is an extension of the conventional logicprogramming language, by allowing each predicate to be annotated as either inductive or coinductive. To define its procedural semantics as well as an alte...
详细信息
ISBN:
(纸本)9783319274362;9783319274355
Co-logicprogramming is an extension of the conventional logicprogramming language, by allowing each predicate to be annotated as either inductive or coinductive. To define its procedural semantics as well as an alternating fixpoint semantics, the stratification restriction, a condition on predicate dependency in programs, has been imposed on co-logicprograms (co-LPs). In this paper, we first consider dual programs in co-logicprogramming: Given a program P, its dual program P* is a program such that it defines the "complement" of P, i.e., for any ground atom p((t) over bar), it computes its negation inverted left perpendiculatp((t) over bar). When we consider co-LPs with negation, we show that the stratification restriction becomes too restrictive in general, and that the Horn-calculus by Charatonik et al. can be used as an extension of co-logicprogramming for handling "non stratified" co-LPs. We then consider some applications of non-stratified co-LPs to Answer Set programming (ASP) and the well-founded semantics (WFS). In particular, we give new iterated fixpoint characterizations of answer sets as well as the WFS via dual programs. We also discuss some applications of non-stratified co-LPs to programtransformation such as partial deduction, and a proof procedure for the WFS.
As part of a platform for computer-assisted verification, we present an intermediate representation of programs that is both language independent and appropriate for the generation of verification conditions. We show ...
详细信息
ISBN:
(纸本)9783319274362;9783319274355
As part of a platform for computer-assisted verification, we present an intermediate representation of programs that is both language independent and appropriate for the generation of verification conditions. We show how many imperative and functional languages can be translated to this generic intermediate representation, and how the generated conditions reflect the axiomatic semantics of the original program. At this representation level, loop invariants and preconditions of recursive functions belonging to the original program are represented by assertions placed at certain edges of a directed graph. the paper defines the generic representation, sketches the transformation algorithms, and describes how the places where the invariants should be placed are computed. Assuming that, either manually or assisted by the platform, the invariants have been settled, it is shown how the verification conditions are generated. A running example illustrates the process.
Concolic execution, a combination of concrete and symbolic execution, has become increasingly popular in recent approaches to model checking and test case generation. In general, an interpreter of the language is augm...
详细信息
ISBN:
(纸本)9783319274362;9783319274355
Concolic execution, a combination of concrete and symbolic execution, has become increasingly popular in recent approaches to model checking and test case generation. In general, an interpreter of the language is augmented in order to also deal with symbolic values. In this paper, in contrast, we present an alternative approach that is based on a program instrumentation. Basically, the execution of the instrumented program in a standard environment produces a sequence of events that can be used to reconstruct the associated symbolic execution.
We explore a transformational approach to the problem of verifying simple array-manipulating programs. Traditionally, verification of such programs requires intricate analysis machinery to reason with universally quan...
详细信息
ISBN:
(纸本)9783319178226;9783319178219
We explore a transformational approach to the problem of verifying simple array-manipulating programs. Traditionally, verification of such programs requires intricate analysis machinery to reason with universally quantified statements about symbolic array segments, such as "every data item stored in the segment A[i] to A[j] is equal to the corresponding item stored in the segment B[i] to B[j]." We define a simple abstract machine which allows for set-valued variables and we show how to translate programs with array operations to array-free code for this machine. For the purpose of program analysis, the translated program remains faithful to the semantics of array manipulation. based on our implementation in LLVM, we evaluate the approach with respect to its ability to extract useful invariants and the cost in terms of code size.
Proofs by induction are often incompatible with functions in tail-recursive form as the accumulator changes in the course of unfolding the definitions. Context-moving and context-splitting (Giesl, 2000) for functional...
详细信息
ISBN:
(纸本)9783319274362;9783319274355
Proofs by induction are often incompatible with functions in tail-recursive form as the accumulator changes in the course of unfolding the definitions. Context-moving and context-splitting (Giesl, 2000) for functional programs transform tail-recursive programs into non tail-recursive ones which are more suitable for proofs by induction and thus for verification. In this paper, we formulate context-moving and context-splitting transformations in the framework of term rewriting systems, and prove their correctness with respect to both eager evaluation semantics and initial algebra semantics under some conditions on the programs to be transformed. the conditions for the correctness with respect to initial algebra semantics can be checked by automated methods for inductive theorem proving developed in the field of term rewriting systems.
Visualization tools of different languages offer its users with a needed set of features allowing them to animate how programs of such languages work. Constraint Handling Rules (CHR) is currently used as a general pur...
详细信息
ISBN:
(纸本)9783319178226;9783319178219
Visualization tools of different languages offer its users with a needed set of features allowing them to animate how programs of such languages work. Constraint Handling Rules (CHR) is currently used as a general purpose language. this results in having complex programs with CHR. Nevertheless, CHR is still lacking on visualization tools. With Constraint Handling Rules (CHR) being a high-level rule-based language, animating CHR programs through animation tools demonstrates the power of the language. Such tools are useful for beginners to the language as well as programmers of sophisticated algorithms. this paper continues upon the efforts made to have a generic visualization platform for CHR using source-to-source transformation. It also provides a new visualization feature that enables viewing all the possible solutions of a CHR program instead of the don't care nondeterminism used in most CHR implementations.
暂无评论