rewrite rules

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

rewrite rules

Sjoerd Visscher-2
Hi all,

I have a rewrite rule as follows:

{-# RULES
"transform/transform" forall (f::forall m. Monoid m => (a -> m) -> (b -
 > m))
                              (g::forall m. Monoid m => (b -> m) -> (c  
-> m))
                              (l::FMList c). transform f (transform g  
l) = transform (g.f) l
   #-}

It fires on this code:

   print $ transform (. (*2)) (transform (. (+1)) (upto 10))

But it doesn't fire on this code:

   print $ map (*2) (map (+1) (upto 10)))

with

   map g x = transform (. g) x

and with or without {-# INLINE map #-}.

What am I doing wrong?

--
Sjoerd Visscher
[hidden email]



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: rewrite rules

Ryan Ingram
Not 100% sure (especially without source/core), but my guess is that
the higher-rank types make the rule unlikely to fire.

Try -ddump-simpl to see the core output, and look for places where you
expect the rule to fire.  I suspect you will find that the types of f
and g are not "forall" at that point in the code, but have already
been specialized.

Is there a reason you cannot use this simpler rule?

{-# RULES "transform/tranform" forall f g l. transform f (transform g
l) = transform (g.f) l #-}

  -- ryan

On Mon, Jun 22, 2009 at 2:41 AM, Sjoerd Visscher<[hidden email]> wrote:

> Hi all,
>
> I have a rewrite rule as follows:
>
> {-# RULES
> "transform/transform" forall (f::forall m. Monoid m => (a -> m) -> (b -> m))
>                             (g::forall m. Monoid m => (b -> m) -> (c -> m))
>                             (l::FMList c). transform f (transform g l) =
> transform (g.f) l
>  #-}
>
> It fires on this code:
>
>  print $ transform (. (*2)) (transform (. (+1)) (upto 10))
>
> But it doesn't fire on this code:
>
>  print $ map (*2) (map (+1) (upto 10)))
>
> with
>
>  map g x = transform (. g) x
>
> and with or without {-# INLINE map #-}.
>
> What am I doing wrong?
>
> --
> Sjoerd Visscher
> [hidden email]
>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: rewrite rules

Daniel Schüssler
In reply to this post by Sjoerd Visscher-2
Hi Sjoerd,

I don't know the cause of the problem, but if I add this rule, it works:

{-# RULES
   "inline_map" forall g x. map g x = transform (. g) x
 -#}

maybe, for whatever reason, the 'map' is inlined "too late" for the
transform/transform rule to see it?


Greetings,
Daniel

On Monday 22 June 2009 11:41:33 Sjoerd Visscher wrote:

> Hi all,
>
> I have a rewrite rule as follows:
>
> {-# RULES
> "transform/transform" forall (f::forall m. Monoid m => (a -> m) -> (b -
>
>  > m))
>
>                               (g::forall m. Monoid m => (b -> m) -> (c
> -> m))
>                               (l::FMList c). transform f (transform g
> l) = transform (g.f) l
>    #-}
>
> It fires on this code:
>
>    print $ transform (. (*2)) (transform (. (+1)) (upto 10))
>
> But it doesn't fire on this code:
>
>    print $ map (*2) (map (+1) (upto 10)))
>
> with
>
>    map g x = transform (. g) x
>
> and with or without {-# INLINE map #-}.
>
> What am I doing wrong?
>
> --
> Sjoerd Visscher
> [hidden email]
>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: rewrite rules

Sjoerd Visscher-2
In reply to this post by Ryan Ingram

On Jun 22, 2009, at 6:38 PM, Ryan Ingram wrote:

> Not 100% sure (especially without source/core), but my guess is that
> the higher-rank types make the rule unlikely to fire.
>
> Try -ddump-simpl to see the core output, and look for places where you
> expect the rule to fire.  I suspect you will find that the types of f
> and g are not "forall" at that point in the code, but have already
> been specialized.
>
> Is there a reason you cannot use this simpler rule?
>
> {-# RULES "transform/tranform" forall f g l. transform f (transform g
> l) = transform (g.f) l #-}
>

Yes, this is the reason:

     Inferred type is less polymorphic than expected
       Quantified type variable `m' is mentioned in the environment:
         f :: (a -> m) -> b -> m (bound at Data/FMList.hs:124:29)
     In the first argument of `transform', namely `f'
     In the expression: transform f (transform g l)
     When checking the transformation rule "transform/transform"

This is the function:

transform :: (forall m. Monoid m => (a -> m) -> (b -> m)) -> FMList b -
 > FMList a
transform t l = FM $ \f -> unFM l (t f)

I'll have to clean things up before the core output becomes manageable.

Sjoerd

>  -- ryan
>
> On Mon, Jun 22, 2009 at 2:41 AM, Sjoerd  
> Visscher<[hidden email]> wrote:
>> Hi all,
>>
>> I have a rewrite rule as follows:
>>
>> {-# RULES
>> "transform/transform" forall (f::forall m. Monoid m => (a -> m) ->  
>> (b -> m))
>>                             (g::forall m. Monoid m => (b -> m) ->  
>> (c -> m))
>>                             (l::FMList c). transform f (transform g  
>> l) =
>> transform (g.f) l
>>  #-}
>>
>> It fires on this code:
>>
>>  print $ transform (. (*2)) (transform (. (+1)) (upto 10))
>>
>> But it doesn't fire on this code:
>>
>>  print $ map (*2) (map (+1) (upto 10)))
>>
>> with
>>
>>  map g x = transform (. g) x
>>
>> and with or without {-# INLINE map #-}.
>>
>> What am I doing wrong?
>>
>> --
>> Sjoerd Visscher
>> [hidden email]
>>
>>
>>
>> _______________________________________________
>> Haskell-Cafe mailing list
>> [hidden email]
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>
>

--
Sjoerd Visscher
[hidden email]



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

RE: rewrite rules

Simon Peyton Jones
In reply to this post by Sjoerd Visscher-2
| I have a rewrite rule as follows:
|
| {-# RULES
| "transform/transform" forall (f::forall m. Monoid m => (a -> m) -> (b -
|  > m))
|                               (g::forall m. Monoid m => (b -> m) -> (c
| -> m))
|                               (l::FMList c). transform f (transform g
| l) = transform (g.f) l
|    #-}
|
| It fires on this code:
|
|    print $ transform (. (*2)) (transform (. (+1)) (upto 10))
|
| But it doesn't fire on this code:
|
|    print $ map (*2) (map (+1) (upto 10)))

That's odd. It works for me.

Specifically, I compiled the attached code with GHC 6.10, and I get two firings of transform/transform.

Does that not happen for you?

Simon


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Rules.hs (904 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: rewrite rules

Sjoerd Visscher-2
Thanks for looking into this.

Your code does give me 2 firings. But not when I replace [] with  
FMList. See the attached code.





Sjoerd

On Jun 23, 2009, at 5:59 PM, Simon Peyton-Jones wrote:

> | I have a rewrite rule as follows:
> |
> | {-# RULES
> | "transform/transform" forall (f::forall m. Monoid m => (a -> m) ->  
> (b -
> |  > m))
> |                               (g::forall m. Monoid m => (b -> m) -
> > (c
> | -> m))
> |                               (l::FMList c). transform f  
> (transform g
> | l) = transform (g.f) l
> |    #-}
> |
> | It fires on this code:
> |
> |    print $ transform (. (*2)) (transform (. (+1)) (upto 10))
> |
> | But it doesn't fire on this code:
> |
> |    print $ map (*2) (map (+1) (upto 10)))
>
> That's odd. It works for me.
>
> Specifically, I compiled the attached code with GHC 6.10, and I get  
> two firings of transform/transform.
>
> Does that not happen for you?
>
> Simon
>
> <Rules.hs>
--
Sjoerd Visscher
[hidden email]




_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Rules.hs (802 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: rewrite rules

Ryan Ingram
Your FMLists are defaulting to Integer, so the rule (which
specifically mentions Int) doesn't apply.  Simon's code doesn't have
this problem because of the explicit signature on "upto"; you could do
the same by limiting "singleton" to Int.

  -- ryan

On Wed, Jun 24, 2009 at 12:44 AM, Sjoerd Visscher<[hidden email]> wrote:

> Thanks for looking into this.
>
> Your code does give me 2 firings. But not when I replace [] with FMList. See
> the attached code.
>
>
>
>
>
> Sjoerd
>
> On Jun 23, 2009, at 5:59 PM, Simon Peyton-Jones wrote:
>
>> | I have a rewrite rule as follows:
>> |
>> | {-# RULES
>> | "transform/transform" forall (f::forall m. Monoid m => (a -> m) -> (b -
>> |  > m))
>> |                               (g::forall m. Monoid m => (b -> m) -> (c
>> | -> m))
>> |                               (l::FMList c). transform f (transform g
>> | l) = transform (g.f) l
>> |    #-}
>> |
>> | It fires on this code:
>> |
>> |    print $ transform (. (*2)) (transform (. (+1)) (upto 10))
>> |
>> | But it doesn't fire on this code:
>> |
>> |    print $ map (*2) (map (+1) (upto 10)))
>>
>> That's odd. It works for me.
>>
>> Specifically, I compiled the attached code with GHC 6.10, and I get two
>> firings of transform/transform.
>>
>> Does that not happen for you?
>>
>> Simon
>>
>> <Rules.hs>
>
> --
> Sjoerd Visscher
> [hidden email]
>
>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: rewrite rules

Sjoerd Visscher-2
Ah, thanks.

It turns out that this works:

   transform t l = error "urk"

but this doesn't:

   transform t l = FM $ error "urk"

So it has something to do with the newtype FMList. They are probably  
already gone when rewrite rules fire?

Sjoerd

On Jun 24, 2009, at 6:32 PM, Ryan Ingram wrote:

> Your FMLists are defaulting to Integer, so the rule (which
> specifically mentions Int) doesn't apply.  Simon's code doesn't have
> this problem because of the explicit signature on "upto"; you could do
> the same by limiting "singleton" to Int.
>
>  -- ryan
>
> On Wed, Jun 24, 2009 at 12:44 AM, Sjoerd  
> Visscher<[hidden email]> wrote:
>> Thanks for looking into this.
>>
>> Your code does give me 2 firings. But not when I replace [] with  
>> FMList. See
>> the attached code.
>>
>>
>>
>>
>>
>> Sjoerd
>>
>> On Jun 23, 2009, at 5:59 PM, Simon Peyton-Jones wrote:
>>
>>> | I have a rewrite rule as follows:
>>> |
>>> | {-# RULES
>>> | "transform/transform" forall (f::forall m. Monoid m => (a -> m) -
>>> > (b -
>>> |  > m))
>>> |                               (g::forall m. Monoid m => (b -> m)  
>>> -> (c
>>> | -> m))
>>> |                               (l::FMList c). transform f  
>>> (transform g
>>> | l) = transform (g.f) l
>>> |    #-}
>>> |
>>> | It fires on this code:
>>> |
>>> |    print $ transform (. (*2)) (transform (. (+1)) (upto 10))
>>> |
>>> | But it doesn't fire on this code:
>>> |
>>> |    print $ map (*2) (map (+1) (upto 10)))
>>>
>>> That's odd. It works for me.
>>>
>>> Specifically, I compiled the attached code with GHC 6.10, and I  
>>> get two
>>> firings of transform/transform.
>>>
>>> Does that not happen for you?
>>>
>>> Simon
>>>
>>> <Rules.hs>
>>
>> --
>> Sjoerd Visscher
>> [hidden email]
>>
>>
>>
>>
>> _______________________________________________
>> Haskell-Cafe mailing list
>> [hidden email]
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>
>>
>

--
Sjoerd Visscher
[hidden email]



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe