Status of Stream Fusion?

[Sebastian Graf]

Hi Jaro,

I'm very glad that you are interested in picking up the pieces I left
behind!

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.

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
https://gitlab.haskell.org/ghc/ghc/-/issues/18962 and the prototype
https://gitlab.haskell.org/ghc/ghc/-/merge_requests/4553 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.

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.
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.

So in short, the problem was never that we couldn't write down the RULE,
but that it's hard to implement in GHC.

I can't really answer (1) or (2), but perhaps my summary above is useful to
you.

Sebastian

Am Mo., 14. Nov. 2022 um 10:47 Uhr schrieb J. Reinders <
jaro.reinders at gmail.com>:

> Dear GHC devs,
>
> 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.
>
> 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?
>
> 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.
>
> However, Duncan Coutts proposed in his thesis to make rewrite rules
> slightly more powerful and use the rewrite rule:
>
>     concatMap (λx → Stream next (f x)) = concatMap' next f
>
> 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.
>
> So my main questions are:
>
> 1. Is the ‘concatMap’ problem really the only problem left on the way to
> using stream fusion instead of foldr/build fusion in base?
>
> 2. Has the rewrite rule approach to solving the ‘concatMap’ problem ever
> been tried?
>
> Any other information about the current status of stream fusion is also
> much appreciated.
>
> Cheers,
>
> Jaro Reinders
>
> _______________________________________________
> ghc-devs mailing list
> ghc-devs at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/ghc-devs/attachments/20221114/8c4a34be/attachment.html>