A Multiple-Clause Folding Rule Using Instantiation and Generalization

• Autorzy: Rosenblueth D.A.
• Języki publikacji: EN

Abstrakty

EN

A program-transformation system is determined by a repertoire of correctness-preserving rules, such as folding and unfolding. Normally, we would like the folding rule to be in some sense the inverse of the unfolding rule. Typically, however, the folding rule of logic program transformation systems is an inverse of a limited kind of unfolding. In many cases this limited kind of folding suffices. We argue, nevertheless, that it is both important and possible to extend such a folding so as to be able to fold the clauses resulting from any unfolding of a positive literal. This extended folding rule allows us to derive some programs underivable by the existing version of this rule alone. In addition, our folding rule has applications to decompilation and reengineering, where we are interested in obtaining high-level program constructs from low-level program constructs. Moreover, we establish a connection between logic program transformation and inductive logic programming. This connection stems from viewing our folding rule as a common extension of the existing multiple-clause folding rule, on the one hand, and an operator devised in inductive logic programming, called ``intra-construction,'' on the other hand. Hence, our folding rule can be regarded as a step towards incorporating inductive inference into logic program transformation. We prove correctness with respect to Dung and Kanchanasut's semantic kernel.

Słowa kluczowe

EN

logic program transformation; folding rule; most specific generalization; semantic kernel; decompilation; inductive logic programming

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 69, nr 1,2
• Strony: 219--249
• Opis fizyczny: bibliogr. 38 poz.

Twórcy

autor

Rosenblueth D.A.

• Instituto de Investigaciones en Matematicas Aplicadas y en Sistemas Universidad Nacional Autónoma de México Apdo. 20-726, 01000 México D.F. México,

Bibliografia

