<div dir="ltr">
<div>Hi Alexis,</div><div><br></div><div>I've been wondering the same things and have worked on it on and off. See my progress in <a href="https://gitlab.haskell.org/ghc/ghc/issues/855#note_149482" target="_blank">https://gitlab.haskell.org/ghc/ghc/issues/855#note_149482</a> and <a href="https://gitlab.haskell.org/ghc/ghc/issues/915#note_241520" target="_blank">https://gitlab.haskell.org/ghc/ghc/issues/915#note_241520</a>.</div><div><br></div><div>The
 big problem with solving the higher-order specialisation problem 
through SpecConstr (which is what I did in my reports in #855) is indeed
 that it's hard to<ol><li>Anticipate what the rewritten program looks 
like without doing a Simplifier pass after each specialisation, so that 
we can see and exploit new specialisation opportunities. SpecConstr does
 use the simple Core optimiser but, that often is not enough IIRC (think
 of ArgOccs from recursive calls). In particular, it will not do RULE 
rewrites. Interleaving SpecConstr with the Simplifier, apart from nigh 
impossible conceptually, is computationally intractable and would 
quickly drift off into Partial Evaluation swamp.<br></li><li>Make the RULE engine match and rewrite call sites in all call patterns they can apply.<br>I.e.,
 `f (\x -> Just (x +1))` calls its argument with one argument and 
scrutinises the resulting Maybe (that's what is described by the 
argument's `ArgOcc`), so that we want to specialise to a call pattern `f
 (\x -> Just <some expression using x>)`, giving rise to the 
specialisation `$sf ctx`, where `ctx x` describes the `<some 
expression using x>` part. In an ideal world, we want a (higher-order
 pattern unification) RULE for `forall f ctx. f (\x -> Just (ctx x)) 
==> $sf ctx`. But from what I remember, GHC's RULE engine works quite
 different from that and isn't even concerned with finding unifiers 
(rather than just matching concrete call sites without meta variables 
against RULEs with meta variables) at all.</li></ol>
</div><div>Note that matching on specific Ids binding functions is just 
an approximation using representional equality (on the Id's Unique) 
rather than some sort of more semantic equality. My latest endeavour 
into the matter in #915 from December was using types as the 
representational entity and type class specialisation. I think I got 
ultimately blocked on thttps://<a href="http://gitlab.haskell.org/ghc/ghc/issues/17548" target="_blank">gitlab.haskell.org/ghc/ghc/issues/17548</a>, but apparently I didn't document the problematic program.</div><div><br></div><div>Maybe
 my failure so far is that I want it to apply and optimise all cases and
 for more complex stream pipelines, rather than just doing a better best
 effort job.<br></div><div><br></div><div>Hope that helps. Anyway, I'm 
also really keen on nailing this! It's one of my high-risk, high-reward 
research topics. So if you need someone to collaborate/exchange ideas 
with, I'm happy to help!</div><div><br></div><div>All the best,<br></div><div>Sebastian</div>

</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Am So., 29. März 2020 um 10:39 Uhr schrieb Alexis King <<a href="mailto:lexi.lambda@gmail.com">lexi.lambda@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">Hi all,<br>
<br>
I have recently been toying with FRP, and I’ve noticed that<br>
traditional formulations generate a lot of tiny loops that GHC does<br>
a very poor job optimizing. Here’s a simplified example:<br>
<br>
    newtype SF a b = SF { runSF :: a -> (b, SF a b) }<br>
<br>
    add1_snd :: SF (String, Int) (String, Int)<br>
    add1_snd = second add1 where<br>
      add1 = SF $ \a -> let !b = a + 1 in (b, add1)<br>
      second f = SF $ \(a, b) -><br>
        let !(c, f') = runSF f b<br>
        in ((a, c), second f')<br>
<br>
Here, `add1_snd` is defined in terms of two recursive bindings,<br>
`add1` and `second`. Because they’re both recursive, GHC doesn’t<br>
know what to do with them, and the optimized program still has two<br>
separate recursive knots. But this is a missed optimization, as<br>
`add1_snd` is equivalent to the following definition, which fuses<br>
the two loops together and consequently has just one recursive knot:<br>
<br>
    add1_snd_fused :: SF (String, Int) (String, Int)<br>
    add1_snd_fused = SF $ \(a, b) -><br>
      let !c = b + 1<br>
      in ((a, c), add1_snd_fused)<br>
<br>
How could GHC get from `add1_snd` to `add1_snd_fused`? In theory,<br>
SpecConstr could do it! Suppose we specialize `second` at the call<br>
pattern `second add1`:<br>
<br>
    {-# RULE "second/add1" second add1 = second_add1 #-}<br>
<br>
    second_add1 = SF $ \(a, b) -><br>
      let !(c, f') = runSF add1 b<br>
      in ((a, c), second f')<br>
<br>
This doesn’t immediately look like an improvement, but we’re<br>
actually almost there. If we unroll `add1` once on the RHS of<br>
`second_add1`, the simplifier will get us the rest of the way. We’ll<br>
end up with<br>
<br>
    let !b1 = b + 1<br>
        !(c, f') = (b1, add1)<br>
    in ((a, c), second f')<br>
<br>
and after substituting f' to get `second add1`, the RULE will tie<br>
the knot for us.<br>
<br>
This may look like small potatoes in isolation, but real programs<br>
can generate hundreds of these tiny, tiny loops, and fusing them<br>
together would be a big win. The only problem is SpecConstr doesn’t<br>
currently specialize on functions! The original paper, “Call-pattern<br>
Specialisation for Haskell Programs,” mentions this as a possibility<br>
in Section 6.2, but it points out that actually doing this in<br>
practice would be pretty tricky:<br>
<br>
> Specialising for function arguments is more slippery than for<br>
> constructor arguments. In the example above the argument was a<br>
> simple variable, but what if it was instead a lambda term? [...]<br>
><br>
> The trouble is that lambda abstractions are much more fragile than<br>
> constructor applications, in the sense that simple transformations<br>
> may make two abstractions look different although they have the<br>
> same value.<br>
<br>
Still, the difference this could make in a program of mine is so<br>
large that I am interested in exploring it anyway. I am wondering if<br>
anyone has investigated this possibility any further since the paper<br>
was published, or if anyone knows of other use cases that would<br>
benefit from this capability.<br>
<br>
Thanks,<br>
Alexis<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>