12 ms·

The Hardest Program I've Ever Written – How a code formatter works (2015)

500 points by pcr910303 7y ago

jleahy 7y ago
To some degree he’s just rediscovered branch and bound, the classic way to solve NP hard problems like this. It’s a neat little trick. The other way of doing this would just be to formulate it as some kind of ILP and plug it into somebody else’s solver, quicker but there’s no way it’d work as well.
Groxx 7y ago
Previously: 2018: https://news.ycombinator.com/item?id=17271963 https://news.ycombinator.com/item?id=17271963 2017: https://news.ycombinator.com/item?id=15063193 https://news.ycombinator.com/item?id=15063193 2015: https://news.ycombinator.com/item?id=10195091 https://news.ycombinator.com/item?id=10195091 (shortly after it was written)
blumomo 7y ago
I can't help myself, the required semicolon at the end of each line in Dart programs keep hurting after writing for many years in Python, JS, Kotlin and Swift. I grew up semicolon-less with QBasic and learned semicolon since Delphi 1.0 and Java 1.0 but today, wanting as few noise on the screen as possible, they are hurting in my eyes.
- seanmcdirmid 7y ago
  Semicolons are just extra signal to humans and compilers, they shouldn’t hurt eyes like the use of fixed width fonts do.
  - jakear 7y ago
    It’s not that they hurt the eyes for me as much as they introduce tons of micro delays and extra keystrokes when editing. For instance, any “X to end of line” (cut, copy, etc), you now need to think about what the destination is and whether you should include the semi, change the selection, go back and delete the semi later, etc. It sounds slight, but it really builds up over time. Once you get used to “powerediting” without them it’s hard to go back.
    - seanmcdirmid 7y ago
      End of line inference algorithms are incredibly fragile, both by the compiler and by the human reader, having a semi-colon can make things clearer in the absence of another secondary signal (like indentation). There are so many type errors in scala or typescript that can be solved by adding a semicolon somewhere to eliminate some idiotic ambiguity.
      - tom_ 7y ago
        Why not infer the end of a line when finding the end of a line? ;) This is what most BASICs and assemblers did. (I think QBasic had a line continuation character? - or maybe that came with Visual BASIC. I don't remember. But, anyway, if you wanted, it was possible to continue a source line past a line break, it just wasn't the default.)
        seanmcdirmid 7y ago
        I’m all for that option also, and we can always add an anti semi colon to write a multi line statement.
      - jackewiehose 7y ago
        Only-EOL like python is fine and always-semicolon like C is fine. Sometimes-optional but sometimes-required semicolon like Javascript is bad in my experience. Javascripts C-like syntax doesn't cope well with missing semicolons
      - saagarjha 7y ago
        > End of line inference algorithms are incredibly fragile I am working on a language right now with optional semicolons (that is, newlines terminate statements unless there is a semicolon, which does the same early) and it’s not really that hard. The only change is that instead of looking for a newline character for statement termination I often also need to look for a semicolon.
        jakear 7y ago
- munificent 7y ago
  I'm the author of the post and work on the Dart language. I spent a bunch of time last year trying to figure out a good way to make semicolons optional in Dart without breaking a lot of stuff. Because of a handful of syntax quirks particular to Dart, it's really difficult. Most other languages that have optional semicolons were designed from the start to make them optional. Dart was not. On top of that it: * Uses C-style variable declarations which means there's no keyword to indicate the start of a variable declaration. * Likewise uses C syntax for function and even local function declarations. Again no keyword marking the beginning of a function. * Has complex syntax for things like function types which means a type annotation can be arbitarily long and may split over multiple lines. * Has lots of "contextual keywords" that are not true reserved words but behave like them only in certain contexts. * Has a rich syntax that overloads a lot of tokens to mean different things in different contexts. "{}" can be an empty map, empty set, empty block, empty function body, or empty lambda body. All of that makes optional semicolons just really difficult. I haven't given up entirely. We have a thing now called "language versioning" that lets different Dart libraries target different specific versions of the language. That lets us evolve the language in nominally "breaking" ways without actually breaking existing code. (For example, this is how we will migrate the world to non-nullable types.) That may give us a way to make other grammar simplifications that would then also let us make semicolons optional. But syntax changes like this are always difficult. People have very strong opinions about you changing their existing syntax under them, and the value proposition in return isn't super compelling. There's an old saying, the best time to plant a tree is twenty years ago. The second best time is today. Language syntax isn't always like that because the migration cost once you have a lot of extant code (and users) can just be too painful. The best time to make semicolons optional was twenty years ago. The next best time may be today, but it may just be never.
  - chubot 7y ago
    Could Dart use this solution, which Python uses and Oil shell now uses? 1. Newlines are significant tokens and they behave like semicolons (this is how shell is) 2. Within () [] {}, newlines are suppressed. The lexer has to recognize the matching pairs. (Oil added an expression language to shell which does this) This means that var x = 1 + 2 is not valid because there's a statement terminator after +, but var x = f(1 + 2) is valid. I feel like this captures the fast majority of cases where you want to break a statement over lines. I don't know Dart, but since it seems to have JavaScript-like syntax, I don't see why that wouldn't work? JavaScript has some weird rules, the common gotcha seems to be is: return { } // oops this does not return a dictionary like I thought With those rules you would write: return { } and hopefully the former is a syntax error, not a mis-parsed program. ---- edit: OK my guess is that Dart probably doesn't want to enforce a brace style like Go (and Oil) do? That is in Go only if (x) { } is valid, rather than if (x) { } which is pretty much like the 'return' example. I have been using that brace style for so long that I forgot other people don't :)
- pansa2 7y ago
  There are benefits to unambiguously marking the end of each statement with a semicolon rather than just using a newline. Is there a good algorithm for determining whether or not a newline actually represents the end of a statement? JavaScript gets this wrong in both directions, sometimes unexpectedly ending a statement (e.g. in `return \n 0`) and sometimes unexpectedly not ending one (e.g. when a new line begins with an open-parenthesis). Python's method (newline always ends a statement unless it's inside (), [] or {}) is straightforward, but makes the language syntax strictly line-based. This matches Python's significant indentation, but can it work in a language without it? Another option I've seen is for all newlines to end statements, unless they follow a token that cannot end a statement. Unfortunately that means that the following two assignments have different behavior: foo = bar + baz foo = bar + baz The first is a sum, the second only assigns `bar`, followed by a standalone unary `+` expression. Go works this way, but considers the second form to be an error ("+baz evaluated but not used"). Python considers both of these to be errors.
  - throwaway_pdp09 7y ago
    > There are benefits to... True, and these kinds of bikeshedding discussions about tiny details are infuriating because they're so irrelevant. I wish we could all rise above them to discuss the next level of expressibility. We let the little stuff suck up so much of or time.
