Closure elimination transformation (continuation style passing
code)
Simon Peyton-Jones
simonpj at microsoft.com
Wed May 20 12:45:48 EDT 2009
| 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
More information about the Glasgow-haskell-users
mailing list