## Notes on the implementation of rewrite RULEs in GHC

### Looking through lets

We recently made the rule-matcher able to "look through" lets, thus

RULE f (g x) = rhs Expression: f (let v = e in g v)

The rule will still match, giving

let v = e in rhs[v/x]

### Dictionaries

Suppose we have

RULE f (g x) = rhs f :: Ord a => a -> a foo :: Int -> Int foo x = f (g x)

Then we tend to get

f_79 :: Int -> Int f_79 = f Int dOrdInt foo :: Int -> Int foo = \x -> f_79 (g x)

Lo, the f/g RULE cannot fire.

Current solution: use `-fno-method-sharing` to get

foo :: Int -> Int foo = \x -> f Int dOrdInt (g x)

But we found other examples where this wasn't enough. Code is below. The solution is: use `-fdicts-cheap`, which makes dictionary construction look really cheap.

Example of when -fno-method-sharing isn't enough.

module Foo where data UArr a = UArr [a] class UA a where ua :: [a] -> [a] instance UA Int where ua xs = xs class DT a where foo :: a -> a bar :: a -> a instance DT Int where foo x = x bar x = x instance (DT a, DT b) => DT (a,b) where foo x = x bar x = x instance UA a => DT (UArr a) where foo x = x bar x = x data Dist a = Dist a mapD :: (DT a, DT b) => (a -> b) -> Dist a -> Dist b {-# INLINE [1] mapD #-} mapD f (Dist x) = Dist (f x) zipWithD :: (DT a, DT b, DT c) => (a -> b -> c) -> Dist a -> Dist b -> Dist c {-# INLINE zipWithD #-} zipWithD f (Dist x) (Dist y) = mapD (uncurry f) (Dist (x,y)) splitD :: UA a => UArr a -> Dist (UArr a) {-# INLINE [1] splitD #-} splitD x = zipWithD const (Dist x) (Dist x) joinD :: UA a => Dist (UArr a) -> UArr a {-# INLINE [1] joinD #-} joinD (Dist x) = x {-# RULES "split/join" forall x. splitD (joinD x) = x #-} ------ module Bar where import Foo foo :: Dist (UArr Int) -> Dist (UArr Int) foo = splitD . joinD ------ Compared to the previous version, the important differences are - the class UA and the instance DT (UArr a) which builds a DT dictionary from an UA one, - splitD . joinD instead of splitD (joinD x) in foo. With this, we get ------ 15 splitD :: UA a => UArr a -> Dist (UArr a) {- Arity: 1 HasNoCafRefs Strictness: A Inline: [1] Unfolding: (__inline_me (\ @ a $dUA :: UA a -> let { $dDT :: DT (UArr a) = $f1 @ a $dUA } in \ x :: UArr a -> zipWithD @ (UArr a) @ (UArr a) @ (UArr a) $dDT $dDT $dDT (GHC.Base.const @ (UArr a) @ (UArr a)) (Dist @ (UArr a) x) (Dist @ (UArr a) x))) -} ------ and the rule doesn't fire. Nor does it with foo x = splitD $ joinD x But it *does* fire with foo x = splitD (joinD x) despite the arity of splitD. Very strange... Roman

Last modified 9 years ago
Last modified on Aug 9, 2006 12:22:46 PM