María Alpuente
Michael Hanus
Salvador Lucas
Germán Vidal
ABSTRACT
Functional logic languages combine the operational principles of the most important declarative programming paradigms, namely functional and logic programming. Inductively sequential programs admit the definition of optimal computation strategies and are the basis of several recent (lazy) functional logic languages. In this paper, we define a partial evaluator for inductively sequential functional logic programs. We prove strong correctness of this partial evaluator and show that the nice properties of inductively sequential programs carry over to the specialization process and the specialized programs. In particular, the structure of the programs is preserved by the specialization process. This is in contrast to other partial evaluation methods for functional logic programs which can destroy the original program structure. Finally, we present some experiments which highlight the practical advantages of our approach.
- 1.E. Albert, M. Alpuente, M. Falaschi, P. Julian, and G. Vidal. Improving Control in Functional Logic Program Specialization. In G. Levi, editor, Proc. of Static Analysis Symposium, SAS'98, pages 262-277. Springer LNCS 1503, 1998.]]Google Scholar
- 2.E. Albert, M. Alpuente, M. Falaschi, and G. Vidal. INDY User's Manual. Technical Report DSIC-II/12/98, UPV, 1998. Available from URL: http://www, dsic. upv. es/users/elp/papers, html.]]Google Scholar
- 3.M. Alpuente, M. Falaschi, P. Julian, and G. Vidal. Specialization of Lazy Functional Logic Programs. In Proc. of PEPM'97, volume 32, 12 of Sigplan Notices, pages 151-162, New York, 1997. ACM Press.]] Google ScholarDigital Library
- 4.M. Alpuente, M. Falaschi, and G. Vidal. Narrowing-driven Partial Evaluation of Functional Logic Programs. in H. Riis Nielson, editor, Proc. of the 6th European Syrup. on Programming, ESOP'96, pages 45-61. Springer LNCS 1058, 1996.]] Google ScholarDigital Library
- 5.M. Alpuente, M. Falaschi, and G. Vidal. Partial Evaluation of Functional Logic Programs. A CM Transactions on Programming Languages and Systems, 20(4):768-844, 1998.]] Google ScholarDigital Library
- 6.M. Alpuente, M. Falaschi, and G. Vidal. A Unifying View of Functional and Logic Program Specialization. A CM Computing Surveys, 30(3es):9es, 1998.]] Google ScholarDigital Library
- 7.M. Alpuente, M. Hauus, S. Lucas, and G. Vidal. Specialization of Functional Logic Programs Based on Needed Narrowing. Technical report 99-4, RWTH Aachen, 1999. Available from ~tp. informaVik, r~rth-aachen, de/pub/report s/.]]Google Scholar
- 8.S. Antoy. Definitional trees. In Proc. of the $rd ~nt'l Conference on Algebraic and Logic Programming, ALP'92, pages 143-157. Springer LNCS 632, 1992.]] Google ScholarDigital Library
- 9.S. Antoy, R. Echahed, and M. Hanus. A Needed Narrowing Strategy. In Proc. 21st A CM Syrup. on Principles of Programming Languages, Portland, pages 268-279, 1994.]] Google ScholarDigital Library
- 10.S. Antoy, R. Echahed, and Ivi. Hanus. Parallel evaluation strategies for functional logic languages. In Proc. of the 1,~th Int'l Conf. on Logic Programming ({CLP'97), pages 138- 152. MIT Press, 1997.]]Google Scholar
- 11.F. Bander and T. Nipkow. Term Rewriting and All That. Cambridge University Press, 1998.]] Google ScholarDigital Library
- 12.F. BeIlegarde. ASTRE: Towards a fully automated program transformation system. In Jieh Hsiang, editor, Prom of RTA '95, pages 403--407. Springer LNCS 914, 1995.]] Google ScholarDigital Library
- 13.A. Bondorf. Towards a Self-Applicable Partial Evaluator for Term Rewriting Systems. In D. Bjorner, A.P. Ershov, and N.D. Jones, editors, Proc. of the Int'l Workshop on Partial Evaluation and Mixed Computation, pages 27-50. North-Holland, Amsterdam, 1988.]]Google Scholar
- 14.R.M. Burstall and J. Darlington. A Transformation System for Developing Recursive Programs. Journal of the A CM, 24(1):44-67, 1977.]] Google ScholarDigital Library
- 15.C. Consel and O. Danvy. Tutorial notes on Partial Evaluation. In Proc. of 20th Annual A CM Syrup. on Principles of Programming Languages, pages 493-501. ACM, New York, 1993.]] Google ScholarDigital Library
- 16.J. Daxlington. Program transformation. In J. Darlington, P. Henderson, and D. A. Turner, editors, Functional Programming and its Applications, pages 193-215. Cambridge University Press, 1982.]]Google Scholar
- 17.N. Dershowitz and J.-P. Jouannaud. Rewrite Systems. In J. van Leeuwen, editor, Handbook o/Theoretical Computer Science, volume B: Formal Models and Semantics, pages 243-320. Elsevier, Amsterdam, 1990.]] Google ScholarDigital Library
- 18.N. Dershowitz and U. Reddy. Deductive and Inductive Synthesis of Equational Programs. Journal o/Symbolic Computation, 15:467-494, 1993.]] Google ScholarDigital Library
- 19.I. Durand. Bounded, Strongly Sequential and Forward- Branching Term Rewriting Systems. Journal of Symbolic Computation, 18(4):319-352, 1994.]] Google ScholarDigital Library
- 20.A.J. Field and P.G. Harrison. Functional Programming. Addison-WesIey, Wokingham, 1988.]]Google Scholar
- 21.J. Gallagher. Tutorial on Specialisation of Logic Programs. In Proc. of PEPM~93, pages 88-98. ACM, New York, 1993.]] Google ScholarDigital Library
- 22.E. Giovannetti, G. Levi, C. Moiso, and C. Palamidessi. Kernel Leaf: A Logic plus Functional Language. Jou~mal of Computer and System Sciences, 42:363-377, 1991.]] Google ScholarDigital Library
- 23.R. Gliick and M.H. S0rensen. Partial Deduction and Driving are Equivalent. In Proc. of PLILP'9d, pages 165-181. Springer LNCS 844, 1994.]] Google ScholarDigital Library
- 24.R. Glfick and M.H. Sorensen. A Roadmap to Metacompuration by Supercompilation. In O. Danvy, R. Glfick, and P. Thiemann, editors, Partial Evaluation, Int'l Seminar, Da~stuhl Castle, Germany, pages 137-160. Springer LNCS 11t0, February 1996.]] Google ScholarDigital Library
- 25.M. Hanus. The Integration of Functions into Logic ProgrammJng: From Theory to Practice. Journal of Logic Programming, 19&20:583-628, 1994.]]Google Scholar
- 26.M. Hanus. Efficient translation of lazy functional logic programs into Prolog. In Proc. 5th Int'l Workshop on Logic Program Synthesis and Transformation, pages 252-266. Springer LNCS 1048, 1995.]] Google ScholarDigital Library
- 27.M. Hanus. A unified computation model for functional and logic programming. In Proc. of the 2~ th A CM Symposium on Principles of Programming Languages (Paris), pages 80-93. AOM, New York, 1997.]] Google ScholarDigital Library
- 28.M. Hanus, S. Lures, and A. Middeldorp. Strongly sequential and inductively sequential term rewriting systems. Infownation Processing Letters, 67(1):1-8, 1998.]] Google ScholarDigital Library
- 29.M. Hanus and C. Prehofer. Higher-Order Narrowing with Definitional Trees. Journal of Functional Programming, 9(1):33-75, 1999.]] Google ScholarDigital Library
- 30.M. Hanus (ed.). Curry: An Integrated Functional Logic Language. Version 0.5, Jan. 1999. Available at http://www-i2, informatik, rwth-aachen, de/~hanus/curry.]]Google Scholar
- 31.G. Huet and J.J. L6vy. Computations in orthogonal rewriting systems, Part I + II. In J.L. Lassez and G.D. Plotkin, editors, Computational Logic - Essays in Honor of Alan Robinson, pages 395-443, 1992.]]Google Scholar
- 32.J.M. Hullot. Canonical Forms and Unification. In Proc of 5th Int'l Conf. on Automated Deduction, pages 318-334. Springer LNCS 87, 1980.]] Google ScholarDigital Library
- 33.N.D. Jones, C.K. Gomaxd, and P. Sestoft. Partial Evaluation and Automatic Program Generation. Prentice-Hall, Englewood Cliffs, N J, 1993.]] Google ScholarDigital Library
- 34.J.W. Klop. Term Rewriting Systems. In S. Abramsky, D. Gabbay, and T. Maibaum, editors, Handbook of Logic in Computer Science, volume I, pages 1-112. Oxford University Press, 1992.]] Google ScholarDigital Library
- 35.H. Kuchen, R. Loogen, J.J. Moreno-Navarro, and M. Rodrigue~-Artalejo. Lazy Narrowing in a Graph Machine. In Proc. of ALP'90, pages 298-317. Springer LNCS 463, 1990.]] Google ScholarDigital Library
- 36.L. Lafave and J.P. Gallagher. Constraint-based Partial Evaluation of Rewriting-based Functional Logic Programs. In Proc. of LOPSTR'9?, pages 168-188. Springer LNCS 1463, 1997.]]Google Scholar
- 37.J. Lam and A. Kusalik. A Comparative Analysis of Partial Deductors for Pure Prolog. Technical report, Department of Computational Science, University of Saskatchewan, Canada, May 1991. Revised April 1991.]]Google Scholar
- 38.M. Leuschel. The ECCE partial deduction system and the DPPD library of benchmarks. Technical report, Accessible via http://~, cs. kuleuven, ac. be/~ lpai, i{998.]]Google Scholar
- 39.M. Leuschel, D. De Schreye, and A. de Ws~I. A Conceptual Embedding of Folding into Partial Deduction: Towards a Maximal Integration. In M. Maher, editor, Proc. of the Joint Int'l Conference and Syraposium on Logic Programrain~, JICSLP'96, pages 319-332. The MIT Press~ Cambridge, MA, 1996.]]Google Scholar
- 40.J.W. Lloyd and J.C. Shepherdson. Partial Evaluation in Logic Programming. Journal of Logic Programming, 11:217- 242, 1991.]] Google ScholarDigital Library
- 41.R. Loogen, F. LSpez-Fraguas, and M. Rodrlguez-Artalejo. A Demand Driven Computation Strategy for Lazy Narrowing. In J. Penjam and M. Bruynooghe, editors, Proc. of PLILP'93, Tallinn (Estonia), pages 184-200. Springer LNCS 714, 1993.]] Google ScholarDigital Library
- 42.A. M{niussi and D. J. Sherman. Squeezing Intermediate Construction in Equational Programs. In O. Danvy, R. Glfick, and P. Thiemann, editors, Partial Evaluation, Int'l Seminar, Da~stuhl Castle, Germany, pages 284-302. Springer LNCS 1110, February 1996.]] Google ScholarDigital Library
- 43.J.J. Moreno-Navarro and M. Rodrfguez-Artalejo. Logic Programming with Functions and Predicates; The language Babel. Journal of Logic Programming, 12(3):191-224, 1992.]] Google ScholarDigital Library
- 44.A. Pettorossi and M. Proietti. A Comparative Revisitation of Some Program Transformation Techniques. In O. Danvy, R. Gliick, and P. Thiemann, editors, Partial Evaluation, fnt'l Seminar, Dagstuhl Castle, Germany, pages 355-385. Springer LNCS 1110, 1996.]] Google ScholarDigital Library
- 45.S.L. Peyton Jones. The Implementation of Functional Programming Languages. Prentice-Hall, 1987.]] Google ScholarDigital Library
- 46.R. Plasmeijer and M. van Eekelen. Function.el Programming and Parallel Graph Rewriting. Addison Wesley, 1993.]] Google ScholarDigital Library
- 47.U.S. Reddy. Narrowing as the Operational Semantics of Functional Languages. In Proc. of Second LEEE Int'l Syrup. on Logic Programming, pages 138-151. IEEE, New York, 1985.]]Google Scholar
- 48.J.R. Slagle. Automated Theorem-Proving fi3r Theories with Simplifiers, Commutativity and Associativity. Journal of the ACM, 21(4):622-642, 1974.]] Google ScholarDigital Library
- 49.M.H. S0rensen, R. Gliick, and N.D. Jones. A Positive Supercompiler. Journal of Functional Programming, 6(6):811- 838, 1996.]]Google ScholarCross Ref
- 50.P.L. Wadler. Deforestation: Transforming programs to eliminate trees. Theoretical Corr~puter Science, 7'3:231-248, 1990.]] Google ScholarDigital Library
- 51.F. Zartmann. Denotational Abstract Interpretation of Functional Logic Programs. In P. Van Hentenryck, editor, Proc. of the 4th Int'l Static Analysis Symposium, SAS'97, pages 141-159. Springer LNCS 1302, 1997.]] Google ScholarDigital Library
Index Terms
- Specialization of inductively sequential functional logic programs
Recommendations
Specialization of inductively sequential functional logic programs
Functional logic languages combine the operational principles of the most important declarative programming paradigms, namely functional and logic programming. Inductively sequential programs admit the definition of optimal computation strategies and ...
Specialization of lazy functional logic programs
Partial evaluation is a method for program specialization based on fold/unfold transformations [8, 25]. Partial evaluation of pure functional programs uses mainly static values of given data to specialize the program [15, 44]. In logic programming, the ...
Specialization of lazy functional logic programs
PEPM '97: Proceedings of the 1997 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulationPartial evaluation is a method for program specialization based on fold/unfold transformations [8, 25]. Partial evaluation of pure functional programs uses mainly static values of given data to specialize the program [15, 44]. In logic programming, the ...
Comments