The Hardest Program I've Ever Written (2015) | Hacker News Reader

The Hardest Program I've Ever Written (2015)

journal.stuffwithstuff.com

303 pointstosh76 comments

I read this before working on prettier and it was a bit scary to be honest :)

I wasn’t convinced that the exhaustive approach with weigths was a good idea. It makes it computationally super intensive and hard to predict what the printer would do.

Instead prettier runs on a simple idea: if something doesn’t fit in one line, break the outermost parent.

This simple rule (implemented via the Wadler IR) is efficient to implement and makes the output generally look good.

Then the hard part was to go through the very looong (took me ~6 months full time) process of adding special cases for every constructs that human write in a special way.

There is nothing in there that’s hard at a computer science level, it’s just a lot of special cases. I don’t believe that there’s a general solution for it, you just need to slog through it.

And the last annoying thing are comments, they can be everywhere and are super annoying to print correctly.

Overall, it wasn’t really hard, but a lot of work.

First, thanks for putting the work in on prettier! It's a great tool, and it's helping a lot of devs & teams.

I find your approach much more reasonable than the one outlined in the article, which to me feels like complexity for complexity's sake. There might be some minor win to breaking lines by analyzing billions of possibilities, but it just seems like overkill, and it's certainly not predictable for the programmer.

As another alternative, gofmt solved it a different way, by not having a limit on line length. I haven't seen it add line breaks at all.

gofmt took a different approach where it respects the author's line breaks. So the following are all going to remain as is with gofmt:

    f(a, b)
    f(
      a, b)
    f(a,
      b,
    )
    f(a,
      b)
    f(
      a,
      b,
    )

My original motivation for prettier was this particular example where I was sick of having to add/remove all those newlines when the line would go below or above 80 columns. So prettier only allows the following two forms and will format code for you as you save:

    f(a, b)
    f(
      a,
      b,
    )

Well okay, but this raises the question of why code needs to always fit within 80 columns. The Go developers decided that it doesn't, and it's fine to check in the code as-is.

(In particular, automatic refactoring tools don't need to wrap lines when they get longer.)

And everything seems to have worked out fine.

It's not the only way to do it, but I think it's interesting how getting everyone to agree that a problem doesn't need solving sometimes simplifies things a lot.

If you do code reviews and your code reviewers take thier role seriously, and so will push back with comments like “this is hard to read, consider breaking it into two lines” then you don’t need automated enforcement. But if code reviewers look for sufficient units tests, obvious errors, and then dash off a LGTM, software style enforcement is second best.

In practice, this doesn't come up in review and Go code is quite readable anyway. Apparently people just don't need much help to get line lengths more or less right.

You want to break --at some point--. The question is, who decides where to break? For gofmt, they decided that the person writing the code is going to make this decision everywhere. For prettier, we decided that the tool was going to make that decision, so that the humans don't have to.

If we want to do it automatically, we need to figure out an algorithm to do that. It turns out that if you use 80 columns as a heuristic, the vast majority of the code will look fine. A lot of people (myself included) tried to use different algorithms but couldn't beat that heuristic.

If you know of a better way, please let me know :)

> It turns out that if you use 80 columns as a heuristic, the vast majority of the code will look fine.

I'm not sure what corpus was used to determine that heuristic (nor what tab size). But it would trash a lot the projects I work on.

Are these projects still JS?

I was speaking in general, I don't have any dart projects which I believe is what the OP is about. I do have JS projects that I think would be rather ugly if limited to 80 char line length is that is what you are asking.

Yeah, I mean the project is specific to JS so not do relevant to consider other languages here

The goal of prettier is not to format code exactly as you would have written but to format it in a reasonable way.

The upside is that as a developer you don’t need to worry about formatting yourself as you can just write code in a bad way, save the file and it’s formatted. And as a team, you will no longer spend any time in code review arguing about formatting and doing roundtrips to change small nits.

If the result is good enough that you are willing to let go of your manual formatting, the upsides are nontrivial.

> [..] why code needs to always fit within 80 columns.

Optimal text width for readability is 4-6 inches or (typically) 50-75 characters. Code, with its indented nature, tends to fit nicely within this if you keep to the 80 column rule.

I would just have it raise an error or warning, but maybe that's me. My first questions when a problem starts to spiral are "Do we really need to solve this problem? And if so, do we really need to solve it right now?"

Is this the paper describing Walder IR you referred to?

https://homepages.inf.ed.ac.uk/wadler/papers/prettier/pretti...

Yes! If you want something less mathematical, you can read the explanation of the various commands: https://github.com/prettier/prettier/blob/master/commands.md

