Personal tools

Lambda lifting

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
m
Current revision (19:08, 19 January 2011) (edit) (undo)
(Fix unfortunate line break.)
 
(2 intermediate revisions 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 68: 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]]

Current revision

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.

Retrieved from "http://www.haskell.org/haskellwiki/Lambda_lifting"

Category: Refactoring