Closure elimination transformation (continuation style passingcode)

[Tyson Whitehead]

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