wstrange 7y ago
The dart formatter is awesome - kudos to Bob. All languages should come with a highly opinionated formatter. It puts an end to useless style arguments.
- munificent 7y ago
  It doesn't really put an end to them, it just turns them from N×N arguments between each pair of programmers to N×1 where everyone argues with me, the formatter maintainer. But, yes, that's a significant performance win (for everyone except me...). :)
  - klodolph 7y ago
    I hear the author of Black (an opinionated Python formatter) was at a conference and gave a presentation that when something like this: > I'm the author of Black. Questions? Questions, of course, filled up the entire rest of the time slot.
  - anthonybullard 7y ago
    From my perspective at least, you've always handled it with grace. Thanks for your work Bob.
    - munificent 7y ago
      You're welcome! :)
- andrewzah 7y ago
  I didn't really understand this until I started using golang. Now I don't want to go back to other languages and have to deal with varying syntaxes and manually running a formatter.
  - thedance 7y ago
    What's a language that lacks such a facility? ClangFormat covers C/C++/Java/JavaScript/Objective-C/Protobuf/C#. gofmt obviously can do Go. buildifier will rewrite your Bazel BUILD files.
mholt 7y ago
I just rewrote our Caddy v2 Caddyfile formatter this week [1]. It's not as "smart" as a true code formatter, but what I thought would be just a 1 hour task ended up taking all day. And I'm lucky it wasn't longer! Lessons learned: - State is hard. There's something to be said for functional languages, or at least functional patterns. - The Caddyfile is a very theoretically-impure syntax. - User input is always messier than you think it will be. (Spend some time helping people on the forums, you'll see what I mean. I'm a neat freak though, so I notice it...) [1]: https://github.com/caddyserver/caddy/commit/7ee3ab7baa2165990d3fd358878d818154f7ee86 https://github.com/caddyserver/caddy/commit/7ee3ab7baa216599...
- pmarreck 7y ago
  > There's something to be said for functional languages, or at least functional patterns. Here’s my obligatory (and excellent) blog post by John Carmack where he adopts the functional style for a month: https://www.gamasutra.com/view/news/169296/Indepth_Functional_programming_in_C.php https://www.gamasutra.com/view/news/169296/Indepth_Functiona...
QuinnWilton 7y ago
Philip Wadler has a seminal paper [0] on implementing pretty printers by modeling them using an algebra. There's implementations of the algorithm in most programming languages nowadays, and some state of the art advances that help with performance [1] It's a very elegant algorithm, and is very pleasant to work. Elixir's formatter uses a variant of it [2], and it appears in the standard library [3]. I've personally made use of it to write a code formatter for GraphQL queries, and it was a very small amount of code for some powerful results. Definitely take a look if you ever need to do something like this. [0] https://homepages.inf.ed.ac.uk/wadler/papers/prettier/prettier.pdf https://homepages.inf.ed.ac.uk/wadler/papers/prettier/pretti... [1] https://jyp.github.io/pdf/Prettiest.pdf https://jyp.github.io/pdf/Prettiest.pdf [2] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.2200 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.2... [3] https://hexdocs.pm/elixir/Inspect.Algebra.html https://hexdocs.pm/elixir/Inspect.Algebra.html
- westoncb 7y ago
  I'm gonna take a look at Wadler's paper—but does anyone want to take a shot at a high-level description of how an algebra would be applicable to the problem of pretty printing? Any more general comments on applying algebras to solving programming problems would also be appreciated. My rough understanding of the benefits/rationale atm: 1) the algebra is a nice/minimal factoring of the problem 2) being able to formally classify it means we know a bunch of its properties, which tells us certain approaches are definitely (im)possible (and these properties are drawn from a fairly small set: e.g. associativity, distributivity, existence of inverses) 3) If the algebra is explicitly represented in code (maybe in a library), we can use that general structure to verify (and generate?) certain aspects of our particular problem solution. Edit: The paper mentions "Over the years, Richard Bird and others have developed the algebra of programming to a fine art" —and I found Bird's book "Algebra of Programming". Seems like what I'm looking for maybe, but would be grateful to hear of any alternative resources as well.
  - QuinnWilton 7y ago
    You'd likely be more interested in the original paper [0] by John Hughes that Wadler built off of. It gets into a ton more detail about the algebraic structure of the documents they're defining: > The question addressed in this paper is: how should libraries of combinators be designed? Our goal is to show how we can use formal specification of the combinators, and a study of their algebraic properties, to guide both the design and implementation of a combinator library. Our case study is a library for pretty-printing. But the methods we present are of wider applicability, and we also show how they can be used to develop a number of different monads. Wadler's paper touches upon some of the same ideas, but the primary goal of his paper is to build a prettier printer, whereas Hughes aimed to demonstrate the power of algebraic properties. [0] http://www.cse.chalmers.se/~rjmh/Papers/pretty.html http://www.cse.chalmers.se/~rjmh/Papers/pretty.html
vjeux 7y ago
I wrote a super short description of the overall architecture of prettier if people are interested: https://blog.vjeux.com/2017/javascript/anatomy-of-a-javascript-pretty-printer.html https://blog.vjeux.com/2017/javascript/anatomy-of-a-javascri...
- nojvek 7y ago
  Prettier is amazing. Thanks for building this tool. I’m not sure where you love but if you’re in Seattle or in the valley I would love to buy you a beverage of your choice sometime. I love the tool.
