# Lambda lifting

### From HaskellWiki

(Difference between revisions)

m |
(Fix unfortunate line break.) |
||

(2 intermediate revisions by one user not shown) | |||

Line 1: | Line 1: | ||

− | Turning free variables into arguments. |
+ | Turning [[free variable]]s into arguments. |

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

<haskell> |
<haskell> |
||

− | isqrt :: Integer -> Integer |
+ | isqrt :: Integer -> Integer |

− | isqrt n |
+ | isqrt n |

| n < 0 = error "isqrt" |
| n < 0 = error "isqrt" |
||

| otherwise = isqrt' ((n+1) `div` 2) |
| otherwise = isqrt' ((n+1) `div` 2) |
||

Line 14: | Line 14: | ||

</haskell> |
</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? |
+ | 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: |
The solution is to promote <hask>n</hask> to be an argument of <hask>isqrt'</hask>. The refactored code might look like this: |
||

<haskell> |
<haskell> |
||

− | isqrt :: Integer -> Integer |
+ | isqrt :: Integer -> Integer |

− | isqrt n |
+ | isqrt n |

| n < 0 = error "isqrt" |
| n < 0 = error "isqrt" |
||

| otherwise = isqrt' n ((n+1) `div` 2) |
| otherwise = isqrt' n ((n+1) `div` 2) |
||

Line 31: | Line 31: | ||

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

− | Note that naive lambda lifting can cause a program to be less lazy. Consider, for example: |
+ | Naive lambda lifting can cause a program to be less lazy. Consider, for example: |

<haskell> |
<haskell> |
||

Line 55: | Line 55: | ||

</haskell> |
</haskell> |
||

− | An expression of this sort which only mentions [[Free variable]]s is |
+ | 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: |

− | 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> |
<haskell> |
||

Line 65: | Line 65: | ||

However, you save no more work here than the second version, and in |
However, you save no more work here than the second version, and in |
||

addition, the resulting function is harder to read. In general, it |
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 |
+ | only makes sense to abstract out a [[free expression]] if it is also a |

− | [[Reducible expression]]. |
+ | [[reducible expression]]. |

− | This converse of lambda lifting is [[Lambda dropping]], also known as |
+ | This converse of lambda lifting is [[lambda dropping]], also known as |

− | avoiding parameter passing. |
+ | [[avoiding parameter passing]]. |

− | |||

− | -- [[User:AndrewBromage]] |
||

[[Category:Refactoring]] |
[[Category:Refactoring]] |

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