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 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)