# Lambda lifting

### From HaskellWiki

(Difference between revisions)

BrettGiles (Talk | contribs) (Converting HaWiki) |
(Fix unfortunate line break.) |

(3 intermediate revisions by 2 users not shown) |

## Latest revision as of 19:08, 19 January 2011

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)

isqrt'

isqrt'

n

n

isqrt'

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

g

f x y = g y x + g y (2*x) where g y x = sqrt y + x

sqrt y

y

sqrt y

f x y = let sy = sqrt y in g sy x + g sy (2*x) where g sy x = sy + x

sqrt y

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.