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