rattray 7y ago
Shameless plug that if you're bored and want a really tough, fun challenge, the prettier project has many open tickets: https://github.com/prettier/prettier/issues?q=is%3Aopen+is%3Aissue+label%3A%22help+wanted%22 https://github.com/prettier/prettier/issues?q=is%3Aopen+is%3... Only two are tagged "difficulty:easy", likely for good reason – when I contributed a few fixes a while back, I found it much more challenging than implementing a language syntax, an unrelated project which I was also doing at the same time. It's really fun, though, and watching colleagues code and use the features of prettier that you built is a nice feeling – "I helped write that code for you!"
qorrect 7y ago
I really don't like this guys writing style.
bmc7505 7y ago
If you enjoyed reading this, you might want to check out CodeBuff: https://github.com/antlr/codebuff https://github.com/antlr/codebuff CodeBuff is based on a paper by Terrence Parr and Juergen Vinju, “Towards a Universal Code Formatter through Machine Learning”: https://arxiv.org/abs/1606.08866 https://arxiv.org/abs/1606.08866
dfox 7y ago
10 years ago I though that writing S-expression pretty printer should be significantly easier than what the complexity of typical CL/Scheme pretty printer (ie. Waters' XP as described in AIM-1102) implies. Well that is not true ;) And since trying to do that I almost involuntarily format any code I write by rigorously applying the pretty printing algorithm of XP by combination of manual line breaks and Emacs' newline-and-indent.
jansan 7y ago
How do you indent block comments? Do they stay untouched? Do you indent them the same as the previous line? If so, what to do if there are already indents in the comment? Add the additional indent? I wrote a simple but IMHO really nice XML prettifier a while ago and remember that I finally gave up on block comments, because I could not find a way to handle all cases in a satisfying manner. So I decided to leave the indenting untouched.
- munificent 7y ago
  > How do you indent block comments? Do they stay untouched? Block comments are a little tricky and there are a handful of heuristics to handle them. Generally they stick to the preceding token. Block comments are rarely used in Dart and when they are, it's often just a small marker to describe the previous element like: foo(null /* missing */, blah); So adhering it to the previous token usually does the right thing. > If so, what to do if there are already indents in the comment? It doesn't touch the body of the comment itself. There's too many ways for that to go wrong given all of the various things a human might choose to stuff in there: ASCII art, tables, prose, etc.
sfvisser 7y ago
I never grasped why this is so hard, you don’t need an exponential blowup with some common sense heuristics. Just look at the AST and put the breaks as high up in the tree as possible. For example: If I have a function application with several arguments one of which is a slightly longer lambda expression, don’t even try to break the lambda before putting the arguments (nicely aligned) on their own line. I’m a big fan of the ergonomics of prettier, but some of its output is objectively ugly and seems the result of over-complicating their search space.
einpoklum 7y ago
The author of that post has it _so easy_! Formatting well-formed programs, in a young language with a short spec. He just starts with an AST! No no my friend. The challenge is when the program is _not_ well-formed, i.e. has errors, or worse yet - refers to to code elsewhere, so you can't even decide if it's well-formed or not. So no AST for you. You have to go into the dark and dangerous word of speculative and partial parsing of language grammars, representing ambiguity, replacing undefined, ambiguous or erroneously-defined semantics with deductions from the author's existing formatting and so on. That's where the real challenges lie. And - it's not gonna be 3,853 lines, I can tell you this much.
- eterm 7y ago
  I actually really like a "format on save; don't format without AST" combination. It's really nice knowing as soon as you hit ctrl+s whether you've just written in a syntax error or not.
  - klodolph 7y ago
    This is how I have Emacs set up, but when I use VS Code I really appreciate that syntax errors get the red squiggly underlines.
  - k__ 7y ago
    Yes, it's like people try to make more science of it than it really is...
  - saagarjha 7y ago
    I know that I’ve missed a delimiter when clang-format arbitrarily adds a level of indentation to the latter half of the file.
  - dmit 7y ago
    To see this concept taken to its logical conclusion, check out Casey Muratori write C code with the editor configured to reformat on every keystroke: https://www.youtube.com/watch?v=S3JutszP9fg&t=11m37s https://www.youtube.com/watch?v=S3JutszP9fg&t=11m37s I'm not sure I'd ever go this far, but that might just be years of conditioning by editors that format code much more slowly than the fork of 4coder that he's using in the video.
svat 7y ago
> Note that “best” is a property of the entire statement being formatted. A line break changes the indentation of the remainder of the statement, which in turn affects which other line breaks are needed. Sorry, Knuth. No dynamic programming this time. For what it's worth, the same is true of TeX's line-breaking algorithm too: “best” is a property of the entire paragraph being formatted; a line break can change the indentation of the remainder of the paragraph (in many ways, but most obviously: discretionary hyphens with nontrivial pre- and post- texts), which in turn affects which other line breaks are needed. And yet TeX uses dynamic programming. So it would be interesting to see how this specific problem differs. (Why dynamic programming works for TeX but not for dartfmt.) Perhaps Knuth chose a definition of "best" that is amenable to dynamic programming (after all he had quite a bit of freedom; it doesn't take much to beat the naive first-fit/best-fit line-breaking algorithms as used in Word etc), or perhaps TeX's algorithm too can be expensive but in practice paragraphs just tend to have a different distribution of feasible breakpoints than code statements. Knuth and Plass's (very readable!) paper on Breaking Paragraphs into Lines is here: http://www.eprg.org/G53DOC/pdfs/knuth-plass-breaking.pdf http://www.eprg.org/G53DOC/pdfs/knuth-plass-breaking.pdf Edit: Ah, I think one relevant difference is probably that when formatting code, one has to "match up" indentation with the previous corresponding sibling of the same nesting level, while with paragraphs the amount of required state is smaller: given a particular line break and indentation, the remainder of a paragraph can always be formatted in the same way, while a code formatter also has to "remember" all previous parent expressions' indentation. (This reason is different from what is directly implied by the quoted statement though…)
- gowld 7y ago
  The answer is in between the extremes. There are multiple choices of linebreaks that lead to the same indent level at char k, so dynamic programmins is still potentially useful.
  - munificent 7y ago
    Exactly right. The formatter does memoization so that if multiple different solutions end up putting the same subtree at the same level of indentation, that subtree itself is only calculated once.
crimsonalucard 7y ago
Why make a language and make a linter? Make the linter part of the language. In my opinion, there's no point in encoding certain concepts into a linter as best practice, if it's best practice encode it as law into the syntax of the language.
333c 7y ago
Footnote 4 [0] discusses the struggles of formatting comments. This was interesting to me because back in December I wrote most of a code formatter for Lox, the toy language from Crafting Interpreters [1], but I never finished it because I got caught up on how exactly to handle and represent comments, and then I got distracted by other projects. Does anyone else have thoughts on how to handle comments in a code formatter? Edit: Well, apparently this blog post (from 2015) is by the author of Crafting Interpreters. That makes this more interesting to me. [0]: http://journal.stuffwithstuff.com/2015/09/08/the-hardest-program-ive-ever-written/#4-note http://journal.stuffwithstuff.com/2015/09/08/the-hardest-pro... [1]: https://craftinginterpreters.com https://craftinginterpreters.com
eyegor 7y ago
I love that the author's final "gotcha" isn't even domain specific. It's a hard limit on recursion, just like all modern debuggers and most other formatting tools. It's crazy to me that they even tried to support formatting auto-generated code snippets, I know I personally would've created a much more naive/conservative bail out. > If the line splitter tries, like, 5,000 solutions and still hasn’t found a winner yet, it just picks the best it found so far and bails.
drelljones 7y ago
"Are You Looking For Professional Web Graphics and Images For Your Websites?" "You Have Found The Complete Source... Over 27,000 High Quality, Professional Web Graphics and Images That You Can Use Over and Over!" Tired Of Surfing Free Graphics Sites Searching For The Perfect Web Graphics? No More Searching, No More Hassles! You've Found The 450 Meg Ultimate Web Graphics Package And You Can Download This Immediately! https://tinyurl.com/sya3956 https://tinyurl.com/sya3956
pansa2 7y ago
I'm surprised it was necessary for the author to design and write Dart's formatter essentially from scratch. Is there not prior art - formatters for other languages that enforce a maximum line length? Also, I'm surprised that enforcing a maximum line length was considered so important that it was worth all this work. Even though I personally like to limit line lengths (and I know plenty of people who don't), I'm not sure enforcing such limits are worth this amount of complexity in the formatter, nor the sheer amount of labor required to implement and maintain that complexity. I think the sweet spot is probably Go's `gofmt` - automatic formatting that allows unlimited line lengths (possibly emitting a warning if formatted code exceeds a desired length) seems to provide almost all of the benefits of a formatter while being a much simpler solution.
nojvek 7y ago
I use prettier religiously. Works on js, typescript, jsx, css, json, html, sass, yaml and a whole bunch of others. The vscode prettier plugin brings format on save and it makes coding a joy. I think what prettier does is much simpler than dart. It tries to put things on a single line if it’s within line length, if it can’t then it uses multi line where each item is in its own line with ending bracket at same indentation level. For arrays, functions, object definitions, jsx etc. I’ve written some automated code generators that output pretty code and that’s how I tend to approach it too. You either get compact or expanded version and that happens recursively. There is some backtracking but there’s early exits when compact strategy exceeds line length so it’s pretty fast. After reading the blog article it put me off that starting and closing brackets were not at same indent level. I know lispers do this but I’m not used to it so it hurts my brain. One of my interview questions is to pretty print json files to a certain line length.
greggman3 7y ago
AFAIK no formatting can understand intent. Example. I want my canvas.drawImage calls that take 9 arguments to be formatted with arguments 2-5 on one line, and 6-9 on another line because 2-5 are sourceX, sourceY, sourceWidth, sourceHeight, and 6-9 are destX, destY, destWidth, destHeight. That's just one example of 100s where an auto formatter can not figure out intent. Another example, I often align numbers and width and height // convert from screen coords to clip space clipX = mouseX / screenWidth * 2 - 1 clipY = mouseY / screenHeight * -2 + 1 Another example would be how to format an if block. Depending on your style guide if (cond) single-statement might be ok. Or maybe you want them on different lines. Or maybe you require brackets. Or maybe you don't. But there will almost ways be some place in the code where an exception to your style guide makes the code more readable. Auto formatters don't understand those exceptions. This is why AFAIK many major projects do NOT use an auto-formatter. Firefox, Safari, Chrome for example. Because there are places where an auto-formatter will make the code far less readable. They'll give the advice that you are free to run an auto-formatter on your own changes but adding an automated one is a no-go. Even the Flutter team does not use an auto-formatter https://github.com/flutter/flutter/wiki/Style-guide-for-Flutter-repo#formatting https://github.com/flutter/flutter/wiki/Style-guide-for-Flut...
- biddlesby 7y ago
  It's a trade off. We've started using a code formatter recently: the overwhelming majority of the code in our team is more readable because it's so standardised. There are a few sub-optimal lines here and there but I wouldn't trade that for going back to the wild old days.
  - greggman3 7y ago
    The projects I mentioned above all have style guides. There's no "wild old days". They just don't use a auto formatter because they know there are cases where the auto formatter makes the code less readable and that there are exceptions to every style guide. It's called a style "guide" not a style "law" because it offers guidance which can be ignored when appropriate.
- faeyanpiraat 7y ago
nickysielicki 7y ago
Somewhere on my todo list is to make a systemverilog autoformatter using the parser from slang [1]. [1]: https://github.com/MikePopoloski/slang https://github.com/MikePopoloski/slang
frozenport 7y ago
>>If every statement fit within the column limit of the page, yup. It’s a piece of cake. could we just not do that?
coldcode 7y ago
The first program I ever wrote as a professional in the early 80's was a Jovial (before Ada what the Air Force used) prettyprinter written in Fortran. Hard to imagine now how little I knew yet still managed to get it to work (required for Air Force documentation) in about 6 months. I wish I still had the source code as that combo is nuts.
nemoniac 7y ago
XP: A Common Lisp Pretty Printing System http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.18.4464 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.18.4...
nojvek 7y ago
I wrote a simple formatter for outputting json values. It respects maximum line length. https://gist.github.com/nojvek/875d8cad1005da0b95da2840bbc894e6 https://gist.github.com/nojvek/875d8cad1005da0b95da2840bbc89... It implements some of the ideas from https://blog.vjeux.com/2017/javascript/anatomy-of-a-javascript-pretty-printer.html https://blog.vjeux.com/2017/javascript/anatomy-of-a-javascri... Could be re-used for other languages very easily. The core is you have nested group chunks with (indent breakpoint, dedent breakpoint, separator breakpoint, more text chunks and child group chunks). when formatting a single line, indent and dedunt breakpoints do nothing, but in multi line format, they specify how text will be laid out. The algorithm is simple, try to format in single line if it fits within maxLineLength, if not break into multiple lines, and do that recursively.

500 points by pcr910303 7y ago

To some degree he’s just rediscovered branch and bound, the classic way to solve NP hard problems like this. It’s a neat little trick. The other way of doing this would just be to formulate it as some kind of ILP and plug it into somebody else’s solver, quicker but there’s no way it’d work as well.

Groxx 7y ago

Previously: 2018: https://news.ycombinator.com/item?id=17271963 https://news.ycombinator.com/item?id=17271963 2017: https://news.ycombinator.com/item?id=15063193 https://news.ycombinator.com/item?id=15063193 2015: https://news.ycombinator.com/item?id=10195091 https://news.ycombinator.com/item?id=10195091 (shortly after it was written)

blumomo 7y ago

I can't help myself, the required semicolon at the end of each line in Dart programs keep hurting after writing for many years in Python, JS, Kotlin and Swift. I grew up semicolon-less with QBasic and learned semicolon since Delphi 1.0 and Java 1.0 but today, wanting as few noise on the screen as possible, they are hurting in my eyes.

seanmcdirmid 7y ago
Semicolons are just extra signal to humans and compilers, they shouldn’t hurt eyes like the use of fixed width fonts do.
- jakear 7y ago
  It’s not that they hurt the eyes for me as much as they introduce tons of micro delays and extra keystrokes when editing. For instance, any “X to end of line” (cut, copy, etc), you now need to think about what the destination is and whether you should include the semi, change the selection, go back and delete the semi later, etc. It sounds slight, but it really builds up over time. Once you get used to “powerediting” without them it’s hard to go back.
  - seanmcdirmid 7y ago
    End of line inference algorithms are incredibly fragile, both by the compiler and by the human reader, having a semi-colon can make things clearer in the absence of another secondary signal (like indentation). There are so many type errors in scala or typescript that can be solved by adding a semicolon somewhere to eliminate some idiotic ambiguity.
    - tom_ 7y ago
      Why not infer the end of a line when finding the end of a line? ;) This is what most BASICs and assemblers did. (I think QBasic had a line continuation character? - or maybe that came with Visual BASIC. I don't remember. But, anyway, if you wanted, it was possible to continue a source line past a line break, it just wasn't the default.)
      - seanmcdirmid 7y ago
        I’m all for that option also, and we can always add an anti semi colon to write a multi line statement.
    - jackewiehose 7y ago
      Only-EOL like python is fine and always-semicolon like C is fine. Sometimes-optional but sometimes-required semicolon like Javascript is bad in my experience. Javascripts C-like syntax doesn't cope well with missing semicolons
    - saagarjha 7y ago
      > End of line inference algorithms are incredibly fragile I am working on a language right now with optional semicolons (that is, newlines terminate statements unless there is a semicolon, which does the same early) and it’s not really that hard. The only change is that instead of looking for a newline character for statement termination I often also need to look for a semicolon.
      - jakear 7y ago
