Closure elimination transformation (continuation style passing code)
Tyson Whitehead
twhitehead at gmail.com
Tue May 19 22:17:39 EDT 2009
I was wondering about GHC's ability to optimize the following code
module Test (test) where
newtype Step a b = Step { unStep :: (a -> Step a b -> b) -> b -> b }
iter :: [a] -> (a -> Step a b -> b) -> b -> b
iter [] next done = done
iter (x:xs) next done = next x (Step $ iter xs)
count :: Int -> Char -> Step Char Int -> Int
count i x step = unStep step (count $ i+1) (i+1)
test :: String -> Int
test xs = iter xs (count 0) 0
(test implements the string length function).
The transformations steps that reduce this to the optimized version are
1- avoid forming the (iter xs) and (count i+1) closures by passing the
function and the arguments instead of the function bound to the argument
iter [] next i done = done
iter (x:xs) next i done = next i x iter xs
count i x step xs = step xs count (i+1) (i+1)
test xs = iter xs count 0 0
2- specialize count for step = iter
iter [] next i done = done
iter (x:xs) next i done = next i x iter xs
count i x xs = iter xs count (i+1) (i+1)
test xs = iter xs count 0 0
3- specializing iter for next = count
iter [] i done = done
iter (x:xs) i done = count i x iter xs
count i x xs = iter xs (i+1) (i+1)
test xs = iter xs 0 0
4- inline count
iter [] i done = done
iter (x:xs) i done = iter xs (i+1) (i+1)
test xs = iter xs 0 0
5- eliminate the done argument as it is always the same as the i argument
iter [] i = i
iter (x:xs) i = iter xs (i+1)
test xs = iter xs 0
Currently 6.10.1 with -O2 seems stuck with regard to step 1 (eliminating the
closures). Is there any hope of getting it to these transformations?
Thanks! -Tyson
More information about the Glasgow-haskell-users
mailing list