[Haskell-cafe] More disciplined alternative to rewrite rules?

[Amos Robinson]

Hi,
Some kind of graph rewriting on the term is a promising idea, but I have no
idea how that would look. I would like to hear more.
I have an example where sharing is a barrier to shortcut fusion.

In Stream fusion combinators like map, filter and so on are implemented as
converting from list to streams, a stream transformer, then back to a list:

map f = unstream . map_s f . stream

Then the rewrite rule removes superfluous conversion:
{-# RULES stream . unstream = id #-}

So if you have map.map, this gets fused away:

map f . map g
= (inline map)
unstream  . map_s f . stream . unstream . map_s g . stream
= (rewrite rule)
unstream . map_s f . map_s g . stream


However, this doesn't work once you introduce sharing:

let ys = map f xs in (map g ys, map h ys)
= (inline map)
let ys = unstream (map_s f (stream xs)) in (unstream (map g (stream ys)),
unstream (map h (stream ys)))

here, we cannot inline substitute "ys" into both use sites as it would
duplicate work, so the rewrite rules have no way of firing.

GHC has another pragma called "CONLIKE", which declares a particular
function to be "cheap enough" to duplicate if duplication would cause a
rule to fire.
Data.Vector doesn't seem to use this in its stream fusion implementation,
and I'm not sure why. It may solve this case, but I'm not sure it solves
all cases

On Tue, 22 Dec 2015 at 07:44 Johannes Waldmann <
johannes.waldmann at htwk-leipzig.de> wrote:

>
> > The syntactic representation of the program is the most natural to
> humans,
> > but it is perhaps not the best for simplification.
>
> Maybe so. Please give examples.
>
> We use graphs (instead of trees) to express sharing.
> Do you see sharing (or the lack of expressibility for it)
> as a problem with GHC rules currently?
>
> - J.W.
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20151221/df9c7d79/attachment.html>