Abstract
We have recently defined a framework for Narrowing-driven Partial Evaluation (NPE) of functional logic programs. This method is as powerful as partial deduction of logic programs and positive supercompilation of functional programs. Although it is possible to treat complex terms containing primitive functions (e.g. conjunctions or equations) in the NPE framework, its basic control mechanisms do not allow for effective polygenetic specialization of these complex expressions. We introduce a sophisticated unfolding rule endowed with a dynamic narrowing strategy which permits flexible scheduling of the elements (in conjunctions) which are reduced during specialization. We also present a novel abstraction operator which extends some partitioning techniques defined in the framework of conjunctive partial deduction. We provide experimental results obtained from an implementation using the Indy system which demonstrate that the control refinements produce better specializations.
This work has been partially supported by CICYT TIC 95-0433-C03-03, by HCM project CONSOLE, and by Acción Integrada HA1997-0073.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
E. Albert, M. Alpuente, M. Falaschi, P. Julián, and G. Vidal. Improving Control in Functional Logic Program Specialization. Technical Report DSIC-II/2/97, UPV, 1998. Available from URL: http://www.dsic.upv.es/users/elp/papers.html.
E. Albert, M. Alpuente, M. Falaschi, and G. Vidal. Indy User’s Manual. Technical Report, available from http://www.dsic.upv.es/users/elp/papers.html.
M. Alpuente, M. Falaschi, P. Julián, 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.
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 Symp. on Programming, ESOP’96, pages 45–61. Springer LNCS 1058, 1996.
M. Alpuente, M. Falaschi, and G. Vidal. Partial Evaluation of Functional Logic Programs. ACM TOPLAS, 1998. To appear.
M. Alpuente, M. Falaschi, and G. Vidal. A Unifying View of Functional and Logic Program Specialization. ACM Computing Surveys, 1998. To appear.
R.M. Burstall and J. Darlington. A Transformation System for Developing Recursive Programs. Journal of the ACM, 24(1):44–67, 1977.
R. Caballero-Roldán, F.J. López-Fraguas, and J. Sánchez-Hernández. User’s manual for Toy. Technical Report SIP-5797, UCM, Madrid (Spain), April 1997.
N. Dershowitz and J.-P. Jouannaud. Rewrite Systems. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B: Formal Models and Semantics, pages 243–320. Elsevier, Amsterdam, 1990.
J. Gallagher. Tutorial on Specialisation of Logic Programs. In Proc. of PEPM’93, pages 88–98. ACM, New York, 1993.
E. Giovannetti, G. Levi, C. Moiso, and C. Palamidessi. Kernel Leaf: A Logic plus Functional Language. J. of Computer and System Sciences, 42:363–377, 1991.
R. Glück, J. Jørgensen, B. Martens, and M.H. Sørensen. Controlling Conjunctive Partial Deduction of Definite Logic Programs. In Proc. of PLILP’96, pages 152–166. Springer LNCS 1140, 1996.
R. Glück and M.H. Sørensen. A Roadmap to Metacomputation by Supercompilation. In Partial Evaluation, Int’l Seminar, Dagstuhl Castle, Germany, pages 137–160. Springer LNCS 1110, February 1996.
M. Hanus. The Integration of Functions into Logic Programming: From Theory to Practice. Journal of Logic Programming, 19&20:583–628, 1994.
M. Hanus, H. Kuchen, and J.J. Moreno-Navarro. Curry: A Truly Functional Logic Language. In Proc. ILPS’95 Workshop on Visions for the Future of Logic Programming, pages 95–107, 1995.
N.D. Jones, C.K. Gomard, and P. Sestoft. Partial Evaluation and Automatic Program Generation. Prentice-Hall, Englewood Cliffs, NJ, 1993.
J.W. Klop and A. Middeldorp. Sequentiality in Orthogonal Term Rewriting Systems. Journal of Symbolic Computation, pages 161–195, 1991.
J. Komorowski. An Introduction to Partial Deduction. In A. Pettorossi, editor, Meta-Programming in Logic, pages 49–69. Springer LNCS 649, 1992.
L. Lafave and J.P. Gallagher. Partial Evaluation of Functional Logic Programs in Rewriting-based Languages. Technical Report CSTR-97-001, Department of Computer Science, University of Bristol, Bristol, England, March 1997.
M. Leuschel. The ecce partial deduction system and the dppd library of benchmarks. Tech. Rep., accessible via http://www.cs.kuleuven.ac.be/~lpai, 1998.
M. Leuschel, D. De Schreye, and A. de Waal. A Conceptual Embedding of Folding into Partial Deduction: Towards a Maximal Integration. In M. Maher, editor, Proc. of JICSLP’96, pages 319–332. The MIT Press, Cambridge, MA, 1996.
J.W. Lloyd and J.C. Shepherdson. Partial Evaluation in Logic Programming. Journal of Logic Programming, 11:217–242, 1991.
R. Loogen, F. López-Fraguas, and M. Rodríguez-Artalejo. A Demand Driven Computation Strategy for Lazy Narrowing. In J. Penjam and M. Bruynooghe, editors, Proc. of PLILP’93, pages 184–200. Springer LNCS 714, 1993.
B. Martens and J. Gallagher. Ensuring Global Termination of Partial Deduction while Allowing Flexible Polyvariance. In L. Sterling, editor, Proc. of ICLP’95, pages 597–611. MIT Press, 1995.
J.J. Moreno-Navarro and M. Rodríguez-Artalejo. Logic programming with functions and predicates: the language Babel. J. Logic Program., 12(3):191–224, 1992.
P. Padawitz. Computing in Horn Clause Theories, volume 16 of EATCS Monographs on Theoretical Computer Science. Springer-Verlag, Berlin, 1988.
A. Pettorossi and M. Proietti. Rules and Strategies for Transforming Functional and Logic Programs. ACM Computing Surveys, 28(2):360–414, 1996.
M.H. Sørensen and R. Glück. An Algorithm of Generalization in Positive Supercompilation. In Proc. of ILPS’95, pages 465–479. The MIT Press, 1995.
M.H. Sørensen, R. Glück, and N.D. Jones. A Positive Supercompiler. Journal of Functional Programming, 6(6):811–838, 1996.
P.L. Wadler. Deforestation: Transforming programs to eliminate trees. Theoretical Computer Science, 73:231–248, 1990.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Albert, E., Alpuente, M., Falaschi, M., Julián, P., Vidal, G. (1998). Improving Control in Functional Logic Program Specialization. In: Levi, G. (eds) Static Analysis. SAS 1998. Lecture Notes in Computer Science, vol 1503. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-49727-7_16
Download citation
DOI: https://doi.org/10.1007/3-540-49727-7_16
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65014-0
Online ISBN: 978-3-540-49727-1
eBook Packages: Springer Book Archive