Some random thoughts on this paper, since I know a lot about the area:
The pretty printing paper (Wadler’s “A Prettier Printer”) presents an algorithm more than a program. The fact that it’s written in Haskell is mostly incidental. It actually makes it a bit harder to implement because the paper’s algorithm relies on Haskell being lazy. To implement it in a strict language (i.e. nearly any other language) without taking exponential time, you need to make some small modifications [1].
There’s a tradition in the programming language research community of writing pretty algorithms papers in Haskell, which really lends itself to it by being (i) short, and (ii) amenable to equational reasoning. See ICFP’s Functional Pearls [2].
The algorithm is very simple and very efficient (technically quadratic time in weird edge cases, but linear time in practice). If you don’t need to support dynamic alignment (aligning one line based on the contents of the previous line, as opposed to static alignment where you always indent by a multiple of e.g. 4 spaces), you should use Wadler’s algorithm.
If you want to learn way more about the state of pretty printing research, you could check out Section 2 (Related Work) of the paper I coauthored [3].
Hm I skimmed the paper, very interesting, and great survey!
Though it seems like the survey leads out some widely used pretty printers that have a very different model (and don’t have publications associated with them).
e.g. clang-format is the best formatter I’ve used, and it apparently has a model that includes “unwrapped lines”, a “layouter”, a line break cost function, exhaustive search with memoization, and Dijikstra’s algorithm:
It almost seems like there are 2 camps – the functional algorithms for expression-based languages, and other algorithms for more statement-based languages. Or would you disagree with that, and maybe there’s some way to account for those formatters in the functional PPL model?
Yelland’s paper (discussed in our related work section) has a bit of comparison with clang-format in their related work section [1].
We don’t think “expression-based languages” and “statement-based languages” are really the distinguishing factor. The combinator based approach should be able to format statement-based languages just fine, evidenced by Prettier, which uses Wadler’s pretty printer for JavaScript. Similarly, the clang-format approach should be workable for expression-based languages too.
Our understanding is that clang-format’s algorithm is a form of ad-hoc pretty printing: the algorithm was designed to format a specific class of languages (see e.g. yapf [2], which hard codes Python constructs in the algorithm). This is to contrast with general-purpose pretty printing, whose algorithm is language-agnostic.
An advantage of ad-hoc pretty printing is that it can arbitrarily bring in domain-specific knowledge about the language. Its downside is that it is not easily extensible / modular / composable. By contrast, general-purpose pretty printing traditionally has very few knobs that you can adjust. The most that you can do is to compose combinators in different ways.
In our work (A Pretty Expressive Printer), we tried to address the limitation of general-purpose pretty printing via the concept of cost factory and by making our PPL more expressive in general. Composability is really crucial for our use case: we want to format a language with macros (Racket), so we want to allow users to define their own formatting rules. This is straightforward with the combinator approach: they simply need to construct a document as they see fit using the combinators. It’s unclear how to achieve the same effect with the ad-hoc pretty printing.
It almost seems like there are 2 camps – the functional algorithms for expression-based languages, and other algorithms for more statement-based languages.
I think you’re right about the correlation, but not the cause. As Sorawee said, there isn’t much of a relationship between whether a language is expression based or statement based and what techniques are useful for printing it. (The only thing I’ve noticed is that s-expression languages are much harder to print than other languages, because they rely so much on various kinds of indentation.) Instead, I think it’s simply that functional language people like to write generic libraries, and imperative statement-y people like to write language-specific ad-hoc libraries.
Here’s a breakdown of what printing approaches are used by various languages:
I would guess that the top two buckets are actually have many more languages than that, but I don’t know much about the pretty printers for most languages.
Amusingly Go isn’t on this list because, despite being famous for having a code formatter, it doesn’t have much of a code formatter. It purposefully doesn’t break long lines, which is the interesting part of pretty printing.
I’d be interested if anyone knows what techniques other languages’ code formatters use. And also to learn more about clang-format’s approach. Anyone know of a write-up that has more detail than that slide show?
I have the same issue with rustfmt. It does what people imagine gofmt doing, but not what it actually does.
gofmt is an error-fixing formatter. It fixes things about formatting it knows are wrong (like braces, indentation), but leaves everything else more or less unchanged (like 1-line vs multi-line choice). There are many ways to format the same construct, and gofmt respects humans’ high-level choice about the “layout” of the code.
Most other formatters are destructive canonicalizers, which completely replace formatting of the input with their own heuristics. The difference between these approaches is very significant, because reformatting based on heuristics doesn’t leave room for common sense, and bulldozes over formatting exceptions.
This feedback seems common – go fmt does what I want, and rust fmt does a bunch of stuff I don’t want.
I think for both usability and engineering reasons (deploying new versions of the formatter) it can be better to use this “error fixing” model. I mentioned that at the end of my HN comment, and now that I think about it, it’s an enormous difference vs. the PPL model.
I think clang-format is also closer to “error fixing”. This is a separate concern from line wrapping.
And I don’t think line wrapping is the dominant concern in “quality”. For example, one reason I chose yapf over the Black formatter is the Black insisted on changing all my single quotes to double quotes … So I think “over-canonicalization” and perhaps “over-layout” is a problem in practice.
The criticism on “over-canonicalization” is very fair. Generally, I think there’s a spectrum on how opinionated code formatters are. Less opinionated ones probably fit experienced developers better (especially for projects with no collaboration), since the developers know what they are doing, and they sometimes have good justifications to break “rules”.
Prettier, which calls itself an “opinionated code formatter”, offers standard justifications for why it does opinionated formatting [1].
For me personally though, I made the Racket code formatter this way for computer education and program synthesis.
Racket is used for teaching programming in many universities. The Racket Discord has many students posting extremely poorly formatted code, and I was tired of demonstrating proper ways to format their code. Notably, Racket already has a tool for automatic indentation (a la Emacs – so it’s even less opinionated than gofmt as it only fixes indentation), but the tool is not remotely enough to deal with these programs. It took significant effort from me to add line breaks, convert bracket types, etc. to properly format. And that motivated me to start working on the automatic code formatting for Racket.
Program synthesis also requires the more opinionated code formatting, because the synthesizers generate AST with no source location to begin with (essentially equivalent to putting everything on a single line). So I needed an algorithm that can add line breaks to make the generated code readable.
It makes sense if you think about the history – they gradually migrated tens of millions of lines of C++ to be auto-formatted, from LLVM/Google/Apple/etc. There are thousands of experienced and opinionated engineers making changes to those codebases every day – it’s sort of a miracle it worked at at all!
For students, I imagine you can just say “this is the best way” and they will accept that. They are writing smaller programs from scratch, and the code doesn’t live that long.
Also I remember Guido van Rossum had some negative feedback about Black – I think that’s evidence that experience makes you less likely to accept somebody else’s opinionated formatter, without config options :)
So, as mentioned, right now my hypothesis is that my two formatters are different – the JSON one is more like synthesis with no natural layout, but the shell one is probably going to be more conservative, and fix problems, like go fmt (but it should grow line wrapping eventually). There is a hazard to taking on “responsibility” for every formatting decision :)
Thanks for the additions. It would be interesting to see a survey of what approaches different languages use for code formatting.
And I don’t think line wrapping is the dominant concern in “quality”.
I wasn’t trying to say that gofmt isn’t useful, just that (i) what it’s doing isn’t hard to implement, especially not from an academic perspective–it doesn’t need any interesting algorithms, and (ii) it’s funny that it’s become the canonical example of a code formatter when it does so much less than many others do.
This feedback seems common – go fmt does what I want, and rust fmt does a bunch of stuff I don’t want.
I think we’re getting to that point where we’re both talking in abstractions, without knowing what those abstractions mean for the other person. What is it that you’re looking for in a code formatter? The things I’m looking for are:
Make the code fit on my screen without fuss. Sometimes I’m travelling with a laptop, and have code open using 3/5 of the screen and something to its side using the other 2/5. This fits lines of width 100; it does not fit lines of width 150. Wrapped lines are horrible. I regularly write expressions that would be 200+ characters long if put all one one line, and would be unhappy to have to line break them manually.
Convenient canonicalization. To import two things in Rust, you say use super_mod::{sub_mod_1, sub_mod_2}. To import one thing, you could say use super_mod::sub_mod_1. Technically you could also say use super_mod::{sub_mod_1} but the braces would be misleading. If I’m deleting a second-to-last import, I’ll just remove the import and let the formatter remove the redundant braces. This is a tiny convenience, but there are dozens of cases like this (ordering imports, when to wrap with braces, etc. etc.) and they add up. I often knowingly write poorly formatted code and let the code formatter format it for me to save typing time.
Consistency. I can read Rust code written by just about anyone, and not have to let my eyes adjust to different formatting conventions. I couldn’t do this even with the code within the C++ codebase of the last company I worked at. Different people had different opinions on formatting (and opinions changed over time), resulting in a codebase with a slew of different formatting and capitalization conventions.
Ultimately, I see the appeal of having code formatted exactly perfectly for the situation, and realize that no code formatter could achieve that, but… it just seems an order of magnitude less important than having consistent, good-enough formatting. Especially across a large team.
Hm from a user perspective, I’d say what I’m looking for is:
Consistency – It should match some existing style guide, which many people can agree on.
Gradually adoptable – I changed our codebase from 2 space to 4 space indents based on feedback from contributors. So the first step was to auto-format it with 2 spaces, and then go dir-by-dir and move it to 4 spaces.
there was some manual work here, because yapf wouldn’t touch Python docstrings, because they can affect runtime behavior
Configurable - I use about 1 option in both clang-format and yapf, but that 1 option could be make or break!
If you have 10,000 users, and 1 in 100 wants an option, then that’s 100 options
Fast - clang-format is very fast, and yapf is very slow (due to being written in Python)
Wrapping is definitely useful – I like 80 cols – and both clang-format and yapf seem to work well.
yapf does a few things more things that are “ugly”, and I often have to add () around long conditions (probably a Python-specific issue)
But I want to write a couple formatters, and there the perspective is pretty different!
Mainly, don’t take “responsibility” for every formatting decision. The formatter unfortunately has to fit within a time budget.
My rough thinking is to fix indentation, spaces between functions, comments, and () {} style first. Those concerns appear on most lines. And then later add some line wrapping for expressions, which aren’t as common in shell code as they are in other languages. It’s mostly commands/statements.
I honestly am not super excited about writing a formatter, because I do think either way it’s a lot of language-specific elbow grease (kinda like all the parsers I laboriously wrote). But I had a good experience with deno having a formatter “out of the box”. I don’t regularly use TypeScript, so having something basic “just there” is very nice, and I don’t have too many opinions on the style (related to the experienced vs. inexperienced axis discussed above)
Again, fast!
So there are two different perspectives here.
I haven’t used rust fmt but I repeatedly see unfavorable comparisons to go fmt. (I don’t use Rust or Go regularly)
I see a lot of very good feedback on go fmt, so I’m inclined to use it as an example. Historically I do think it kind of changed the game, maybe because it’s almost universally adopted, and many other languages followed suit (e.g. “no config options” in Black is based on go fmt, but that doesn’t work as well for a language with more history).
I think clang-format was also directly influenced by go fmt, but it had a much harder problem due to all the legacy. But it now seems to be a solved problem!
I might draw an analogy with parsing. If you don’t have the basic algorithms right, you will probably end up with a big, never-ending mess. It’s easy to write a bad parser.
But at the end of the day, there’s a large amount of irreducible elbow grease and language-specific logic to get a quality result. Many implementations switch from generated parsers to hand-written parsers to get good error messages (e.g. GCC I think, and Lua).
You’d think in 2023 there would an easier way, but it’s a lot of work, coding, and cranking through test cases. You need low-level control to generate good errors, generate specific structures, and make it fast
Looks like it’s >18,500 lines of C now, which is a lot bigger than the last time I looked:
That all makes sense. Thanks for all the info and perspective!
I think the fundamental difference is that I’m trying not to think about formatting. It needs to be consistent, or else the differences will stand out when I read code, and it needs to not make code hard to read [1]. But so long as it’s consistent and not terrible, I can spend zero brain cycles on formatting code or decoding the formatting that other people have decided to use. It becomes invisible, and I can think about semantics instead.
[1] E.g. IIRC clang-format insisted on formatting if (AAA && BBB) { stuff } by putting BBB) { before stuff at the same alignment, making it look visually like BBB was the first statement inside the if, and neither a co-worker nor I could figure out how to make it not do that.
My rough thinking is to fix indentation, spaces between functions, comments, and () {} style first.
If I were you, here’s what I would do.
Parse the file, but don’t make a full AST. Make a syntax tree that only separates out “functions, comments, and () {}”, and keeps everything else as uninterpreted strings. Use Strictly Pretty b.c. it’s really easy and very fast, and handles indentation for now and line wrapping for when you need it. When making a Doc, most things (e.g. commands) will be strings and hard newlines. Only “functions, comments, and () {}” will be non-trivial. Construct those based on a combination of how-it-was-before and how-it-should-be and configuration options.
I might draw an analogy with parsing. If you don’t have the basic algorithms right, you will probably end up with a big, never-ending mess.
It’s worse than that: in both cases, if you don’t have the basic algorithms right you’ll get exponential runtime. But only in edge cases, so it’ll work fine for a year and then someone will hit the exponential behavior badly and get an essentially non-terminating parser/printer. E.g. rustfmt handles deeply nested lists ([[[...100...]]]) badly (though maybe only quadratically or cubically so?). As another example, there’s a PEG parser for Rust called Pest, which has worst case exponential runtime because it isn’t a Packrat PEG parser; it just skips the memoization and hopes its users will have LL1 or nearly-LL1 grammars. I found this out the hard way at a job.
If you don’t have the basic algorithms right, you will probably end up with a big, never-ending mess. […] But at the end of the day, there’s a large amount of irreducible elbow grease and language-specific logic to get a quality result.
Parse the file, but don’t make a full AST. Make a syntax tree that only separates out “functions, comments, and () {}”, and keeps everything else as uninterpreted strings. Use Strictly Pretty b.c. it’s really easy and very fast, and handles indentation for now and line wrapping for when you need it.
Hm this seems like it’s worth trying … Do you know what the running time of Strictly Pretty is? The paper is motivated by avoiding exponential blowup, but as far as I can see it doesn’t make a specific claim about speed. It just say it is “efficient”?
I looked in your paper, and Table 1 says Wadler’s is O(n^2) but doesn’t seem to mention Strictly Pretty specifically.
I definitely share your viewpoint – algorithms that blow up in rare cases are super annoying. And we will have to print some big JSON, so scalability does matter here.
yapf has what looks like a simple implementation of Dijikstra’s algorithm, and I think that alone would work on JSON, so it could be interesting to compare.
There’s a slight variation of Wadler’s printer that’s more expressive. It’s what’s my Partial Pretty Printer uses, but it’s all tangled up with other features there. So I wrote up a prototype of it yesterday and just published a blog post describing it. It also serves as a walkthrough of more-or-less Wadler’s algorithm.
Though it would be nice to see up front in the blog post what a realistic JSON doc looks like formatted with the Rust code?
Done.
column-wise wrapping
Regular line wrapping is as easy as using group(" ")txt(" ") | nl in my printer (“a twist on Wadler”) or group(" ") in Wadler for each soft-break. Example here:
I’ve seen table-like alignment used for things like match/case statements:
match x {
short_case => 1,
extremely_verbosely_long_case => 2,
middle_length_case => 3,
}
but not for aligning list elements like that. Personally I think the second example looks rather hideous, but if you want it sure.
I’m pretty sure that node.js must be taking at least quadratic time to print that list (quadratic in the length of the list). Say you have a list of length 1000, with mostly small elements (length 1) but a couple dozen longer elements (length 10), and 20 columns of space available. You could print it in two columns, whose lengths are 10 and 10, where each column contains mostly small elements but a few long ones. Or you could notice that the indices of all the longer elements happen to be multiples of 7, so actually the list can be formatted in seven columns of lengths 10,1,1,1,1,1,1. I don’t know how you’d do that without checking for all plausible numbers of columns, which is quadratic.
You could do this with my printing algorithm I think? Make an outer choice for “how many columns to try”, then within that choice determine the max width of all elements in each column, and pad them all to that length. The one modification you’d need is an exposed way to determine the width of a Notation. And maybe a modification for padding.
Both Wadler and Strictly Pretty are, in practice, O(nw) where n is the size of the doc and w is the printing width. The quadratic is from weird edge cases you won’t hit by accident. It’s a fast O(nw) too. No big hash tables, for example, just linear time vector manipulation.
Thanks for the reply! The point about compositionality makes sense.
I like that the PPL approach separates policy and mechanism – i.e. language specific rules vs. wrapping algorithms. I want to write multiple formatters, so that seems attractive.
It’s indeed hard to understand exactly why clang-format works well, and I wonder if the authors would choose the same model in hindsight. I mostly attribute it to being very regularly tested on tens of millions of lines of C++ (LLVM, Google, Chromium, Apple, etc.) – i.e. lots of elbow grease.
I replied to munificent, the author of dart fmt, here. He did run into expressiveness problems with the IR described in the 2015 blog post, and Dart is a bit unusual for its extremely long expressions, so it does seem like all the PPL work directly addresses that. (although I take the point that PPLs work as intended for both statements and expressions)
Still, clang-format and yapf are the two formatters I use the most. They definitely work, and are solving hard problems. clang-format is also extremely fast.
I’ve looked at the source code to both, and the biggest files by far are filled with language-specific policy, and that will be true no matter what algorithm you use. There is also a lot about pretty printing that has nothing to do with line wrapping, as go fmt shows. (And I don’t think this is a bad thing about Go!)
But I want to write more than one formatter, for both simple JSON-like data languages and shell (arguably the language with the most syntax, except for Perl 5 and 6 maybe).
JSON isn’t too different than S-expressions, so I think the simplest PPL algorithms will work fine there, and they’re small amounts of code (although I also want it to be fast).
For a syntactically complex language like shell, I suspect something that “fixes” like go fmt or clang-format might have some advantages. Both clang-format and yapf have dozens of options to express style preferences. I wonder if that is easily encoded in the cost functions. But maybe the JSON experience will encourage me to keep going with the PPL style!
Both clang-format and yapf have dozens of options to express style preferences.
I don’t think style preferences are any more difficult to encode using the PPL approach. The language for “documents” in the PPL is fixed, but you’re constructing a document using arbitrary code, so you just encode style choices by changing the “document” you construct.
But I want to write more than one formatter, for both simple JSON-like data languages and shell
Yeah, JSON is very easy to format. Though it gets harder if you allow comments.
Formatting shell sounds like a nightmare. I’m normally on the side of over-canonicalization, but for shell I agree with you and think you would want error-correcting-only. There’s a big gap between syntax and semantics in shell, and the formatting should follow the semantics.
I’m currently working on a pretty printing library that aims to be very fast. And peephole-optimized, meaning that you can print just part of a document without paying the cost of printing everything above it. It can print the middle 80 lines of a JSON document that’s ~480k lines long in ~500μs. The expressivity is that of Wadler, but with arbitrary choice (so the thing it can’t do is dynamic alignment).
https://github.com/justinpombrio/partial-pretty-printer/tree/master
I’ve looked at the source code to both
Is there a core algorithm behind them, to be extracted and presented? I (and I suspect many others) would be excited to read a blog post that dived into exactly how they work!
Yeah we have actually described the complete syntax of shell, statically, with algebraic data types [1] … but I think if you try to just dump that whole thing into a PPL, you will probably end up with a formatter people complain a lot about, and a never-ending pile of work.
But with JSON I imagine it works pretty well, so I want to see what the fastest / least expressive model I need is.
The partial pretty printer looks cool! Right now all my use cases are batch, not interactive, but it makes sense
I think the main characteristic of clang-format and yapf is that they’re not really “global” optimization? They try to limit the window to a small number of lines. I’m looking at the code now, but I think the better way to understand is to re-create parts of it. As mentioned I think line wrapping is only part of what makes people like the formatter.
It seems like I can accept most line wrappings because the languages I code in don’t have very long expressions. As long as it’s consistent and automated and fast, it’s fine.
Some random thoughts on this paper, since I know a lot about the area:
The pretty printing paper (Wadler’s “A Prettier Printer”) presents an algorithm more than a program. The fact that it’s written in Haskell is mostly incidental. It actually makes it a bit harder to implement because the paper’s algorithm relies on Haskell being lazy. To implement it in a strict language (i.e. nearly any other language) without taking exponential time, you need to make some small modifications [1].
There’s a tradition in the programming language research community of writing pretty algorithms papers in Haskell, which really lends itself to it by being (i) short, and (ii) amenable to equational reasoning. See ICFP’s Functional Pearls [2].
The algorithm is very simple and very efficient (technically quadratic time in weird edge cases, but linear time in practice). If you don’t need to support dynamic alignment (aligning one line based on the contents of the previous line, as opposed to static alignment where you always indent by a multiple of e.g. 4 spaces), you should use Wadler’s algorithm.
If you want to learn way more about the state of pretty printing research, you could check out Section 2 (Related Work) of the paper I coauthored [3].
[1] https://lindig.github.io/papers/strictly-pretty-2000.pdf
[2] https://wiki.haskell.org/Research_papers/Functional_pearls
[3] https://arxiv.org/pdf/2310.01530.pdf
Hm I skimmed the paper, very interesting, and great survey!
Though it seems like the survey leads out some widely used pretty printers that have a very different model (and don’t have publications associated with them).
e.g.
clang-formatis the best formatter I’ve used, and it apparently has a model that includes “unwrapped lines”, a “layouter”, a line break cost function, exhaustive search with memoization, and Dijikstra’s algorithm:https://llvm.org/devmtg/2013-04/jasper-slides.pdf
The YAPF Python formatter is based on this same model - https://github.com/google/yapf
The Dart formatter used a model of “chunks, rules, and spans” - https://journal.stuffwithstuff.com/2015/09/08/the-hardest-program-ive-ever-written/
It almost seems like there are 2 camps – the functional algorithms for expression-based languages, and other algorithms for more statement-based languages. Or would you disagree with that, and maybe there’s some way to account for those formatters in the functional PPL model?
Sorawee’s reply:
I think you’re right about the correlation, but not the cause. As Sorawee said, there isn’t much of a relationship between whether a language is expression based or statement based and what techniques are useful for printing it. (The only thing I’ve noticed is that s-expression languages are much harder to print than other languages, because they rely so much on various kinds of indentation.) Instead, I think it’s simply that functional language people like to write generic libraries, and imperative statement-y people like to write language-specific ad-hoc libraries.
Here’s a breakdown of what printing approaches are used by various languages:
Traditional Pretty Printers (Wadler):
Arbitrary-choice printers (Hughes, Sweistra, Yelland, etc.):
Our printer (Porncharoenwase):
Graph search (not published):
I would guess that the top two buckets are actually have many more languages than that, but I don’t know much about the pretty printers for most languages.
Amusingly Go isn’t on this list because, despite being famous for having a code formatter, it doesn’t have much of a code formatter. It purposefully doesn’t break long lines, which is the interesting part of pretty printing.
I’d be interested if anyone knows what techniques other languages’ code formatters use. And also to learn more about clang-format’s approach. Anyone know of a write-up that has more detail than that slide show?
Also as for other formatters
They’re both Erlang/BEAM languages, so there could be some mutual influence.
OK actually this is some good feedback I saved
https://lobste.rs/s/dfrvp3/clang_format_considered_harmful#c_so8uje (I strongly disagree with the title, clang-format is awesome, but that’s besides the point)
This feedback seems common – go fmt does what I want, and rust fmt does a bunch of stuff I don’t want.
I think for both usability and engineering reasons (deploying new versions of the formatter) it can be better to use this “error fixing” model. I mentioned that at the end of my HN comment, and now that I think about it, it’s an enormous difference vs. the PPL model.
I think clang-format is also closer to “error fixing”. This is a separate concern from line wrapping.
And I don’t think line wrapping is the dominant concern in “quality”. For example, one reason I chose yapf over the Black formatter is the Black insisted on changing all my single quotes to double quotes … So I think “over-canonicalization” and perhaps “over-layout” is a problem in practice.
The criticism on “over-canonicalization” is very fair. Generally, I think there’s a spectrum on how opinionated code formatters are. Less opinionated ones probably fit experienced developers better (especially for projects with no collaboration), since the developers know what they are doing, and they sometimes have good justifications to break “rules”.
Prettier, which calls itself an “opinionated code formatter”, offers standard justifications for why it does opinionated formatting [1].
For me personally though, I made the Racket code formatter this way for computer education and program synthesis.
Racket is used for teaching programming in many universities. The Racket Discord has many students posting extremely poorly formatted code, and I was tired of demonstrating proper ways to format their code. Notably, Racket already has a tool for automatic indentation (a la Emacs – so it’s even less opinionated than gofmt as it only fixes indentation), but the tool is not remotely enough to deal with these programs. It took significant effort from me to add line breaks, convert bracket types, etc. to properly format. And that motivated me to start working on the automatic code formatting for Racket.
Program synthesis also requires the more opinionated code formatting, because the synthesizers generate AST with no source location to begin with (essentially equivalent to putting everything on a single line). So I needed an algorithm that can add line breaks to make the generated code readable.
[1] https://prettier.io/docs/en/why-prettier
Hm I hadn’t thought about the experienced vs. inexperienced axis, but I think that’s exactly right!
e.g. when I looked at the link munificent posted on Hacker News, I’m a little startled by how much Dart programmers care about formatting:
https://github.com/dart-lang/dart_style/issues/1253
And both clang-format and yapf have a ridiculous number of configurable options - https://clang.llvm.org/docs/ClangFormatStyleOptions.html
It makes sense if you think about the history – they gradually migrated tens of millions of lines of C++ to be auto-formatted, from LLVM/Google/Apple/etc. There are thousands of experienced and opinionated engineers making changes to those codebases every day – it’s sort of a miracle it worked at at all!
For students, I imagine you can just say “this is the best way” and they will accept that. They are writing smaller programs from scratch, and the code doesn’t live that long.
Also I remember Guido van Rossum had some negative feedback about Black – I think that’s evidence that experience makes you less likely to accept somebody else’s opinionated formatter, without config options :)
So, as mentioned, right now my hypothesis is that my two formatters are different – the JSON one is more like synthesis with no natural layout, but the shell one is probably going to be more conservative, and fix problems, like
go fmt(but it should grow line wrapping eventually). There is a hazard to taking on “responsibility” for every formatting decision :)Thanks for the additions. It would be interesting to see a survey of what approaches different languages use for code formatting.
I wasn’t trying to say that
gofmtisn’t useful, just that (i) what it’s doing isn’t hard to implement, especially not from an academic perspective–it doesn’t need any interesting algorithms, and (ii) it’s funny that it’s become the canonical example of a code formatter when it does so much less than many others do.I think we’re getting to that point where we’re both talking in abstractions, without knowing what those abstractions mean for the other person. What is it that you’re looking for in a code formatter? The things I’m looking for are:
use super_mod::{sub_mod_1, sub_mod_2}. To import one thing, you could sayuse super_mod::sub_mod_1. Technically you could also sayuse super_mod::{sub_mod_1}but the braces would be misleading. If I’m deleting a second-to-last import, I’ll just remove the import and let the formatter remove the redundant braces. This is a tiny convenience, but there are dozens of cases like this (ordering imports, when to wrap with braces, etc. etc.) and they add up. I often knowingly write poorly formatted code and let the code formatter format it for me to save typing time.And what are some cases where a formatter does something you don’t want it to (especially
rustfmtas I’m most familiar with it)?. The only thingrustfmthas ever done to make me sad is to insist on putting an array of strings on one line, when those strings represented lines of expected test case output. This could be worked around by adding a comment to force it to split the strings across lines (https://github.com/justinpombrio/partial-pretty-printer/blob/master/tests/standard/test_cases/json.rs#L154). Though I would argue this problem is better attributed to the Rust language not having nice multiline strings like Zig (https://ziglang.org/documentation/master/#toc-Multiline-String-Literals).Ultimately, I see the appeal of having code formatted exactly perfectly for the situation, and realize that no code formatter could achieve that, but… it just seems an order of magnitude less important than having consistent, good-enough formatting. Especially across a large team.
Hm from a user perspective, I’d say what I’m looking for is:
clang-formatandyapf, but that 1 option could be make or break!clang-formatis very fast, andyapfis very slow (due to being written in Python)()around long conditions (probably a Python-specific issue)But I want to write a couple formatters, and there the perspective is pretty different!
() {}style first. Those concerns appear on most lines. And then later add some line wrapping for expressions, which aren’t as common in shell code as they are in other languages. It’s mostly commands/statements.denohaving a formatter “out of the box”. I don’t regularly use TypeScript, so having something basic “just there” is very nice, and I don’t have too many opinions on the style (related to the experienced vs. inexperienced axis discussed above)So there are two different perspectives here.
I haven’t used
rust fmtbut I repeatedly see unfavorable comparisons togo fmt. (I don’t use Rust or Go regularly)I see a lot of very good feedback on
go fmt, so I’m inclined to use it as an example. Historically I do think it kind of changed the game, maybe because it’s almost universally adopted, and many other languages followed suit (e.g. “no config options” in Black is based ongo fmt, but that doesn’t work as well for a language with more history).I think
clang-formatwas also directly influenced bygo fmt, but it had a much harder problem due to all the legacy. But it now seems to be a solved problem!I might draw an analogy with parsing. If you don’t have the basic algorithms right, you will probably end up with a big, never-ending mess. It’s easy to write a bad parser.
But at the end of the day, there’s a large amount of irreducible elbow grease and language-specific logic to get a quality result. Many implementations switch from generated parsers to hand-written parsers to get good error messages (e.g. GCC I think, and Lua).
e.g. This is a good article I remember about rewriting the Ruby parser - https://lobste.rs/s/1y78kf/rewriting_ruby_parser
You’d think in 2023 there would an easier way, but it’s a lot of work, coding, and cranking through test cases. You need low-level control to generate good errors, generate specific structures, and make it fast
Looks like it’s >18,500 lines of C now, which is a lot bigger than the last time I looked:
https://github.com/ruby/prism/blob/main/src/prism.c
This seems not too different from what clang-format is like … just a lot of logic and tests, and it has to be fast!
That all makes sense. Thanks for all the info and perspective!
I think the fundamental difference is that I’m trying not to think about formatting. It needs to be consistent, or else the differences will stand out when I read code, and it needs to not make code hard to read [1]. But so long as it’s consistent and not terrible, I can spend zero brain cycles on formatting code or decoding the formatting that other people have decided to use. It becomes invisible, and I can think about semantics instead.
[1] E.g. IIRC
clang-formatinsisted on formattingif (AAA && BBB) { stuff }by puttingBBB) {beforestuffat the same alignment, making it look visually likeBBBwas the first statement inside theif, and neither a co-worker nor I could figure out how to make it not do that.If I were you, here’s what I would do.
Parse the file, but don’t make a full AST. Make a syntax tree that only separates out “functions, comments, and () {}”, and keeps everything else as uninterpreted strings. Use Strictly Pretty b.c. it’s really easy and very fast, and handles indentation for now and line wrapping for when you need it. When making a Doc, most things (e.g. commands) will be strings and hard newlines. Only “functions, comments, and () {}” will be non-trivial. Construct those based on a combination of how-it-was-before and how-it-should-be and configuration options.
It’s worse than that: in both cases, if you don’t have the basic algorithms right you’ll get exponential runtime. But only in edge cases, so it’ll work fine for a year and then someone will hit the exponential behavior badly and get an essentially non-terminating parser/printer. E.g.
rustfmthandles deeply nested lists ([[[...100...]]]) badly (though maybe only quadratically or cubically so?). As another example, there’s a PEG parser for Rust called Pest, which has worst case exponential runtime because it isn’t a Packrat PEG parser; it just skips the memoization and hopes its users will have LL1 or nearly-LL1 grammars. I found this out the hard way at a job.This is the way.
Hm this seems like it’s worth trying … Do you know what the running time of Strictly Pretty is? The paper is motivated by avoiding exponential blowup, but as far as I can see it doesn’t make a specific claim about speed. It just say it is “efficient”?
https://lindig.github.io/papers/strictly-pretty-2000.pdf
I looked in your paper, and Table 1 says Wadler’s is O(n^2) but doesn’t seem to mention Strictly Pretty specifically.
I definitely share your viewpoint – algorithms that blow up in rare cases are super annoying. And we will have to print some big JSON, so scalability does matter here.
yapf has what looks like a simple implementation of Dijikstra’s algorithm, and I think that alone would work on JSON, so it could be interesting to compare.
There’s a slight variation of Wadler’s printer that’s more expressive. It’s what’s my Partial Pretty Printer uses, but it’s all tangled up with other features there. So I wrote up a prototype of it yesterday and just published a blog post describing it. It also serves as a walkthrough of more-or-less Wadler’s algorithm.
https://justinpombrio.net/2024/02/23/a-twist-on-Wadlers-printer.html
This is great, thank you! I was looking at this earlier today and I will compare
https://github.com/prettier/prettier/blob/main/commands.md
Though it would be nice to see up front in the blog post what a realistic JSON doc looks like formatted with the Rust code?
One thing I noticed is that node.js has some column-wise wrapping like this
It even does stuff like this
Right now I’m not sure if either the Wadler IRs or yapf/Dijikstra handle that, but I want to do some testing
I think it’s this code that’s doing it, but I’m not sure about that - https://github.com/v8/v8/blob/0e8fb8620a443cdaa206cec115182f9bce3cb71d/src/json/json-stringifier.cc#L347
(I want Oils to look at least as nice as node.js)
Done.
Regular line wrapping is as easy as using
group(" ")txt(" ") | nlin my printer (“a twist on Wadler”) orgroup(" ")in Wadler for each soft-break. Example here:https://github.com/justinpombrio/partial-pretty-printer/blob/master/tests/standard/test_cases/flow_wrap.rs#L27
I’ve seen table-like alignment used for things like match/case statements:
but not for aligning list elements like that. Personally I think the second example looks rather hideous, but if you want it sure.
I’m pretty sure that node.js must be taking at least quadratic time to print that list (quadratic in the length of the list). Say you have a list of length 1000, with mostly small elements (length 1) but a couple dozen longer elements (length 10), and 20 columns of space available. You could print it in two columns, whose lengths are 10 and 10, where each column contains mostly small elements but a few long ones. Or you could notice that the indices of all the longer elements happen to be multiples of 7, so actually the list can be formatted in seven columns of lengths 10,1,1,1,1,1,1. I don’t know how you’d do that without checking for all plausible numbers of columns, which is quadratic.
You could do this with my printing algorithm I think? Make an outer choice for “how many columns to try”, then within that choice determine the max width of all elements in each column, and pad them all to that length. The one modification you’d need is an exposed way to determine the width of a Notation. And maybe a modification for padding.
Both Wadler and Strictly Pretty are, in practice, O(nw) where n is the size of the doc and w is the printing width. The quadratic is from weird edge cases you won’t hit by accident. It’s a fast O(nw) too. No big hash tables, for example, just linear time vector manipulation.
Thanks for the reply! The point about compositionality makes sense.
I like that the PPL approach separates policy and mechanism – i.e. language specific rules vs. wrapping algorithms. I want to write multiple formatters, so that seems attractive.
It’s indeed hard to understand exactly why clang-format works well, and I wonder if the authors would choose the same model in hindsight. I mostly attribute it to being very regularly tested on tens of millions of lines of C++ (LLVM, Google, Chromium, Apple, etc.) – i.e. lots of elbow grease.
I replied to munificent, the author of dart fmt, here. He did run into expressiveness problems with the IR described in the 2015 blog post, and Dart is a bit unusual for its extremely long expressions, so it does seem like all the PPL work directly addresses that. (although I take the point that PPLs work as intended for both statements and expressions)
https://news.ycombinator.com/item?id=39449613
Still, clang-format and yapf are the two formatters I use the most. They definitely work, and are solving hard problems. clang-format is also extremely fast.
I’ve looked at the source code to both, and the biggest files by far are filled with language-specific policy, and that will be true no matter what algorithm you use. There is also a lot about pretty printing that has nothing to do with line wrapping, as go fmt shows. (And I don’t think this is a bad thing about Go!)
But I want to write more than one formatter, for both simple JSON-like data languages and shell (arguably the language with the most syntax, except for Perl 5 and 6 maybe).
JSON isn’t too different than S-expressions, so I think the simplest PPL algorithms will work fine there, and they’re small amounts of code (although I also want it to be fast).
For a syntactically complex language like shell, I suspect something that “fixes” like go fmt or clang-format might have some advantages. Both clang-format and yapf have dozens of options to express style preferences. I wonder if that is easily encoded in the cost functions. But maybe the JSON experience will encourage me to keep going with the PPL style!
I don’t think style preferences are any more difficult to encode using the PPL approach. The language for “documents” in the PPL is fixed, but you’re constructing a document using arbitrary code, so you just encode style choices by changing the “document” you construct.
Yeah, JSON is very easy to format. Though it gets harder if you allow comments.
Formatting shell sounds like a nightmare. I’m normally on the side of over-canonicalization, but for shell I agree with you and think you would want error-correcting-only. There’s a big gap between syntax and semantics in shell, and the formatting should follow the semantics.
I’m currently working on a pretty printing library that aims to be very fast. And peephole-optimized, meaning that you can print just part of a document without paying the cost of printing everything above it. It can print the middle 80 lines of a JSON document that’s ~480k lines long in ~500μs. The expressivity is that of Wadler, but with arbitrary choice (so the thing it can’t do is dynamic alignment). https://github.com/justinpombrio/partial-pretty-printer/tree/master
Is there a core algorithm behind them, to be extracted and presented? I (and I suspect many others) would be excited to read a blog post that dived into exactly how they work!
Yeah we have actually described the complete syntax of shell, statically, with algebraic data types [1] … but I think if you try to just dump that whole thing into a PPL, you will probably end up with a formatter people complain a lot about, and a never-ending pile of work.
But with JSON I imagine it works pretty well, so I want to see what the fastest / least expressive model I need is.
The partial pretty printer looks cool! Right now all my use cases are batch, not interactive, but it makes sense
I think the main characteristic of clang-format and yapf is that they’re not really “global” optimization? They try to limit the window to a small number of lines. I’m looking at the code now, but I think the better way to understand is to re-create parts of it. As mentioned I think line wrapping is only part of what makes people like the formatter.
It seems like I can accept most line wrappings because the languages I code in don’t have very long expressions. As long as it’s consistent and automated and fast, it’s fine.
[1] https://www.oilshell.org/release/0.20.0/pub/src-tree.wwz/frontend/syntax.asdl.html
In the Python world the equivalent is Black, which makes use of Python exposing a lot of its own internals in order to check that the semantics of your code are preserved across a formatting operation.