Arrow preprocessor and *** combinator - Haskell-Cafe - Haskell.org

newer
Google SoC: Space profiling...

Arrow preprocessor and *** combinator

older
unsafeSTToIO and stToIO

Peter Verswyvelen

29 Apr 2009 29 Apr '09

9:07 a.m.

After doing some pragmatic tests, it seems that neither the arrow preprocessor nor GHC's builtin one generate / optimize to the (***) combinator. For example, p = proc (x,y) -> do x' <- f <- x y' <- g <- y return (x',y') is equivalent to p = f *** g But I have the impression this kind of rewrites is not being done? Is it possible to provide rewrite rules for arrows? Since *** is a method of the arrow type class, it might have a more optimal implementation. I haven't looked at the arrow preprocessor or GHC's code yet, but comments are welcome, I might see things wrongly. Cheers, Peter

Attachments:

attachment.html (text/html — 1023 bytes)

Reply

Sign in to reply online Use email software

Show replies by date

Ross Paterson

29 Apr 29 Apr

9:43 a.m.

On Wed, Apr 29, 2009 at 03:07:25PM +0200, Peter Verswyvelen wrote:

After doing some pragmatic tests, it seems that neither the arrow preprocessor nor GHC's builtin one generate / optimize to the (***) combinator.

Right, neither of them do that. It might be possible to do that using GHC rules, but it isn't done at the moment.

Reply

Sign in to reply online Use email software

Peter Verswyvelen

30 Apr 30 Apr

1:42 p.m.

Thanks Ross. Does anyone know how to tackle this? Combining GHC's builtin arrow processor and rewrite rules? On Wed, Apr 29, 2009 at 3:43 PM, Ross Paterson wrote:

...
After doing some pragmatic tests, it seems that neither the arrow

On Wed, Apr 29, 2009 at 03:07:25PM +0200, Peter Verswyvelen wrote: preprocessor

...
nor GHC's builtin one generate / optimize to the (***) combinator.

Right, neither of them do that. It might be possible to do that using GHC rules, but it isn't done at the moment. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Reply

Sign in to reply online Use email software

Luke Palmer

4:15 p.m.

On Thu, Apr 30, 2009 at 11:42 AM, Peter Verswyvelen wrote:

Thanks Ross. Does anyone know how to tackle this? Combining GHC's builtin arrow processor and rewrite rules?

Another possibility is to make an "optimizer" arrow transformer that encodes the rules. Eg. data Optimize a b c where Arr :: (b -> c) -> Optimize a b c (:>>>) :: Optimize a b c -> Optimize a c d -> Optimize a b d First :: Optimize a b c -> Optimize a (b,d) (c,d) Second :: Optimize a b c -> Optimize a (b,d) (c,d) (:***) :: Optimize a b b' -> Optimize a c c' -> Optimize a (b,b') (c,c') optimize :: Optimize a b c -> Optimize a b c optimize (First f :>>> Second g) = f :*** g ... compile :: (Arrow a) => Optimize a b c -> a b c compile (Arr f) = arr f compile (f :>>> g) = compile f >>> compile g ... I have of course handwaved over optimize, which will have some interesting traversal structure; esp. if you want to take advantage of the associativity of >>>. Unfortunately, Arr is not quite transparent enough to do everything one might want with this. e.g.,this rule cannot be encoded: swap (x,y) = (y,x) first f >>> arr swap >>> first g = f *** g >>> arr swap If you are serious about arrow optimizations, it might be worthwhile to modify the original preprocessor to output a richer GADT (with cases for things like ArrSwap) with all the information it knows, so that user code can experiment with optimizations. Godspeed on this interesting problem. Please publish :-) Luke

On Wed, Apr 29, 2009 at 3:43 PM, Ross Paterson wrote:

...
...
After doing some pragmatic tests, it seems that neither the arrow

On Wed, Apr 29, 2009 at 03:07:25PM +0200, Peter Verswyvelen wrote: preprocessor

...
nor GHC's builtin one generate / optimize to the (***) combinator.

Right, neither of them do that. It might be possible to do that using GHC rules, but it isn't done at the moment. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Reply

Sign in to reply online Use email software

Peter Verswyvelen

6:15 p.m.

If you are serious about arrow optimizations, it might be worthwhile to modify the original preprocessor to output a richer GADT (with cases for things like ArrSwap) with all the information it knows, so that user code can experiment with optimizations.

Godspeed on this interesting problem. Please publish :-)

Thanks for the tips Luke. I didn't think of that. But would doing these optimizations at runtime be as efficient as using rewrite rules? I know Yampa uses these GADTs for optimization. No I won't be able to make such a big optimizer myself - but Paul Liu and Paul Hudak are working on something like that I think (see the Causal Commutative Arrows paper). But my code made use of a non-default *** and I found it odd that it was never called, so I hoped it would be easy to add a couple of simple rewrite rule so that *** was generated.

Reply

Sign in to reply online Use email software

5865

Age (days ago)

5866

Last active (days ago)

Download

4 comments

3 participants

tags

participants (3)

Luke Palmer
Peter Verswyvelen
Ross Paterson