Basic transformation operations which preserve computed answer substitutions of logic programs

From MaRDI portal





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.




Cited in
(32)








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)