Abstract
Lambda lifting is a technique for transforming a functional program with local function definitions, possibly with free variables in the function definitions, into a program consisting only of global function (combinator) definitions which will be used as rewrite rules. Different ways of doing lambda lifting are presented, as well as reasons for rejecting or selecting the method used in our Lazy ML compiler. A functional program implementing the chosen algorithm is given.
uucp: ..!mcvax!enea!chalmers!johnsson
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The design and Analysis of Algorithms, Addison-Wesley, Reading, Mass. (1976).
L. Augustsson, "A Compiler for Lazy ML", pp. 218–227 in Proceedings of the 1984 ACM Symposium on Lisp and Functional Programming, Austin (August 1984).
L. Augustsson, "Compiling Pattern Matching" in Proceedings 1985 Conference on Functional Programming Languages and Computer Architecture, Nancy, France (September 1985).
R. S. Bird, "Using Circular Programs to Eliminate Multiple Traverals of Data", Acta Informatica, Vol. 21, pp. 239–250 (1984).
J. Hughes, "Super Combinators — A New Implementation Method for Applicative Languages", pp. 1–10 in Proceedings of the 1982 ACM Symposium on Lisp and Functional Programming, Pittsburgh (1982).
T. Johnsson, "Efficient Compilation of Lazy Evaluation", pp. 58–69 in Proceedings of the SIGPLAN '84 Symposium on Compiler Construction, Montreal (June 1984).
P. J. Landin, "The Next 700 Programming Languages", Communications of the ACM, Vol. 9 no. 3, pp. 157–164 (March 1966).
D. A. Turner, "A New Implementation Technique for Applicative Languages", Software — Practice and Experience, Vol. 9, pp. 31–49 (1979).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1985 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Johnsson, T. (1985). Lambda lifting: Transforming programs to recursive equations. In: Jouannaud, JP. (eds) Functional Programming Languages and Computer Architecture. FPCA 1985. Lecture Notes in Computer Science, vol 201. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-15975-4_37
Download citation
DOI: https://doi.org/10.1007/3-540-15975-4_37
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-15975-9
Online ISBN: 978-3-540-39677-2
eBook Packages: Springer Book Archive