> I wasn’t convinced that the exhaustive approach with weigths was a good idea. It makes it computationally super intensive and hard to predict what the printer would do.

Yes, you are right on both accounts. I'm still not entirely sure it's the right approach for dartfmt.

I started with a corpus of code that was hand-formatted by people who I felt had great style. And then I worked backwards to figure out what kinds of formatting mechanics I would need to be able to automate that.

Unfortunately, there are some very common formatting idioms in Dart that really just don't play nice with any simpler formalism. For example, it's common to use embedded function literals as if they were blocks:

    group("test some stuff", () {
      test("test a thing with a very long"
          "multi-line description of the thing being tested", () {
        expect(thing, isSomeThing);
      });
    });

Note here how the body of the innermost function literal does not respect the surrounding expression nesting, even though it is technically all an argument to test().

But in other cases, a function parameter should work like a normal indented expression:

    things
        .map((thing) {
          ...
        })
        .where((thing) => thing.isFoo);
        .toList();

I probably could have said, "Well, these idioms are going away and this code will look different." and then designed a much simpler formatter. A huge part of software engineering is picking the right problem to solve and knowing when to push against requirement and when to take them as given.

For dartfmt, I did my best to keep the original requirements even thought it meant a much more complex formatter. That made my implementation job harder. But it made the political job of convincing everyone inside Google (and most users outside) to use dartfmt much easier because the output was closer to what they wanted.

> For dartfmt, I did my best to keep the original requirements even thought it meant a much more complex formatter. That made my implementation job harder. But it made the political job of convincing everyone inside Google (and most users outside) to use dartfmt much easier because the output was closer to what they wanted.

I couldn't have said it better :)

I added a ton of special cases in the step that takes an AST and outputs the IR to handle those two things (and many many more).

For 1), I special case functions that look like `test(` and completely ignore the 80 column rule so that the name stays in one line. https://github.com/prettier/prettier/blob/3e0dceda9954658860...

For 2), member chains is actually the most complex piece of prettier, but it was important to get right. There's plenty of comments in the implementation: https://github.com/prettier/prettier/blob/3e0dceda9954658860...

I'm sure you did something similar as well :)

Yes! There is a whole separate class just to handle formatting method chains:

https://github.com/dart-lang/dart_style/blob/master/lib/src/...

Hm... It took me a good minute to understand what you're talking about with those two examples, because apparently my mental model is different than yours.

For me, the indentation rules for those two examples are identical, because of a different rule: the adjacent-string concatenation means the two editor lines are one conceptual line.

Pretty printers are hard.

    "We sat down one morning," recalls Steele. "I was at
    the keyboard, and he was at my elbow," says Steele.
    "He was perfectly willing to let me type, but he was
    also telling me what to type. 

    The programming session lasted 10 hours. Throughout
    that entire time, Steele says, neither he nor Stallman
    took a break or made any small talk. By the end of the
    session, they had managed to hack the pretty print
    source code to just under 100 lines. "My fingers were
    on the keyboard the whole time," Steele recalls, "but
    it felt like both of our ideas were flowing onto the
    screen. He told me what to type, and I typed it." 

   The length of the session revealed itself when Steele
   finally left the AI Lab. Standing outside the building
   at 545 Tech Square, he was surprised to find himself
   surrounded by nighttime darkness. As a programmer,
   Steele was used to marathon coding sessions. Still,
   something about this session was different. Working with
   Stallman had forced Steele to block out all external
   stimuli and focus his entire mental energies on the task
   at hand. Looking back, Steele says he found the Stallman
   mind-meld both exhilarating and scary at the same
   time. "My first thought afterward was: it was a great
   experience, very intense, and that I never wanted to do
   it again in  my life."  - Guy Steele

Heck! to get a taste one can take a stab at writing a formatter for printing a floating point number.

Hah! Yes.

I recently did a coding test for a job where one of the tasks was to write a formatter for Dutch license plates. Typically these are in the format XX-99-YY, but there are... exceptions. At first glance it seems like it won't be too hard. But it ended up sucking up something like half of the whole coding test time.

I did beat it, with a lot of help from unit tests, but formatting is indeed a tougher problem than you'd expect.

https://en.wikipedia.org/wiki/Vehicle_registration_plates_of... is complex, indeed, but I don’t see how formatting would be difficult. How do they store those, other than as the formatted string?

Parsing/validity checking, on the other hand, could be cumbersome.

I'm assuming "formatting" means "inserting hyphens in the correct place".

Based on the examples in that Wikipedia page, it looks like the correct rule is to insert a hyphen between a letter and a digit that are adjacent, or in the middle of a group of 4 letters or 4 digits. But maybe there are other edge cases where that fails.

