Opened 11 months ago

Last modified 8 months ago

#9496 new task

Simplify primitives for short cut fusion

Reported by: dfeuer Owned by: dfeuer
Priority: lowest Milestone:
Component: Core Libraries Version: 7.8.3
Keywords: fusion Cc: hvr, ekmett, core-libraries-committee@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Other Test Case:
Blocked By: Blocking:
Related Tickets: Differential Revisions:

Description

Currently, there appear to be two production primitives, build and augment (although I may have missed some). There are multiple consumption primitives (at least: foldr, head, and, or, any, and all). The rule sets for some producers seem to forget to handle augment, and the augment/augment rule is omitted as "true, but not, I think, useful".

A number of other functions are instead rewritten into foldr forms, and then written back if they don't fuse.

What to do:

Personally, I'd be very tempted to start by saying build g = augment g [] (or possibly even build g = extend [] g [] if I can ever get that idea to work) and cut the problem in half. The main problem I see with this is if other people are importing GHC.Exts or GHC.Base, writing things with build, and expecting them to fuse. One way to deal with this, perhaps, is to hack a special rule into the RULES compiler to recognize GHC.Base.build on the LHS of RULES and replace it with the appropriate augment form, emitting a warning.

Where to go after that: the question remains whether it's best in general to rewrite a form to foldr to make it fuse, or to fuse directly with augment. The answer presumably depends, at least in part, on whether there are additional foldr-based rules we may want to add that would take advantage of the effort put into the translation back from the foldr form. I would conjecture that most such rules we could want would go beyond what the RULES system actually can do. That said, if we can find a way to use foldr forms without the horrible pain of translating back from them, that would be a very good thing.

Change History (5)

comment:1 Changed 11 months ago by dfeuer

  • Owner set to dfeuer

comment:2 follow-up: Changed 11 months ago by simonpj

I believe that there are good reasons for distinguishing build and augment. Andy Gill's thesis would be a good place to look. But perhaps one could do everything in terms of augment; I'm not sure. Worth a try.

I think there is really only one primitive consumer, foldr. I thought we rewrote into foldr and then back. If that is not done for or, any, etc, I'm not sure why. Again, perhaps worth investigation.

Certainly the original goal of the foldr/build paper was to say "ONE rule, not n*m rules".

Simon

comment:3 in reply to: ↑ 2 Changed 11 months ago by dfeuer

Replying to simonpj:

I believe that there are good reasons for distinguishing build and augment. Andy Gill's thesis would be a good place to look. But perhaps one could do everything in terms of augment; I'm not sure. Worth a try.

I think there is really only one primitive consumer, foldr. I thought we rewrote into foldr and then back. If that is not done for or, any, etc, I'm not sure why. Again, perhaps worth investigation.

Certainly the original goal of the foldr/build paper was to say "ONE rule, not n*m rules".

Simon

An aside: Just last night I saw a bit of the work Takano Akio has done on incorporating a worker/wrapper transformation into the framework (although I don't quite understand how it works yet). It doesn't seem to be quite ready for prime time (there were apparently some issues with one NoFib benchmark), but we might want to keep it in mind.

I think the one rule concept is great. If that can be made to really work, that would be ideal. Unfortunately, the need to wrangle the inliner as it currently works turns the one rule concept into an n*m-rule concept, where m is certainly at least 1, but currently 2 (the rewrite back rule clearly seems necessary for now—I don't yet understand things deeply enough to know for sure if the rewrite to rule is strictly necessary in all cases). I would speculate that the and/or/any/head/... rules came about because someone thought to themselves "There's only one [sic] producer, build, so we can skip this difficult and invasive rewrite to/from process and just fuse with build. That's easy!" Well, they were a little wrong, but I'm not sure they were very wrong.

I haven't had a chance to read the thesis yet, but from a purely practical perspective, I don't see any difference between build g and augment g []. I don't think anyone's tossing around partially applied augments or anything.

Last edited 11 months ago by dfeuer (previous) (diff)

comment:4 Changed 9 months ago by thoughtpolice

  • Component changed from libraries/base to Core Libraries

Moving over to new owning component 'Core Libraries'.

comment:5 Changed 8 months ago by dfeuer

  • Cc core-libraries-committee@… added
  • Milestone set to
  • Priority changed from normal to lowest

Duncan Coutts doesn't seem to think this is really a problem, per se. It even has an advantage: we avoid speculative rewrites that can be bad.

Note: See TracTickets for help on using tickets.