Closure elimination transformation (continuation style
passingcode)
Tyson Whitehead
twhitehead at gmail.com
Wed May 20 11:27:32 EDT 2009
On May 20, 2009 05:50:54 Claus Reinke wrote:
> I'm not at all sure what you're aiming for (the above doesn't compile),
Yeah. The newtype Step a b was required to break the recursive types, and I
dropped it when performing the various transformations, so they don't type
check. Here it is again with the newtypes so each bit can be compiled.
0- initial code
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
1a- avoid forming the (count _) closures by passing the function and the
argument instead of the function bound to the argument
newtype Step a c b = Step { unStep :: (c -> a -> Step a c b -> b) -> c -> b
-> b }
iter :: [a] -> (c -> a -> Step a c b -> b) -> c -> b -> b
iter [] next i done = done
iter (x:xs) next i done = next i x (Step $ iter xs)
count :: Int -> Char -> Step Char Int Int -> Int
count i x step = unStep step count (i+1) (i+1)
test :: String -> Int
test xs = iter xs count 0 0
1b- avoid forming the (iter _) closure by passing the function and the
argument instead of the function bound to the argument
newtype Step a c b = Step { unStep :: [a] -> (c -> a -> Step a c b -> [a] ->
b) -> c -> b -> b }
iter :: [a] -> (c -> a -> Step a c b -> [a] -> b) -> c -> b -> b
iter [] next i done = done
iter (x:xs) next i done = next i x (Step iter) xs
count :: Int -> Char -> Step Char Int Int -> String -> Int
count i x step xs = unStep step xs count (i+1) (i+1)
test :: String -> Int
test xs = iter xs count 0 0
2- specialize iter for next = count
newtype Step a c b = Step { unStep :: [a] -> (c -> a -> Step a c b -> [a] ->
b) -> c -> b -> b }
iter :: [a] -> (c -> a -> Step a c b -> [a] -> b) -> c -> b -> b
iter' :: String -> Int -> Int -> Int
iter [] next i done = done
iter (x:xs) next i done = next i x (Step iter) xs
iter' [] i done = done
iter' (x:xs) i done = count i x (Step iter) xs
count :: Int -> Char -> Step Char Int Int -> String -> Int
count i x step xs = unStep step xs count (i+1) (i+1)
test :: String -> Int
test xs = iter' xs 0 0
3- specialize count for step = iter (and use the specialized iter')
newtype Step a c b = Step { unStep :: [a] -> (c -> a -> Step a c b -> [a] ->
b) -> c -> b -> b }
iter :: [a] -> (c -> a -> Step a c b -> [a] -> b) -> c -> b -> b
iter' :: String -> Int -> Int -> Int
iter [] next i done = done
iter (x:xs) next i done = next i x (Step iter) xs
iter' [] i done = done
iter' (x:xs) i done = count' i x xs
count :: Int -> Char -> Step Char Int Int -> String -> Int
count' :: Int -> Char -> String -> Int
count i x step xs = unStep step xs count (i+1) (i+1)
count' i x xs = iter' xs (i+1) (i+1)
test :: String -> Int
test xs = iter' xs 0 0
(iter and count are no longer used and can be dropped at this point)
4- inline count'
iter' :: String -> Int -> Int -> Int
iter' [] i done = done
iter' (x:xs) i done = iter' xs (i+1) (i+1)
count' :: Int -> Char -> String -> Int
count' i x xs = iter' xs (i+1) (i+1)
test :: String -> Int
test xs = iter' xs 0 0
(count' is no longer used and can be dropped at this point)
5- eliminate the done argument as it is always the same as the i argument
iter'' :: String -> Int -> Int
iter'' [] i = i
iter'' (x:xs) i = iter'' xs (i+1)
test :: String -> Int
test xs = iter'' xs 0
Cheers! -Tyson
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part.
Url : http://www.haskell.org/pipermail/glasgow-haskell-users/attachments/20090520/841ac54c/attachment.bin
More information about the Glasgow-haskell-users
mailing list