# Closure elimination transformation (continuation style passingcode)

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.