Re: [Haskell-cafe] Pretty Printing Libraries with an Emphasis on Consistency

Yes, hindent is exponential in its pretty printing and that's exactly the
program I'm trying to speed up ;) To be specific, hindent has `sandbox`
which runs a printer and then lets me make decisions on what the resulting
state might be. I'm curious if there are other approaches.
- ocharles
On Sat, Oct 11, 2014 at 12:01 PM, Alan & Kim Zimmerman
Have you looked at hindent? On 11 Oct 2014 11:52 AM, "Oliver Charles"
wrote: Hi all,
It seems that all of the pretty printing libraries on Hackage at the moment have an emphasis on being compact, but not necessarily consistent. By consistent, I mean that similar blocks of code are indented in the same fashion, even when not strictly necessary.
Take for example, the start of "Pretty Printing with Lazy Dequeues". Here, the example is:
if True then if True then True else True else if False then False else False
I call this inconsistent, because the two sides of the top-level if have been formatted under different rules. A consistent formatting of this would be:
if True then if True then True else True else if False then False else False
The above can obviously be reached if you *always* format `if` in this style, but that's not what I'm after. If it's possible to format both sides on one-line, then that should be preferred. So an equally desirable output (that meets my "consistency" requirement) is:
if True then if True then True else True else if True then True else True
It doesn't seem that there is a library on Hackage that lets one express such a pretty printer. It seems that a pretty printer of this nature would need to have some sort of backtracking ability - I can imagine trying to print both sides of the if statement on one-line, and if this fails, try printing *both* on multiple lines.
Curious to hear what people have to say on this matter, - ocharles
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Oliver Charles wrote:
Yes, hindent is exponential in its pretty printing and that's exactly the program I'm trying to speed up ;) To be specific, hindent has `sandbox` which runs a printer and then lets me make decisions on what the resulting state might be. I'm curious if there are other approaches.
I wager you need some kind of context-freeness to pretty print efficiently. At least, Wadler's pretty printer [1] makes use of that in section 2, where he argues that you can efficiently choose a minimal element in a huge set of possible layouts, the latter being represented by the type `Doc`. [1]: http://homepages.inf.ed.ac.uk/wadler/papers/prettier/prettier.pdf If you allow non-context free restrictions on the possible layouts, as you do, then it's no longer clear to me how to efficiently pick an optimal one. To see whether this is a hard problem, you may want to do to the following test: Formalize (a subset of) the restrictions that you want to allow and check whether the problem is NP complete, i.e. whether you can encode solutions to an NP complete problem (knapsack?) as solutions of your desired layout algorithm. Best regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com

On 11 October 2014 18:00, Oliver Charles
Yes, hindent is exponential in its pretty printing and that's exactly the program I'm trying to speed up ;) To be specific, hindent has `sandbox` which runs a printer and then lets me make decisions on what the resulting state might be. I'm curious if there are other approaches.
Indeed, it's slow to backtrack like that. For what it's worth, one trick to speed that up is if the resulting state is OK, then just `put` that state and continue with it, rather than throwing away a rendered result. I doubled the speed of my style like that. But yeah, it's not much consolation. If you compare with the "Fundamental" style: that can pretty print a 60-line function I have here instantly, it takes no time, but my "ChrisDone" style takes over 50 seconds and counting. So there's a massive cost to this, but I haven't profiled it yet or attempted any real optimizations yet (been too busy). Perhaps that can be next on my todo list. Another thing to consider is to turn off this branching of "this style or that style" after a certain depth. Sort of "prune" the results to be smaller. The deeper down the tree, the fewer branches it could make, for example. I haven't tried this, but it could be nice. Good luck! If you find a similarly expressive and faster way to do this I'm all ears. :-)

I'm not sure if it is relevant, but in HaRe (or rather
haskell-token-utils), I use the dual-tree structure from diagrams. This
allows you to push constraints down from the top, but then build the
formatting up from the bottom, and you only need to look at one level at a
time. So effectively you format the leaves, then move up a level and format
there, and so on.
On Tue, Oct 14, 2014 at 12:51 AM, Christopher Done
On 11 October 2014 18:00, Oliver Charles
wrote: Yes, hindent is exponential in its pretty printing and that's exactly the program I'm trying to speed up ;) To be specific, hindent has `sandbox` which runs a printer and then lets me make decisions on what the resulting state might be. I'm curious if there are other approaches.
Indeed, it's slow to backtrack like that. For what it's worth, one trick to speed that up is if the resulting state is OK, then just `put` that state and continue with it, rather than throwing away a rendered result. I doubled the speed of my style like that. But yeah, it's not much consolation.
If you compare with the "Fundamental" style: that can pretty print a 60-line function I have here instantly, it takes no time, but my "ChrisDone" style takes over 50 seconds and counting. So there's a massive cost to this, but I haven't profiled it yet or attempted any real optimizations yet (been too busy). Perhaps that can be next on my todo list.
Another thing to consider is to turn off this branching of "this style or that style" after a certain depth. Sort of "prune" the results to be smaller. The deeper down the tree, the fewer branches it could make, for example. I haven't tried this, but it could be nice.
Good luck! If you find a similarly expressive and faster way to do this I'm all ears. :-)
participants (4)
-
Alan & Kim Zimmerman
-
Christopher Done
-
Heinrich Apfelmus
-
Oliver Charles