munificent 7y ago
I'm the author of the post and work on the Dart language. I spent a bunch of time last year trying to figure out a good way to make semicolons optional in Dart without breaking a lot of stuff. Because of a handful of syntax quirks particular to Dart, it's really difficult. Most other languages that have optional semicolons were designed from the start to make them optional. Dart was not. On top of that it: * Uses C-style variable declarations which means there's no keyword to indicate the start of a variable declaration. * Likewise uses C syntax for function and even local function declarations. Again no keyword marking the beginning of a function. * Has complex syntax for things like function types which means a type annotation can be arbitarily long and may split over multiple lines. * Has lots of "contextual keywords" that are not true reserved words but behave like them only in certain contexts. * Has a rich syntax that overloads a lot of tokens to mean different things in different contexts. "{}" can be an empty map, empty set, empty block, empty function body, or empty lambda body. All of that makes optional semicolons just really difficult. I haven't given up entirely. We have a thing now called "language versioning" that lets different Dart libraries target different specific versions of the language. That lets us evolve the language in nominally "breaking" ways without actually breaking existing code. (For example, this is how we will migrate the world to non-nullable types.) That may give us a way to make other grammar simplifications that would then also let us make semicolons optional. But syntax changes like this are always difficult. People have very strong opinions about you changing their existing syntax under them, and the value proposition in return isn't super compelling. There's an old saying, the best time to plant a tree is twenty years ago. The second best time is today. Language syntax isn't always like that because the migration cost once you have a lot of extant code (and users) can just be too painful. The best time to make semicolons optional was twenty years ago. The next best time may be today, but it may just be never.
- chubot 7y ago
  Could Dart use this solution, which Python uses and Oil shell now uses? 1. Newlines are significant tokens and they behave like semicolons (this is how shell is) 2. Within () [] {}, newlines are suppressed. The lexer has to recognize the matching pairs. (Oil added an expression language to shell which does this) This means that var x = 1 + 2 is not valid because there's a statement terminator after +, but var x = f(1 + 2) is valid. I feel like this captures the fast majority of cases where you want to break a statement over lines. I don't know Dart, but since it seems to have JavaScript-like syntax, I don't see why that wouldn't work? JavaScript has some weird rules, the common gotcha seems to be is: return { } // oops this does not return a dictionary like I thought With those rules you would write: return { } and hopefully the former is a syntax error, not a mis-parsed program. ---- edit: OK my guess is that Dart probably doesn't want to enforce a brace style like Go (and Oil) do? That is in Go only if (x) { } is valid, rather than if (x) { } which is pretty much like the 'return' example. I have been using that brace style for so long that I forgot other people don't :)
