search

haskell / pretty

Haskell Pretty-printer library
Other
69 stars 30 forks source link

Optimized rendering function for infinite band width case #44

Open bgamari opened 7 years ago

bgamari commented 7 years ago

In the case of rendering for an infinite band width we needn't do any layout (e.g. backtracking) at all. Providing a rendering function which optimizes for this case should improve performance in these cases considerably. In particular GHC would benefit greatly from this as it uses pretty to produce large quantities of assembler code.

bgamari commented 7 years ago

@adinapoli I think you were interested in picking this up.

adinapoli commented 7 years ago

Hey Ben, indeed I am! Do you have any pointers on where I should start looking? 😉

bgamari commented 7 years ago

Hey Ben, indeed I am! Do you have any pointers on where I should start looking? 😉

I have only vague recollections of when I briefly looked into this. Sadly, I seem to remember that the way the library is currently structured makes the change a bit invasive. Namely, there are a few points where we do layout during AST construction. Looking briefly at the code, I think aboveNest is one such culprit.

You may want to take inspiration from ansi-wl-pprint, which provides the sort of combinator discussed here (which it calls renderCompact). Note that ansi-wl-pprint actually provides two distinct document types: Doc and SimpleDoc (pretty actually has a somewhat similar distinction internally, but it isn't manifest in the types).

I think this approach of having a "cheap" AST, with a set of interpreters to do layout to produce in simpler AST is a good one. Doing this in pretty is a significant surgery, but I think it shouldn't be hard. Simply add the constructors to Doc to represent the cases where we currently do layout during AST construction, introduce a SimpleDoc type reflecting the "normalized" AST, and implement the interpreter to convert the former into the latter. After that is done, writing an inefficient infinite-ribbon interpreter should be easy.

bgamari commented 7 years ago

To clarify, note that the AST of pretty will look a bit different from that in ansi-wl-pprint as they use different pretty-printing algorithms (apologies if that was obvious). Nevertheless, the general idea of "staged" ASTs should carry over without any trouble

adinapoli commented 7 years ago

Thanks Ben, this is quite useful and more than I hoped! It looks like I need to finally delve into the guts of pretty and actually understand what I'm doing 😁

bgamari commented 7 years ago

Alfredo Di Napoli notifications@github.com writes:

Thanks Ben, this is quite useful and more than I hoped! It looks like I need to finally delve into the guts of pretty and actually understand what I'm doing 😁

Indeed, I think that reading through the Hughes paper (and perhaps the Wadler paper which ansi-wl-pprint is based on) would be a great place to start.

quchen commented 7 years ago

For what it’s worth, I modified the WL prettyprinting algorithm in my own prettyprinter library to allow infinite page width. It comes down to basically a Maybe (Width, RibbonFrac) type that the layout algorithm takes into account. It works well! :-)

Relevant source:

adinapoli commented 7 years ago

Awesome! I think that having this reference implementation will really help.