View source for Lambda lifting

Turning [[free variable]]s into arguments.

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

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

Suppose that you find that the worker function, <hask>isqrt'</hask>, 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, <hask>isqrt'</hask> contains a [[free variable]], <hask>n</hask>, which is bound in the outer function.  What to do?

The solution is to promote <hask>n</hask> to be an argument of <hask>isqrt'</hask>.  The refactored code might look like this:

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

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:

<haskell>
 f x y = g x + g (2*x)
   where
     g x = sqrt y + x
</haskell>

If you want to lift the definition of <hask>g</hask>, you might be tempted to write:

<haskell>
 f x y = g y x + g y (2*x)
   where
     g y x = sqrt y + x
</haskell>

However, this would mean that <hask>sqrt y</hask> 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 <hask>y</hask>, but rather the expression <hask>sqrt y</hask>:

<haskell>
 f x y = let sy = sqrt y in g sy x + g sy (2*x)
   where
     g sy x = sy + x
</haskell>

An expression of this sort which only mentions [[free variable]]s 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 <hask>sqrt y</hask> is actually not technically maximal.  Lifting out the MFE would give you:

<haskell>
 f x y = let psy = (+) (sqrt y) in g psy x + g psy (2*x)
   where
     g psy x = psy x
</haskell>

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]].

[[Category:Refactoring]]