The Hardest Program I've Ever Written (2015)

&quot;If it took that much thrashing to get it right, you’d expect it to do something pretty deep right? Maybe a low-level hardware interface or .. I’m talking, of course, about an automated code formatter.&quot;<p>This reminds me of the Tao of Programming 3.3, at <a href="http:&#x2F;&#x2F;www.mit.edu&#x2F;~xela&#x2F;tao.html" rel="nofollow">http:&#x2F;&#x2F;www.mit.edu&#x2F;~xela&#x2F;tao.html</a> , the relevant part of which I will copy here:<p>There was once a programmer who was attached to the court of the warlord of Wu. The warlord asked the programmer: &quot;Which is easier to design: an accounting package or an operating system?&quot;<p>&quot;An operating system,&quot; replied the programmer.<p>The warlord uttered an exclamation of disbelief. &quot;Surely an accounting package is trivial next to the complexity of an operating system,&quot; he said.<p>&quot;Not so,&quot; said the programmer, &quot;When designing an accounting package, the programmer operates as a mediator between people having different ideas: how it must operate, how its reports must appear, and how it must conform to the tax laws. By contrast, an operating system is not limited by outside appearances. When designing an operating system, the programmer seeks the simplest harmony between machine and ideas. This is why an operating system is easier to design.&quot;

Pretty-printing is tough. That said, please don&#x27;t reinvent the wheel. There is research that has gone into this that should make most of this stuff pretty straightforward. I personally recommend Wadler&#x27;s &quot;A Prettier Printer&quot; [0] (although credit goes to Hughes for laying a lot of the groundwork [1]). It too uses an IR and has several possible heuristics for rendering.<p>I&#x27;ve been using an implementation of it [2] with a lot of success for pretty printing Rust code [3].<p><pre><code> [0]: https:&#x2F;&#x2F;homepages.inf.ed.ac.uk&#x2F;wadler&#x2F;papers&#x2F;prettier&#x2F;prettier.pdf [1]: http:&#x2F;&#x2F;belle.sourceforge.net&#x2F;doc&#x2F;hughes95design.pdf [2]: https:&#x2F;&#x2F;hackage.haskell.org&#x2F;package&#x2F;prettyprinter [3]: https:&#x2F;&#x2F;github.com&#x2F;harpocrates&#x2F;language-rust</code></pre>

It sounds like perhaps a case of being so focused on whether the program <i>could</i> be built that they didn&#x27;t stop to ask whether it <i>should</i> be built.<p>Automatic code formatters don&#x27;t need to be perfect or complete; they simply must format <i>good</i> code well. If bad code (as many of the difficult examples were) formats poorly, that&#x27;s just another reason for people to write better code.

I wrote a pretty-printer for bash scripts using PHP. Colouring the keywords was fun, but I moved on to other personal projects instead of tackling line breaks.<p>More recently I&#x27;ve been trying to learn Chinese, and one of the features of Pingtype is to put spaces between words.<p><a href="http:&#x2F;&#x2F;pingtype.github.io" rel="nofollow">http:&#x2F;&#x2F;pingtype.github.io</a><p>To my surprise, this article linked to a Wikipedia page about line wrapping, which says that line wrapping in CJK is unsolved.<p><a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Line_wrap_and_word_wrap#Word_wrapping_in_text_containing_Chinese.2C_Japanese.2C_and_Korean" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Line_wrap_and_word_wrap#Word_w...</a><p>&quot;Most existing word processors and typesetting software cannot handle either [personal names or compound words].&quot;<p>My method works, but I don&#x27;t know who to give it to. This is Hacker News and there&#x27;s people from all different backgrounds here, so I&#x27;ll just throw it out there - if anyone is interested, please contact me.

Why do you necessarily need a line limit?<p>I would simply indent all chained function calls and be done with it. Eg.<p><pre><code> return foo(param) .then(bar) .catch(err =&gt; { logger.error(err); return -1; });</code></pre>

One of my side project was an auto formatter for R. There are some limits in existing formatters:<p>- I think most of them doesn&#x27;t recognize multi line string literals, which is difficult if you consider the case that you can have &quot;&quot; in comments, comment symbol in &quot;&quot; string literals and line breaks. The only way to deal with it is to scan linearly with context.<p>- It&#x27;s tricky to wrap a long line: + some points in a long line are more suitable for breaking points in logic level + but sometimes you want less lines and not to break too often, even it&#x27;s more clear in logic. The lines could be just some parameter list that will be both well represented in one column or multi columns. + with nested code the natural indent position could be at the far right, which make each line very short if you stick to 80 columns rule.<p>After quite some efforts my code can deal with all the comments, multi line strings, all the operators I known (I need to separate unary and binary operators to determine whether to insert space), but the script take several seconds to run, and I haven&#x27;t start to deal with indent. I probably can save some time if I do more optimization, but I don&#x27;t have time to finish it now.<p>This python formatter talked about its algorithm, worth a read.<p><a href="https:&#x2F;&#x2F;github.com&#x2F;google&#x2F;yapf" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;google&#x2F;yapf</a>

Cool post. Some insight into why this problem is so hard: what this post is describing seems to be an integer linear programming problem [1]. I.e. optimizing a linear cost function constrained by (convex) linear bounds with integer-valued variables. The reason it&#x27;s so difficult is that ILP is an NP-hard problem. Finding the right way to represent program source is also tricky, but, as the post says, doing so in a way that caters to the extremely performance-sensitive solver code is the really difficult bit. A better approach might be to produce an explicit ILP program and use an ILP solver to decide where the line breaks should go. As with many NP-hard problems (e.g. SAT, TSP), there are very good solvers these days that are much faster than anything you could ever hope to write yourself – and they produce fully optimal solutions.<p>[1] <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Integer_programming" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Integer_programming</a>

&gt; <i>There are thirteen places where a line break is possible here according to our style rules. That’s 8,192 different combinations if we brute force them all</i><p>This is why the language should be designed with a formatter in mind from the beginning, as Go was designed. Just enough mustaches to make formatters accurate and fast. How many possibilities should there be? Exactly one.

<i>&quot;There are thirteen places where a line break is possible here according to our style rules. That’s 8,192 different combinations if we brute force them all. The search space we have to cover is exponentially large...&quot;</i><p>Sounds like this might be a good candidate for some AI methods which are not intimidated by such large search spaces.

I remember this coming up before :) <a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=10195091" rel="nofollow">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=10195091</a><p>ninja edit: I mostly jump remembered the picture of Robert with his&#x2F;a dog and the text, “Hi! I&#x27;m Bob Nystrom, the one on the left.”

&gt; That means adding line breaks (or “splits” as the formatter calls them), and determining the best place to add those is famously hard.<p>Naive question here: What is so hard? It can be solved with dynamic programming, right? Doesn&#x27;t he even link to solutions of the problem?

<a href="http:&#x2F;&#x2F;suckless.org&#x2F;philosophy" rel="nofollow">http:&#x2F;&#x2F;suckless.org&#x2F;philosophy</a>

Please mark with (2015).