11 ms·
The Hardest Program I've Ever Written
- jcizzle 11y agoHuh, I thought the 'Reformat to Dart Style' option in IntelliJ was using dartfmt and I was so disappointed at its output I stopped using it. Just went and tried dartfmt from the command line after reading this - dartfmt is significantly better. Fun to hear the approach that went into it. For anyone that hasn't tried it, grab the Dart SDK and the IntellIJ Dart plugin. Takes less than 5 minutes to setup. It's been a great platform for building server side stuff - I haven't tried it for front end web stuff. It took about 3 reads of the language tour (https://www.dartlang.org/docs/dart-up-and-running/ch02.html https://www.dartlang.org/docs/dart-up-and-running/ch02.html) and about a week and I already felt very comfortable with the entire platform.
- munificent 11y ago> Just went and tried dartfmt from the command line after reading this - dartfmt is significantly better. \o/ It improved a lot in the past two months. That's when rules and the new splitter landed.
- ridiculous_fish 11y agoThanks for writing this, it was a great read! I maintain a source beautifier too [1], and it's not as nice as I would like. One of the issues I run into is that the correct indent on a broken line is context dependent. For example: while (someReallyReallyReallyReallyLongFunction() && anotherLongFunction()) { loopBody(); } is a nicer indenting than: while (someReallyReallyReallyReallyLongFunction() && anotherLongFunction()) { loopBody(); } In the first case, the two conditions are aligned which makes the code clearer. Does dartfmt handle this? If not, do you have ideas on how it might? Also, how does it handle invalid input? I may want to reindent my code before it's correct. Also, did you explore constraint solvers instead of a graph traversal? It seems like they would be a natural fit. [1]: fish_indent, https://github.com/fish-shell/fish-shell/blob/master/src/fish_indent.cpp https://github.com/fish-shell/fish-shell/blob/master/src/fis...
- sklogic 11y agoFor this sort of things I'm using an intermediate language (guess it's similar to what OP is talking about) with stack semantics: there are instructions like "PUSHINDENT", 'POPINDENT" and "INCINDENT" - with PUSHINDENT inserted after '(' in ifs, function calls, etc. - ensuring that if line breaks before the POP instruction, indentation would reflect the context. So, the biggest problem is in assigning weights to the break candidate instructions is this stream. This can only be done by a lot of experimenting, I could not find any formal method or a passable heuristic.
- vog 11y agoIn that specific case, isn't it better style to write it differently anyway? Either: conditionWithReadableName: function() { return someReallyReallyReallyReallyLongFunction() && anotherLongFunction(); } ... while (conditionWithReadableName()) { loopBody(); } Or if you don't want to make up a good name for your conditional: while (true) { if (!someReallyReallyReallyReallyLongFunction()) break; if (!anotherLongFunction()) break; loopBody(); } Or, in a more rules-based fashion: conditionWithReadableName: function() { if (!someReallyReallyReallyReallyLongFunction()) return false; if (!anotherLongFunction()) return false; return true; } ... while (conditionWithReadableName()) { loopBody(); } I find it troubling to make up "good" indentation rules when the code to indent isn't well-written in the first place. Multi-line conditionals are an anti-pattern in itself (no matter if they appear in "while", "if" or "for").
- ikurei 11y agoI agree with you in that multi-line conditionals should go, and no beautifier is going to make it up for bad code, but it's still great that they try. You can't always devote as much time as you'd like to make the code perfect, and that is when a beautifier comes the most handy. Also, having a good beautifier when you have to deal with other not-so-perfectionist programmer's code is great.
- vog 11y ago
- sudo_bang_bang 11y ago"you’d expect it to do something pretty deep right?... Nope. It reads in a string and writes out a string." We're all just doing the same thing in one way or another :) Good work and nice article.
- aiiane 11y agoAlong these lines, we have a joke at Google that all of our problems are just transforming one protocol buffer into another.
- feelix 11y agoAnd programming anything, or taking over the universe for that matter, is just a matter of the hitting the right keys on the keyboard in the right order.
- sudo_bang_bang 11y ago"Protocol buffers are a language-neutral, platform-neutral extensible mechanism for serializing structured data." [1] Interesting, I figured Google was handling data serialization in their own way, and now I know[2] [1]https://developers.google.com/protocol-buffers/docs/overview https://developers.google.com/protocol-buffers/docs/overview [2]https://github.com/google/protobuf https://github.com/google/protobuf
- QuercusMax 11y agoIt's so true... I've only been at Google since the end of June and already have written a few proto converters. And teaching the super-newbies (i.e. fresh out of school) the difference between the frontend and backend protobufs...
- Kenji 11y agoEvery surviving line has about three fallen comrades. My first thought was CSS.
- lolptdr 11y agoHas anyone done any comparisons to other code formatters of other languages? Or even other code formatters within Dart? Wish I could gain more context on how big an arena of these types of programs. I'm a bit lost as to how important code formatters and beautifiers were until reading more on the difficulty of writing such a program by Mr. Nystrom.
- eltaco 11y agoFor javascript, there's been jsbeautifier [1], jsfmt [2], uglify. JSCS [3] added autofixing a while back for most whitespace rules, and ESLint has just begun autofixing as well [4] [1] http://jsbeautifier.org/ http://jsbeautifier.org/ [2] https://github.com/rdio/jsfmt https://github.com/rdio/jsfmt [3] http://jscs.info/ http://jscs.info/ [4] https://github.com/eslint/eslint/pull/3635 https://github.com/eslint/eslint/pull/3635
- bigger_cheese 11y agoIn the intro to programming course I took at University the final assignment we had was something similar (Format Text) we had to write a program that when given three arguments (a text file to read from, an int specifying the characters per line and an int specifying the lines per page) would output the text file formatted correctly breaking on words etc. From memory there were other requirements indenting the first word of each paragraph things like that. As the article alludes to it was a surprisingly complex problem - we also had to worry about memory allocation as we were using C. I remember I was quite proud when I got the sample text (which was a few paragraphs from "The Hobbit") to render correctly. I've never thought about writing a code formatter I just trust emacs to format my code for me. I'd be interested in digging up my old code and seeing how easily I could modify it to operate on source code.
- gchpaco 11y agoPretty printing is surprisingly tricky. Last time I had to do it, I ended up with this: https://github.com/rethinkdb/rethinkdb/blob/next/src/pprint/pprint.cc https://github.com/rethinkdb/rethinkdb/blob/next/src/pprint/... which has become my favorite algorithm for it as it's quite tweakable for specific needs. Fun little algorithm.
- AceJohnny2 11y ago"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!" -- Steve Yegge, 2008 [1] That really struck me back then, and I've kept it in mind whenever I hear about code beautifying/indenting. [1] http://steve-yegge.blogspot.com/2008/03/js2-mode-new-javascript-mode-for-emacs.html http://steve-yegge.blogspot.com/2008/03/js2-mode-new-javascr...
- sklogic 11y agoAnd yet, the best place to add your pretty-printing and indentation hints is parser. Hints are attached to the grammar, so it makes sense to merge the two things, and then generate two different tools out of the single source. Three, actually - an AST pretty-printer, a textual code formatter and, finally, a parser itself.
- eltaco 11y agoThere's an issue for a CST (AST with whitespace, comments, etc) in the estree repo [1]. JSCS is planning on using https://github.com/mdevils/cst https://github.com/mdevils/cst for future autofixing rules. [1] https://github.com/estree/estree/issues/41 https://github.com/estree/estree/issues/41
- 11y ago
- eliben 11y agoYup, all of this is fairly tricky for YAPF as well (https://github.com/google/yapf https://github.com/google/yapf). We ended up reusing clang-format's algorithm
- pjtr 11y agoI've never worked with a fmt tool, but run C# StyleCop[1] on each build to warn about style violations. Naively to me that seems to give the same benefit, but is probably significantly easier to write, is easily configurable and extensible, and leaves me in control. Isn't it annoying when a globally optimizing tool switches back and forth between "all arguments on one line" and "all arguments on separate lines"? E.g. producing overly complex whitespace changes in diffs for small "triggering" changes? [1] https://stylecop.codeplex.com/ https://stylecop.codeplex.com/
- xkcd_353 11y agoI've never tried StyleCop, but I was under the impression that Resharper can do a lot of auto-formatting for you, can't it?
- justinator 11y agoThis made me curious as to what the Perl Tidy formatter was like, as I use it often. You know, it's Perl, so maybe a few regexes here and there, and much wizardry. The Tidy.pm module is 1.1M in size, and over 30,000 lines long. I have much respect for formatters now, I thought the job they do was an easy one. Fantastic looking sourcecode, btw, https://metacpan.org/source/SHANCOCK/Perl-Tidy-20150815/lib/Perl/Tidy.pm https://metacpan.org/source/SHANCOCK/Perl-Tidy-20150815/lib/...
- qznc 11y agoThis whole "Pruning redundant branches" stuff essentially reduces to "do A* search". It is fascinating that we don't have a definitive method for formatting, yet. http://beza1e1.tuxen.de/articles/formatting_code.html http://beza1e1.tuxen.de/articles/formatting_code.html
- munificent 11y agoA* implies that you have a heuristic function pointing towards a known destination. It's about knowing where you want to go, but not how to get there. In this case, we don't know where in the solution space the best solution will be. It's not even that easy to tell if we've found it. So that rules out simple pathfinding algorithms like A*.
- sytelus 11y agoI have tried few code formatters and almost always regretted it. The big problem is that code formatting contains a significant portion of intent and explanation. Sometimes I want to put two assignments on same line because it emphasizes relationship and atomicity but other times it's better to keep them on separate lines for sparcity. There are actually quite a few times I wanted a line go well beyond 80 chars because I wanted to de-emphasize unimportant monotonous part taking away all attention and have far more more important steps immediately stand out to reader. I take code formatting very seriously and consider an integral part of my expression. Style guides are good but they shouldn't be followed like a robot, let alone enforced by robot. In fact code formatting tells a lot about culture and philosophy of an author. For example K&R C starts braces on same line to emphasis compactness as elegance, C# doesn't to emphasize sparse code as elegance. In SQL sometime it's great to put subquery on same line and sometime it doesn't - it really depends on what you want to emphasize and convey rather than hard and fast rules on number of tokens and syntax analysis. Code formatting is not just set of fixed rules, it's a communication mechanism that guides reader on what to focus, what is unimportant, where is a gasoline spill and where wild fires may burn. This is not to say everyone takes their formatting seriously which is where automate formatter would probably add value (and the case where you are importing/copy pasting from somewhere else). I think K&R C is likely the gold standard for code formatting. You should try out your formatter on those snippets ;).
- dmytrish 11y agoI wish your comment was formatted with some paragraphs :(
- weavie 11y agoThat's all fine if you are the only person who will be touching that file. The problem is that most of the time a piece of code will have multiple developers working on it over time. Each dev will have a different perspective of what that intent and explanation should be. I have wasted far too much of my life arguing with people about how code should be formatted. Ideally I would just have a rule set up in source control to format the code on checkin and be done with it.. Then if I want a different style when I come to edit a file I can run whatever formatter I want on it and it won't affect anyone else.
- chriswarbo 11y agoI think code formatters are a great idea, but they're not quite clever enough for me yet. For example, if there's a common pattern among a set of lines, I'll often line them up vertically to make the repetition clear and focus attention on the differences rather than the commonalities; for example: if (foo || quux || baz) { .... } let foo = 10 quux = foo * 2 baz = quux + 1 in baz * 2 fields = ['name', 'address', 'country', 'dob', 'status', 'salary'] To me, those few extra spaces make it easier to glance over the code than without: if (foo || quux || baz) { .... } let foo = 10 quux = foo * 2 baz = quux + 1 in baz * 2 fields = ['name', 'address', 'country', 'dob', 'status', 'salary']
- xkcd_353 11y agoCan somebody name the pattern used in the doughnutFryer example and tell me where I can read more about how to write them and when they are useful?
- kitd 11y agoGood article! The most complex single piece of code I ever wrote was a scheduler. The user could specify a pattern of when events should be raised (eg on this date, at this time, every other hour on the last day of every month, at midnight for me in this TZ on a server in another TZ, etc), and the scheduler would raise the events at the prescribed instant(s). That took about 9 months, and my biggest takeaway was that how humans measure time is completely f*ed up!
- _ZeD_ 11y agoI suggest you guys to play a little with eclipse and its configurable source formatter.
- jdbernard 11y agoI work in a team that uses the eclipse formatter to enforce our style-guide, so I get the value. Having said that, configurable defeats the point of a community-wide formatting tool. From the article: Even if the output of the formatter isn’t great, it ends those interminable soul-crushing arguments on code reviews about formatting. With a configurable formatter you just move those arguments into the style-guide discussions and still have disagreements between people and teams using different configured values.
- amelius 11y agoNow try to write a formatter that runs incrementally (i.e., keeps formatting while the user types).
- greggman 11y agoGreat blog post and super interesting. My feeling though is the problem is they have a line limit. Maybe they should rethink their style. I'm serious. Before I worked at Google, in 30 years of programming I never worked at a company that had a line limit. Adding a line limit at Google did not make me more productive. At first I thought "hey, I guess 80 chars makes side by side comparison easier" but then I thought back, hmm. I never had problems comparing code before when I didn't have a line limit. Instead what I found was that 80 character limit was a giant waste of time. The article just pointed out a year of wasted time. I can point to searching and replacing an identifier and then having to go manually reformat hundreds of lines of code all because of some arbitrary style guide. I also had code generators at google that had to generate code that followed the line limit. I too wasted days futsing with the generator to break the lines at the correct places all because of some arbitrary line limit. That should be the real takeaway here. Make sure each rule of your style guide actually serves a purpose or that its supposed benefits outway its costs.
- tantalor 11y agoI also had code generators at google that had to generate code that followed the line limit. That's an unusual requirement for a code generator. What is the purpose? Generated code generally is not read by humans or checked into source control. I suppose in the rare event where you want to read the code you could rely on your editor's line wrapping feature.
- rch 11y agoJust to choose an open source example: JET generated code from the Eclipse Modeling Framework is generally expected to be checked in, read, and edited by humans.
- philh 11y agoIt looks like this formatter isn't just for internal use, at a company that can buy each of their developers multiple 25-inch monitors. Not everyone has screen space to burn making their editors and terminals arbitrarily wide. If the majority of Dart code was formatted with a line length limit above 80, that would significantly deter me from exploring Dart.
- al2o3cr 11y ago" Even if the output of the formatter isn’t great, it ends those interminable soul-crushing arguments on code reviews about formatting." Similarly, covering all your food in Doritos dust doesn't always taste great but it ends the interminable soul-crushing arguments about what flavor things should have.
- munificent 11y agoI think a better analogy is that having a free cafe ends those interminable discussions about where to go to lunch each day.
- rfrey 11y agoFlavor (as well as texture and aroma) is the whole point of cooking (otherwise, Soylent). Formatting is not the point of programming.
- tremon 11y agoI'd say nourishment is the whole point of cooking. The advent of cooking made more foods digestable to our intestines and other foods less risky. Flavour, texture and aroma are learned appreciations, and are not universal. So I think the comparison with code style is quite apt.
- jdbernard 11y agoNo, nourishment is just the bare essentials of cooking. In fact, we have a very large problem, literally and figuratively, because we often don't care about the nourishment. Consider junk foods and others that we call "empty calories" because they have no real nutritional value. My point being that I don't really see the persuasive value of the analogy. It's a false-equivalence. The point was that yes many people often care deeply about the formatting of the code (myself included), but discussions around formatting are almost always a form of bike-shedding. A better analogy would be "randomly selecting the restaurant doesn't always lead you to your favorite place, but at least it prevents the interminable discussions about where to go."
- 11y ago
- adultSwim 11y agoGood article; poor title.