<div dir="ltr">Hi,<div>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.<br><div>I have an example where sharing is a barrier to shortcut fusion.</div><div><br></div><div>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:</div><div><br></div><div>map f = unstream . map_s f . stream</div><div><br></div><div>Then the rewrite rule removes superfluous conversion:</div><div>{-# RULES stream . unstream = id #-}</div><div><br></div><div>So if you have map.map, this gets fused away:</div><div><br></div><div>map f . map g</div><div>= (inline map)</div><div>unstream  . map_s f . stream . unstream . map_s g . stream</div><div>= (rewrite rule)</div><div>unstream . map_s f . map_s g . stream</div><div><br></div><div><br></div><div>However, this doesn't work once you introduce sharing:</div><div><br></div><div>let ys = map f xs <span style="line-height:1.5">in (map g ys, map h ys)</span></div><div>= (inline map)</div></div><div><div>let ys = unstream (map_s f (stream xs)) <span style="line-height:1.5">in (unstream (map g (stream ys)), unstream (map h (stream ys)))</span></div></div><div><span style="line-height:1.5"><br></span></div><div><span style="line-height:1.5">here, we cannot inline substitute "ys" into both use sites as it would duplicate work, so the rewrite rules have no way of firing.</span></div><div><span style="line-height:1.5"><br></span></div><div><span style="line-height:1.5">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.</span></div><div><span style="line-height:1.5">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</span></div></div><br><div class="gmail_quote"><div dir="ltr">On Tue, 22 Dec 2015 at 07:44 Johannes Waldmann <<a href="mailto:johannes.waldmann@htwk-leipzig.de">johannes.waldmann@htwk-leipzig.de</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><br>
> The syntactic representation of the program is the most natural to humans,<br>
> but it is perhaps not the best for simplification.<br>
<br>
Maybe so. Please give examples.<br>
<br>
We use graphs (instead of trees) to express sharing.<br>
Do you see sharing (or the lack of expressibility for it)<br>
as a problem with GHC rules currently?<br>
<br>
- J.W.<br>
<br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org" target="_blank">Haskell-Cafe@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
</blockquote></div>