Changes between Initial Version and Version 1 of RewriteRules


Ignore:
Timestamp:
Aug 9, 2006 12:22:46 PM (9 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}}}