# 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