Difference between revisions of "Lambda lifting"
(Fixing link) 
m 

Line 1:  Line 1:  
Turning free variables into arguments. 
Turning free variables into arguments. 

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

−  +  isqrt :: Integer > Integer 

−  +  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 [[ 
+  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 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 toplevel. 
The isqrt' function may now be safely lifted to the toplevel. 

−  +  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 [[ 
+  An expression of this sort which only mentions [[free variable]]s is 
−  called a [[ 
+  called a [[free expression]]. If a free expression is as large as it can 
−  be, it is called a [[ 
+  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: 
<hask>sqrt y</hask> is actually not technically maximal. Lifting out the MFE would give you: 

Line 68:  Line 68:  
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 [[ 
+  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 
This converse of lambda lifting is [[lambda dropping]], also known as 
Revision as of 06:20, 20 July 2010
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 toplevel.
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.