Basic transformation operations which preserve computed answer substitutions of logic programs
All transformation techniques for logic programs, such as partial deduction, program specialization and optimization and even program synthesis from specifications, are based on a strategy which appropriately combines a set of basic transformation operations. These consist in the introduction of new definitions in order to group a set of predicates, the unfolding of such definitions, the simplification of the unfolded program by pruning a clause which becomes redundant, thinning a clause, that is eliminating an atom which has become superfluous, or restricting the program to a subprogram of interest. After simplification a folding of definitions is applied to the transformed program, in order to introduce recursion and to obtain a more compact and simple program. For simplifying or folding it is often necessary the fattening of a clause, namely adding to it some redundant atom. The most important problem in program transformation consists in ensuring that a transformation has some meaning preserving property. All the basic transformation operations are studied with resepct to the S-semantics defined in [\textit{M. Falaschi}, \textit{G. Levi}, \textit{M. Martelli} and \textit{C. Palamidessi}, Theor. Comput. Sci. 69, No. 3, 289-318 (1989; Zbl 0699.68113)]. Such a semantics deals with definite programs (i.e. programs without negation) and it is more expressive than the least Herbrand model one, since it captures the program's behaviour in terms of computed answers. For each basic operation (except unfolding) a general applicability condition is given which restricts the application of the operation. It is also proved that such condition guarantees that the \(S\)-semantics of a program is not modified by the transformation. The conditions are independent from the transformation strategy in which they are used and are defined solely in terms of the \(S\)-semantics of the program. Hence any program manipulation technique which combines the basic operations and guarantees the validity of the applicability conditions, preserves the computed answers of the program. Some sufficient conditions, which cover most practical cases and are easy to verify, since they are mostly syntactical, are also supplied and exemplified. The paper is intended both to analyze transformations operations useful in logic programming and to make a further step towards the definition of operations for transforming Pure Prolog programs. In order to reach this goal more difficult problems should still be considered such as termination properties and the introduction of negation-as-failure.
- S-semantics for logic programming: a retrospective look
- On the transformation of logic programs with instantiation based computation rules
- Transforming constraint logic programs
- Uniform closures: Order-theoretically reconstructing logic program semantics and abstract domain refinements
- A compositional semantics for logic programs
- Linearisability on Datalog programs
- Rules + strategies for transforming lazy functional logic programs
- Totally correct logic program transformations via well-founded annotations
- Roles of program extension
- Unfold/fold transformations for disjunctive logic programs
- scientific article; zbMATH DE number 440117 (Why is no real title available?)
- scientific article; zbMATH DE number 3890698 (Why is no real title available?)
- The transformational approach to program development
- scientific article; zbMATH DE number 4106263 (Why is no real title available?)
- A framework for bottom up specialisation of logic programs
- Supporting Transformations for the Partial Evaluation of Logic Programs
- scientific article; zbMATH DE number 549994 (Why is no real title available?)
- scientific article; zbMATH DE number 1508931 (Why is no real title available?)
- scientific article; zbMATH DE number 1534593 (Why is no real title available?)
- Transformation systems and nondeclarative properties
- Transformations of logic programs with goals as arguments
- Simultaneous Replacement in Normal Programs
- scientific article; zbMATH DE number 1420816 (Why is no real title available?)
- The loop absorption and the generalization strategies for the development of logic programs and partial deduction
- Optimizing fuzzy logic programs by unfolding, aggregation and folding
- Predicate Introduction Under Stable and Well-Founded Semantics
- Transformations of logic programs
- On transformations into linear database logic programs
- Transformations of CLP modules
- Unfolding--definition--folding, in this order, for avoiding unnecessary variables in logic programs
- Logical query optimization by proof-tree transformation
- Preservation of stronger equivalence in unfold/fold logic program transformation
This page was built for publication: Basic transformation operations which preserve computed answer substitutions of logic programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5286917)