Closure elimination transformation (continuation style passing code)

[Simon Peyton-Jones]

| GHC's optimizer needs serious work. Personally, I'm rooting for the
| LHC/JHC guys, because I'm increasingly coming to the conclusion that
| you need whole-program compilation with flow analysis and bucketloads
| of specialisation on the back of that to make serious progress at
| optimizing Haskell.

I think you can get much further than GHC does without whole-program compilation.

Notably, GHC does call-pattern specialisation.  That is, if GHC sees the call
        f (C x xs)
and f case-analyses its first argument, then GHC makes a specialised copy of f, suitable for such applications.  (Paper on my home page.)

There's no reason in principle why it should not also look for calls
        f (c x xs)
where c is a function of arity > 2 (so that (c x xs) is a partial application), and f calls its first argument.  Then it could make a specialised version of f, suitable for calls of that shape.  If you think of the Church encoding of data constructors, it's just the same.

There are many engineering details to get right.  For example, at the moment GHC mostly concentrates on call patterns in f's right hand side; but for the higher order stuff you may want to focus on calls *elsewhere*.  It's not clear how to control code bloat.

But just for the record, below is how Tyson's program would go under this regime.

Simon

------------
Original program

  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

-------------
-- Specialise iter
-- RULE: iter xs (count m) done = iter1 xs m done

iter1 [] m done = done
iter1 [] m done = count m x (Step (iter xs))

-- count unchanged

test xs = iter1 xs 0 0

------------------
-- Specialise count
-- RULE: count m x (Step (iter xs)) = count1 m x xs

count1 m x xs = iter xs (count (m+1)) (m+1)
              = iter1 xs (m+1) (m+1)

iter1 []     m done = done
iter1 (x:xs) m done = count1 m x xs

--------------------
-- Inline count1 in iter1

iter1 []     m done = done
iter1 (x:xs) m done = iter1 xs (m+1) (m+1)


-- All this is left is the redundant calculation of m+1