Closure Conversion

Closure conversion is a program transformation that transforms higher-order functional programs to first-order functional programs.

The transformation works by replacing free variables in a local function definition by references to an environment, i.e. a data structure that contains the values of the free variables.

While the concept of closure was pioneered by Peter Landin, the jury is still out on the origin of closure conversion. The approach goes back at least to 1978 and the Lambda papers on Scheme. See e.g. Minamide et al. 1996 for a few more references.

Typing

In a paper at POPL 1996 Minamide, Morrisett, and Harper showed that one way of performing type-safe closure conversion for simply-typed languages makes use of existential types in the target language in order to give a type to the environment.

References

An approach to type-directed type-safe closure conversion is given in

Minamide, Yasuhiko, Greg Morrisett, and Robert Harper. 1996. ‘Typed Closure Conversion’. In Proceedings of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 271–83. New York, NY, USA: Association for Computing Machinery. https://doi.org/10.1145/237721.237791. extended version

@inproceedings{minamide_1996,
	address = {New York, NY, USA},
	title = {Typed {Closure} {Conversion}},
	doi = {10.1145/237721.237791},
	booktitle = {Proceedings of the 23rd {ACM} {SIGPLAN}-{SIGACT} {Symposium} on {Principles} of {Programming} {Languages}},
	publisher = {Association for Computing Machinery},
	author = {Minamide, Yasuhiko and Morrisett, Greg and Harper, Robert},
	year = {1996},
	pages = {271--283}
}