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.

(1994-12-01)