• [1] Aravindan, C., Dung, P. M.: On the correctness of unfold/fold transformation of normal and extended logic programs, The Journal of Logic Programming, 24(3), 1995, 201-217.
• [2] Arsac, J., Kodratoff, Y.: Some techniques for recursion removal from recursive functions, ACM Transactions on Programming Languages and Systems, 4(2), 1982, 295-322.
• [3] Baker, B. S.: An algorithm for structuring flowgraphs, Journal of the ACM, 24(1), 1977, 98-120.
• [4] Bowen, J. P.: From programs to object code and back again using logic programming: compilation and decompilation, Journal of Software Maintenance: Research and Practice, 5(4), 1993, 205-234.
• [5] Breuer, P. T., Bowen, J. P.: Decompilation: the enumeration of types and grammars, ACM Transactions on Programming Languages and Systems, 16(5), 1994, 1613-1647.
• [6] Burstall, R. M., Darlington, J.: A Transformation System for Developing Recursive Programs, Journal of the ACM, 24(1), 1977, 44-67.
• [7] Clark, K., Sickel, S.: Predicate logic: a calculus for deriving programs, Proc. IJCAI-77, 1977.
• [8] Dung, P. M., Kanchanasut, K.: A fixpoint approach to declarative semantics of logic programs, North American Logic Programming Conference (E. L. Lusk, R. A. Overbeek, Eds.), 1989.
• [9] van Emden, M. H., Yukawa, K.: Logic programming with equations, The Journal of Logic Programming, 4, 1987, 265-288.
• [10] Gardner, P. A., Shepherdson, J. C.: Unfold/Fold Transformations of Logic Programs, in: Computational Logic. Essays in Honor of Alan Robinson (J.-L. Lassez, G. Plotkin, Eds.), The MIT Press, 1992, 565-583.
• [11] Gergatsoulis, M., Katzouraki,M.: Unfold/fold transformations for definite clause programs, Proc. 6th International Symposium, Programming Language Implementation and Logic Programming (M. Hermenegildo, J. Penjam, Eds.), Springer-Verlag,Madrid, Spain, 1994, Lecture Notes in Computer Science No. 844.
• [12] Halstead, M. H.: Machine-independent computer programming, Spartan Books, 1962.
• [13] Hogger, C. J.: Derivation of Logic Programs, Journal of the ACM, 28(2), 1981, 372-392.
• [14] Kanamori, T., Fujita, H.: Unfold/fold transfomation of logic programs with counters, Technical report, ICOT, 1986.
• [15] Knuth, D. E., Morris, J. H., Pratt, V. R.: Fast Pattern Matching in Strings, SIAM Journal on Computing, 6(2), 1977, 323-350.
• [16] Lloyd, J. W.: Foundations of Logic Programming, 2nd edition, Springer-Verlag, 1987.
• [17] Maher, M. J.: A Transformation System for Deductive Database Modules with Perfect Model Semantics, Theoretical Computer Science, 110, 1993, 377-403.
• [18] Manna, Z., Waldinger, R.: Synthesis: Dreams → Programs, IEEE Transactions on Software Engineering, SE-5(4), 1979, 294-328.
• [19] Muggleton, S., Buntine, W.: Machine Invention of First-order Predicates by Inverting Resolution, Proc. Fifth International Conference on Machine Learning (J. Laird, Ed.), Morgan Kaufmann, 1988, Also in S. Muggleton (ed), Inductive Logic Programming, Academic Press, 1992, APIC-38, pp 261-280.
• [20] Mycroft, A.: Type-based decompilation, Proc. Eighth European Symposium on Programming (S. D. Swierstra, Ed.), 1999, Lecture Notes in Computer Science No. 1576.
• [21] Pettorossi, A., Proietti, M.: Transformation of Logic Programs: Foundations and Techniques, The Journal of Logic Programming, 19, 20, 1994, 261-320.
• [22] Pettorossi, A., Proietti, M.: Program Derivation via List Introduction, Proc. IFIP TC2 Working Conference on Algorithmic Languages and Calculi (R. Bird, L. Meertens, Eds.), Chapman & Hall, 1997.
• [23] Pettorossi, A., Proietti, M.: Transformation of Logic Programs, in: Handbook of Logic in Artificial Intelligence and Logic Programming (D.M. Gabbay, C. J. Hogger, J. A. Robinson, Eds.), vol. 5, Oxford University Press, 1998, 697-787.
• [24] Pettorossi, A., Proietti, M.: The List Introduction Strategy for the Derivation of Logic Programs, Formal Aspects of Computing, 13, 2002, 233-251.
• [25] Pettorossi, A., Proietti, M., Renault, S.: Derivation of Efficient Logic Programs by Specialization and Reduction of Nondeterminism, to appear in: Higher-Order and Symbolic Computation.
• [26] Pettorossi, A., Proietti, M., Renault, S.: Enhancing Partial Deduction via Unfold/Fold Rules, Proc. 6th Int. Workshop on Logic Program Synthesis and Transformation, Springer-Verlag, Stockholm, Sweden, 1996, Lecture Notes in Computer Science No. 1207.
• [27] Plotkin, G. D.: A note on inductive generalization, in: Machine Intelligence 5 (B. Meltzer, D. Michie, Eds.), Edinburgh University Press, 1970, 153-163.
• [28] Plotkin, G. D.: Building-in equational theories, in: Machine Intelligence 7 (B. Meltzer, D. Michie, Eds.), Edinburgh University Press, 1972, 73-90.
• [29] Proietti, M., Pettorossi, A.: Unfolding-definition-folding, in this order, for avoiding unnecessary variables in logic programs, Theoretical Computer Science, 142, 1995, 89-124.
• [30] Reynolds, J. C.: Transformational Systems and the Algebraic Structure of Atomic Formulas, in: Machine Intelligence 5 (B. Meltzer, D. Michie, Eds.), Edinburgh University Press, 1970, 135-151.
• [31] Roychoudhury, A., Kumar, K. N., Ramakrishnan, C. R., Ramakrishnan, I.: Beyond Tamaki-Sato style unfold/ fold transformations for normal logic programs, International Journal of Foundations of Computer Science, 13(3), 2002, 387-403.
• [32] Roychoudhury, A., Kumar, K. N., Ramakrishnan, C. R., Ramakrishnan, I. V.: A parameterized unfold/fold transformation framework for definite logic programs, Proc. Principles and Practice of Declarative Programming (G. Nadathur, Ed.), Springer-Verlag, 1999, Lecture Notes in Computer Science No. 1702.
• [33] Seki, H.: Unfold/fold transformation of stratified programs, Theoretical Computer Science, 86, 1991, 107-139.
• [34] Seki, H.: Unfold/fold transformation of general logic programs for the well-founded semantics, The Journal of Logic Programming, 16, 1993, 5-23.
• [35] Tamaki, H., Sato, T.: Unfold/fold transformation of logic programs, Proc. Second International Logic Programming Conference, 1984.
• [36] Tamaki, H., Sato, T.: A generalized correctness proof of the unfold/fold logic program transformation, Technical report, Ibaraki University, 1986.
• [37] Ward, M. P.: Pigs from sausages? reengineering from assembler to C via FermaT transformation, Science of Computer Programming (special issue on program transformation), 52(1-3), 2004, 213-255.
• [38] Wegbreit, B.: Goal-Directed Program Transformation, Technical Report CSL-75-8, XEROX Palo Alto Research Center, September 1975.