×

zbMATH — the first resource for mathematics

Preserving sharing in the partial evaluation of lazy functional programs. (English) Zbl 1179.68036
King, Andy (ed.), Logic-based program synthesis and transformation. 17th international symposium, LOPSTR 2007, Kongens Lyngby, Denmark, August 23–24, 2007. Revised selected papers. Berlin: Springer (ISBN 978-3-540-78768-6/pbk). Lecture Notes in Computer Science 4915, 74-89 (2008).
Summary: The goal of partial evaluation is the specialization of programs w.r.t. part of their input data. Although this technique is already well-known in the context of functional languages, current approaches are either overly restrictive or destroy sharing through the specialization process, which is unacceptable from a performance point of view. In this work, we present the basis of a new partial evaluation scheme for first-order lazy functional programs that preserves sharing through the specialization process and still allows the unfolding of arbitrary function calls.
For the entire collection see [Zbl 1154.68018].
MSC:
68N30 Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.)
68N18 Functional programming and lambda calculus
Software:
GHC; Haskell; LOGEN
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Albert, E., Hanus, M., Huch, F., Oliver, J., Vidal, G.: Operational Semantics for Declarative Multi-Paradigm Languages. Journal of Symbolic Computation 40(1), 795–829 (2005) · Zbl 1129.68042 · doi:10.1016/j.jsc.2004.01.001
[2] Albert, E., Hanus, M., Vidal, G.: A Practical Partial Evaluation Scheme for Multi-Paradigm Declarative Languages. Journal of Functional and Logic Programming 2002(1) (2002) · Zbl 1037.68011
[3] Albert, E., Hanus, M., Vidal, G.: A Residualizing Semantics for the Partial Evaluation of Functional Logic Programs. Information Processing Letters 85(1), 19–25 (2003) · Zbl 1042.68023 · doi:10.1016/S0020-0190(02)00336-8
[4] Alpuente, M., Falaschi, M., Julián, P., Vidal, G.: Specialization of Lazy Functional Logic Programs. In: Proc. of the ACM SIGPLAN Conf. on Partial Evaluation and Semantics-Based Program Manipulation, PEPM 1997, vol. 32, pp. 151–162. ACM Press, New York (1997)
[5] Andersen, L.O.: Program Analysis and Specialization for the C Programming Language. PhD thesis, DIKU, University of Copenhagen (1994)
[6] Arroyo, G., Ramos, J.G., Silva, J., Vidal, G.: Improving Offline Narrowing-Driven Partial Evaluation using Size-Change Graphs. In: Puebla, G. (ed.) LOPSTR 2006. LNCS, vol. 4407, pp. 60–76. Springer, Heidelberg (2007) · Zbl 1196.68037 · doi:10.1007/978-3-540-71410-1_6
[7] Barendregt, H.P.: The Lambda Calculus–Its Syntax and Semantics. Elsevier, Amsterdam (1984) · Zbl 0551.03007
[8] Bondorf, A.: Similix 5.0 Manual (1993)
[9] Bondorf, A., Jørgensen, J.: Efficient Analyses for Realistic Off-Line Partial Evaluation. Journal of Functional Programming 3(3), 315–346 (1993) · doi:10.1017/S0956796800000769
[10] Consel, C., Danvy, O.: Tutorial notes on Partial Evaluation. In: Proc. of the ACM Symp. on Principles of Programming Languages, pp. 493–501. ACM, New York (1993)
[11] Glenstrup, A.J., Jones, N.D.: Termination analysis and specialization-point insertion in offline partial evaluation. ACM TOPLAS 27(6), 1147–1215 (2005) · Zbl 05459265 · doi:10.1145/1108970.1108973
[12] Jones, N.D., Gomard, C.K., Sestoft, P.: Partial Evaluation and Automatic Program Generation. Prentice-Hall, Englewood Cliffs, NJ (1993) · Zbl 0875.68290
[13] Launchbury, J.: A Natural Semantics for Lazy Evaluation. In: Proc. of the ACM Symp. on Principles of Programming Languages (POPL 1993), pp. 144–154. ACM Press, New York (1993)
[14] Leuschel, M., Elphick, D., Varea, M., Craig, S., Fontaine, M.: The Ecce and Logen Partial Evaluators and Their Web Interfaces. In: Proc. of PEPM 2006, pp. 88–94. IBM Press (2006) · doi:10.1145/1111542.1111557
[15] Peyton-Jones, S. (ed.): Haskell 98 Language and Libraries–The Revised Report. Cambridge University Press, Cambridge (2003) · Zbl 1067.68041
[16] Peyton Jones, S.L., Marlow, S.: Secrets of the Glasgow Haskell Compiler Inliner. Journal of Functional Programming 12(4&5), 393–433 (2002) · Zbl 1037.68042
[17] Ramos, J.G., Silva, J., Vidal, G.: Fast Narrowing-Driven Partial Evaluation for Inductively Sequential Systems. In: Proc. of the 10th ACM SIGPLAN Int’l Conf. on Functional Programming (ICFP 2005), pp. 228–239. ACM Press, New York (2005) · Zbl 1302.68067
[18] Wadler, P.L.: Deforestation: Transforming programs to eliminate trees. Theoretical Computer Science 73, 231–248 (1990) · Zbl 0701.68013 · doi:10.1016/0304-3975(90)90147-A
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.