Abstract
The replacement transformation operation, already defined in [28], is studied wrt normal programs. We give applicability conditions able to ensure the correctness of the operation wrt Fitting's and Kunen's semantics. We show how replacement can mimic other transformation operations such as thinning, fattening and folding, thus producing applicability conditions for them too. Furthermore we characterize a transformation sequence for which the preservation of Fitting's and Kunen's semantics is ensured.
This work has been partially supported by ”Progetto Finalizzato Sistemi Informatici e Calcolo Parallelo” of CNR under grant n. 89.00026.69
This is a preview of subscription content, log in via an institution.
Preview
Unable to display preview. Download preview PDF.
References
K. Apt. Introduction to logic programming. In Handbook of Theoretical Computer Science, pages 493–574. Elsevier Science Publishers B.V., 1990.
K. R. Apt, H. A. Blair, and A. Walker. Towards a theory of declarative knowledge. In e. J. Minker, editor, Foundation of Deductive Databases and Logic Programming, pages 89–148. Morgan Kaufmann, 1988.
A. Bossi and N. Cocco. Basic transformation operations for logic programs which preserve computed answer substitutions. Technical Report 16, Dip. Matematica Pura e Applicata, Università di Padova, Italy, April 1990. to appear in Special Issue on Partial Deduction of the Journal of Logic Programming.
A. Bossi, N. Cocco, and S. Dulli. A method for specializing logic programs. ACM Transactions on Programming Languages and Systems, 12(2):253–302, April 1990.
A. Bossi, N. Cocco, and S. Etalle. Transforming normal program by replacement. Technical Report 18, Dip. Matematica Pura e Applicata, Università di Padova, Italy, November 1991.
R. Burstall and J. Darlington. A transformation system for developing recursive programs. Journal of the ACM, 24(1):44–67, January 1977.
K. L. Clark. Negation as failure rule. In H. Gallaire and G. Minker, editors, Logic and Data Bases, pages 293–322. Plenum Press, 1978.
Y. Deville. Logic Programming. Systematic Program Development. Addison-Wesley, 1990.
S. Etalle. Transformazione dei programmi logici con negazione, Tesi di Laurea, Dip. Matematica Pura e Applicata, Università di Padova, Padova, Italy, July 1991.
M. Fitting. A Kripke-Kleene semantics for logic programs. Journal of Logic Programming, (4), 1985.
P. Gardner and J. Shepherdson. Unfold/fold transformations of logic programs. In J.-L. Lassez and e. G. Plotkin, editors, Computational Logic: Essays in Honor of Alan Robinson. 1991.
C. Hogger. Derivation of logic programs. Journal of the ACM, 28(2):372–392, April 1981.
C. Hogger. Introduction to Logic Programming. Academic Press, 1984.
S. Kleene. Introduction to Metamathematics. D. van Nostrand, Princeton, New Jersey, 1952.
H. Komorowski. Partial evaluation as a means for inferencing data structures in an applicative language: A theory and implementation in the case of Prolog. In Ninth ACM Symposium on Principles of Programming Languages, Albuquerque, New Mexico, pages 255–267, 1982.
K. Kunen. Negation in logic programming. Journal of Logic Programming, (4):289–308, 1985.
J. Lloyd. Foundations of Logic Programming. Springer-Verlag, 1987.
J. Lloyd and J. Shepherdson. Partial evaluation in logic programming. Technical Report CS-87-09, Department of Computer Science, University of Bristol, England, 1987. to appear in Journal of Logic Programming.
M. Maher. Correctness of a logic program transformation system. IBM Research Report RC13496, T.J. Watson Research Center, 1987.
M. Maher. A transformation system for deductive databases with perfect model semantics. Theoretical Computer Science, to appear.
M. Proietti and A. Pettorossi. The synthesis of eureka predicates for developing logic programs. In N. Jones, editor, ESOP'90, (Lecture Notes in Computer Science, Vol. 432), pages 306–325. Springer-Verlag, 1990.
M. Proietti and A. Pettorossi. Unfolding, definition, folding, in this order for avoiding unnecessary variables in logic programs. In Maluszynski and M. Wirsing, editors, PLILP 91, Passau, Germany (Lecture Notes in Computer Science, Vol.528), pages 347–358. Springer-Verlag, 1991.
T. Sato. An equivalence preserving first order unfold/fold transformation system. In Second Int. Conference on Algebraic and Logic Programming, Nancy, France, October 1990, (Lecture Notes in Computer Science, Vol. 463), pages 175–188. Springer-Verlag, 1990.
H. Seki. A comparative study of the well-founded and stable model semantics: Transformation's viewpoint. In D. P. W. Marek, A. Nerode and V. Subrahmanian, editors, Workshop on Logic Programming and Non-Monotonic Logic, Austin, Texas, October 1990, pages 115–123, 1990.
H. Seki. Unfold/fold transformation of stratified programs. Journal of Theoretical Computer Science, 86:107–139, 1991.
J. C. Shepherdson. Negation as failure: a comparision of Clark's completed data base and Reiter's closed world assumption. Journal of Logic Programming, (1):1–48, 1984.
J. C. Shepherdson. Negation in logic programming. In E. J. Minker, editor, Foundation of Deductive Databases and Logic Programming, pages 19–88. Morgan Kaufmann, 1988.
H. Tamaki and T. Sato. Unfold/fold transformation ol logic programs. In S. Tarnlund, editor, 2nd International Logic Programming Conference, Uppsala, Sweden, July 1984, pages 127–138, 1984.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1992 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bossi, A., Cocco, N., Etalle, S. (1992). Transforming normal programs by replacement. In: Pettorossi, A. (eds) Meta-Programming in Logic. META 1992. Lecture Notes in Computer Science, vol 649. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-56282-6_18
Download citation
DOI: https://doi.org/10.1007/3-540-56282-6_18
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-56282-5
Online ISBN: 978-3-540-47505-7
eBook Packages: Springer Book Archive