Fusing loops by specializing on functions with SpecConstr?

[Alexis King]

> On Apr 1, 2020, at 03:21, Sebastian Graf <sgraf1337 at gmail.com> wrote:
> 
> That is indeed true. But note that as long as you manage to inline `mapMaybeSF`, the final `runSF` will only allocate once on the "edge" of each iteration, all intermediate allocations will have been fused away. But the allocation of these non-sense records seems unfortunate.

Yes, that is technically true, but note that even if we inline mapMaybeSF, those nonsense records don’t go away, they just bubble up to the “fringe” of the enclosing computation. And consider how tiny mapMaybeSF is: I shudder to think how enormous that “fringe” would be for a large program written in SF!

(And of course, nothing prevents the runSF itself from appearing in a loop—quite probable, in fact, given its use in the hypothetical `lazy` combinator.)

> So this already seems quite brittle. Maybe a very targeted optimisation that gets rid of the boring ((), _) wrappers could be worthwhile, given that a potential caller is never able to construct such a thing themselves. But that very much hinges on being able to prove that in fact every such ((), _) constructed in the function itself terminates.

Yes, that is a good point. I concede that seems much less tractable than I had initially hoped.

Still, as you suggest, it does seem plausible that a different encoding could avoid this problem. I will experiment with a few different things and get back to you if I find anything interesting (assuming you don’t beat me to it first!).