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)
Nearby terms:
full outer join « fully associative cache « Fully
Automated Compiling Technique « fully lazy lambda
lifting » fully qualified domain name » fum »
Fun
|
