fully lazy lambda lifting

fully lazy lambda lifting

John Hughes's optimisation of lambda lifting to give full laziness. Maximal free expressions are shared to minimisethe amount of recalculation. Each inner sub-expression isreplaced by a function of its maximal free expressions(expressions not containing any bound variable) applied tothose 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 replacedwith

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

Now, if a partial application of f is shared, the result ofevaluating (sqrt x) will also be shared rather thanre-evaluated on each application of f. As Chin notes, thesame benefit could be achieved without introducing the newhigher-order function, g, if we just extracted out (sqrt x).

This is similar to the code motion optimisation inprocedural languages where constant expressions are movedoutside a loop or procedure.