Partial evaluation of functional logic programs

ABSTRACT

Languages that integrate functional and logic programming with a complete operational semantics are based on narrowing, a unification-based goal-solving mechanism which subsumes the reduction principle of functional languages and the resolution principle of logic languages. In this article, we present a partial evaluation scheme for functional logic languages based on an automatic unfolding algorithm which builds narrowing trees. The method is formalized within the theoretical framework established by Lloyd and Shepherdson for the partial deduction of logic programs, which we have generalized for dealing with functional computations. A generic specialization algorithm is proposed which does not depend on the eager or lazy nature of the narrower being used. To the best of our knowledge, this is the first generic algorithm for the specialization of functional logic programs. We also discuss the relation to work on partial evaluation in functional programming, term-rewriting systems, and logic programming. Finally, we present some experimental results with an implementation of the algorithm which show in practice that the narrowing-driven partial evaluator effectively combines the propagation of partial data structures (by means of logical variables and unification) with better opportunities for optimization (thanks to the functional dimension).

REFERENCES

• 1: Elvira Albert , María Alpuente , Moreno Falaschi , P. Julián , Germán Vidal, Improving Control in Functional Logic Program Specialization, Proceedings of the 5th International Symposium on Static Analysis, p.262-277, September 14-16, 1998
• 2: ALBERT, E., ALPUENTE, M., FALASCHI, M., AND VIDAL, G. 1998. INDY user's manual. Tech. Rep. DSIC-II/12/98, UPV. Available from URL: http://www, dsic. upv. es/users/elp/papers, html.
• 3: M. Alpuente , M. Falaschi , P. Julián , G. Vidal, Specialization of lazy functional logic programs, Proceedings of the 1997 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.151-162, June 12-13, 1997, Amsterdam, The Netherlands
• 4: María Alpuente , Moreno Falaschi , Giorgio Levi, Incremental constraint satisfaction for equational logic programming, Theoretical Computer Science, v.142 n.1, p.27-57, May 1, 1995
• 5: María Alpuente , Moreno Falaschi , Germán Vidal, A compositional semantic basis for the analysis of equational Horn programs, Theoretical Computer Science, v.165 n.1, p.133-169, Sept. 30, 1996
• 6: María Alpuente , Moreno Falaschi , Germán Vidal, Narrowing-Driven Partial Evaluation of Functional Logic Programs, Proceedings of the 6th European Symposium on Programming Languages and Systems, p.45-61, April 22-24, 1996
• 7: ALPUENTE, M., FALASCHI, M.,AND VIDAL, G. 1998a.Experiments with the callby-value partial evaluator.Tech. Rep. DSIC-II/13/98, UPV. Available from http://www, dsic. upv. es/users/elp/papers, html.
• 8: Maria Alpuente , Moreno Falaschi , German Vidal, A unifying view of functional and logic program specialization, ACM Computing Surveys (CSUR), v.30 n.3es, Sept. 1998 [doi>10.1145/289121.289130]
• 9: Sergio Antoy , Rachid Echahed , Michael Hanus, A needed narrowing strategy, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.268-279, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.177899]
• 10: Puri Arenas-Sánchez , Ana Gil-Luezas , Francisco Javier López-Fraguas, Combining Layz Narrowing with Disequality Constraints, Proceedings of the 6th International Symposium on Programming Language Implementation and Logic Programming, p.385-399, September 14-16, 1994
• 11: Franz Baader , Tobias Nipkow, Term rewriting and all that, Cambridge University Press, New York, NY, 1998
• 12: Françoise Bellegarde, ASTRE: Towards a Fully Automated Program Transformation System, Proceedings of the 6th International Conference on Rewriting Techniques and Applications, p.403-407, April 05-07, 1995
• 13: BENKERIMI, I~. AND HILL, P. 1993. Supporting transformations for the partial evaluation of logic programs. J. Logic Comput. 3, 5, 469-486.
• 14: Kerima Benkerimi , John W. Lloyd, A partial evaluation procedure for logic programs, Proceedings of the 1990 North American conference on Logic programming, p.343-358, January 1990, Austin, Texas, United States
• 15: D Bert , R Echahed, Design and implementation of a generic, logic and functional programming language, Proc. of the European symposium on programming on ESOP 86, p.119-132, March 1986, Saarbru:9Aicken, Germany
• 16: Didier Bert , Rachid Echahed, On the Operational Semantics of the Algebraic and Logic Programming Language LPG, Selected papers from the 10th Workshop on Specification of Abstract Data Types Joint with the 5th COMPASS Workshop on Recent Trends in Data Type Specification, p.132-152, May 30-June 03, 1994
• 17: Alexander Bockmayr , Andreas Werner, LSE Narrowing for Decreasing Conditional Term Rewrite Systems, Proceedings of the 4th International Workshop on Conditional and Typed Rewriting Systems, p.51-70, July 13-15, 1994
• 18: BOL, R. 1993. Loop checking in partial deduction. J. Logic Program. 16, 1&2, 25-46.
• 19: BONACINA, M. 1988. Partial evaluation by completion. In Conferenza dell'Associazione Italiana per il Calcolo Automatico, G. Italiani et al., Ed.
• 20: BONDORF, t. 1988. Towards a self-applicable partial evaluator for term rewriting systems. In Proceedings of the International Workshop on Partial Evaluation and Mixed Computation, D. Bj0rner, A. Ershov, and N. Jones, Eds. North-Holland, Amsterdam, 27-50.
• 21: Anders Bondorf, A Self-Applicable Partial Evaluator for Term Rewriting Systems, Proceedings of the International Joint Conference on Theory and Practice of Software Development, Volume 2: Advanced Seminar on Foundations of Innovative Software Development II and Colloquium on Current Issues in Programming Languages, p.81-95, March 13-17, 1989
• 22: BossI, t., GABBRIELLI, M., LEVI, G., AND MARTELLI, M. 1994. The s-semantics approach: Theory and applications. J. Logic Program. 19-20, 149-197.
• 23: BOWEN, K. AND KOWALSKI, R. 1982. Amalgamating language and metalanguage in logic programruing. In Logic Programming, K. Clark and S. Tgrnlund, Eds. Academic Press, New York, 153-172.
• 24: BRUYNOOGHE, M., DE SCHREYE, D., AND MARTENS, B. 1992. A general criterion for avoiding infinite unfolding. New Gen. Comput. 11, 1, 47-79.
• 25: 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]
• 26: P. H. Cheong , Laurent Fribourg, A Survey of the Implementations of Narrowing, Seminar and Workshop on Declarative Programming, p.177-187, November 18-22, 1991
• 27: 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]
• 28: Charles Consel , Olivier Danvy, Static and dynamic semantics processing, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.14-24, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99588]
• 29: Charles Consel , Olivier Danvy, Tutorial notes on partial evaluation, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.493-501, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158707]
• 30: DARLINGTON, J. 1982. Program transformations. In Functional Programming and Its Applications, J. Darlington, P. Henderson, and D. A. Turner, Eds. Cambridge University Press, Cambridge, U.K., 193-215.
• 31: DARLINGTON, J. AND PULL, H. 1988. A program development methodology based on a unified approach to execution and transformation. In Proceedings of the International Workshop on Partial Evaluation and Mixed Computation, D. Bj0rner, A. Ershov, and N. Jones, Eds. North- Holland, Amsterdam, 117-131.
• 32: DERSHOWITZ, N. 1995. Goal solving as operational semantics. In Proceedings of the 1995 International Logic Programming Symposium, J. Lloyd, Ed. The MIT Press, Cambridge, MA, 3-17.
• 33: Nachum Dershowitz , Jean-Pierre Jouannaud, Rewrite systems, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• 34: DERSHOWITZ, N. AND JOUANNAUD, J.-P. 1991. Notations for rewriting. Bull. Euro. Assoc. Theor. Comp. Sci. 43, 162-172.
• 35: Nachum Dershowitz , Uday S. Reddy, Deductive and inductive synthesis of equational programs, Journal of Symbolic Computation, v.15 n.5-6, p.467-494, May/June 1993 [doi>10.1016/S0747-7171(06)80002-7]
• 36: Rachid Echahed, On Comleteness of Narrowing Strategies, Proceedings of the 13th Colloquium on Trees in Algebra and Programming, p.89-101, March 21-24, 1988
• 37: FERNANDEZ, M. 1992. Narrowing based procedures for equational disunification. Appl. Alg. Eng. Commun. Comput. 3, 1-26.
• 38: FRIBOURG, L. 1985. SLOG: A logic programming language interpreter based on clausal superposition and rewriting. In Proceedings of the 2nd IEEE International Symposium on Logic Programming. IEEE Press, New York, 172-185.
• 39: 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]
• 40: CJALLAGHER, J. AND BRUYNOOGHE, M. 1990. Some low-level source transformations for logic programs. In Proceedings of the 2nd Workshop on Meta-Programming in Logic, M. Bruynooghe, Ed. Department of Computer Science, KU Leuven, Belgium, 229-246.
• 41: Robert Glück , Andrei V. Klimov, Occam's Razor in Metacompuation: the Notion of a Perfect Process Tree, Proceedings of the Third International Workshop on Static Analysis, p.112-123, September 22-24, 1993
• 42: Robert Glück , Morten Heine Sørensen, Partial Deduction and Driving are Equivalent, Proceedings of the 6th International Symposium on Programming Language Implementation and Logic Programming, p.165-181, September 14-16, 1994
• 43: Robert Glück , Morten Heine Sørensen, A Roadmap to Metacomputation by Supercompilation, Selected Papers from the Internaltional Seminar on Partial Evaluation, p.137-160, February 12-16, 1996
• 44: Robert Glück , Jesper Jørgensen , Bern Martens , Morten Heine Sørensen, Controlling Conjunctive Partial Deduction, Proceedings of the 8th International Symposium on Programming Languages: Implementations, Logics, and Programs, p.152-166, September 24-27, 1996
• 45: Michael Hanus, Compiling Logic Programs with Equality, Proceedings of the 2nd International Workshop on Programming Language Implementation and Logic Programming, p.387-400, August 20-22, 1990
• 46: Michael Hanus, Efficient Implementation of Narrowing and Rewriting, Proceedings of the International Workshop on Processing Declarative Knowledge, p.344-365, July 01-03, 1991
• 47: Michael Hanus, Improving Control of Logic Programs by Using Functional Logic Languages, Proceedings of the 4th International Symposium on Programming Language Implementation and Logic Programming, p.1-23, August 26-28, 1992
• 48: Michael Hanus, Combining Lazy Narrowing and Simplification, Proceedings of the 6th International Symposium on Programming Language Implementation and Logic Programming, p.370-384, September 14-16, 1994
• 49: HANUS, M. 1994b. The integration of functions into logic programming: From theory to practice. J. Logic Program. 19~20, 583-628.
• 50: HANUS, M. 1995. On extra variables in (equational) logic programming. In Proceedings of the 20th International Conference on Logic Programming. The MIT Press, Cambridge, MA, 665-678.
• 51: HANUS, M., KUCHEN, H., AND MORENO-NAVARRO, J. 1995. Curry: A truly functional logic language. In Proceedings of the ILPS'95 Workshop on Visions for the Future of Logic Programming. 95-107.
• 52: HERMENEGILDO, M. AND ROSSI, F. 1989. On the correctness and efficiency of independent Andparallelism in logic programs. In Proceedings of the 1989 North American Conference on Logic Programming, E. Lusk and R. Overbeck, Eds. The MIT Press, Cambridge, MA, 369-389.
• 53: Steffen Hölldobler, Foundations of Equational Logic Programming, Springer-Verlag New York, Inc., New York, NY, 1989
• 54: Jean-Marie Hullot, Canonical Forms and Unification, Proceedings of the 5th Conference on Automated Deduction, p.318-334, July 08-11, 1980
• 55: Heinrich Hußmann, Unification in Conditional Equational Theories, Research Contributions from the European Conference on Computer Algebra-Volume 2, p.543-553, April 01-03, 1985
• 56: J. Jaffar , J.-L. Lassez, Constraint logic programming, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.111-119, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41635]
• 57: JONES, N. 1994. The essence of program transformation by partial evaluation and driving. In Logic, Language and Computation, N. Jones, M. Hagiya, and M. Sato, Eds. Lecture Notes in Computer Science, vol. 792. Springer-Verlag, Berlin, 206-224.
• 58: Neil D. Jones , Carsten K. Gomard , Peter Sestoft, Partial evaluation and automatic program generation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 59: Jesper Jørgensen , Michael Leuschel , Bern Martens, Conjunctive Partial Deduction in Practice, Proceedings of the 6th International Workshop on Logic Programming Synthesis and Transformation, p.59-82, August 28-30, 1996
• 60: J. W. Klop, Term rewriting systems, Handbook of logic in computer science (vol. 2): background: computational structures, Oxford University Press, Inc., New York, NY, 1993
• 61: H. Jan Komorowski, Partial evaluation as a means for inferencing data structures in an applicative language: a theory and implementation in the case of prolog, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.255-267, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582181]
• 62: Laura Lafave , John P. Gallagher, Constraint-Based Partial Evaluation of Rewriting-Based Functional Logic Programs, Proceedings of the 7th International Workshop on Logic Programming Synthesis and Transformation, p.168-188, July 10-12, 1997
• 63: L. Lafave , J. P. Gallagher, Partial Evaluation of Functional Logic Programs in Rewriting-based Languages, University of Bristol, Bristol, UK, 1997
• 64: LAM, J. AND I~USALIK, t. 1991. A comparative analysis of partial deductors for pure Prolog. Tech. rep., Department of Computational Science, University of Saskatchewan, Canada. Revised April 1991.
• 65: J.-L. Lassez , M. J. Maher , K. Marriott, Unification revisited, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 66: LEUSCHEL, M. 1998. The ECCE partial deduction system and the DPPD library of benchmarks. Tech. rep., Accessible via http ://www. cs. kuleuven, ac. be/~ipai.
• 67: LEUSCHEL, M., DE SCHREYE, D., AND DE WAAL, A. 1996. A conceptual embedding of folding into partial deduction: Towards a maximal integration. In Proceedings of the Joint International Conference and Symposium on Logic Programming, JICSLP'96, M. Maher, Ed. The MIT Press, Cambridge, MA, 319-332.
• 68: Michael Leuschel , Bern Martens, Global Control for Partial Deduction through Characteristic Atoms and Global Trees, Selected Papers from the Internaltional Seminar on Partial Evaluation, p.263-283, February 12-16, 1996
• 69: Michael Leuschel , Bern Martens , Danny De Schreye, Controlling generalization and polyvariance in partial deduction of normal logic programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.1, p.208-258, Jan. 1998 [doi>10.1145/271510.271525]
• 70: LEVI, G. AND SIROVICH, F. 1975. Proving program properties, symbolic evaluation and logical procedural semantics. In Proceedings of the ~th International Symposium on Mathematical Foundations of Computer Science, MFCS'75. Lecture Notes in Computer Science, vol. 32. Springer-Verlag, Berlin, 294-301.
• 71: 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 ]
• 72: MARTENS, B. AND GALLAGHER, J. 1995. Ensuring global termination of partial deduction while allowing flexible polyvariance. In Proceedings of the 12th International Conference on Logic Programming, L. Sterling, Ed. The MIT Press, Cambridge, MA, 597-611.
• 73: MIDDELDORP, A. AND HAMOEN, E. 1994. Completeness results for basic narrowing. Appl. Alg. Eng. Commun. Comput. 5, 213-253.
• 74: Aart Middeldorp , Satoshi Okui , Tetsuo Ida, Lazy narrowing: strong completeness and eager variable elimination, Theoretical Computer Science, v.167 n.1-2, p.95-130, Oct. 30, 1996
• 75: Alain Miniussi , David Sherman, Squeezing Intermediate Construction in Equational Programs, Selected Papers from the Internaltional Seminar on Partial Evaluation, p.284-302, February 12-16, 1996
• 76: 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 ]
• 77: Werner Nutt , Pierre Réty , Gert Smolka, Basic narrowing revisited, Journal of Symbolic Computation, v.7 n.3-4, p.295-317, March/April 1989 [doi>10.1016/S0747-7171(89)80014-8]
• 78: Peter Padawitz, Computing in Horn clause theories, Springer-Verlag New York, Inc., New York, NY, 1988
• 79: Catuscia Palamidessi, Algebraic properties of idempotent substitutions, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.386-399, July 1990, Warwick University, England
• 80: PETTOROSSI, t. AND PROIETTI, M. 1994. Transformation of logic programs: Foundations and techniques. J. Logic Program. 19,20, 261-320.
• 81: Alberto Pettorossi , Maurizio Proietti, A Comparative Revisitation of Some Program Transformation Techniques, Selected Papers from the Internaltional Seminar on Partial Evaluation, p.355-385, February 12-16, 1996
• 82: María José Ramírez , Moreno Falaschi, Conditional Narrowing with Constructive Negation, Proceedings of the Third International Workshop on Extensions of Logic Programming, p.59-79, February 26-28, 1992
• 83: REDDY, U. 1985. Narrowing as the operational semantics of functional languages. In Proceedings of 2nd IEEE International Symposium on Logic Programming. IEEE Press, New York, 138-151.
• 84: P. Réty, Improving basic narrowing techniques, on Rewriting techniques and applications, p.228-241, May 1987, Bordeaux, France
• 85: Alexander Romanenko, Inversion and metacomputation, Proceedings of the 1991 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.12-22, June 17-19, 1991, New Haven, Connecticut, United States
• 86: David Sands, Higher-order expression procedures, Proceedings of the 1995 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.178-189, June 21-23, 1995, La Jolla, California, United States [doi>10.1145/215465.215587]
• 87: 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]
• 88: James R. Slagle, Automated Theorem-Proving for Theories with Simplifiers Commutativity, and Associativity, Journal of the ACM (JACM), v.21 n.4, p.622-642, Oct. 1974 [doi>10.1145/321850.321859]
• 89: SORENSEN, M. 1994. Turchin's supercompiler revisited: An operational theory of positive information propagation. Tech. Rep. 94//7, Master's Thesis, DIKU, University of Copenhagen, Denmark.
• 90: SORENSEN, M. AND GLUCK, R. 1995. An algorithm of generalization in positive supercompilation. In Proceedings of the 1995 International Logic Programming Symposium, J. Lloyd, Ed. The MIT Press, Cambridge, MA, 465-479.
• 91: Morten Heine Sørensen , Robert Glück , Neil D. Jones, Towards Unifying Partial Evaluation, Deforestation, Supercompilation, and GPC, Proceedings of the 5th European Symposium on Programming: Programming Languages and Systems, p.485-500, April 11-13, 1994
• 92: SORENSEN, M., GL/JCK, R., AND JONES, N. 1996. A positive supercompiler. J. Fttnct. Program. 6, 6, 811-838.
• 93: Taro Suzuki , Aart Middeldorp , Tetsuo Ida, Level-Confluence of Conditional Rewrite Systems with Extra Variables in Right-Hand Sides, Proceedings of the 6th International Conference on Rewriting Techniques and Applications, p.179-193, April 05-07, 1995
• 94: Valentin F. Turchin, The concept of a supercompiler, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.3, p.292-325, July 1986 [doi>10.1145/5956.5957]
• 95: TURCHIN, V. 1988. The algorithm of generalization in the supercompiler. In Proceedings of the International Workshop on Partial Evaluation and Mixed Computation, D. Bjorner, A. Ershov, and N. Jones, Eds. North-Holland, Amsterdam, 531-549.
• 96: Valentin F. Turchin, Metacomputation: Metasystem Transitions plus Supercompilation, Selected Papers from the Internaltional Seminar on Partial Evaluation, p.481-509, February 12-16, 1996
• 97: VIDAL, G. 1996. Semantics-based analysis and transformation of functional logic programs. Ph.D. thesis, DSIC, Universidad Polit6cnica de Valencia, Spain. In spanish.
• 98: Philip Wadler, Deforestation: transforming programs to eliminate trees, Theoretical Computer Science, v.73 n.2, p.231-248, June 22, 1990

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.3 PROGRAMMING LANGUAGES

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program transformation

General Terms:
Languages, Performance, Theory

Keywords:
conditional term-rewriting systems, integration of functional and logic programming, narrowing strategies, partial evaluation