Translation

powered by

Computing (FOLDOC) dictionary

fully lazy lambda lifting

John Hughes's optimisation of lambda lifting to give fulllaziness. Maximal free expressions are shared to minimise

the amount of recalculation. Each inner sub-expression is

replaced by a function of its maximal free expressions

(expressions not containing any bound variable) applied to

those expressions. E.g.

f = x . ( y . (+) (sqrt x) y)

((+) (sqrt x)) is a maximal free expression in

( y . (+) (sqrt x) y) so this inner abstraction is replaced

with

( g . y . g y) ((+) (sqrt x))

Now, if a partial application of f is shared, the result of

evaluating (sqrt x) will also be shared rather than

re-evaluated on each application of f. As Chin notes, the

same benefit could be achieved without introducing the new

higher-order function, g, if we just extracted out (sqrt x).

This is similar to the code motion optimisation in

procedural languages where constant expressions are moved

outside a loop or procedure.