Hyper Dictionary

English Dictionary Computer Dictionary Thesaurus Dream Dictionary Medical Dictionary


Search Dictionary:  

Meaning of FULLY LAZY LAMBDA LIFTING

Computing Dictionary
 
 Definition: 

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.

 
 Websites: 
 

 

COPYRIGHT © 2000-2003 WEBNOX CORP. HOME | ABOUT HYPERDICTIONARY