Changes between Initial Version and Version 1 of RewriteRules


Ignore:
Timestamp:
Aug 9, 2006 12:22:46 PM (8 years ago)
Author:
simonpj
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • RewriteRules

    v1 v1  
     1== Notes on the implementation of rewrite RULEs in GHC == 
     2 
     3=== Looking through lets === 
     4 
     5We recently made the rule-matcher able to "look through" lets, thus 
     6{{{ 
     7   RULE f (g x) = rhs 
     8 
     9   Expression:  f (let v = e in g v) 
     10}}} 
     11  The rule will still match, giving 
     12{{{ 
     13   let v = e in rhs[v/x] 
     14}}} 
     15 
     16=== Dictionaries === 
     17 
     18Suppose we have 
     19{{{ 
     20  RULE f (g x) = rhs 
     21 
     22  f :: Ord a => a -> a 
     23 
     24  foo :: Int -> Int 
     25  foo x = f (g x) 
     26}}} 
     27Then we tend to get 
     28{{{ 
     29  f_79 :: Int -> Int 
     30  f_79 = f Int dOrdInt 
     31 
     32  foo :: Int -> Int 
     33  foo = \x -> f_79 (g x) 
     34}}} 
     35Lo, the f/g RULE cannot fire.  
     36 
     37Current solution: use {{{-fno-method-sharing}}} to get 
     38{{{ 
     39  foo :: Int -> Int 
     40  foo = \x -> f Int dOrdInt (g x) 
     41}}} 
     42But 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. 
     43 
     44Example of when -fno-method-sharing isn't enough. 
     45{{{ 
     46module Foo where 
     47 
     48data UArr a = UArr [a] 
     49 
     50class UA a where 
     51  ua :: [a] -> [a] 
     52 
     53instance UA Int where 
     54  ua xs = xs 
     55 
     56class DT a where 
     57  foo :: a -> a 
     58  bar :: a -> a 
     59 
     60instance DT Int where 
     61  foo x = x 
     62  bar x = x 
     63 
     64instance (DT a, DT b) => DT (a,b) where 
     65  foo x = x 
     66  bar x = x 
     67 
     68instance UA a => DT (UArr a) where 
     69  foo x = x 
     70  bar x = x 
     71 
     72data Dist a = Dist a 
     73 
     74mapD :: (DT a, DT b) => (a -> b) -> Dist a -> Dist b 
     75{-# INLINE [1] mapD #-} 
     76mapD f (Dist x) = Dist (f x) 
     77 
     78zipWithD :: (DT a, DT b, DT c) => (a -> b -> c) -> Dist a -> Dist b -> 
     79Dist c 
     80{-# INLINE zipWithD #-} 
     81zipWithD f (Dist x) (Dist y) = mapD (uncurry f) (Dist (x,y)) 
     82 
     83splitD :: UA a => UArr a -> Dist (UArr a) 
     84{-# INLINE [1] splitD #-} 
     85splitD x = zipWithD const (Dist x) (Dist x) 
     86 
     87joinD :: UA a => Dist (UArr a) -> UArr a 
     88{-# INLINE [1] joinD #-} 
     89joinD (Dist x) = x 
     90 
     91{-# RULES 
     92 
     93"split/join" forall x. 
     94  splitD (joinD x) = x 
     95 
     96 #-} 
     97 
     98------ 
     99 
     100module Bar where 
     101 
     102import Foo 
     103 
     104foo :: Dist (UArr Int) -> Dist (UArr Int) 
     105foo = splitD . joinD 
     106 
     107------ 
     108 
     109Compared to the previous version, the important differences are 
     110 
     111  - the class UA and the instance DT (UArr a) which builds a DT  
     112    dictionary from an UA one, 
     113  - splitD . joinD instead of splitD (joinD x) in foo. 
     114 
     115With this, we get 
     116 
     117------ 
     118 
     11915 splitD :: UA a => UArr a -> Dist (UArr a) 
     120     {- Arity: 1 HasNoCafRefs Strictness: A Inline: [1] 
     121        Unfolding: (__inline_me (\ @ a $dUA :: UA a -> 
     122                                 let { 
     123                                   $dDT :: DT (UArr a) = $f1 @ a $dUA 
     124                                 } in 
     125                                 \ x :: UArr a -> 
     126                                 zipWithD 
     127                                   @ (UArr a) 
     128                                   @ (UArr a) 
     129                                   @ (UArr a) 
     130                                   $dDT 
     131                                   $dDT 
     132                                   $dDT 
     133                                   (GHC.Base.const @ (UArr a) @ (UArr a)) 
     134                                   (Dist @ (UArr a) x) 
     135                                   (Dist @ (UArr a) x))) -} 
     136 
     137------ 
     138 
     139and the rule doesn't fire. Nor does it with 
     140 
     141  foo x = splitD $ joinD x 
     142 
     143But it *does* fire with 
     144 
     145  foo x = splitD (joinD x) 
     146 
     147despite the arity of splitD. Very strange... 
     148 
     149Roman 
     150}}}