4 ms·
> 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
by 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 agoThe 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 agoExactly 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.
- svat 7y agoThanks, calculating subtrees only once makes sense. But can't you go further (as in TeX and in the comment you're replying to) — that is, if there are two "paths" of breaking that eventually end with the same break at the same indentations (plural because of the matching-siblings issue), then you should have to recalculate the rest only once? Another question: I must confess not understanding everything clearly, but it sounds like you pop off the lowest-cost breaks until finding a solution that fits the column limit. Couldn't there be cases where avoiding the "best" split in the first step could ultimately result in a lower overall cost? Optimizing over such solutions is the main thing that makes TeX's paragraph-breaking better than the usual greedy algorithms…
- munificent 7y ago> that is, if there are two "paths" of breaking that eventually end with the same break at the same indentations (plural because of the matching-siblings issue), then you should have to recalculate the rest only once? In theory, yes. But there are other constraints across a statement that the formatter tries to preserve, so the memoization needs to take those into account too. Basically, the key used in the memo table is more complex than just "where in the code" and "indentation level". It has to roll in some extra contextual information about other line breaking choices that were made if those choices force this subtree to be formatted in certain ways. > Couldn't there be cases where avoiding the "best" split in the first step could ultimately result in a lower overall cost? Yes, there exactly are, which is why it does indeed find the overall lowest cost solution.
- amelius 7y agoOne thing that Knuth forgot is that it is (imho) ugly if two successive lines in a paragraph start or end with the same word. Or more generally if two instances of the same word appear close to eachother. This shows that writing a formatter is a task that is probably never finished :)
- svat 7y agoDefinitely, the definition of "good" is subjective and one can never get it fully right automatically — but as far as TeX's line-breaking algorithm goes, avoiding successive lines starting or ending with the same word wouldn't require any major change, it could just be added similar to the existing method for consecutive lines being hyphenated (\doublehyphendemerits), without giving up the dynamic-programming algorithm.