Abstract
Source-program modifications can make a partial evaluator yield dramatically better results. For example, eta-redexes can preserve static data flow by acting as an interface between values and contexts. This note presents a type-based explanation of what eta-expansion achieves, why it works, and how it can be automated. This leads to a unified view of various source-code improvements, including a popular transformation called “The Trick.”
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
Henk P. Barendregt. The Lambda Calculus: Its Syntax and Semantics. North-Holland, 1984.
U. Berger and H. Schwichtenberg. An inverse of the evaluation functional for typed λ-calculus. In LICS’91, Sixth Annual Symposium on Logic in Computer Science, pages 203–211, 1991.
Anders Bondorf. Automatic autoprojection of higher order recursive equations. Science of Computer Programming, 17(1–3):3–34, December 1991.
Anders Bondorf and Dirk Dussart. Improving CPS-based partial evaluation: Writing cogen by hand. In Proc. ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation, pages 1–10, 1994.
Anders Bondorf and Jens Palsberg. Generating action compilers by partial evaluation. Journal of Functional Programming, 6(2):269–298, 1996. Preliminary version in Proc. FPCA’93, Sixth ACM Conference on Functional Programming Languages and Computer Architecture, pages 308–317, Copenhagen, Denmark, June 1993.
Charles Consel and Olivier Danvy. Tutorial notes on partial evaluation. In Proc. POPL’93, Twentieth Annual SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 493–501, 1993.
Olivier Danvy. Type-directed partial evaluation. In Proc. POPL’96, 23nd Annual SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 242–257, 1996.
Olivier Danvy and Andrzej Filinski. Representing control, a study of the CPS transformation. Mathematical Structures in Computer Science, 2(4):361–391, 1992.
Olivier Danvy, Karoline Malmkjær, and Jens Palsberg. The essence of eta-expansion in partial evaluation. Lisp and Symbolic Computation, 8(3):209–227, 1995. Preliminary version in Proc. PEPM’94, ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation, pages 11–20, Orlando, Florida, June 1994.
Olivier Danvy, Karoline Malmkjær, and Jens Palsberg. Eta-expansion does the trick. ACM Transactions on Programming Languages and Systems, 18(6):730–751, November 1996.
Carsten K. Gomard. Program Analysis Matters. PhD thesis, DIKU, University of Copenhagen, November 1991. DIKU Report 91-17.
Nevin Heintze. Set Based Program Analysis. PhD thesis, Carnegie Mellon University, October 1992. CMU-CS-92-201.
Neil D. Jones. Automatic program specialization: A re-examination from basic principles. In Proc. Partial Evaluation and Mixed Computation, pages 225–282, 1988.
Neil D. Jones, Carsten K. Gomard, and Peter Sestoft. Partial Evaluation and Automatic Program Generation. Prentice-Hall International, 1993.
Guy L. Steele Jr. Rabbit: A compiler for Scheme. Technical Report AI-TR-474, Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, Massachusetts, May 1978.
Y. Minamide, G. Morrisett, and R. Harper. Typed closure conversion. In Proc. POPL’96, 23nd Annual SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 271–283, 1996.
Torben Æ Mogensen. Constructor specialization. In Proc. PEPM’93, Second ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation, pages 22–32, 1993.
Christian Mossin. Partial evaluation of general parsers. In Proc. PEPM’93, Second ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation, pages 13–21, 1993.
Flemming Nielson and Hanne Riis Nielson. Two-Level Functional Languages. Cambridge University Press, 1992.
Jens Palsberg. Correctness of binding-time analysis. Journal of Functional Programming, 3(3):347–363, 1993.
Gordon D. Plotkin. Call-by-name, call-by-value and the λ-calculus. Theoretical Computer Science, 1:125–159, 1975.
John C. Reynolds. Definitional interpreters for higher-order programming languages. In Proc. 25th ACM National Conference, pages 717–740. ACM Press, 1972.
Peter Sestoft. Replacing function parameters by global variables. In Proc. Conference on Functional Programming Languages and Computer Architecture, pages 39–53, 1989.
Olin Shivers. Control-Flow Analysis of Higher-Order Languages. PhD thesis, CMU, May 1991. CMU-CS-91-145.
Mitchell Wand. Specifying the correctness of binding-time analysis. Journal of Functional Programming, 3(3):365–387, 1993.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Palsberg, J. (1999). Eta-Redexes in Partial Evaluation. In: Hatcliff, J., Mogensen, T.Æ., Thiemann, P. (eds) Partial Evaluation. DIKU 1998. Lecture Notes in Computer Science, vol 1706. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-47018-2_15
Download citation
DOI: https://doi.org/10.1007/3-540-47018-2_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66710-0
Online ISBN: 978-3-540-47018-2
eBook Packages: Springer Book Archive