Personal tools

Lambda lifting

From HaskellWiki

Revision as of 06:20, 20 July 2010 by AndrewBromage (Talk | contribs)
Jump to: navigation, search

Turning free variables into arguments.

As an example, consider the following worker wrapper function, which computes the truncated square root of an integer: 

isqrt :: Integer -> Integer
isqrt n
   | n < 0     = error "isqrt"
   | otherwise = isqrt' ((n+1) `div` 2)
   where
     isqrt' s
         | s*s <= n && n < (s+1)*(s+1) = s
         | otherwise                   = isqrt' ((s + (n `div` s)) `div` 2)
Suppose that you find that the worker function,
isqrt'
, might be useful somewhere else (say, in a context where a better initial estimate is known). You would like to use the lifting pattern to raise it to the top level. However,
isqrt'
contains a free variable,
n
, which is bound in the outer function. What to do? The solution is to promote
n
to be an argument of
isqrt'
. The refactored code might look like this: 
isqrt :: Integer -> Integer
isqrt n
   | n < 0     = error "isqrt"
   | otherwise = isqrt' n ((n+1) `div` 2)
   where
     isqrt' n s
         | s*s <= n && n < (s+1)*(s+1) = s
         | otherwise                   = isqrt' n ((s + (n `div` s)) `div` 2)

The isqrt' function may now be safely lifted to the top-level.

Naive lambda lifting can cause a program to be less lazy. Consider, for example: 

f x y = g x + g (2*x)
   where
     g x = sqrt y + x
If you want to lift the definition of
g
, you might be tempted to write: 
f x y = g y x + g y (2*x)
   where
     g y x = sqrt y + x
However, this would mean that
sqrt y
is evaluated twice, whereas in the first program, it would be evaluated only once. A more efficient approach is not to lift out the variable
y
, but rather the expression
sqrt y
: 
f x y = let sy = sqrt y in g sy x + g sy (2*x)
   where
     g sy x = sy + x

An expression of this sort which only mentions free variables is called a free expression. If a free expression is as large as it can be, it is called a maximal free expression, or MFE for short. Note that

sqrt y
is actually not technically maximal. Lifting out the MFE would give you: 
f x y = let psy = (+) (sqrt y) in g psy x + g psy (2*x)
   where
     g psy x = psy x

However, you save no more work here than the second version, and in addition, the resulting function is harder to read. In general, it only makes sense to abstract out a free expression if it is also a reducible expression.

This converse of lambda lifting is lambda dropping, also known as avoiding parameter passing.

Retrieved from "http://www.haskell.org/haskellwiki/Lambda_lifting"

Category: Refactoring