Personal tools

Lambda lifting

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(Converting HaWiki)
 
m
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 [[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]].
   

Revision as of 14:47, 26 January 2007

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.

Note that 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.

-- User:AndrewBromage