lambda lifting

You are here: irt.org | FOLDOC | lambda lifting

A program transformation to remove free variables. An expression containing a free variable is replaced by a function applied to that variable. E.g.

	f x = g 3  where g y = y + x

x is a free variable of g so it is added as an extra argument:

	f x = g 3 x  where g y x = y + x

Functions like this with no free variables are known as supercombinators and are traditionally given upper-case names beginning with "$". This transformation tends to produce many supercombinators of the form f x = g x which can be eliminated by eta reduction and substitution. Changing the order of the parameters may also allow more optimisations. References to global (top-level) constants and functions are not transformed to function parameters though they are technically free variables.

A closely related technique is closure conversion. See also Full laziness.

Nearby terms: lambda abstraction « lambda-calculus « lambda expression « lambda lifting » LambdaMOO » Lambda Prolog » lamer

FOLDOC, Topics, A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, ?, ALL