Optimized rendering function for infinite band width case

[bgamari]

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]

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

[adinapoli]

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

[bgamari]

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]

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]

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]

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]

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:

• Type
• Layout algorithm

[adinapoli]

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