pansa2 7y ago
There are benefits to unambiguously marking the end of each statement with a semicolon rather than just using a newline. Is there a good algorithm for determining whether or not a newline actually represents the end of a statement? JavaScript gets this wrong in both directions, sometimes unexpectedly ending a statement (e.g. in `return \n 0`) and sometimes unexpectedly not ending one (e.g. when a new line begins with an open-parenthesis). Python's method (newline always ends a statement unless it's inside (), [] or {}) is straightforward, but makes the language syntax strictly line-based. This matches Python's significant indentation, but can it work in a language without it? Another option I've seen is for all newlines to end statements, unless they follow a token that cannot end a statement. Unfortunately that means that the following two assignments have different behavior: foo = bar + baz foo = bar + baz The first is a sum, the second only assigns `bar`, followed by a standalone unary `+` expression. Go works this way, but considers the second form to be an error ("+baz evaluated but not used"). Python considers both of these to be errors.
- throwaway_pdp09 7y ago
  > There are benefits to... True, and these kinds of bikeshedding discussions about tiny details are infuriating because they're so irrelevant. I wish we could all rise above them to discuss the next level of expressibility. We let the little stuff suck up so much of or time.

wstrange 7y ago

The dart formatter is awesome - kudos to Bob. All languages should come with a highly opinionated formatter. It puts an end to useless style arguments.

