×

The narrowing-driven approach to functional logic program specialization. (English) Zbl 1016.68024

Summary: Partial evaluation is a semantics-based program optimization technique which has been investigated within different programming paradigms and applied to a wide variety of languages. Recently, a partial evaluation framework for functional logic programs has been proposed. In this framework, narrowing – the standard operational semantics of integrated languages – is used to drive the partial evaluation process. This paper surveys the essentials of narrowing-driven partial evaluation.

MSC:

68N18 Functional programming and lambda calculus
68N15 Theory of programming languages
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abramov, Sergei; Glück, Robert, The Universal Resolving Algorithm: Inverse Computation in a Functional Language, 187-212 (2000), Berlin, Heidelberg · Zbl 0963.68500
[2] Albert, E., “<Emphasis Type=”Italic“>Partial Evaluation of Multi-Paradigm Declarative Languages: Foundations, Control, Algorithms and Efficiency,” Ph.D. thesis, DSIC, Universidad Politécnica de Valencia, 2001. Available from URL: http://www.dsic.upv.es/users/elp/papers.html.
[3] Albert, E.; Alpuente, M.; Falaschi, M.; Julián, P.; Vidal, G., Improving Control in Functional Logic Program Specialization, 262-277 (1998), Berlin, Heidelberg · Zbl 0911.68036 · doi:10.1007/3-540-49727-7_16
[4] Albert, E., Alpuente, M., Hanus, M. and Vidal, G., “A Partial Evaluation Framework for Curry Programs,” inProc. of the 6th Int’l Conf. on Logic Programming and Automated Reasoning (LPAR’99), Springer LNAI 1705, pp. 376-395, 1999.
[5] Albert, E., Antoy, S. and Vidal, G., “Measuring the Effectiveness of Partial Evaluation in Functional Logic Languages,” inProc. of the 10th Int’l Workshop on Logic-Based Program Synthesis and Transformation (LOPSTR’2000), Springer LNCS 2042, pp. 103-124, 2001. · Zbl 1018.68500
[6] Albert, E., Hanus, M. and Vidal, G., “Using an Abstract Representation to Specialize Functional Logic Programs,” inProc. of the 7th Int’l Conf. on Logic for Programming and Automated Reasoning (LPAR’2000), Springer LNAI 1955, pp. 381-398, 2000. · Zbl 0988.68516
[7] Albert, E., Hanus, M. and Vidal, G., “A Practical Partial Evaluator, for a Multi-Paradigm Declarative Language,” inProc. of the 4th Fuji Int’l Symp. on Functional and Logic Programming (FLOPS’2001), Springer LNCS 2024, pp. 326-342, 2001. · Zbl 0977.68593
[8] Alpuente, M., Falaschi, M., Julián, P. and Vidal, G., “Specialization of Lazy Functional Logic Programs,” inProc. of the ACM SIGPLAN Symp. on Partial Evaluation and Semantics-Based Program Manipulation (PEPM’97) Sigplan Notices, 32, 12, ACM Press, pp. 151-162, 1997. · doi:10.1145/258994.259015
[9] Alpuente, M., Falaschi, M. and Vidal, G., “Narrowing-driven Partial Evaluation of Functional Logic Programs,” inProc. of the 6th European Symposium on Programming (ESOP’96), Springer LNCS 1058, pp. 45-61, 1996.
[10] Alpuente, M., Falaschi, M. and Vidal, G., “Partial Evaluation of Functional Logic Programs,”ACM Transactions on Programming Languages and Systems, 20, 4, pp. 768-844, 1998. · doi:10.1145/291891.291896
[11] Alpuente M., Hanus M., Lucas S. and Vidal, G., “Specialization of Inductively Sequential Functional Logic Programs,” inProc. of the 4th ACM SIGPLAN Int’l Conf. on Functional Programming (ICFP’99), 34, 9 ofSigplan Notices, ACM Press, pp. 273-283, 1999. · Zbl 1345.68090 · doi:10.1145/317765.317910
[12] Antoy, S., “Definitional Trees,” inProc. of the 3rd Int’l Conf. on Algebraic and Logic Programming (ALP’92), Springer LNCS 632, pp. 143-157, 1992.
[13] Antoy, S., Echahed, R. and Hanus, M., “A Needed Narrowing Strategy,”Journal of the ACM, 47, 4, pp. 776-822, 2000. · Zbl 1327.68141 · doi:10.1145/347476.347484
[14] Baader, F. and Nipkow, T.,Term Rewriting and All That, Cambridge University Press, 1998. · Zbl 0948.68098
[15] Bol, R., “Loop Checking in Partial Deduction,”Journal of Logic Programming, 16, 1&2, pp. 25-46, 1993. · Zbl 0780.68012 · doi:10.1016/0743-1066(93)90022-9
[16] Bondorf, A., “A Self-Applicable Partial Evaluator for Term Rewriting Systems,” inProc. of the Int’l Joint Conf. on Theory and Practice of Software Development (TAP-SOFT’89), Springer LNCS 352, pp. 81-95, 1989.
[17] Bruynooghe, M., de Schreye, D. and Martens, B., “A General Criterion for Avoiding Infinite Unfolding,”New Generation Computing, 11, 1, pp. 47-79, 1992. · Zbl 0782.68024 · doi:10.1007/BF03037527
[18] Burstall, R. and Darlington, J., “A Transformation System for Developing Recursive Programs,”Journal of the ACM, 24, 1, pp. 44-67, 1977. · Zbl 0343.68014 · doi:10.1145/321992.321996
[19] Consel, C. and Danvy, O., “Tutorial Notes on Partial Evaluation,” inProc. of the 20th Annual ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages (POPL’93), ACM Press, pp. 493-501, 1993.
[20] Darlington, J. and Pull, H., “A Program Development Methodology Based on a Unified Approach to Execution and Transformation,” inProc. of the IFIP TC2 Workshop on Partial Evaluation and Mixed Computation, North-Holland, pp. 117-131, 1988.
[21] De Schreye, D., Glück, R., Jørgensen, J., Leuschel, M., Martens, B. and Sørensen, M., “Conjunctive Partial Deduction: Foundations, Control, Algorihtms, and Experiments,”Journal of Logic Programming, 41, 2&3, pp. 231-277, 1999. · Zbl 0944.68025 · doi:10.1016/S0743-1066(99)00030-8
[22] Etalle, S., Gabbrielli, M. and Marchiori, E., “A Transformation System for CLP with Dynamic Scheduling and CCP,” inProc. of the ACM SIGPLAN Symp. on Partial Evaluation and Semantics-Based Program Manipulation (PEPM’97), volume 32, 12 ofSigplan Notices, ACM Press, pp. 137-150, 1997.
[23] Fribourg, L., “SLOG: A Logic Programming Language Interpreter Based on Clausal Superposition and Rewriting,” inProc. of the 2nd IEEE Int’l Symp. on Logic Programming, IEEE Press, pp. 172-185, 1985.
[24] Futamura, Y., “Partial Evaluation of Computation Process—An Approach to a Compiler-Compiler,”Higher-Order and Symbolic Computation, 12, 4, pp. 381-391, 1999. Reprint of article inSystems, Computers, Controls 1971. · Zbl 1009.68504 · doi:10.1023/A:1010095604496
[25] Gallagher, J., “Tutorial on Specialisation of Logic Programs,” inProc. of the ACM SIGPLAN Symp. on Partial Evaluation and Semantics-Based Program Manipulation (PEPM’93), pp. 88-98, ACM Press, 1993.
[26] Giovannetti, E., Levi, G., Moiso, C. and Palamidessi, C., “Kernel Leaf: A Logic plus Functional Language,”Journal of Computer and System Sciences, 42, pp. 363-377, 1991. · Zbl 0717.68013 · doi:10.1016/0022-0000(91)90009-T
[27] Glück, R. and Klimov, A., “Occam’s Razor in Metacomputation: the Notion of a Perfect Process Tree,” inProc. of the 3rd Int’l Workshop on Static Analysis, Springer LNCS 724, pp. 112-123, 1993.
[28] Glück, R. and Sørensen, M., “Partial Deduction and Driving are Equivalent,” inProc. of the 6th Int’l Symp. on Programming Language Implementation and Logic Programming (PLILP’94), Springer LNCS 844, pp. 165-181, 1994.
[29] Hanus, M., “The Integration of Functions into Logic Programming: From Theory to Practice,”Journal of Logic Programming, 19&20, pp. 583-628, 1994. · Zbl 0942.68526 · doi:10.1016/0743-1066(94)90034-5
[30] Hanus, M., “A Unified Computation Model for Functional and Logic Programming,” inProc. of 24th ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages (POPL’97), ACM Press, pp. 80-93, 1997.
[31] Hanus, M., Antoy, S., Koj, J., Sadre, R. and Steiner, F., “PAKCS 1.2: The Portland Aachen Kiel Curry System User Manual,” Technical report, University of Kiel, Germany, 2000.
[32] Hanus, M. and Prehofer, C., “Higher-Order Narrowing with Definitional Trees,”Journal of Functional Programming, 9, 1, pp. 33-75, 1999. · Zbl 0926.68028 · doi:10.1017/S0956796899003330
[33] “‘Curry: An Integrated Functional Logic Language,” (Hanus, M., ed.) Available at http://www.informatik.uni-kiel.de/ curry/report.html, 2000.
[34] Hortalá-González, T. and Ullán, E., “An Abstract Machine Based System for a Lazy Narrowing Calculus,” inProc. of the 4th Fuji Int’l Symp. on Functional and Logic Programming (FLOPS’2001), pp. 216-232, Springer LNCS 2024, 2001. · Zbl 0987.68855
[35] Huet, G. and Lévy, J., “Computations in Orthogonal Rewriting Systems, Part I+II,”, inComputational Logic—Essays in Honor of Alan Robinson (J. Lassez and G. Plotkin, eds.), pp. 395-443, 1992.
[36] Hullot, Jean-Marie, Canonical forms and unification, 318-334 (1980), Berlin, Heidelberg · Zbl 0441.68108 · doi:10.1007/3-540-10009-1_25
[37] Jones, N., Sestoft, P. and Søndergaard, H., “Mix: A Self-Applicable Partial Evaluator for Experiments in Compiler Generation,”Lisp and Symbolic Computation, 2, 1, pp. 9-50, 1989. · doi:10.1007/BF01806312
[38] Julián-Iranzo, P.,Specialization of Lazy Functional Logic Programs, Ph.D. thesis, DSIC, Universidad Politécnica de Valencia May 2000. In Spanish. · Zbl 1159.68388
[39] Klop, J., “Term Rewriting Systems,” inHandbook of Logic in Computer Science (S. Abramsky, D. Gabbay, and T. Maibaum, eds.), I, Oxford University Press, pp. 1-112, 1992.
[40] Kruskal, J., “Well-quasi-ordering, the Tree Theorem, and Vazsonyi’s Conjecture,”Transactions of the American Mathematical Society, 95, pp. 210-225, 1960. · Zbl 0158.27002
[41] Lafave, L. and Gallagher, J., “Partial Evaluation of Functional Logic Programs in Rewriting-based Languages,” Technical Report CSTR-97-001, Department of Computer Science, University of Bristol, England, March 1997.
[42] Lassez, J. L.; Maher, M. J.; Marriott, K.; Minker, J. (ed.), Unification Revisited, 587-625 (1988), Los Altos, Ca. · Zbl 0645.68046 · doi:10.1016/B978-0-934613-40-8.50019-1
[43] Leuschel, M., “On the Power of Homeomorphic Embedding for Online Termination,” inProc. of the 5th Int’l Static Analysis Symposium (SAS’98), Springer LNCS 1503, pp. 230-245, 1998.
[44] Leuschel, M.; Schreye, D.; Waal, A., A Conceptual Embedding of Folding into Partial Deduction: Towards a Maximal Integration, 319-332 (1996), Cambridge, MA
[45] Leuschel, M., Martens, B. and de Schreye, D., “Controlling Generalization and Polyvariance in Partial Deduction of Normal Logic Programs”,ACM Transactions on Programming Languages and Systems, 20, 1, pp. 208-258., 1998. · doi:10.1145/271510.271525
[46] Lloyd, J. and Shepherdson, J., “Partial Evaluation in Logic Programming”,Journal of Logic Programming, 11, pp. 217-242, 1991. · Zbl 0741.68030 · doi:10.1016/0743-1066(91)90027-M
[47] Loogen, R., López-Fraguas, F. and Rodríguez-Artalejo, M., “A Demand Driven Computation Strategy for Lazy Narrowing”, inProc. of the 5th Int’l Symp. on Programming Language Implementation and Logic Programming (PLILP’93), Springer LNCS 714, pp. 184-200, 1993. · Zbl 0791.68021
[48] López Fraguas, F. J.; Sánchez Hernández, J., TOY: A Multiparadigm Declarative System, 244-247 (1999), Berlin, Heidelberg · doi:10.1007/3-540-48685-2_19
[49] Lux, Wolfgang; Kuchen, Herbert, An Efficient Abstract Machine for Curry, 390-399 (1999), Berlin, Heidelberg
[50] Martens, B. and Gallagher, J., “Ensuring Global Termination of Partial Deduction while Allowing Flexible Polyvariance,” inProc. of the 12th Int’l Conf. on Logic Programming (ICLP’95), The MIT Press, pp. 597-611, 1995.
[51] Moreno-Navarro, J. and Rodríguez-Artalejo, M., “Logic Programming with Functions and Predicates: The Language Babel,”Journal of Logic Programming, 12, 3, pp. 191-224, 1992. · Zbl 0754.68031 · doi:10.1016/0743-1066(92)90024-W
[52] Nemytykh, Andrei P.; Pinchuk, Victoria A.; Turchin, Valentin F., A Self-Applicable supercompiler, 322-337 (1996), Berlin, Heidelberg · doi:10.1007/3-540-61580-6_16
[53] Pettorossi, Alberto; Proietti, Maurizio, A comparative revisitation of some program transformation techniques, 355-385 (1996), Berlin, Heidelberg · doi:10.1007/3-540-61580-6_18
[54] Plasmeijer, R. and Eekelen, M.,Functional Programming and Parallel Graph Rewriting, Addison Wesley, 1993. · Zbl 0788.68023
[55] Reddy, U.S., “Narrowing as the Operational Semantics of Functional Languages,” inProc. of the 2nd IEEE Int’l Symp. on Logic Programmin, IEEE, New York, pp. 138-151, 1985.
[56] Slagle, J., “Automated Theorem-Proving for Theories with Simplifiers, Commutativity and Associativity,”Journal of the ACM, 21, 4, pp. 622-642, 1974. · Zbl 0296.68092 · doi:10.1145/321850.321859
[57] Sørensen, M., “Turchin’s Supercompiler Revisited: An Operational Theory of Positive Information Propagation,” Technical Report 94/7, Master’s Thesis, DIKU, University of Copenhagen, Denmark, 1994.
[58] Sørensen, M. and Glück, R., “An Algorithm of Generalization in Positive Supercompilation,” inProc. of the 1995 Int’l Logic Programming Symposium (ILPS’95), The MIT Press, pp. 465-479, 1995.
[59] Sørensen, M., Glück, R. and Jones, N., “A Positive Supercompiler,”Journal of Functional Programming, 6, 6, pp. 811-838, 1996. · Zbl 0870.68040 · doi:10.1017/S0956796800002008
[60] Turchin, V., “The Concept of a Supercompiler,”ACM Transactions on Programming Languages and Systems, 8, 3, pp. 292-325, July 1986. · Zbl 0598.68016 · doi:10.1145/5956.5957
[61] Vidal, G.,Semantics-Based Analysis and Transformation of Functional Logic Programs, Ph.D. thesis, DSIC, Universidad Politécnica de Valencia, Sept. 1996. In Spanish.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.