If you require the output to be the shortest possible (e.g. 0.1+0.11 should print as “0.21”, not as “0.21000000000000002”) and to have your output round-trip (if you read in what you printed, you get back the number you printed) I would think printing floating point numbers is harder than writing a pretty-printer.

Pretty-printers have the advantage never being finished, as there always are cases where some people would say “I would format that differently”. That’s an advantage because it also means you can declare any version that works decently “finished”. For formatting floats, it’s much more black or white. Your formatter either works or it is buggy.

The first working formatter for floating point numbers is from 1980, IIRC, and doing it correctly only became somewhat the expected case after Steelers 1990 paper (https://lists.nongnu.org/archive/html/gcl-devel/2012-10/pdfk...)

> and to have your output round-trip

Unless you're simply talking about round-trip within the application itself, that's not possible.

It is possible, and most reasonable format systems guarantee it. Javascript guarantees that parseFloat(x.toString()) === x for any fp number x. The same extends to JSON formatting. Python guarantees that eval(str(x)) == x.

That's because Javascript doesn't print out the shortest possible output.

OP's requirement is that the output for 0.1 + 0.11 is displayed as 0.21, and that the output survives a round-trip. Your example satisfies the latter but not the former.

Another example, more specialized than the others given, is MIT Scheme: IIRC it guarantees that when you READ back a float written by WRITE, you get the same float back, bit for bit.

Getting a floating point number printed "exactly" (as in with full precision, not necessarily what people expect) is not very hard; the tricky part is, as you mention, having the shortest possible representation and rounding it correctly, as well as making it efficient.

You need to find the shortest number that’s closer to your target float than any other float. Then to go the other direction you just find the nearest float.

It's interesting to notice after a concentrated session, how little you managed to do.

Programming is fun, but sometimes it seems like you're cutting a tree down with a knife.

...except you have this magic wand that can sometimes turn the tree into small patch of grass if you know the correct words... In my experience if it's difficult, then the approach is probably wrong.

That is an amazing story I have never read earlier and we are talking about Steele and Stallman.

Between, I want to read more. Source of this story please?

Its from here https://www.oreilly.com/openbook/freedom/ch06.html

Speaking of pretty printing, here is a copy of that quote made readable for mobile devices. (Don't use leading spaces to format quotes on HN, it doesn't work well.)

> "We sat down one morning," recalls Steele. "I was at the keyboard, and he was at my elbow," says Steele. "He was perfectly willing to let me type, but he was also telling me what to type.

> The programming session lasted 10 hours. Throughout that entire time, Steele says, neither he nor Stallman took a break or made any small talk. By the end of the session, they had managed to hack the pretty print source code to just under 100 lines. "My fingers were on the keyboard the whole time," Steele recalls, "but it felt like both of our ideas were flowing onto the screen. He told me what to type, and I typed it."

> The length of the session revealed itself when Steele finally left the AI Lab. Standing outside the building at 545 Tech Square, he was surprised to find himself surrounded by nighttime darkness. As a programmer, Steele was used to marathon coding sessions. Still, something about this session was different. Working with Stallman had forced Steele to block out all external stimuli and focus his entire mental energies on the task at hand. Looking back, Steele says he found the Stallman mind-meld both exhilarating and scary at the same time. "My first thought afterward was: it was a great experience, very intense, and that I never wanted to do it again in my life." - Guy Steele

Thanks! If you’re thinking about reposting broken quotes, just do it. A lot of people browse HN on mobile and will be happy to see that.

> (Don't use leading spaces to format quotes on HN, it doesn't work well.)

I hear you. It does suck on small screens.

But that's exactly what the leading space syntax is for -- to markup quotes. It works fine tablet/laptop/netbook etc but I hear that smaller form factors is a problem.

I think the right solution is to fix the layout so that it works form mobile. Not using the markup that's specially intended for quotes seems a wrong way of going about it.

> "But that's exactly what the leading space syntax is for -- to markup quotes"

Per the HN docs, leading spaces are meant for code, not quotes.

> "Text after a blank line that is indented by two or more spaces is reproduced verbatim. (This is intended for code.)"

https://news.ycombinator.com/formatdoc

HN doesn't have specific formatting for quotes. Many people use leading '>' along with quotation marks and italics to set off quoted text.

Ah I see, I got it wrong.

No worries, it's an easy mistake to make. The formatting options on HN are pretty meager: two leading spaces (not four like Markdown) for block code, asterisks for emphasis. So it's natural that people try to make do with what's available.

I don't mind, I get a lot of upvotes for posting those mobile friendly quotes. Just call me the Quote Fixer Bot. ;-)

Markdown recognizes the > quote convention and puts the text in a <blockquote> so it can be styled, typically indented a bit with a vertical bar on the left. I wish HN did that too!

A convention that is often used for quotes here is to both use the > and italicize them, like this:

  > *You can quote me on this.*

which renders as:

> You can quote me on this.

This is especially useful when you are interspersing quotes with your own text, as grzm did above. I can't make up my mind which I like better for longer multi-paragraph quotes: the italics make it look more like a quote, but I find long stretches of italic text harder to read.

The leading greater than is the old usenet and mailing list convention. With multiple greater thans for deeper levels of quotes. There wasn’t italics but people used to surround words with stars or underscores for emphasis.

You are too patient and kind.

I can't even imagine a 10 hour coding session without breaks.

The longest I did was 5 hours for ACM ICPC kind of stuff, but that left me wasted.

The code for this pretty print "@" was online[0] at one point but the site was never captured by archive.org.

[0] https://people.csail.mit.edu/gregs/ll1-discuss-archive-html/...

Reminds me of Steve Yegge's introduction of js2-mode, a new JavaScript mode for Emacs, and how hard it was to get its indentation right:

Amazingly, surprisingly, counterintuitively, the indentation problem is almost totally orthogonal to parsing and syntax validation. I'd never have guessed it. But for indentation you care about totally different things that don't matter at all to parsers. Say you have a JavaScript argument list: it's just (blah, blah, blah): a paren-delimited, comma-separated, possibly empty list of identifiers. Parsing that is pretty easy. But for indentation purposes, that list is rife with possibility!

http://steve-yegge.blogspot.com/2008/03/js2-mode-new-javascr...

> It reads in a string and writes out a string.

That’s usually where a lot of the hard problems lie, in my experience. Parsers, compilers, interpreters, sanitizers, and of course formatters are always a deep dive into formal language theory, where the limits are often fundamental rather than technical and you have to make tradeoffs to get a solution that works well.

The hardest thing I ever wrote was an inliner for a language I made myself.

You'd think it is a simple problem, but soon you will have a rabid animal on a leash and you will be struggling to restrain it.

I gave the source to a friend who modified it a bit and commited it to a language that was mentioned a couple of times on HN in the early days. It has since been replaced, but was used for a good 5 years.

Can you expand on some of the problems?

I was going to write an inliner for a Lisp I was working on for a couple years. Emacs seems to have a decent one. But I know there are tricky corner cases.

Writing a simple inliner isn't too bad, writing a good one is hard. Let's pretend you just "copy/paste" the code into place, there's the question of deciding when/if to copy/paste the code in -- what heuristic do you use. Now there's constant propagation, possibly more doing dead code (from constant propagation), dependency reanalysis (because you've changed the basic block, possibly adding more basic blocks). There are reasons the resultant code could even be less efficient (register pressure for locals for the inline code comes to mind), and there's i-cache complexities that come from blowing up your code size.

Inlining is really hard.

nappy-doo answered the question very well. One thing that should be mentioned is that a bad inliner actually removes information that might be useful for future optimisations.

Reading the inliners of languages like chez scheme or ghc is enough to give me a hardon.

  return doughnutFryer
    .start()
    .then((_) => _frostingGlazer.start())
    .then((_) => Future.wait([
          _conveyorBelts.start(),
          sprinkleSprinkler.start(),
          sauceDripper.start()
        ]))
  ...
  ...

> (The funny names are because this was sanitized from internal code.)

And for about 3 seconds I was really excited to learn more about who wrote this code!

I really hope the author did some research. There is a very old work from Derek Oppen that has been adapted to the functional world later. The principles sound very similar to the OP's approach. It would be a shame if so much work went into reinventing the wheel...

I read once that this is the difference between research and hacking. Research is about researching related work and the field and ensuring that we’re not re-inventing the wheel. Hacking is about writing code as fast as possible.

A good software engineer should be able to do both of them successfully.

Yes, I read a few papers and poked around the source of gofmt, clang-format and a couple of others. They weren't as helpful as I'd hoped, but I got a few ideas from them here and there. Most of the implementation of a formatter is grunt-work stuff that's fairly specific to the grammar of the input language, the style rules it's trying to apply, and the weird vagaries of whatever parser or lexer you're using. There isn't that much I found I could take away from them.

The most useful research I did was actually around graph search algorithms. Branch-and-bound and most of the other stock pathfinding algorithms didn't work, but they gave me the pieces I needed to get to something that did.

Dynamic programming and memoization was key too. I got to use so many fundamental data structures and algorithms in this program. It was a joy.

I know this is a stupid question, and please forgive me for asking it... but just how wide do monitors need to get or how high do resolutions need to go before longer lines become reasonable?

It's not about monitor size or resolution - text just gets hard to read once lines exceed a certain width, because the eye starts losing track of which line it's on as it sweeps from the end of one line to the start of the next. That's true for prose as well as code - and code has the additional complexity of having to keep track of possibly-deeply-nested paired pieces of syntax (parentheses, braces etc); that part can be made easier with indentation, but not if everything's on one line.

Wider screens still have their advantages even if you keep your text narrow, mind - when you want to display multiple things side-by-side; the halves of a diff, or your code & a reference, for example.

With a larger monitor I'd use the additional space for another document or window.

> Yes, I really did brute force all of the combinations at first. It let me focus on getting the output correct before I worried about performance.

The programmer spoke correctly.

Not nearly as difficult, but I recently did a large project on converting Erlang Dialyzer output into Elixir friendly output in the Dialyxir[0] project, which involved a lot of lexing and parsing and pretty printing, though I was fortunately able to take advantage of the Elixir code formatter for a lot of the heavy lifting for output. My grammar rules, while better than they've been, are still pretty bad, but they seem to work well enough in practice for most programs that I've seen.

The tl;dr for that project is that it runs dialyzer, finds the relevant Warning module for each warning, which will pretty print parts of the error output into a larger explanation, which involves taking the output, lexing it, parsing it, then pretty printing the IR back into Elixir, then running through the formatter.

[0] https://github.com/jeremyjh/dialyxir

I hope we can have a library for this kind of formatting so each new $hotlanguage can have $hotlanguagefmt easily..

Speaking of hot new languages, check out ArnoldC https://github.com/lhartikk/ArnoldC

There's an effort to make a plugin system for Prettier so that it can format languages other than JS and company. See https://prettier.io/docs/en/plugins.html

On reading this, does it seem like the language parser itself should demand that the code is formatted correctly, rather than relying on a separate tool to format the code? I.e. incorrectly formatted code would be a syntax error.

That way all this hard work is off-loaded on human brains. They'll complain a bit but in practice will pick up very quickly where the line-breaks go.

(This would probably have to be a decision made by the language designers from the outset.)

Couldn't you start from Dart's BNF grammar, create a BNF grammar of "formatted" Dart and then format the code accordingly?

You could, but in reality it won't work very well due to recursive rules.

Maybe. If you think of the formatted output as a grammar that includes whitespace, you'll probably discover it is very context-sensitive. Then determining what context to synthesize when making the translation is probably more or less equivalent to how you'd otherwise write the formatter.

i'm a regular reader of this blog; there's always something non-obvious (at least to me) plus just really fine, fine writing--eg,

"Some Dart users really dig a functional style and appear to be playing a game where whoever crams the most work before a single semicolon wins."

sort of the Dave Eggers of software engineering

> you’d expect it to do something pretty deep right? ... Nope. It reads in a string and writes out a string.

If an optimizing compiler takes in a program decides to spit out the executable in a string (in base-64 format) which can later be converted to binary, using xxd for example, that makes the optimizing compiler "not pretty deep"?

Automated code formatting is fairly deep as far as I'm concerned.

sounds like a case of bruteforcing a simple task with a pile of hacks.

can't imagine why all that mess is saner then putting a pretty printer on the other end of the language parser.

also this mess will be extremely non deterministic, depending on machine speed etc

Side tangent:

He mentioned the algorithm questions he had to study to pass the interview and that knowing the algorithms came in handy.

If you are interviewing for Google, Facebook, Amazon, or Netflix, etc. solving problems that have never been solved at thier scale, algorithm questions are important.

If you just want someone to right the next software as a service CRUD app, don't waste my time.

Speaking as a former Googler, many (most?) Googlers never work on complex algorithms at huge scale. The interview questions are often completely irrelevant to their work.

Do you think that even at Google the algorithm questions are useless and shouldn’t be asked? I was trying to give Google the benefit of the doubt.

"At Google" is such a broad category that no single answer suffices. For anyone working on the hot-path of search/ads/knowledge graph back-end, sure, they need to know their algorithms. Same for the language teams like Nystrom is on. For a front-end engineer, which is what I was at Google (exclusively in Dart fwiw)? Probably not. I implemented a graph traversal exactly once.

However, Google uses the same interview process for all software engineers, and mostly decides what job they will do after deciding whether to hire them. So they really can't tailor their questions without changing their entire process. I think they should change it, but I understand why they haven't.

Reply on news.ycombinator.com