| 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
_______________________________________________
Glasgow-haskell-users mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
