λ-lifting (or lambda lifting) is a program transformation that transforms a higher-order functional program into a first-order functional program.
The notion of λ-lifting seems to be due to Thomas Johnsson [Johnsson 1984]. However, [Danvy and Schultz 2004] seem to credit it jointly to Augustsson, Hughes, Johnsson, and Peyton Jones in the mid 1980s.
The transformation proceeds in two-steps:
As such, λ-lifting may be considered a technique for implementing a higher-order functional language.
This is a somewhat confusing topic. Please expand.
Thomas Johnsson. 1984. Efficient compilation of lazy evaluation. In Proceedings of the 1984 SIGPLAN symposium on Compiler construction (SIGPLAN '84). Association for Computing Machinery, New York, NY, USA, 58–69. https://doi.org/10.1145/502874.502880
The same paper is also available as a SIGPLAN notice from the same year, but also as a SIGPLAN Notice from 2004 (???) (https://doi.org/10.1145/989393.989409).
Peyton Jones, Simon L. 1987. The Implementation of Functional Programming Languages. Prentice Hall International. pdf
@book{peyton_jones_1987,
title = {The implementation of functional programming languages},
url = {https://www.microsoft.com/en-us/research/publication/the-implementation-of-functional-programming-languages/},
publisher = {Prentice Hall International},
author = {Peyton Jones, Simon L.},
year = {1987}
}
There is a Wikipedia page.
In a paper at FLOPS 2002, Danvy and Schultz showed how λ-lifting can be performed in quadratic time (instead of cubic, as the naive algorithm suggests). This was then published in the Journal of Functional and Logic Programming in 2004:
Danvy, Olivier, and Ulrik P. Schultz. 2004. ‘Lambda-Lifting in Quadratic Time’. Journal of Functional and Logic Programming 2004 (1). [link]
@article{danvy_2004,
title = {Lambda-{Lifting} in {Quadratic} {Time}},
volume = {2004},
url = {http://danae.uni-muenster.de/lehre/kuchen/JFLP/articles/2004/A2004-01/A2004-01.html},
number = {1},
journal = {Journal of Functional and Logic Programming},
author = {Danvy, Olivier and Schultz, Ulrik P.},
year = {2004}
}