Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Powiadomienia systemowe
  • Sesja wygasła!
  • Sesja wygasła!

Znaleziono wyników: 12

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  program transformation
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
EN
The transformation of constraint logic programs (CLP programs) has been shown to be an effective methodology for verifying properties of imperative programs. By following this methodology, we encode the negation of a partial correctness property of an imperative program prog as a predicate incorrect defined by a CLP program T, and we show that prog is correct by transforming T into the empty program (and thus incorrect does not hold) through the application of semantics preserving transformation rules. We can also show that prog is incorrect by transforming T into a program with the fact incorrect (and thus incorrect does hold). Some of the transformation rules perform replacements of constraints that are based on properties of the data structures manipulated by the program prog. In this paper we show that Constraint Handling Rules (CHR) are a suitable formalism for representing and applying constraint replacements during the transformation of CLP programs. In particular, we consider programs that manipulate integer arrays and we present a CHR encoding of a constraint replacement strategy based on the theory of arrays. We also propose a novel generalization strategy for constraints on integer arrays that combines CHR constraint replacements with various generalization operators on integer constraints, such as widening and convex hull. Generalization is controlled by additional constraints that relate the variable identifiers in the imperative program prog and the CLP representation of their values. The method presented in this paper has been implemented and we have demonstrated its effectiveness on a set of benchmark programs taken from the literature.
EN
The advent of language implementation tools such as PyPy and Truffle/Graal have reinvigorated and broadened interest in topics related to automatic compiler generation and optimization. Given this broader interest, we revisit the Futamura Projections using a novel diagram scheme. Through these diagrams we emphasize the recurring patterns in the Futamura Projections while addressing their complexity and abstract nature. We anticipate that this approach will improve the accessibility of the Futamura Projections and help foster analysis of those new tools through the lens of partial evaluation.
3
Content available remote Proving Theorems by Program Transformation
EN
In this paper we present an overview of the unfold/fold proof method, a method for proving theorems about programs, based on program transformation. As a metalanguage for specifying programs and program properties we adopt constraint logic programming (CLP), and we present a set of transformation rules (including the familiar unfolding and folding rules) which preserve the semantics of CLP programs. Then, we show how program transformation strategies can be used, similarly to theorem proving tactics, for guiding the application of the transformation rules and inferring the properties to be proved. We work out three examples: (i) the proof of predicate equivalences, applied to the verification of equality between CCS processes, (ii) the proof of first order formulas via an extension of the quantifier elimination method, and (iii) the proof of temporal properties of infinite state concurrent systems, by using a transformation strategy that performs program specialization.
4
Content available remote Improving Reachability Analysis of Infinite State Systems by Specialization
EN
We consider infinite state reactive systems specified by using linear constraints over the integers, and we address the problem of verifying safety properties of these systems by applying reachability analysis techniques. We propose a method based on program specialization, which improves the effectiveness of the backward and forward reachability analyses. For backward reachability our method consists in: (i) specializing the reactive system with respect to the initial states, and then (ii) applying to the specialized system the reachability analysis that works backwards from the unsafe states. For reasons of efficiency, during specialization we make use of a relaxation from integers to reals. In particular, we test the satisfiability or entailment of constraints over the real numbers, while preserving the reachability properties of the reactive systems when constraints are interpreted over the integers. For forward reachability our method works as for backward reachability, except that the role of the initial states and the unsafe states are interchanged. We have implemented our method using the MAP transformation system and the ALV verification system. Through various experiments performed on several infinite state systems, we have shown that our specialization-based verification technique considerably increases the number of successful verifications without a significant degradation of the time performance.
EN
A classification of dependence relations representing exact dependences in program loops is presented. The class of a relation causes the choice of techniques for program loop parallelization. Techniques to recognize the class of a relation are presented. The implementation of these techniques by means of the Omega library is discussed. Results of an experimental study aimed at recognizing classes of dependence relations extracted for popular benchmarks (Livermore Loops, NAS, and UTDSP) are outlined.
PL
W artykule dokonano podziału relacji zależności występujących w pętlach programowych. Na podstawie przeprowadzonych obserwacji wyodrębniono sześć podstawowych klas takich relacji. Trafne rozpoznanie danej klasy relacji opisującej zależności, determinuje dobór odpowiedniej techniki transformacji pętli programowej i tym samym pozwala na uzyskanie znacznie większego jej stopnia równoległości w porównaniu z metodami bazującymi na rozwiązaniach przybliżonych. Rozwiązania takie, zawierają zdecydowanie większą liczbę zależności, aniżeli ich faktyczna liczba wystąpień. W celu ułatwienia procesu identyfikacji poszczególnych klas relacji zależności, przedstawiono szereg formalnych metod ich rozpoznania wykorzystujących szeroki wachlarz mechanizmów zawartych w bibliotece Omega. Na potrzeby przeprowadzonych badań zaimplementowano narzędzie, w ramach którego przeanalizowano zestawy pętli trzech popularnych benchmarków : Livermoore, NAS i UTDSP. Uzyskane wyniki pozwoliły wyciągnąć wnioski odnośnie procentowego udziału relacji zależności w zaproponowanych przez autorów klasach.
PL
Przedstawiliśmy w artykule sposoby obliczenia domknięcia przechodniego sparametryzowanych relacji nie należących do klasy relacji d-form. Do takich relacji należą relacje, których ograniczenia tranzytywnego domknięcia mają nieliniowe wyrażenia oraz relacje hybrydowe czyli takie, których część odpowiadających sobie składowych krotki wejściowej i wyjściowej jest charakterystyczna dla relacji d-form [9], a pozostała pozwala na zastosowanie techniki opartej na utworzeniu i rozwiązaniu układu równań rekurencyjnych [7]. Przedstawione podejścia pozwalają na rozszerzenie możliwości obliczania tranzytywnego domknięcia relacji, a znaczy znajdowanie równoległości dla większego spektrum pętli programowych.
EN
Approaches for calculating the exact transitive closure of a single dependence relation are presented. These approaches are based on calculating firstly the power k of a relation, then transitive closure is easily formed by making k in the formula received to be existentially quantified. Supposed approaches permit for enlarging the scope of dependence relations for which it is possible to calculale exact transitive closure. This enlarges the scope of program loops for which it is possible to extract both fine- and coarse-grained paralIelism. Results of experiments with popular benchmarks are presented.
7
EN
The existential variables of a clause in a constraint logic program are the variables which occur in the body of the clause and not in its head. The elimination of these variables is a transformation technique which is often used for improving program efficiency and verifying program properties. We consider a folding transformation rule which ensures the elimination of existential variables and we propose an algorithm for applying this rule in the case where the constraints are linear inequations over rational or real numbers. The algorithm combines techniques for matching terms modulo equational theories and techniques for solving systems of linear inequations. Through some examples we show that an implementation of our folding algorithm has a good performance in practice.
PL
W artykule rozważane są idealnie zagnieżdżone pętle afiniczne, w których dolne oraz górne granice pętli, a także odwołania do tablic oraz instrukcji warunkowych są określane przy pomocy funkcji afinicznych, których argumentami są indeksy otaczających pętli oraz opcjonalnie parametry stukturalne.
EN
An approach to calculate the power k of an affine normalized relation is presented. A way to normalize an arbitrary affine relation is discussed. The approach is illustrated by an example. It is clarified how to calculate the positive transitive closure and transitive closure of a relation on the basis of the power k of the relation. Results of experiments are discussed. It is demonstrated how the calculated power k of a relation can be used for extracting both coarse- and fine-grained parallelism available in program loops. Feature, research is outlined.
9
Content available remote The Impact of seq on Free Theorems-Based Program Transformations
EN
Parametric polymorphism constrains the behavior of pure functional programs in a way that allows the derivation of interesting theorems about them solely from their types, i.e., virtually for free. Unfortunately, standard parametricity results - including so-called free theorems - fail for nonstrict languages supporting a polymorphic strict evaluation primitive such as Haskell's seq. A folk theorem maintains that such results hold for a subset of Haskell corresponding to a Girard-Reynolds calculus with fixpoints and algebraic datatypes even when seq is present provided the relations which appear in their derivations are required to be bottom-reflecting and admissible. In this paper we show that this folklore is incorrect, but that parametricity results can be recovered in the presence of seq by restricting attention to left-closed, total, and admissible relations instead. The key novelty of our approach is the asymmetry introduced by left-closedness, which leads to ``inequational'' versions of standard parametricity results together with preconditions guaranteeing their validity even when seq is present. We use these results to derive criteria ensuring that both equational and inequational versions of short cut fusion and related program transformations based on free theorems hold in the presence of seq.
10
Content available remote Control Generation by Program Transformation
EN
The objective of control generation in logic programming is to derive a computation rule for a program that is efficient and yet does not compromise program correctness. Progress in solving this fundamental problem in logic programming has been slow and, to date, only partial solutions have been proposed. Previously proposed schemes are either inefficient, incomplete (incorrect) or difficult to apply for programs consisting of many components (the scheme is not modular). This paper shows how the control generation problem can be tackled by program transformation. The transformation relies on information about the depths of derivations to derive delay declarations which orchestrate the control. To prove correctness of the transformation, the notion of semi-delay recurrency is introduced, which generalises previous ideas in the termination literature for reasoning about logic programs with delay declarations. In contrast to previous work, semi-delay recurrency does not require an atom to be completely resolved before another is selected for reduction. This enhancement permits the transformation to introduce control which is flexible and relatively efficient.
11
Content available remote Point-free Program Transformation
EN
Functional programs are particularly well suited to formal manipulation by equational reasoning. In particular, it is straightforward to use calculational methods for program transformation. Well-known transformation techniques, like tupling or the introduction of accumulating parameters, can be implemented using calculation through the use of the fusion (or promotion) strategy. In this paper we revisit this transformation method, but, unlike most of the previous work on this subject, we adhere to a pure point-free calculus that emphasizes the advantages of equational reasoning. We focus on the accumulation strategy initially proposed by Bird, where the transformed programs are seen as higher-order folds calculated systematically from a specification. The machinery of the calculus is expanded with higher-order point-free operators that simplify the calculations. A substantial number of examples (both classic and new) are fully developed, and we introduce several shortcut optimization rules that capture typical transformation patterns.
12
Content available remote A Method for Automatic Program Inversion Based on LR(0) Parsing
EN
We describe a method for automatic program inversion of first-order functional programs based on methods of LR(0) parsing. We formalize the transformation and illustrate it with several example programs. We approach one of the main problems of automatic program inversion-the elimination of nondeterminism-by viewing an inverse program as a context-free grammar. We apply LR-based parsing methods to turn a nondeterministic program into a deterministic program. This improves the efficiency of the inverse programs and greatly expands the application range of our earlier method for program inversion.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.