λ-lifting

λ-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.

Description

The transformation proceeds in two-steps:

Parameter lifting: Free variables are turned into parameters.
Block floating: Local functions become global functions.

As such, λ-lifting may be considered a technique for implementing a higher-order functional language.

Comparison to closures

This is a somewhat confusing topic. Please expand.

References

λ-lifting seems to have appeared in print for the first time in a SIGPLAN 1984 paper:

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).

The topic is covered in SPJ's classic textbook:

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}
}