Fully lazy lambda lifting
John Hughes's optimisation of
lambda lifting to give
full laziness.
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.
