Rules and strategies for transforming functional and logic programs

ABSTRACT

We present an overview of the program transformation methodology, focusing our attention on the so-called “rules + strategies” approach in the case of functional and logic programs. The paper is intended to offer an introduction to the subject. The various techniques we present are illustrated via simple examples.

REFERENCES

• 1: S. Abramsky , C. Hankin, Abstract interpretation of declarative languages, Halsted Press, New York, NY, 1987
• 2: AERTS, K. AND VAN BESIEN, D. 1991. Autolap: A system for transforming logic programs. Department of Electronics Rep. University of Rome, Tor Vergata, Rome, Italy.
• 3: Francis Alexandre , Khaled Bsaïes , Jean-Pierre Finance , Alain Quéré, Spes: A System for Logic Program Transformation, Proceedings of the International Conference on Logic Programming and Automated Reasoning, p.445-447, July 15-20, 1992
• 4: ARAVINDAN, C. AND DUNG, P. M. 1993. On the Correctness of unfold/fold transformation of normal and extended logic programs. Tech. Rep., Computer Science Division, Asian Institute of Technology, Bangkok, Thailand.
• 5: J. Arsac , Y. Kodratoff, Some Techniques for Recursion Removal from Recursive Functions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.2, p.295-322, April 1982 [doi>10.1145/357162.357171]
• 6: AUBIN, R. 1979. Mechanizing structural induction: Part I and II. Theor. Comput. Sci. 9, 3, 329-362.
• 7: John Backus, Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs, Communications of the ACM, v.21 n.8, p.613-641, Aug. 1978 [doi>10.1145/359576.359579]
• 8: Joseph L. Bates , Robert L. Constable, Proofs as programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.1, p.113-136, Jan. 1985 [doi>10.1145/2363.2528]
• 9: F. L. Bauer , H. Ehler , A. Horsch , B. Moeller , H. Partsch , O. Paukner , P. Pepper, The/Munich Project CIP, Springer-Verlag New York, Inc., New York, NY, 1988
• 10: F L Bauer , R Berghammer , M Broy , W Dosch , F Geiselbrechtinger , R Gnatz , E Hangel , W Hesse , B Krieg-Brückner , A Laut , T Matzner , B Möller , F Nickl , H Partsch , P Pepper , K Samelson , M Wirsing , H Wössner, The Munich Project CIP: Volume I: the wide spectrum language CIP-L, Springer-Verlag, London, 1986
• 11: BERRY, G. 1976. Bottom-up computation of recursive programs. RAIRO Inf. Thgor. 10, 3, 47-82.
• 12: BIRD, R. S. 1984a. Using circular programs to eliminate multiple traversal of data. Acta Inf. 21, 239 -250.
• 13: R. S. Bird, The promotion and accumulation strategies in transformational programming, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.4, p.487-504, Oct. 1984 [doi>10.1145/1780.1781]
• 14: R. S. Bird, Tabulation Techniques for Recursive Programs, ACM Computing Surveys (CSUR), v.12 n.4, p.403-417, Dec. 1980 [doi>10.1145/356827.356831]
• 15: R. S. Bird , L. Meertens, Two exercises found in a book on algorithmics, The IFIP TC2/WG 2.1 Working Conference on Program specification and transformation, p.451-457, June 1987, Bad To:9Ailz, Germany
• 16: BJDRNER, D., ERSHOV, A. P., AND JONES, N. D., EDS. 1988. Partial evaluation and mixed computation. In Proceedings of the IFIP TC2 Workshop on Partial and Mixed Computation (Gammel Avernms, Denmark), North Holland.
• 17: BOITEN, E. A. 1990. Views of formal program development. Catholic University of Nijmegen, Nijmegen, The Netherlands, Ph. D. Thesis.
• 18: Bosco, P. G., GIOVANETTI, E., LEVI, G., MOISO, C., AND PALAMIDESSI, C. 1987. A complete semantic characterization of K-LEAF, a logic language with partial functions. In Proceedings of the Fourth Symposium on Logic Programming (San Francisco, CA), IEEE Computer Society Press, Los Alamitos, CA, 1-27.
• 19: BossI, n. AND COCCO, N. 1993. Basic transformation operations for logic programs which preserve computed answer substitutions. J. Logic Program., Special Issue on Partial Deduction 16, 47-87.
• 20: Annalisa Bossi , Nicoletta Cocco , Sandro Etalle, Transforming Normal Programs by Replacement, Proceedings of the 3rd International Workshop on Meta-Programming in Logic, p.265-279, June 10-12, 1992
• 21: Dmitri Boulanger , Maurice Bruynooghe, Deriving fold/unfold transformations of logic programs using extended OLDT-based abstract interpretation, Journal of Symbolic Computation, v.15 n.5-6, p.495-521, May/June 1993 [doi>10.1016/S0747-7171(06)80003-9]
• 22: BOYLE, g. M. 1984. Lisp to Fortran--program transformation applied. In Proceedings of the Workshop on Program Transformation and Programming Environments. Nato ASI Series F, Computer and Systems Sciences 8, P. Pepper, Ed., Springer Verlag, 291-298.
• 23: Robert S. Boyer , J. Strother Moore, Proving Theorems about LISP Functions, Journal of the ACM (JACM), v.22 n.1, p.129-144, Jan. 1975 [doi>10.1145/321864.321875]
• 24: D. R. Brough , C. J. Hogger, Grammar-related transformations of logic programs, New Generation Computing, v.9 n.2, p.115-134, 1991 [doi>10.1007/BF03037639]
• 25: Maurice Bruynooghe , Danny de Schreye , Bruno Krekels, Compiling control, Journal of Logic Programming, v.6 n.1-2, p.135-162, Jan./Mar. 1989 [doi>10.1016/0743-1066(89)90033-2]
• 26: Janusz A. Brzozowski, Derivatives of Regular Expressions, Journal of the ACM (JACM), v.11 n.4, p.481-494, Oct. 1964 [doi>10.1145/321239.321249]
• 27: R. M. Burstall , John Darlington, A Transformation System for Developing Recursive Programs, Journal of the ACM (JACM), v.24 n.1, p.44-67, Jan. 1977 [doi>10.1145/321992.321996]
• 28: R. M. Burstall , John Darlington, Some transformations for developing recursive programs, Proceedings of the international conference on Reliable software, p.465-472, April 21-23, 1975, Los Angeles, California
• 29: BURSTALL, R. M. ET AL. 1991. The Lego project. Computer Science Department, Edinburgh University, Edinburgh, Scotland.
• 30: CAI, J. AND PAIGE, R. 1990. The RAPTS transformation system. Computer Science Department, New York University, New York.
• 31: CHATELIN, P. 1976. Program manipulation: To duplicate is not to complicate. Rep. CNRS Laboratoire d'Informatique. Universit~ de Grenoble, France.
• 32: Wei-Ngan Chin, Towards an automated tupling strategy, Proceedings of the 1993 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.119-132, June 14-16, 1993, Copenhagen, Denmark [doi>10.1145/154630.154643]
• 33: Wei-Ngan Chin, Safe fusion of functional expressions, Proceedings of the 1992 ACM conference on LISP and functional programming, p.11-20, June 22-24, 1992, San Francisco, California, United States
• 34: CHIN, W.-N. 1990. Automatic methods for program transformation. Imperial College of Science, Technology and Medicine, University of London, London, U.K., Ph.D. Thesis.
• 35: Thierry Coquand , Gerard Huet, The calculus of constructions, Information and Computation, v.76 n.2-3, p.95-120, February/March 1988 [doi>10.1016/0890-5401(88)90005-3]
• 36: Bruno Courcelle, Recursive applicative program schemes, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• 37: Patrick Cousot , Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.238-252, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512973]
• 38: DARLINGTON, J. 1981. An experimental program transformation system. Artif. Intell. 16, 1-46.
• 39: DARLINGTON, g. 1972. A semantic approach to automatic program improvement. Department of Machine Intelligence, Edinburgh University, Edinburgh, U.K., Ph.D. Thesis.
• 40: DARLINGTON, J. AND GUO, Y. 1979. The unification of functional and logic languages, towards constraint functional programming. Tech. Rep., Imperial College, London, U.K.
• 41: DEBRAY, S. K., ED. 1992. Special Issue of J. Logic Program. Abstract Interpretation. 12, 2 & 3.
• 42: S. K. Debray, Unfold/fold transformations and loop optimization of logic programs, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.297-307, June 20-24, 1988, Atlanta, Georgia, United States
• 43: Saumya K. Debray , David S. Warren, Automatic mode inference for logic programs, Journal of Logic Programming, v.5 n.3, p.207-229, Sept. 1988 [doi>10.1016/0743-1066(88)90010-6]
• 44: DERSHOWITZ, N. 1985. Synthesis by completion. In Proceedings of the Ninth International Joint Conference on Artificial Intelligence 1,208-214.
• 45: Yves Deville, Logic programming: systematic program development, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 46: DEVILLE, Y. AND BURNAY, J. 1989. Generalization and Program Schemata. In Proceedings of NACLP '89, MIT Press, Cambridge, MA, 409-425.
• 47: DEVILLE, Y. AND LAU, K.-K. 1994. Logic program synthesis. J. Logic Program. 19 & 20, 321-350.
• 48: Maarten H. van Emden , Keitaro Yukawa, Logic programming with equations, Journal of Logic Programming, v.4 n.4, p.265-288, December 1, 1987 [doi>10.1016/0743-1066(87)90006-9]
• 49: ERSHOV, A. P. 1982. Mixed computation: Potential applications and problems for study. Theor. Comput. Sci. 18, 41-67.
• 50: M. S. Feather, A survey and classification of some program transformation approaches and techniques, The IFIP TC2/WG 2.1 Working Conference on Program specification and transformation, p.165-195, June 1987, Bad To:9Ailz, Germany
• 51: Martin S. Feather, A System for Assisting Program Transformation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.1, p.1-20, Jan. 1982 [doi>10.1145/357153.357154]
• 52: FRIBOURG, L. 1985. SLOG: A logic programming language interpreter based on clausal superposition and rewriting. In Proceedings of the IEEE International Symposium on Logic Programming, (Boston, MA), IEEE Computer Society Press, Los Alamitos, CA, 172-184.
• 53: FUCHS, N. E. AND FROMHERZ, M. P. J. 1992. Schema-based transformations of logic programs. In Logic Program Synthesis and Transformation, Proceedings LOPSTR '91 (Manchester, UK), T. Clement and K. K. Lau, Eds., Springer-Verlag, 111-125.
• 54: FUTAMURA, Y. 1971. Partial evaluation of computation process--an approach to a compiler-compiler. Syst. Comput. Controls 2, 5, 45-50.
• 55: J. P. Gallagher, Tutorial on specialisation of logic programs, Proceedings of the 1993 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.88-98, June 14-16, 1993, Copenhagen, Denmark [doi>10.1145/154630.154640]
• 56: GALMICHE, D. 1991. Proofs and program development in AF2. In Notes of the IFIP W.G. 2.1 Meeting (Louvain-la-Neuve, Belgium).
• 57: G. Gardarin , I. Guessarian , C. de Maindreville, Translation of logic programs into functional fixpoint equations, Theoretical Computer Science, v.63 n.3, p.253-274, March 1989 [doi>10.1016/0304-3975(89)90009-1]
• 58: GARDNER, P. A. AND SHEPHERDSON, J.C. 1991.Unfold/fold transformations of logic programs. In Computational Logic, Essays in Honor of Alan Robinson, J.-L. Lassez and G. Plotkin, Eds., MIT Press, Cambridge, MA, 565-583.
• 59: GOGUEN J. AND MESEGUER J. 1986. Eqlog: Equality, types, and generic modules for logic programming. In Logic Programming: Functions, Relations, and Equations, D. De Groot and G. Lindstrom, Eds., Prentice-Hall, Englewood Cliffs, NJ, 295-363. An earlier version appears in J. Logic Program. 1, 2, 179-210.
• 60: C. J. Hogger, Derivation of Logic Programs, Journal of the ACM (JACM), v.28 n.2, p.372-392, April 1981 [doi>10.1145/322248.322258]
• 61: HUET, G. AND LANG, B. 1978. Proving and applying program transformation expressed with secondorder patterns. Acta Inf. 11, 31-55.
• 62: R. J. M. Hughes, Super-combinators a new implementation method for applicative languages, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.1-10, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802129]
• 63: Martin Illsley, Transforming imperative programs (transformation rule), 1988
• 64: Thomas Johnsson, Lambda lifting: transforming programs to recursive equations, Proc. of a conference on Functional programming languages and computer architecture, p.190-203, January 1985, Nancy, France
• 65: JONES, N. D. 1987. Automatic program specialization: A re-examination from basic principles. In Proceedings of the IFIP TC2 Working Conference on Partial and Mixed Computation (Ebberup, Denmark), D. Bjcrner and A. P. Ershov, Eds., 225-282.
• 66: Neil D. Jones , Carsten K. Gomard , Peter Sestoft, Partial evaluation and automatic program generation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 67: JONES, N. AND SONDERGAARD, H. 1987. A semantics-based framework for the abstract interpretation of Prolog. In Abstract Interpretation of Declarative Languages, S. Abramsky and C. Hankin, Eds., Ellis Horwood, Chichester, UK, 123-142.
• 68: Ulrik Jørring , William L. Scherlis, Compilers and staging transformations, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.86-96, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512652]
• 69: KANAMORI, T. AND HORIUCHI, K. 1987. Construction of logic programs based on generalized unfold/fold rules. In Proceedings of the Fourth International Conference on Logic Programming, MIT Press, Cambridge, MA, 744-768.
• 70: KANAMORI, T. AND MAEJI, M. 1986. Derivation of logic programs from implicit definition. Tech. Rep. TR-178, ICOT, Tokyo.
• 71: KAWAMURA, T. AND KANAMORI, T. 1988. Preservation of stronger equivalence in unfold/fold logic program transformation. In Proceedings of the International Conference on Fifth Generation Computer Systems (Tokyo), 413-422.
• 72: KOTT, L. 1982. The McCarthy's induction principle: "Oldy" but "Goody." Calcolo 19, 1, 59-69.
• 73: KOTT, L. 1978. About Transformation System: A Theoretical Study. In Troisi~me Colloque International sur la Programmation, Dunod, Paris, France, 232-247.
• 74: KRIEG-BR~CKNER, B., ED. 1989. COMPASS, A comprehensive algebraic approach to system specification and development. ESPRIT Basic Research Working Group 3264, Objectives, State of the Art, References. University of Bremen, Germany, Bericht no. 6/89.
• 75: A. Lakhotia , L. Sterling, Composing recursive logic programs with clausal join, New Generation Computing, v.6 n.2-3, p.211-225, March-April 1988 [doi>10.1007/BF03037138]
• 76: John Launchbury, Projection factorisations in partial evaluation, Cambridge University Press, New York, NY, 1991
• 77: LINCOLN, P., MARTI-OLIET, N., AND MESEGUER, g. 1994. Specification, transformation, and programming of concurrent systems in rewriting logic. In Proceedings of the DIMACS Conference on Specification of Parallel Algorithms (Princeton, NJ), G. Blelloch, K. M. Chandy, and S. Jagannathan, Eds., American Mathematical Society, Providence, RI, 309-339.
• 78: J. W. Lloyd, Foundations of logic programming; (2nd extended ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 79: J. W. Lloyd , J. C. Shepherdson, Partial evaluation in logic programming, Journal of Logic Programming, v.11 n.3-4, p.217-242, Oct./Nov. 1991 [doi>10.1016/0743-1066(91)90027-M]
• 80: Michael J. Maher, A transformation system for deductive database modules with perfect model semantics, Theoretical Computer Science, v.110 n.2, p.377-403, March 29, 1993 [doi>10.1016/0304-3975(93)90013-J]
• 81: Zohar Manna, Introduction to Mathematical Theory of Computation, McGraw-Hill, Inc., New York, NY, 1974
• 82: MANNA, Z. AND WALDINGER, R. 1991. Fundamentals of deductive program synthesis. In Logic, Algebra, and Computation. F. L. Bauer, Ed., Springer-Verlag, 41-107.
• 83: E. Marakakis , John P. Gallagher, Schema-Based Top-Down Design of Logic Programs Using Abstract Data Types, Proceedings of the 4th International Workshops on Logic Programming Synthesis and Transformation - Meta-Programming in Logic, p.138-153, June 20-21, 1994
• 84: MEERTENS, L. G. L. T., ED. 1987. Program specification and transformation. In Proceedings of the IFIP TC2 W.G. 2.1 Working Conference on Program Specification and Transformation (Bad Ti31z, Germany), North Holland.
• 85: MOGENSEN, T. AND BONDORF, A. 1993. Logimix: A self-applicable partial evaluator for Prolog. In Logic Program Synthesis and Transformation, Proceedings LOPSTR '92 (Manchester, UK), K.-K. Lau and T. Clement, Eds., Springer-Verlag, 214-227.
• 86: Bernhard Möller, Derivation of Graph and Pointer Algorithms, Proceedings of the IFIP TC2/WG 2.1 State-of-the-Art Report on Formal Program Development, p.123-160, January 1993
• 87: MOLLER, B. 1991. Relations as a program development language. In Proceedings of the IFIP TC2 Working Conference on Constructing Programs from Specifications (Pacific Grove, CA), North Holland.
• 88: Proceedings of the IFIP TC2/WG 2.1 State-of-the-Art Report on Formal Program Development, January 1993
• 89: Juan Jose Moreno-Navarro , Mario Rodriguez-Artalejo, Logic programming with functions and predicates: the language Babel, Journal of Logic Programming, v.12 n.3, p.191-223, Feb. 1992 [doi>10.1016/0743-1066(92)90024-W]
• 90: MYCROFT, A. 1981. Abstract interpretation and optimizing transformations for applicative programs. CTS 15-81, University of Edinburgh, Scotland, Ph.D. Thesis.
• 91: H. R. Nielson , F. Nielson, Automatic binding time analysis for a typed &lgr;-calculus, Science of Computer Programming, v.10 n.2, p.139-176, April 1988 [doi>10.1016/0167-6423(88)90025-1]
• 92: Robert Paige , Shaye Koenig, Finite Differencing of Computable Expressions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.402-454, July 1982 [doi>10.1145/357172.357177]
• 93: PAIGE, R., REIF, J., AND WACHTER, R., EDS. 1993. Parallel algorithm derivation and program transformation. In Proceedings of the Workshop at Courant Institute of Mathematical Sciences (New York), Kluwer Academic Publishers.
• 94: Helmut A. Partsch, Specification and transformation of programs: a formal approach to software development, Springer-Verlag New York, Inc., New York, NY, 1990
• 95: H. Partsch , R. Steinbrüggen, Program Transformation Systems, ACM Computing Surveys (CSUR), v.15 n.3, p.199-236, Sept. 1983 [doi>10.1145/356914.356917]
• 96: PATERSON, M. S. AND HEWITT, C. E. 1970. Comparative schematology. In Conference on Concurrent Systems and Parallel Computation Project MAC (Woods Hole, MA), 119-127.
• 97: Peter Pepper, A simple calculus for program transformation (inclusive of induction), Science of Computer Programming, v.9 n.3, p.221-262, December 1, 1987 [doi>10.1016/0167-6423(87)90008-6]
• 98: Peter Pepper, Program Transformation and Programming Environments, Springer-Verlag New York, Inc., Secaucus, NJ, 1984
• 99: A. Pettorossi, Derivation of efficient programs for computing sequences of actions, Theoretical Computer Science, v.53 n.1, p.151-167, August, 1987 [doi>10.1016/0304-3975(87)90030-2]
• 100: A. Pettorossi, Derivation of programs which traverse their input data only once, Advanced Programming Methodologies, Academic Press Professional, Inc., San Diego, CA, 1989
• 101: PETTOROSSI, A. 1984. Methodologies for transformations and memoing in applicative languages. Edinburgh University, Edinburgh, Scotland, Ph.D. Thesis.
• 102: PETTOROSSI, A. AND BURSTALL, R. M. 1982. Deriving very efficient algorithms for evaluating linear recurrence relations using the program transformation technique. Acta Inf. 18, 181-206.
• 103: PETTOROSSI, A. AND PROIETTI, M. 1994. Transformation of logic programs: Foundations and techniques. J. Logic Program. 19, 20, 261-320.
• 104: PETTOROSSI, A. AND PROIETTI, M. 1987. Importing and exporting information in program development. In Proceedings of the IFIP TC2 Workshop on Partial Evaluation and Mixed Computation (Gammel Avernaes, Denmark), North Holland, 405-425.
• 105: A. Pettorossi , A. Skowron, Higher order generalization in program derivation, II and Colloquium on Functional and Logic Programming and Specifications (CFLP) on TAPSOFT '87: Advanced Seminar on Foundations of Innovative Software Development, p.182-196, March 1987, Pisa, Italy
• 106: Alberto Pettorossi , Andrzej Skowron, Communicating agents for applicative concurrent programming, Proceedings of the 5th Colloquium on International Symposium on Programming, p.305-322, April 06-08, 1982
• 107: Maurizio Proietti , Alberto Pettorossi, Semantics preserving transformation rules for Prolog, ACM SIGPLAN Notices, v.26 n.9, p.274-284, Sept. 1991
• 108: Maurizio Proietti , Alberto Pettorossi, Unfolding-definition-folding, in this order, for avoiding unnecessary variables in logic programs, Selected papers of the symposium on Programming language implementation and logic programming, p.89-124, May 1995, Passau, Germany
• 109: PROIETTI, M. AND PETTOROSSI, A. 1994. Synthesis of programs from unfold/fold proofs. In Proceedings LOPSTR '93 (Louvain-la-Neuve, Belgium), Workshops in Computing Series, Springer Verlag, 141-158.
• 110: M. Proietti , A. Pettorossi, Synthesis of eureka predicates for developing logic programs, Proceedings of the third European symposium on programming on ESOP '90, p.306-325, May 1990, Copenhagen, Denmark
• 111: Uday S. Reddy, Functional logic languages, Part I, Proc. of a workshop on Graph reduction, p.401-425, September 1987, Santa Fe, New Mexico, United States
• 112: REDDY, U. S. 1984. Transformation of logic programs into functional programs. In Proceedings of the IEEE International Symposium on Logic Programming, IEEE Computer Society Press, Los Alamitos, CA, 187-197.
• 113: T. Reps, Algebraic properties of program integration, Proceedings of the third European symposium on programming on ESOP '90, p.326-340, May 1990, Copenhagen, Denmark
• 114: SANDS, D. 1994. Total correctness and improvement in the transformation of functional programs. Tech. Rep. DIKU, University of Copenhagen, Denmark.
• 115: Taisuke Sato, Equivalence-preserving first-order unfold/fold transformation systems, Theoretical Computer Science, v.105 n.1, p.57-84, Oct. 26, 1992 [doi>10.1016/0304-3975(92)90287-P]
• 116: William L. Scherlis, Program improvement by internal specialization, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.41-49, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567536]
• 117: SCHWARZ, J. 1982. Using annotations to make recursive equations behave. IEEE Trans. Softw. Eng. SE 8, 1, 21-33.
• 118: SEKI, H. 1993. Unfold/fold transformation of general logic programs for the well-founded semantics. J. Logic Program., Special Issue on Partial Deduction 16, 1 & 2, 5-23.
• 119: Hiroshisa Seki, Unfold/fold transformation of stratified programs, Theoretical Computer Science, v.86 n.1, p.107-139, Aug. 18, 1991 [doi>10.1016/0304-3975(91)90007-O]
• 120: SEKI, H. AND FURUKAWA, K. 1987. Notes on transformation techniques for generate and test logic programs. In Proceedings of the International Symposium on Logic Programming, (San Francisco), IEEE Press, Piscataway, NJ, 215-223.
• 121: SINTZOFF, M., WEBER, M., DE GROOTE, P., AND CAZIN, J. 1989. Definition 1.1 of the generic development language Deva. Tech. Rep., Unit~ d'Informatique, Universit~ Catholique de Louvain, Louvain-La- Neuve, Belgium.
• 122: Douglas R. Smith, Automating the Design of Algorithm, Proceedings of the IFIP TC2/WG 2.1 State-of-the-Art Report on Formal Program Development, p.324-354, January 1993
• 123: Douglas R. Smith, The design of divide and conquer algorithms, Science of Computer Programming, v.5 n.1, p.37-58, Feb. 1985
• 124: Leon Sterling , Mark Kirschenbaum, Applying techniques to skeletons, Constructing logic programs, John Wiley & Sons, Inc., New York, NY, 1993
• 125: SUBRAHMANYAM, P. A. AND YOU, J. H. 1986. FUNLOG: A computational model integrating logic programming and functional programming. In Logic Programming: Functions, Relations, and Equations, D. De Groot, and G. Lindstrom, Eds., Prentice-Hall, Englewood Cliffs, NJ, 157-198.
• 126: Masato Takeichi, Partial parametrization eliminates multiple traversals of data structures, Acta Informatica, v.24 n.1, p.57-77, Feb. 1987 [doi>10.1007/BF00290706]
• 127: TAMAKI, H. AND SATO, T. 1984. Unfold/fold transformation of logic programs. In Proceedings of the Second International Conference on Logic Programming (Uppsala, Sweden), 127-138.
• 128: Paul Tarau , Michel Boyer, Elementary Logic Programs, Proceedings of the 2nd International Workshop on Programming Language Implementation and Logic Programming, p.159-173, August 20-22, 1990
• 129: Atsushi Togashi , Shoichi Noguchi, A program transformation from equational programs into logic programs, Journal of Logic Programming, v.4 n.2, p.85-103, June 1, 19876 [doi>10.1016/0743-1066(87)90013-6]
• 130: TURNER, D. A. 1979. A new implementation technique for applicative languages. Softw. Pract. Exper. 9, 31-49.
• 131: Philip Lee Wadler, Listlessness is better than laziness: an algorithm that transforms applicative programs to eliminate intermediate lists, 1984
• 132: Mitchell Wand, Continuation-Based Program Transformation Strategies, Journal of the ACM (JACM), v.27 n.1, p.164-180, Jan. 1980 [doi>10.1145/322169.322183]
• 133: WEGBREIT, B. 1976. Goal-directed program transformation. IEEE Trans. Softw. Eng. SE 2, 69-79.
• 134: WILE, D. 1982. POPART: Producer of parser and related tools. Tech. Rep. RR-82-21, ISI, 4676 Admiralty Way, Marina del Rey, CA.
• 135: Niklaus Wirth, Algorithms & data structures, Prentice-Hall, Inc., Upper Saddle River, NJ, 1985
• 136: ZHU, H. 1994. How powerful are folding/unfolding transformations? J. Funct. Program. 4, 1, 89-112.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.2 SOFTWARE ENGINEERING
        D.2.10 Design**
            Subjects: Methodologies**
      D.2.4 Software/Program Verification
          Subjects: Correctness proofs
      D.2.5 Testing and Debugging
          Subjects: Symbolic execution
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
  F.3 LOGICS AND MEANINGS OF PROGRAMS

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program transformation
      I.2.3 Deduction and Theorem Proving
          Subjects: Logic programming

General Terms:
Algorithms, Design, Theory, Verification

Keywords:
program derivation, program improvement, transformation rules, transformation strategies