munificent 7y ago
It doesn't really put an end to them, it just turns them from N×N arguments between each pair of programmers to N×1 where everyone argues with me, the formatter maintainer. But, yes, that's a significant performance win (for everyone except me...). :)
- klodolph 7y ago
  I hear the author of Black (an opinionated Python formatter) was at a conference and gave a presentation that when something like this: > I'm the author of Black. Questions? Questions, of course, filled up the entire rest of the time slot.
- anthonybullard 7y ago
  From my perspective at least, you've always handled it with grace. Thanks for your work Bob.
  - munificent 7y ago
    You're welcome! :)
andrewzah 7y ago
I didn't really understand this until I started using golang. Now I don't want to go back to other languages and have to deal with varying syntaxes and manually running a formatter.
- thedance 7y ago
  What's a language that lacks such a facility? ClangFormat covers C/C++/Java/JavaScript/Objective-C/Protobuf/C#. gofmt obviously can do Go. buildifier will rewrite your Bazel BUILD files.

mholt 7y ago

I just rewrote our Caddy v2 Caddyfile formatter this week [1]. It's not as "smart" as a true code formatter, but what I thought would be just a 1 hour task ended up taking all day. And I'm lucky it wasn't longer! Lessons learned: - State is hard. There's something to be said for functional languages, or at least functional patterns. - The Caddyfile is a very theoretically-impure syntax. - User input is always messier than you think it will be. (Spend some time helping people on the forums, you'll see what I mean. I'm a neat freak though, so I notice it...) [1]: https://github.com/caddyserver/caddy/commit/7ee3ab7baa2165990d3fd358878d818154f7ee86 https://github.com/caddyserver/caddy/commit/7ee3ab7baa216599...

pmarreck 7y ago
> There's something to be said for functional languages, or at least functional patterns. Here’s my obligatory (and excellent) blog post by John Carmack where he adopts the functional style for a month: https://www.gamasutra.com/view/news/169296/Indepth_Functional_programming_in_C.php https://www.gamasutra.com/view/news/169296/Indepth_Functiona...

QuinnWilton 7y ago

Philip Wadler has a seminal paper [0] on implementing pretty printers by modeling them using an algebra. There's implementations of the algorithm in most programming languages nowadays, and some state of the art advances that help with performance [1] It's a very elegant algorithm, and is very pleasant to work. Elixir's formatter uses a variant of it [2], and it appears in the standard library [3]. I've personally made use of it to write a code formatter for GraphQL queries, and it was a very small amount of code for some powerful results. Definitely take a look if you ever need to do something like this. [0] https://homepages.inf.ed.ac.uk/wadler/papers/prettier/prettier.pdf https://homepages.inf.ed.ac.uk/wadler/papers/prettier/pretti... [1] https://jyp.github.io/pdf/Prettiest.pdf https://jyp.github.io/pdf/Prettiest.pdf [2] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.2200 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.2... [3] https://hexdocs.pm/elixir/Inspect.Algebra.html https://hexdocs.pm/elixir/Inspect.Algebra.html

westoncb 7y ago
I'm gonna take a look at Wadler's paper—but does anyone want to take a shot at a high-level description of how an algebra would be applicable to the problem of pretty printing? Any more general comments on applying algebras to solving programming problems would also be appreciated. My rough understanding of the benefits/rationale atm: 1) the algebra is a nice/minimal factoring of the problem 2) being able to formally classify it means we know a bunch of its properties, which tells us certain approaches are definitely (im)possible (and these properties are drawn from a fairly small set: e.g. associativity, distributivity, existence of inverses) 3) If the algebra is explicitly represented in code (maybe in a library), we can use that general structure to verify (and generate?) certain aspects of our particular problem solution. Edit: The paper mentions "Over the years, Richard Bird and others have developed the algebra of programming to a fine art" —and I found Bird's book "Algebra of Programming". Seems like what I'm looking for maybe, but would be grateful to hear of any alternative resources as well.
- QuinnWilton 7y ago
  You'd likely be more interested in the original paper [0] by John Hughes that Wadler built off of. It gets into a ton more detail about the algebraic structure of the documents they're defining: > The question addressed in this paper is: how should libraries of combinators be designed? Our goal is to show how we can use formal specification of the combinators, and a study of their algebraic properties, to guide both the design and implementation of a combinator library. Our case study is a library for pretty-printing. But the methods we present are of wider applicability, and we also show how they can be used to develop a number of different monads. Wadler's paper touches upon some of the same ideas, but the primary goal of his paper is to build a prettier printer, whereas Hughes aimed to demonstrate the power of algebraic properties. [0] http://www.cse.chalmers.se/~rjmh/Papers/pretty.html http://www.cse.chalmers.se/~rjmh/Papers/pretty.html

vjeux 7y ago

I wrote a super short description of the overall architecture of prettier if people are interested: https://blog.vjeux.com/2017/javascript/anatomy-of-a-javascript-pretty-printer.html https://blog.vjeux.com/2017/javascript/anatomy-of-a-javascri...

nojvek 7y ago
Prettier is amazing. Thanks for building this tool. I’m not sure where you love but if you’re in Seattle or in the valley I would love to buy you a beverage of your choice sometime. I love the tool.

rattray 7y ago

Shameless plug that if you're bored and want a really tough, fun challenge, the prettier project has many open tickets: https://github.com/prettier/prettier/issues?q=is%3Aopen+is%3Aissue+label%3A%22help+wanted%22 https://github.com/prettier/prettier/issues?q=is%3Aopen+is%3... Only two are tagged "difficulty:easy", likely for good reason – when I contributed a few fixes a while back, I found it much more challenging than implementing a language syntax, an unrelated project which I was also doing at the same time. It's really fun, though, and watching colleagues code and use the features of prettier that you built is a nice feeling – "I helped write that code for you!"

