# Difference between revisions of "Lambda lifting"

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

Line 1: | Line 1: | ||

− | Turning free |
+ | 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: |
||

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

## 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)
```

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.