<div dir="ltr"><div>Hi Jaro,</div><div><br></div><div>I'm very glad that you are interested in picking up the pieces I left behind!</div><div><br></div><div>Re: SpecConstr: Yes, that pass is already moderately complicated and gets much more complicated when you start specialisation for non-bound lambdas, because that would need higher-order pattern unification in RULEs to be useful (as well as SpecConstr applying those RULEs when specialising). One smart suggestion by Simon to prevent that was to only specialise on bound lambdas only and do a pass before that assigns a name to every lambda. I'm not sure if that is enough for the recursive specialisation problem arising in stream fusion, though. I simply haven't played it through so far.</div><div><br></div><div>Re: Static argument transformation: I find that much more promising indeed. Not the pass that transforms the RHS of a  binding, but a my new idea that evaluates in the Simplifier for a recursive function whether it makes sense to inline its on-the-fly SAT'd form. See <a href="https://gitlab.haskell.org/ghc/ghc/-/issues/18962">https://gitlab.haskell.org/ghc/ghc/-/issues/18962</a> and the prototype <a href="https://gitlab.haskell.org/ghc/ghc/-/merge_requests/4553">https://gitlab.haskell.org/ghc/ghc/-/merge_requests/4553</a> for details. It does just fine on concatMap stream fusion pipelines (at least when the stepper function is small enough to inline), although I remember there are a few annoying issues regarding SAT'ing stable unfoldings (think INLINE recursive functions). Just thinking about it makes me excited again, but I've to finish other stuff in my PhD first.<br></div><div><br></div><div>Re: Beefing up rewrite rules: I *think* the RULE you suggest amounts to implementing pattern unification in RULEs (perhaps you could prevent that by saying that `x` may not occur freely in `next` or `f`, but the paper explicitly *wants* `x` to occur in `next`). I'd find that cool, but I'm a bit wary that the RULE matcher (which I'm not very familiar with) might behave subtly different in certain key scenarios than vanilla pattern unification and we might get breaking changes as a result.</div><div>At the moment, RULEs matching only ever matches a term against a pattern, where the former has no "unification variables", so it might be simpler than full-blown pattern unification.<br></div><div><br></div><div>So in short, the problem was never that we couldn't write down the RULE, but that it's hard to implement in GHC.</div><div><br></div><div>I can't really answer (1) or (2), but perhaps my summary above is useful to you.</div><div><br></div><div>Sebastian<br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Am Mo., 14. Nov. 2022 um 10:47 Uhr schrieb J. Reinders <<a href="mailto:jaro.reinders@gmail.com">jaro.reinders@gmail.com</a>>:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Dear GHC devs,<br>
<br>
I’m interested in stream fusion and would like to see what it takes to fix the remaining issues, so that it can replace foldr/build fusion in base.<br>
<br>
First of all I would like to know what exactly the challenges are that are left. I believe one of the main remaining problems is the fusion of ‘concatMap’. Is that really the only thing?<br>
<br>
Secondly, I would like to know what has already been tried. I know Sebastian Graf has spent a lot of effort trying to get SpecConstr to work on lambda arguments without success. I’ve read that Sebastian now considers the static argument transformation more promising.<br>
<br>
However, Duncan Coutts proposed in his thesis to make rewrite rules slightly more powerful and use the rewrite rule:<br>
<br>
    concatMap (λx → Stream next (f x)) = concatMap' next f<br>
<br>
Has that ever been tried? If so, what is the problem with this rewrite rule approach? I can understand that the `f x` function application is usually in a more reduced form, but it seems relatively easy to make the rewrite rule matcher smart enough to see through beta-reductions like that.<br>
<br>
So my main questions are:<br>
<br>
1. Is the ‘concatMap’ problem really the only problem left on the way to using stream fusion instead of foldr/build fusion in base?<br>
<br>
2. Has the rewrite rule approach to solving the ‘concatMap’ problem ever been tried?<br>
<br>
Any other information about the current status of stream fusion is also much appreciated.<br>
<br>
Cheers,<br>
<br>
Jaro Reinders<br>
<br>
_______________________________________________<br>
ghc-devs mailing list<br>
<a href="mailto:ghc-devs@haskell.org" target="_blank">ghc-devs@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs</a><br>
</blockquote></div>