qorrect 7y ago

I really don't like this guys writing style.

bmc7505 7y ago

If you enjoyed reading this, you might want to check out CodeBuff: https://github.com/antlr/codebuff https://github.com/antlr/codebuff CodeBuff is based on a paper by Terrence Parr and Juergen Vinju, “Towards a Universal Code Formatter through Machine Learning”: https://arxiv.org/abs/1606.08866 https://arxiv.org/abs/1606.08866

dfox 7y ago

10 years ago I though that writing S-expression pretty printer should be significantly easier than what the complexity of typical CL/Scheme pretty printer (ie. Waters' XP as described in AIM-1102) implies. Well that is not true ;) And since trying to do that I almost involuntarily format any code I write by rigorously applying the pretty printing algorithm of XP by combination of manual line breaks and Emacs' newline-and-indent.

jansan 7y ago

How do you indent block comments? Do they stay untouched? Do you indent them the same as the previous line? If so, what to do if there are already indents in the comment? Add the additional indent? I wrote a simple but IMHO really nice XML prettifier a while ago and remember that I finally gave up on block comments, because I could not find a way to handle all cases in a satisfying manner. So I decided to leave the indenting untouched.

munificent 7y ago
> How do you indent block comments? Do they stay untouched? Block comments are a little tricky and there are a handful of heuristics to handle them. Generally they stick to the preceding token. Block comments are rarely used in Dart and when they are, it's often just a small marker to describe the previous element like: foo(null /* missing */, blah); So adhering it to the previous token usually does the right thing. > If so, what to do if there are already indents in the comment? It doesn't touch the body of the comment itself. There's too many ways for that to go wrong given all of the various things a human might choose to stuff in there: ASCII art, tables, prose, etc.

sfvisser 7y ago

I never grasped why this is so hard, you don’t need an exponential blowup with some common sense heuristics. Just look at the AST and put the breaks as high up in the tree as possible. For example: If I have a function application with several arguments one of which is a slightly longer lambda expression, don’t even try to break the lambda before putting the arguments (nicely aligned) on their own line. I’m a big fan of the ergonomics of prettier, but some of its output is objectively ugly and seems the result of over-complicating their search space.

einpoklum 7y ago

The author of that post has it _so easy_! Formatting well-formed programs, in a young language with a short spec. He just starts with an AST! No no my friend. The challenge is when the program is _not_ well-formed, i.e. has errors, or worse yet - refers to to code elsewhere, so you can't even decide if it's well-formed or not. So no AST for you. You have to go into the dark and dangerous word of speculative and partial parsing of language grammars, representing ambiguity, replacing undefined, ambiguous or erroneously-defined semantics with deductions from the author's existing formatting and so on. That's where the real challenges lie. And - it's not gonna be 3,853 lines, I can tell you this much.

eterm 7y ago
I actually really like a "format on save; don't format without AST" combination. It's really nice knowing as soon as you hit ctrl+s whether you've just written in a syntax error or not.
- klodolph 7y ago
  This is how I have Emacs set up, but when I use VS Code I really appreciate that syntax errors get the red squiggly underlines.
- k__ 7y ago
  Yes, it's like people try to make more science of it than it really is...
- saagarjha 7y ago
  I know that I’ve missed a delimiter when clang-format arbitrarily adds a level of indentation to the latter half of the file.
- dmit 7y ago
  To see this concept taken to its logical conclusion, check out Casey Muratori write C code with the editor configured to reformat on every keystroke: https://www.youtube.com/watch?v=S3JutszP9fg&t=11m37s https://www.youtube.com/watch?v=S3JutszP9fg&t=11m37s I'm not sure I'd ever go this far, but that might just be years of conditioning by editors that format code much more slowly than the fork of 4coder that he's using in the video.

svat 7y ago

> Note that “best” is a property of the entire statement being formatted. A line break changes the indentation of the remainder of the statement, which in turn affects which other line breaks are needed. Sorry, Knuth. No dynamic programming this time. For what it's worth, the same is true of TeX's line-breaking algorithm too: “best” is a property of the entire paragraph being formatted; a line break can change the indentation of the remainder of the paragraph (in many ways, but most obviously: discretionary hyphens with nontrivial pre- and post- texts), which in turn affects which other line breaks are needed. And yet TeX uses dynamic programming. So it would be interesting to see how this specific problem differs. (Why dynamic programming works for TeX but not for dartfmt.) Perhaps Knuth chose a definition of "best" that is amenable to dynamic programming (after all he had quite a bit of freedom; it doesn't take much to beat the naive first-fit/best-fit line-breaking algorithms as used in Word etc), or perhaps TeX's algorithm too can be expensive but in practice paragraphs just tend to have a different distribution of feasible breakpoints than code statements. Knuth and Plass's (very readable!) paper on Breaking Paragraphs into Lines is here: http://www.eprg.org/G53DOC/pdfs/knuth-plass-breaking.pdf http://www.eprg.org/G53DOC/pdfs/knuth-plass-breaking.pdf Edit: Ah, I think one relevant difference is probably that when formatting code, one has to "match up" indentation with the previous corresponding sibling of the same nesting level, while with paragraphs the amount of required state is smaller: given a particular line break and indentation, the remainder of a paragraph can always be formatted in the same way, while a code formatter also has to "remember" all previous parent expressions' indentation. (This reason is different from what is directly implied by the quoted statement though…)

gowld 7y ago
The answer is in between the extremes. There are multiple choices of linebreaks that lead to the same indent level at char k, so dynamic programmins is still potentially useful.
- munificent 7y ago
  Exactly right. The formatter does memoization so that if multiple different solutions end up putting the same subtree at the same level of indentation, that subtree itself is only calculated once.

crimsonalucard 7y ago

Why make a language and make a linter? Make the linter part of the language. In my opinion, there's no point in encoding certain concepts into a linter as best practice, if it's best practice encode it as law into the syntax of the language.

333c 7y ago

Footnote 4 [0] discusses the struggles of formatting comments. This was interesting to me because back in December I wrote most of a code formatter for Lox, the toy language from Crafting Interpreters [1], but I never finished it because I got caught up on how exactly to handle and represent comments, and then I got distracted by other projects. Does anyone else have thoughts on how to handle comments in a code formatter? Edit: Well, apparently this blog post (from 2015) is by the author of Crafting Interpreters. That makes this more interesting to me. [0]: http://journal.stuffwithstuff.com/2015/09/08/the-hardest-program-ive-ever-written/#4-note http://journal.stuffwithstuff.com/2015/09/08/the-hardest-pro... [1]: https://craftinginterpreters.com https://craftinginterpreters.com

eyegor 7y ago

I love that the author's final "gotcha" isn't even domain specific. It's a hard limit on recursion, just like all modern debuggers and most other formatting tools. It's crazy to me that they even tried to support formatting auto-generated code snippets, I know I personally would've created a much more naive/conservative bail out. > If the line splitter tries, like, 5,000 solutions and still hasn’t found a winner yet, it just picks the best it found so far and bails.

drelljones 7y ago

"Are You Looking For Professional Web Graphics and Images For Your Websites?" "You Have Found The Complete Source... Over 27,000 High Quality, Professional Web Graphics and Images That You Can Use Over and Over!" Tired Of Surfing Free Graphics Sites Searching For The Perfect Web Graphics? No More Searching, No More Hassles! You've Found The 450 Meg Ultimate Web Graphics Package And You Can Download This Immediately! https://tinyurl.com/sya3956 https://tinyurl.com/sya3956

pansa2 7y ago

I'm surprised it was necessary for the author to design and write Dart's formatter essentially from scratch. Is there not prior art - formatters for other languages that enforce a maximum line length? Also, I'm surprised that enforcing a maximum line length was considered so important that it was worth all this work. Even though I personally like to limit line lengths (and I know plenty of people who don't), I'm not sure enforcing such limits are worth this amount of complexity in the formatter, nor the sheer amount of labor required to implement and maintain that complexity. I think the sweet spot is probably Go's `gofmt` - automatic formatting that allows unlimited line lengths (possibly emitting a warning if formatted code exceeds a desired length) seems to provide almost all of the benefits of a formatter while being a much simpler solution.

nojvek 7y ago

I use prettier religiously. Works on js, typescript, jsx, css, json, html, sass, yaml and a whole bunch of others. The vscode prettier plugin brings format on save and it makes coding a joy. I think what prettier does is much simpler than dart. It tries to put things on a single line if it’s within line length, if it can’t then it uses multi line where each item is in its own line with ending bracket at same indentation level. For arrays, functions, object definitions, jsx etc. I’ve written some automated code generators that output pretty code and that’s how I tend to approach it too. You either get compact or expanded version and that happens recursively. There is some backtracking but there’s early exits when compact strategy exceeds line length so it’s pretty fast. After reading the blog article it put me off that starting and closing brackets were not at same indent level. I know lispers do this but I’m not used to it so it hurts my brain. One of my interview questions is to pretty print json files to a certain line length.

greggman3 7y ago

AFAIK no formatting can understand intent. Example. I want my canvas.drawImage calls that take 9 arguments to be formatted with arguments 2-5 on one line, and 6-9 on another line because 2-5 are sourceX, sourceY, sourceWidth, sourceHeight, and 6-9 are destX, destY, destWidth, destHeight. That's just one example of 100s where an auto formatter can not figure out intent. Another example, I often align numbers and width and height // convert from screen coords to clip space clipX = mouseX / screenWidth * 2 - 1 clipY = mouseY / screenHeight * -2 + 1 Another example would be how to format an if block. Depending on your style guide if (cond) single-statement might be ok. Or maybe you want them on different lines. Or maybe you require brackets. Or maybe you don't. But there will almost ways be some place in the code where an exception to your style guide makes the code more readable. Auto formatters don't understand those exceptions. This is why AFAIK many major projects do NOT use an auto-formatter. Firefox, Safari, Chrome for example. Because there are places where an auto-formatter will make the code far less readable. They'll give the advice that you are free to run an auto-formatter on your own changes but adding an automated one is a no-go. Even the Flutter team does not use an auto-formatter https://github.com/flutter/flutter/wiki/Style-guide-for-Flutter-repo#formatting https://github.com/flutter/flutter/wiki/Style-guide-for-Flut...

biddlesby 7y ago
It's a trade off. We've started using a code formatter recently: the overwhelming majority of the code in our team is more readable because it's so standardised. There are a few sub-optimal lines here and there but I wouldn't trade that for going back to the wild old days.
- greggman3 7y ago
  The projects I mentioned above all have style guides. There's no "wild old days". They just don't use a auto formatter because they know there are cases where the auto formatter makes the code less readable and that there are exceptions to every style guide. It's called a style "guide" not a style "law" because it offers guidance which can be ignored when appropriate.
faeyanpiraat 7y ago

nickysielicki 7y ago

Somewhere on my todo list is to make a systemverilog autoformatter using the parser from slang [1]. [1]: https://github.com/MikePopoloski/slang https://github.com/MikePopoloski/slang

frozenport 7y ago

>>If every statement fit within the column limit of the page, yup. It’s a piece of cake. could we just not do that?

coldcode 7y ago

The first program I ever wrote as a professional in the early 80's was a Jovial (before Ada what the Air Force used) prettyprinter written in Fortran. Hard to imagine now how little I knew yet still managed to get it to work (required for Air Force documentation) in about 6 months. I wish I still had the source code as that combo is nuts.

nemoniac 7y ago

XP: A Common Lisp Pretty Printing System http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.18.4464 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.18.4...

nojvek 7y ago

I wrote a simple formatter for outputting json values. It respects maximum line length. https://gist.github.com/nojvek/875d8cad1005da0b95da2840bbc894e6 https://gist.github.com/nojvek/875d8cad1005da0b95da2840bbc89... It implements some of the ideas from https://blog.vjeux.com/2017/javascript/anatomy-of-a-javascript-pretty-printer.html https://blog.vjeux.com/2017/javascript/anatomy-of-a-javascri... Could be re-used for other languages very easily. The core is you have nested group chunks with (indent breakpoint, dedent breakpoint, separator breakpoint, more text chunks and child group chunks). when formatting a single line, indent and dedunt breakpoints do nothing, but in multi line format, they specify how text will be laid out. The algorithm is simple, try to format in single line if it fits within maxLineLength, if not break into multiple lines, and do that recursively.