Paragraph adjust "badness" calculation

[reffort]

I'd like to propose a change to the way the line breaking "badness" value is calculated in paragraph adjust mode. The current calculation occasionally produces a line or cluster of lines that have obviously loose spacing followed by one or more lines that have obviously tight spacing (or vice versa). That's the sort of thing that paragraph adjustment is supposed to minimize. The change I suggest corrects this behavior.

It is a minor change to line 1765 in function penalty() in n7.c.

The current line is:

t = t >= 0 ? t * 5 / 3 : -t;

The proposed new line is:

t = t >= 0 ? t * 2 : t * -2 ;

The current calculation is heavily skewed to favor really tight lines that have a space size at or near the value defined by the .minss request if the space size for the line being considered cannot be near the normal size. These small word spaces (which fall into the "very tight" class in TeX parlance) are actually favored more than word spaces that are on the looser side of the "normal" class. When the input text needs help the most, the badness curve acts much like a word processor and the result is uneven word spacing.

The factors I'm proposing produce badness values that are symmetrical about the normal space size and favor neither loose nor tight lines. The curve assigns a much higher penalty to tighter-than-normal spaces than does the current curve, and a modestly higher penalty to looser-than-normal spaces. The penalties assigned to looser and tighter space sizes are evenly balanced, and this significantly reduces the occurrence of obvious loose-tight lines.

[n-t-roff]

Thank you for this proposal.

Up to now there had only been lots of C coding bugs (most of them originating in DWB 2) and roff issues (mainly updating mdoc(7) to groff's extensions).

To make a decision here I have to work through the Knuth-Plass document and Gunnars undocumended paragraph formatting code (like you did already). This may take a while.

Do you have an example input (small if possible) with which the difference can be reproduced?

[reffort]

OK, I will assemble something that can be easily reproduced, probably with a stable free font and some public domain text that exacerbates the problem. It usually takes a fair-sized paragraph for the problem to be noticeable the first time, but after you see it, it is obvious. It will probably take a few days.

The magnitude of the problem is dependent upon how the text fits the line and whether or not hyphenation is being considered. The main things that affect it are:

1) The distance between minss and the normal space size. The penalty curve will try to use the smaller spaces if they are available.

2) Hyphenation. The way the hyphenation penalty is implemented in Heirloom, it avoids hyphenating words much more than the penalty number we input would seem to imply (I think the calculation might be based on what looks to me like a typo in the 1981 Knuth-Plass paper). This serves to help push the space sizes smaller.

3) The author's vocabulary, and arrangement of words in the paragraph, the typeface and size, etc.

I've attached a graph of the space size penalty curves for TeX, Heirloom, and the proposed curve. The dashed horizontal lines show the ranges of the "normal" space sizes for the curves: TeX, 10-15; proposed curve, 9-15; Heirloom, 7-15. The Heirloom "normal" size can be smaller than TeX's minimum of 8 troff units.

The curves are normalized so that the smallest and largest spaces that can be termed "generally acceptable" have a penalty of 100. For TeX, those values are 8 and 18; for the proposed curve, 6 and 18; Heirloom is 0 (!) and 19.2.

If we generalize and say that the "normal" range can extend halfway to the "generally acceptable" value, then Heirloom's "normal" space size ranges from 6 units to 16.1.

Hyphenation penalty: Currently in Heirloom, the sum of the three hyphenation penalties p is added to the space size adjustment ratio rj, and that sum is then cubed to obtain the badness t

t = rj + p ;
t = t * t * t ;

which seems to be a variation of the typo in Knuth's paper. I think it should be a sum of the squares calculation as described in the TeX82 pdf (2014):

t = rj * rj * rj ;  // the bathtub curve
t = t * t ;
t += p * p ;

which I think produces much better looking paragraphs. I suggest making this change, too.

[n-t-roff]

What exactly do you regard as a typo in the 1981 Knuth-Plass paper?

[reffort]

On journal page 1128, near the bottom of the page are the three cases for calculating the demerits for a line. The first calculation is the normal case, and it places the first hyphenation penalty inside the parentheses and squares it along with the badness value and line penalty. The (squared by the user) consecutive hyphenation penalty is then added to that squared sum.

d = (1 + b + p1)^2 + p2 * p2

In looking at the three calculations on that page, it is readily apparent that "one of these things is not like the others"; but in the pseudo-code on journal page 1160 (PDF page 42), in "compute demerits d, etc" the same calculation is repeated.

However . . . in TeX82.pdf (authorship attributed to Knuth), section 859, on page 318, "Compute the demerits, etc.", it describes the calculation in a more expected way,

d = (1 + b)^2 + p1 * p1 + p2 * p2 + p3 * p3

and again with p2 and p3 having already been squared by the user.

I had forgotten about the second occurrence in KP-81, so it looks like my initial statement, that this is a typo in the article, is probably incorrect; but that calculation was clearly changed to a more conventional version in TeX82. The KP-81 version is so grossly out of character that I believe it almost has to be the result of a trivial error that occurred somewhere.

The calculation I suggested previously, where the sum of the hyphenation penalties is squared and then added to the total demerits, is in between the Heirloom method and the TeX method in strength, which is why I suggested it. I think the TeX82 calculation works the best, but I do not know what the balance is here among backward compatibility, bug fixes, and performance improvements, so I was attempting to stay in the middle ground. Gunnar was obviously not attempting to replicate TeX.

What would be the preferred method for uploading a sample troff file of about 4K? Can that be attached the same way as an image, or is there a different way?

[saper]

@reffort can you try https://gist.github.com/ ?

[n-t-roff]

That's why I asked for the typo. I had followed the calculations in the paper using the given numbers and it showed that the printed equations had been used. So it had been intended to use this equation.

This had been an early theoretical paper and of course there had been new ideas and refinements. So any deviation between KP-81 an TeX82 is not surprising.

Why not replicate TeX. I think Gunnar just had read KP-81. The pseudo code in TeX82 is not easy to read (IMHO). Mathematical equations are much more clear and easier to follow. If you had not pointed out TeX82 I had ignored it too.

In this case I see no reason for backward compatibility. I hope no existing document relies on a very special formatting which only KP-81 produces. Even if this is the case a compatibility flag could be added later for this user.

So I suggest to change the algorithm to the best which is known and for which the required changes are not too substantial.

Even performance should not be an issue today as long as time complexity doesn't change radical. I would assume that TeX is much slower that Heirloom but IMHO this is not a point against TeX on today's hardware. IMHO most important for the user today is the typesetting quality.

[reffort]

It looks like that calculation was changed in 1982.

From the TeX bug list at ftp://ftp.cs.stanford.edu/pub/tex/errata/tex82.bug

35. Here's an improvement in the formula for demerits; previously
more weight was given to minimizing bad spacing on lines with penalties,
so that (slightly loose hyphenated line)(OK line) was considered worse
than (OK hyphenated line)(quite loose line). (fixed 11/8/82)
Change lines 2--7 of module 772 to the following:
        d:=line_penalty+b; d:=d*d;
        if pi<>0 then
                if pi>0 then d:=d+pi*pi
                else if pi>eject_penalty then d:=d-pi*pi;

That code begins on line 16881 of tex.web of TeX14.

In "The Errors of TeX" (a PDF[1] listing of the bugs with no commentary, probably from an article of the same name), is this description:

554 Compute demerits more suitably by adding a penalty squared,
instead of adding penalties before squaring. §859 A

    • Previously a slightly loose hyphenated line followed by a decent
    line was considered worse than a decent hyphenated line followed
    by a quite loose line.

[1] https://www.tug.org/texlive//devsrc/Master/texmf-dist/doc/generic/knuth/errata/errorlog.pdf

If backward compatibility is not a problem, I'll suggest considering the use of the square of the rj's for the range of acceptable space sizes, and the square of that value for the for the space sizes we'd rather not have (they would be considered an error to be minimized). Gunnar implemented the calculations with floating point, so, it's just

t = rj * rj ;
if (t > 1)
    t = t * t ;
t += other penalties, etc.

Most of the time the line breaks are identical; but when they differ, this calculation almost always makes a better looking paragraph. The downside is that the improvement is often achieved with a little more hyphenation, and the Heirloom behavior is to be really averse to hyphenation.

I agree, speed is not a problem any more.

[reffort]

@saper, Thanks for that suggestion. I will do that.

[n-t-roff]

Why not use your initial suggestion of

t = rj ^ 3 // * 100 ?
t = t ^ 2
t += etc.

so small deviations from ideal space width result in even lower demerits? (I mean rj^3 instead of rj^2 and unconditional t^2.)

So you imply that hyphenation behaviour also should be improved? What I have read from typographs (e.g. Tschichold) is that much hyphenation is not a problem. More severe is uneven or too large word spacing. But also KP-81 states that hyphenation is the last effort (again, IMHO I can't agree with that opinion). But can't hyphenation aversion be adjusted via the penalty value?

Also TeX82 §108 mentions 100 * (t/s)^3. But a lot of simplifications are done there, maybe for hardware from some decades ago. We need not to be compatibel to KP-81, TeX82, existing Heirloom or whatever. If time complexity is acceptable also no simplifications are required (there is a lot improvement potential in Heirloom at other areas, e.g. large lists of strings which are searched linear).

[n-t-roff]

Regarding your very first proposal--why should t be doubled, why not just say

t = |t|;

there?

In general the proposed changes make sense (details need to be finally agreed), so the code will be changed eventually. If you like this could be done as a pull request which has the advantage that the changes are committed effectively (directly) by you. (If you're not interessted in creating the pull request then alternatively your name is written in the commit message (and the change log anyway).)

Since it is clear now that the changes make sense, the example is of less importance actually (it would not be a prove anyway of course). So if there is still quite some work to do for it then maybe it's better to stop it. If it is ready already then it can be used for some tests with different line lengths etc.

[reffort]

So if there is still quite some work to do for it then maybe it's better to stop it.

Oops, maybe I should check my messages more often.

These files demonstrate the problem with the Heirloom badness/penalty calculation, and compare it with the TeX, KP-81, and the things I suggested.

https://gist.github.com/reffort/45d2e4d989d045829250 curves.tr - formats two paragraphs: an easy one (the "Frog Prince" paragraph from KP-81) and a more difficult one that requires a number of decisions regarding hyphenation (the first paragraph of Moby Dick). It varies minss and hypp so that changes in the output are readily visible.

https://gist.github.com/reffort/60288c3bb2e42d678ef7 penalty.c - a temporary experimental replacement for the n7.c penalty() function for comparing the different space range windows and penalty calculations.

https://gist.github.com/reffort/ef857c786a4c35b33c38 spreadmark.c - some code to temporarily insert in n7.c that prints a space size category in the margin, so that there is a quantitative way to compare the paragraphs.

The instructions are contained in the snippets, but the idea is to change the space range window and calculation type in the temporary penalty() function, rerun make and make install, then run the curves.tr file using

troff curves.tr | dpost | ps2pdf - > curves.pdf

(Run curves.tr with an unmodified n-t-roff first to obtain a clean baseline.)

Even without comparing the output to the other methods, paging through the baseline PDF should make it obvious how Heirloom really tries to avoid hyphenation by placing as many characters on the line as it can until it runs into the brick wall at minss. There are quite a few noticeable loose-line tight-line blotches in the paragraphs. The other methods use a more selective curve to try to make even word spaces as described by the curve.

The space range windows and calculation types can be patched together as desired.

[reffort]

Regarding your very first proposal--why should t be doubled, why not just say t = |t|; there?

Those values scale the space adjustment ratio so that the upper and lower badness values are both 1.0, allowing rj to be calculated in one step. It is a clever but non-intuitive way to do it. If the numbers are 2 and -3, for example, that defines the range of acceptable space sizes for the TeX model: 8 troff units to 18 units, with 12 being the desired size (that corresponds to adjustment ratios of 0.667 and 1.5). 1.0/(1.5-1) = 2, and 1.0/(0.667-1) = -3. The Heirloom numbers -1 and 5/3 correspond to a space size window of 0 to 19.2 units for a badness of 1. -2 and 2 define a window of 6 to 18 units. -1 and 1 would be 0 to 24 units.

Why not use your initial suggestion of t = rj ^ 3 // * 100 ? t = t ^ 2 t += etc. so small deviations from ideal space width result in even lower demerits? (I mean rj^3 instead of rj^2 and unconditional t^2.)

The TeX curve is nicely designed to do just that. By squaring the cubic function it becomes rj^5, and the bottom of the curve becomes flatter and broader so that it doesn't begin to turn up very much until it has just exceeded the "normal" space size range, and then it curves upward sharply. The down side is that there is little to differentiate spaces within the normal range because the penalties are all about the same. The tradeoff is that it favors "normal" spaces much more than "loose" or "tight" spaces but allows the "normal" spaces to drift more.

Also TeX82 §108 mentions 100 * (t/s)^3

That looks like the same thing. TeX's handling of spaces is more complicated than troff's, but t is probably the amount of space in the line to be adjusted, and s is the probably nominal space size (Gunnar uses the same names in penalty() ). I recall from somewhare that Knuth said he originally wrote TeX with floating point but it wasn't portable, so it looks like section 108 is a way to calculate it using integers.

So you imply that hyphenation behaviour also should be improved?

The direct modification of the badness function in the KP-81 and Heirloom methods is what causes them to perform not-so-great. Heirloom is also affected by a shallow badness curve.

What I have read from typographs (e.g. Tschichold) is that much hyphenation is not a problem. More severe is uneven or too large word spacing.

That's the tradeoff, isn't it? When I'm reading, if there's enough hyphenation that I notice it, it becomes distracting. Same with bad word spacing. I think people who are interested in books as an art form (made to be looked at) want a prettier page at the expense of readability. (Nobody is going to read a folio-size edition of Moby Dick, but there are people who will pay thousands of dollars for a copy of one because it is so attractive.) Math books, on the other hand, need to be unambiguous.

[saper]

Hello @reffort! I understand that you are pretty new to Github and probably also the concept of using a git tool to control source files. While it is a significant effort, I would recommend learning how to use a git tool - this is a very handy directory "snapshotting" tool that most people use as a "version control system" (a modern successor to CVS, SCCS, SVN etc.)

Of course posting snippets or test documents to gist.github.com is fine - this is what it's for.

But in case of proposed source code changes, it is much easier to grab a copy of the source code and the git repository (usually done via "git clone" command) and create your own "fork". This can be done on the Github interface using a "fork" button.

Then you can just edit the files as needed, commit (git commit) your changes and submit them to your fork (git push). The good thing about fork is that this is your private - yet fully functional - copy of the software source and it can be very easily compared against the original source code, with the git diff or even on the Github web interface. Anyone can then compile your code and test it, submit their remarks etc. and there is little danger of ambiguity re how to modify the files. Github has extensive documentation in their help (mostly to learn about "fork" and "pull request" facility) but I also highly recommend learning command line git (if you haven't already).

With all its ugliness (alas) this seems to become a tool du jour for today's software projects.

This way of proceeding (along with the "pull request" function) makes it very easy for others to review and integrate your code (sometimes it's just clicking one button).

[n-t-roff]

@saper: Normally I tend to reject pull requests for such a small project because of the additional work they cause. It is our limited spare time that we should use efficiently. Simple bug reports are recommended instead. But in this case of an excellent analysis of a difficult problem a pull request is indeed prefered for this contribution. Nethertheless it is up to @reffort to delegate the work of applying the patch. @reffort: I'm not convinced that a symmetrical scaling is prefered. IMHO it is more problematic, if a space is reduced by some amount than if it is widened by this amount. So TeX's -4, +6 is somehow "weighted symmetrical". Wouldn't you agree that this would make sense? (I.e. use scaletype=2)

[saper]

@n-t-roff It is up to you to accept pull request or not, what I mean there is no need to describe changes which need to be applied to the file by hand when the changed files can just be pushed to a fork on Github. "Compare branches" facility can be used instead of the pull request, for example.

[reffort]

@n-t-roff If we have 4 pounds on one side of a scale and 6 pounds on the other, I suppose we could describe that as a weighted balance. I'm not sure that the Bureau of Weights and Measures would agree, though.

Generally, I think anything that we limit works to degrade the results. Paging through the sample PDF, we can see that the paragraphs formatted by the different methods become stable at some value of minss (except for Heirloom, unfortunately), which suggests the notion of a "best" value for this particular combination of font/text/measure. Other material will no doubt be different, but how much different is the question.

I am hoping that if n-t-roff users evaluate the methods I provided on their own material, that some general agreement might result as to which should be the best choice to implement. As it is, I think all of them (with the exception of the KP-81 calculation) are better than the current method, but I'm very hesitant to just copy the smart kid's homework willy-nilly.

[reffort]

@saper I evaluated converting to git some years ago, but scrubbed it from my machine within the week. Any interaction with GitHub will have to be done without git on my end.

[saper]

@reffort Fair enough. I fully understad that. In that case probably just sending the output of diff(1) (preferably in the unified format) is most helpful.

[n-t-roff]

What I have meant by weighted balance is that 12 is the the symmetry center and we have a non-linear function which treats 0 on one side like "infinity" on the other side. Since 0 is clearly unexceptable (also values near 0) but 12*2 (although a bad value) could be accepted--it could have a badness of lets say space size 3 or so. But this had only been a question to think about.

They question is how we can inform other users of the methods you provided. Many of those may not read the issue list. The groff mailing list (groff@gnu.org) did agree that this list can be used for Heirloom roff too. Many users may not read this list but I'll inform the list about the methods you provided. But we can't simply have a vote. I prefer that either you decide which scaletype and calctype is used (only values > 1 allowed ...) or we make that configurable, than we could even allow value 1 for both to have backward compatibility (but I think nobody needs that), and you decide for the default setting.

git(1) is IMHO a very good tool but I think you can do all the work with the browser on github. Making the fork, editing the file and creating the pull request can easily be done via the web browser on github. But of course you may decide to provide a diff file or even the complete file and let me make the diff. The patch is committed with your user ID anyway.

[n-t-roff]

Comparing the documents (I have generated all cases) I tend to choose TeX14 (s=2 c=2). calctype 4 leads to values more far from 4 (0 ... 9), calctype 5 is similar to 2. When comparing calctype 2 with scaletype 2 ... 4 scaletype 3 and 4 have very tight and loose lines which are not in scaletype 2 (although there are cases where scaletype 3 and 4 are better). So according yor document TeX14 (scaletype 2, calctype 2) is a good compromise, albeit it does not have the best result in any case.

Since we to not seem to agree it looks like we make that configureable? ;)

[reffort]

What you've described hilites the need to evalute what works and what doesn't for the types of material that are used with n-t-roff.

To make a more equal comparison of the curves with each other the hypp value needs to match the point on its curve corresponding to the same space size, but we can't really do that very well because the curves have different asymmetries. But what you've described sounds about right. The TeX curve (effectively t^5) tries to funnel the space sizes into what is roughly the "normal" range, and the cubic and quadratic curves don't do that as strongly. The intermediate and symmetrical windows give the algorithm more room to work (TeX has a fixed limit at the equivalent of minss=8, so that's why its lower window is set at that value).

it looks like we make that configureable?

That's exactly what I've done on my local copy. I added a .wordspace low% high% request to set the window as a percent of nominal size. It defaults to the TeX values (66.7 and 150), but I usually change the lower value. I found no need to change the curve (which is not the TeX curve), even a linear "curve" will work surprisingly well.

allow value 1 for both to have backward compatibility (but I think nobody needs that)

If anyone has any documents that were formatted using Heirloom's paragraph adjust, those documents will be significantly broken with these methods because the text will reflow very differently.

Since we to not seem to agree

Agreeing on how something looks is kind of tough. Some people like looser spaces, some tighter. The current fad is for bland, boring pages, but some of us like a little texture. And with a very general sample like this one, none of the examples is likely to be at its best. But I hope we agree that they are all better than the Heirloom and KP-81 curves.

[n-t-roff]

With fixed scale type when looking at the rating numbers alone KP-81 is best, TeX in the middle and calc type 4 is much worse (calc type 5 is similar to TeX). But this seems to depend on hyphenation. The reason for the good rating of KP-81 seems that it does "not" respect hypp and the bad rating of calc type 4 is that it avoids hyphens whenever possible (not as sensitive to hypp as TeX). So again for your document I prefer calc type 2 since there I have very good control via hypp.

That KP-81 seems to "ignore" hypp is a problem but else it is not much worse than calc type 2. But current Heirloom is unacceptable bad, compared to the other variants.

So .wordspace does only have influence on a and b in t = t >= 0 ? t * a : t * -b?

It might be correct that the further demerit calculation has not much influence as long as it is correct. But I'm not quite happy with calc type 4. If no "better than all others" algorithm can be found, I tend to make the calc type selectable also.

I have asked the Heirloom users on the groff list, if unchanged rendering of existing documents is required. My opinion at the moment is that although text is rendered differently a document should not be designed sensitive to that. Anyway we can introduce an option later to bring the old behaviour back if one needs that.

Sorry for asking one time regarding git again. I know a lot of version control tools--what I like on git that it is so easy to use. At first sight the local repositry seems to be a disadvantage but this is rather small and diffs, greps etc. are much faster. Also off-line work is an advantage. I only use maybe 0.1% of it's functions (only the five commands pull, push, commit, diff, and grep) but it's already very powerful with that. If you don't like to use it--ok, else we could discuss some basic usage via mail (troff@arcor.de).

[reffort]

To make an equal comparison, hypp should be set individually for each curve so that the effect is about the same on each curve, but it isn't possible to match the effects exactly. You can often achieve identical paragraphs for a given input scale with any curve type just by changing hypp.

One caveat about comparing the category numbers directly is that the range of "acceptable" space sizes (the scale) defines the range of "acceptable" category numbers. With the TeX scale, that range is from 8 to 18 troff units, so category numbers of 2 through 8 would be OK. Category numbers less than 2, like the zero that occurs with the TeX/TeX pair with minss 6, or greater than eight (like "B"), are actually not OK, but the algorithm will use them if it really needs to and it is allowed to do so by the setting of minss. "B" is an unacceptably loose line (the TeX program has an adjacent line compatibility penalty that would try to get rid of the 3-B sequence, but usually at the expense of OK lines).

When changing the scale to "symmetrical", the "acceptable" range becomes 6 to 18, so we are saying that space size 6 (category 0) is OK for the algorithm to use. We can limit that with .minss 8 and have a symmetrical response to the extent that the fixed lower limit allows. We won't have spaces smaller than 8 units (category 2), but that can cause unacceptably loose lines.

The definition of the range of "acceptable" space sizes (the scale) has a greater effect on the paragraph than the calculation does. For example, if the TeX calculation (2) is matched with the Heirloom scale (1), the output acts more like Heirloom (1/1) than it does TeX (2/2), although it has more hyphenation than Heirloom because of the different method of applying hypp.

a document should not be designed sensitive to [reflow]

There is no way to avoid that that I'm aware of, at least for anything that matters. I will propose that it matters a lot for a book with graphs, tables, notes, an index, and matched spreads.

But current Heirloom is unacceptable bad, compared to the other variants.

Heirloom is designed to have fairly even space sizes if it doesn't have to hyphenate any words, and to place as many characters on a line as it can to avoid hyphenating words, and it does that well. The other methods are designed to make the space sizes as uniform as they can with a controlled amount of hyphenation.

[n-t-roff]

It did ask Heirloom users via the groff list to test your examples and their documents and I did ask if it is a problem to not be compatible to current Heirloom anymore. As somewho expected ther is no repsonse. Only few Heirloom users are aware that the groff list can be used for Heirloom topics.

After all my suggestions are:

• Adding .wordspace as it is in your local copy
• Adding an additional request to set the paragraph formatting method which can be one of
  • Current Heirloom (for compatibility) -> (1/1)
  • As close as possible to current TeX (I would suggest that even if a better algorithm is found) -> (2/2)
  • A new method -> e.g. (3/4)

The new request (like .padjmethod N where N is 1 ... 3) which sets the method and adjusts other parameters, e.g. the .wordspace setting or even that of minss and hypp (They can manually be adjusted after the .padjmethod request). Method (3/4) could be the default, I would choose (2/2) for my documents (I prefer word space as even as possible as long as there are not too many consecutive hyphenated lines).

How about that adjacent line compatibility penalty, shoudn't we have that option too? Two consecutive lines with two very different categories are very noticeable. I would prefer slightly worse other lines instead of this.

[n-t-roff]

Do you already have a idea for the bugfix regarding the "\c" instead of simply "" problem? If not I would meanwhile look into this.

I can't veryfy that issue. I produced a PS file, removed all " \c$" and produced a second PS file. They don't differ.

[reffort]

After thinking about this a little, I agree that the TeX curve looks like the logical choice. It is the successor to the KP-81 curve, has a long track record, performs well, and we know what the default hyphenation penalty is. The cubic curve I originally suggested is in keeping with what Heirloom currently uses. The quadratic curve may be too nerdy (needs more tweaking). An Heirloom compatibility mode would not be difficult to implement.

The .wordspace range is really an adjustment that helps to fit the text/font/size/measure and helps get the best balance of even word spaces and minimal hyphenation, along with .hypp. So I think that having it adjustable is the way to go. The TeX defaults are reasonable, but Knuth based them on the "old" Monotype (before 1912, maybe before 1908) instead of the "new" Monotype (after ~1950).

Adjacent line compatibility - Gunnar didn't seem to like that, and I can't say I much disagree with him. I've looked at it for a good while and my opinion is that, with Heirloom, sometimes it helps but usually it messes up the overall paragraph. A pair of loose-tight lines is already heavily penalized, but it is still the "best" solution the algorithm could come up with for that paragraph. There are usually other factors at work that need attention, like words that need hyphenation points defined or just can't be broken; sometimes nudging something manually (with a tie \~) helps, sometimes it is just the best you can get. It isn't hard to implement, it just doesn't seem do much for us, in my experience.

Something that plays into that is that the Heirloom implementation of the paragraph adjust algorithm is based on the simplified version described in KP-81, which keeps only the best score for each breakpoint. The general version of the algorithm keeps a larger network with breakpoints for all four fitness classes (and line numbers), so it has access to more options when it comes to choosing suboptimal breaks. Implementing that would significantly complicate the outer loop in parcomp(). In KP-81, even Knuth was not sure if it was worth while, and they were using the flawed KP-81 badness calculation that magnified that very problem.

The space adjustment problem is difficult to see until you see it. I knew the pages didn't look right somehow, but the way I discovered what it was was to place a page formatted with tweaked Heirloom next to an identical page with identical line breaks formatted by InDesign, and then I could tell that the left side of the paragraph looked different from the right side. It's subtle but it affects the overall grayness. I think it is occurring in the output code, but I've not been able to spot it. You can look at the ditroff output file that feeds dpost and find the differences in the word spaces for the two inputs. I think the automatic space might be interpreted by the output code as similar to a space at the beginning of a line (=don't adjust following spaces) but have not pursued that idea. It might also be possible that the 64-bit conversion fixed the problem.

There are a couple of other space anomalies, too. Consecutive spaces are treated as one space on the input side and up through at least the paragraph adjustment functions, but they are expanded separately in the output stage. That causes lines with consecutive spaces to protrude very obviously on the right side. Another anomaly is that the sentence spaces don't seem to act like they are being adjusted by the output stage, but they are treated as adjustable elsewhere. I haven't looked into that much, either.

There's also a problem with OpenType class kerning that causes many commercial fonts to have bad-looking kerns. Heirloom expects the first left class to be an "everything else" class (kerns that are not defined, usually meaning there's no kerning adjustment to be applied), but no commercial font I've seen is set up that way. The result is that the kerning of the first left class is applied to "everything else" rather than to just the glyphs defined by that class. Adobe original fonts, and those from a few other houses, very often use the first left class for little-used glyphs so the impact is minimized. When the first left kern class really is "everything else," Heirloom's kerning works well. Have not looked into this problem, either.

[n-t-roff]

So we agree to implement the TeX curve? So if you wish you may prepare the final source files for testing and eventually commiting.

For Heirloom compatibility I suggest a simple number register (or request) which is set to a boolean value.

I opened a new issue for the space adjustment problem (#24). You may not get a mail notification for that issue, so please have a look at it at github.

For the other issues I also suggest to open a dedicated issue. I'll have a look at it nethertheless, but if there is further discussion it is better to have it in an separate thread.

[reffort]

If Heirloom compatibility isn't the default, the Tex curve would be good as a default, but some of its design characteristics are easily bettered by the other curves. The adjacent line incompatibility penalty, for example, which doesn't do all that much for us with the other curves, appears to address an inherent deficiency in the TeX curve that is mostly taken care of by the nature of the other curves.

The suggestion to make the curve user-selectable seems fitting. If it allowed orders of 2, 3, 4, and 5, plus Heirloom compatibility, that would give the user a choice of the quadratic on one end of the scale to the TeX curve on the other (reduces hyphenation, but spaces in the normal range and a little beyond it are treated about equal). The cubic curve is implemented in Heirloom and in the current n-t-roff (although with the flawed KP-81 calculation), and appears in Knuth's 1977 "memo to self" about TeX.

Those other things all have simple workarounds, except for the OpenType class kerning one, so I don't worry much about them. If I were to pick one that really needs fixing it would be the kerning problem. I'll recheck that one space adjustment issue with n-t-roff.

[n-t-roff]

Ok, so we would have a new request to select the algorithm plus your .wordspace request. If you wish you may now prepare the commit candidate source files for review, testing and possibly refinements. (Only) IMHO the TeX characteristics (as close as possible, maybe without adjacent line incompatibility penalty) would be good as the new default, or at least it should be one of the selectable characteristics. Which other methods are available is then up to you.

[reffort]

Am at last getting back to this. Apologies for the delay.

Is there some type of test suite that I could run to determine whether or not there are any surprises? I've built the Troff User's Manual, and there were two things that didn't format correctly per the doc.tr file: the tabular description for the .lpfx request, and the tabular description for the .ta request for repeated tab stops (this looks like it is probably an automatic space problem at the end of a sentence, I'll post more detail over on that topic). Received today a test book made with n-t-roff and 64-bit dpost to check for problems with text/graphics/tables when printed on commercial printing equipment; have not had a chance to go through it in detail but haven't found any problems or surprises so far.

Below is a current description of the requests related to this topic. I'm open to suggestions about request names, behavior, etc.

There is no Heirloom compatibility mode request shown, but I think it would probably have to be limited to essentially executing the existing penalty() function instead of the new one, so it wouldn't actually be strictly compatible with Heirloom (e.g., wouldn't all new features and many bug fixes need to be disabled to be compatible?). If so, some name other than "compatibility mode" might be worth considering.

New requests (note that all penalty values are divided by 100 internally):

.wsmethod n Method used to calculate the badness and the word space / hyphenation penalty for a line. Methods (n): 0=Heirloom, 1=TeX, 2=Quadratic, 3=Cubic, 4=Quadratic with t^6 reject band, 5=Cubic with t^6 reject band, 6=KP-81. Initially 1 (TeX). With no parameter sets the method to 1 (TeX).

.wrdspc n m Defines the lower (n) and upper (m) edges of the passband for the badness calculation. Units are percent of the nominal space size set by .ss. The space size is not limited by these values; they define the space sizes where badness = 1.0 and begins to increase more sharply in accordance with the method selected. With no parameters, sets the values to 66.7 and 150.

.adjpenalty p t p is the penalty, initially 0 (off). t is the threshold. If the absolute value of the difference in the rj values of two consecutive lines is greater than the threshold, the penalty is applied. Default is 1.25. With no parameters, sets p = 100 and t = 1.25. (Input penalty of 100 equates to a badness of 1.0.) .adjpenalty 0 turns it off .adjpenalty p sets the penalty only, leaving threshold unchanged. .adjpenalty - t sets the threshold only, leaving the penalty unchanged.

The behavior of the last line of a paragraph should also be changed. Currently, the last line is filled as tightly as possible until no more characters will fit; if the last word fits on the line, the badness is not calculated (penalty = 0). Fixing that is simple, but then there will be a need to control overruns, so:

.overrunpenalty p t where p is the penalty, and t is the threshold as a percent of the full line length. If the actual length of the last line is shorter than the threshold, the penalty is applied on a sliding (cubic) scale---the shorter the line the greater the penalty. If the algorithm wants to make an adjustment, it can move the overrun line up to the previous one or words can be brought down to make the overrun longer. Initially off. With no parameters sets p=10 and t=25. (10 is a small penalty) p and t can be set independently as with adjpenalty.

.linepenalty p Adds penalty p to each line. Initially 0, with no parameters p is set to 10. This is the method TeX uses to control overruns, it will only move the overrun up into the previous line.

There is only one other useful request I've added that affects the parcomp() function: .looseness +-n to change the length of a paragraph. Why not throw that in at the same time?

[n-t-roff]

Generating the documents under doc may serve as a test suite. I compare the PostScript output with diff(1) after changes (especially for doc/troff/doc.tr), usually only the time stamp should change.

This would only be used for a regression test. For testing the new features I would use the test documents you had provided already.

I agree that there had been bug fixes or "improvements" which did already change the rendering behaviour of heirloom troff. I had this in mind--this was one of the reasons I had not been very interested in this compatibility mode. Having this mode only for penalty() may not make much sense if one wants to reproduce the output of 32 bit heirloom. In this case a true compatibility mode would be necessary to withdraw "all" changes. IMHO it is not impossible to add something for this. I would add the source code changes for this. Do you have a suggestion how to enable this mode?

I agree to the suggested requests. Details may be discussed when actual source code is available. I also agree to add the .looseness request.

[reffort]

For Heirloom compatibility, it became apparent that having the calculation type default to 0 (Heirloom) would be the way to go. In parcomp() the portions of the code that call the penalty() function and work the last line of the paragraph could be invoked with a simple test for zero or nonzero. If the user wants to use some other method, the "calculation type" variable will become nonzero. To use the Heirloom calculation without "compatibility mode," the calculation type would be set to 1, for example, turning off the compatibility mode (the "calculation type" numbers seem more intuitive if they are rearranged from what I described above). All the other stuff will initially default to "off" and be turned on by the user as desired.

Have done considerable testing with this and didn't find anything out of kilter with the routines, although I did find a few other things that should be fixed or updated (will provide a list or fixes later). Some of them are more intuitive with a different syntax for their .request. Also revised a book I did about 7 years ago in groff and revised twice with Heirloom. These routines did by themselves or with a little finesse the things I had to do by brute force before, so I feel pretty comfortable with how they work.

I became really frustrated with stuff that doesn't work (especially fonts) while wringing this out. The Torvalds rant from a couple of weeks ago sort of got me started again. Free fonts are a real mess.

I need to put this code into usable form and generate a brief tutorial, and then find out if anyone has any troubles with it. Would appreciate any pointers on the easiest way to do that.

In the meantime, here's a demo PDF with three dozen free fonts set in two-page spreads, showing the paragraphing quality in book width lines and narrow columns. This uses all of the new features, and all of the specimen pages use the same settings for those features; there was no optimization for each font (the point size was adjusted to make them about the same x-height, however). In a few cases I did use the .looseness to pull up an ornery overrun in the third paragraph. The long paragraphs show the ability to make uniform word spaces throughout the paragraph and page-to-page, except on some of the narrow-column pages, where a little tweaking of the adjustments would be beneficial.

book-v3a.pdf

[n-t-roff]

The described configuration for the new features is ok. I'd like to have something TeX-like as the default, but this is really not important. So old Heirloom behaviour can be the default as proposed by you.

IMHO it would be best to use git and GitHub for the code reviews and tests. So you could clone the whole project at GitHub, then clone it to your PC and work with "git push" then from your PC. So when others wants to test it they can clone your GitHub project. If everything is fine you make a pull request and your changes will be in this repository. Other methods (like exchanging .tgz) is possible too but this makes it more complicated for others to test it. If you have any questions regarding git or GitHub please contact me at troff@arcor.de

Thanks for preparing the demo PDF--a lot of work--it looks really good. Could I have the source please? ;)

[reffort]

An Heirloom default would probably be least disruptive for existing documents, but I have no idea if there are very many of them or not. If there aren't many Heirloom documents it wouldn't matter much what the default is. The TeX mode won't exactly match TeX's, of course, but then it is also possible to do better than TeX.

Thanks for the comments on the PDF, I was surprised by how good some of the free fonts look. Gunnar did some really nice work setting up Heirloom.

I need to change the syntax of some of the requests and clean the code up a bit, and extract it from the older version it is in, but will upload it soon as that is done.

[n-t-roff]

OT: The last release had been done a long time ago and there had been so many fixes and improvments since then so I'd like to do a new release. I intented to wait until the new paragraph formatting is available but if it is unclear when this will be it is better to do a release now and a second with the new formatting algorithm. Can you make an estimation when you have some code to be released? Could you please contact me per mail (troff@arcor.de) to discuss such things which are not of interest to most other users?

[asb]

@reffort your demo book looks great! +1 to @n-t-roff's request for the source

[n-t-roff]

Indeed, @reffort's work is really excellent.

He had already included links to older versions of his code in posts to this issue which could be merged into the repository. I would use other preferences then--make his new algorithm the default one and choose the TeX parameters as the default. But @reffort may be busy with other things, so I'll wait for some further time to let him implement it the way he prefers to. If he doesn't have time or interest anymore then some day his already available code will be include. Definitely before the next release.

@reffort if there are any technical issues with git please contact me via mail.

[reffort]

@asb Thanks for the support! @n-t-roff - will contact you per your request.

Sorry to take so long before checking back with this. I wanted to get the microtypography working because it is an important part of making paragraphs that are competitive with other applications, but I underestimated how long it would take to investigate the various methods and the time got away from me.

Attached is a PDF that describes and demonstrates the paragraphing and microtypography features and how they can be mixed and matched. There three general parts: a general description, a set of example pages, and histograms of the word spaces in the examples; the histograms show pretty well the differences in the various methods. The PDF is set up to resemble the style of a technical paper mainly so I would have an excuse to use the preprocessors.

The code needs a lot of cleanup at this point (my n7.c is 140KB); when I get it trimmed down and added to the current n-t-roff code, I'll make it available if there is still any interest in doing this.

If there are any questions, or something doesn't make sense, seems too complicated to use, etc., please feel free to comment.

about.pdf

[n-t-roff]

Thank you for your excellent work. If nobody else has an opposite opinion your work will be committed as is. This will be the major improvement of troff's typesetting quailty, more than heirloom had been in contrast to traditional troff.

[reffort]

I really appreciate your comments. The Heirloom code, though, is doing all of the heavy lifting, and the way Gunnar set it up made it straightforward to modify. I think the Heirloom features are actually the big advancement. My code is just telling some of the Heirloom code to do a few things a little differently.

[asb]

The code needs a lot of cleanup at this point (my n7.c is 140KB); when I get it trimmed down and added to the current n-t-roff code, I'll make it available if there is still any interest in doing this

There's definitely still interest here! Thanks for the detailed description of your work and demonstrations.

[reffort]

@asb, Thanks!

[aksr]

Hi reffort, any progress on this?

[reffort]

Hi, yes, the code is (at last) cleaned up and I am putting together a brief reference and test document. I hope to have it ready for folks to evaluate in a week or so.

On 12/30/2016 09:03 AM, aksr wrote:

Hi reffort, any progress on this?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/n-t-roff/heirloom-doctools/issues/22#issuecomment-269781281, or mute the thread https://github.com/notifications/unsubscribe-auth/AMxHv4NG4gOePtJ1LXKhtBark0vQaf8Bks5rNR1EgaJpZM4FbPJg.

[aksr]

reffort: That's good to hear, thank you.

[reffort]

Code for this is now at https://github.com/reffort/typo-tests .

Documentation covering the requests is in the typodoc.pdf located in the doc/typo/PDF directory. There are quite a few adjustments that can be made with these requests, so a basic starting point might be with the setups described on page 17, which emulate the major characteristics of TeX and pdfTeX.

The other files in the doc/typo/PDF directory are: demopage.pdf - a warmed over version of Gunnar's Troff Demonstration Page, and usermanual.pdf - the nroff/troff User's Manual reformatted to take advantage of the new features.

I would welcome any thoughts about improving the request names, arguments, behavior, etc. They follow a somewhat of a pattern, but in some cases they don't. None of these settings are currently part of the troff environment (mostly because I keep changing the variable names); diversions might turn out a bit different than anticipated if the settings are changed while the diversion is being built.

[n-t-roff]

An excellent work, thank you!

I would agree with the described interface and settings. BTW: Why is .elpchar necessary? Isn't this the combination of .sentchar and .transchar?

Could you please start a pull-request for your first two commits already? ("Increase buffer size to allow longer file names" and "Allow use of OS/2 table versions 4 and 5.")

For the final integration of your work I would prefer not to have generated documents in the source repository. There is already repository https://github.com/n-t-roff/heirloom for generated documents, which are then integrated in the project web page http://n-t-roff.github.io/heirloom/doctools.html . If you want you may fork https://github.com/n-t-roff/heirloom and do desired changes. It would be good (but not strictly required) to have the source code of typodoc.pdf (using free fonts) in doc/typo later. It would then be added to the automatic regression test.

[reffort]

Why is .elpchar necessary? Isn't this the combination of .sentchar and .transchar?

There is a lot of overlap, especially with the transparent characters, but the purpose of the character lists is different. If a user changes the sentchars or transchars to change where sentence spaces are applied, that shouldn't necessarily affect which punctuation characters are favored or disfavored at the end of a line.

There are also three common punctuation characters that are never sentchars or transchars: the comma, semicolon, and emdash. As a result, there would have to be a separate list of elpchars, anyway. There is a mechanism for defining custom elpchars, so if the user wants it to match the (possibly modified) transchars, requesting .elpchar \n[.transchar] is a way to do that. An entirely custom list can also be specified with .elpchar [list of characters]; the characters are not restricted to being only punctuation.

prefer not to have generated documents in the source repository

No problem. In this case, the inclusion of a readable document that describes the modifications is sort of a necessity. And the nroff/troff user's manual is the only thing I know of that might qualify as a sort of test file; it was included to show that the modifications do not appear to cause any problems when generating it (other than those caused by errors in the document source and the ones in the underlying troff code).

[n-t-roff]

Readable documents are necessary. But the place for them need not be the source repository (https://github.com/n-t-roff/heirloom-doctools). Of course it would be good to just download the source and then have all necessary documentation. But it also increases the repository size. Especially for binary formats like PDF where the whole file needs to be stored for each version. I do already include PS--which is much larger than PDF but allows differences to be stored in the repo. And the only reason I did include them is using them for regression tests. The PDF is stored in https://github.com/n-t-roff/heirloom and honestly I also would like to have your new PDF documents there. Optional PS and source code can be in https://github.com/n-t-roff/heirloom-doctools (actually it would be good to have them there, but it is not necessary if you don't like that).

Is there an issue with putting the PDFs in a different repo? There is a HTML link at top of the source repo to the doc repo anyways.

[reffort]

I don't have a problem with setting up the documentation however it makes sense. There isn't any reason I can think of for you to bring over the PDFs just because they are there. I'm guessing that github allows excluding files that you don't want; but if not, I can just remake the repository without them.

The code isn't a finished thing, yet. In addition to any bug fixes, there are some tweaks I'd like to make, and I'd really like to change the units for the letter spacing portion of the .letadj request from ens to ems so the numbers are consistent with the way tracking is usually specified (there are a number of m/2 calculations in the Heirloom code to convert ems to ens, so it would mostly be a matter of finding all of them). Similarly, the documentation should probably be expanded so it is more explanatory.

On 03/01/2017 03:00 AM, n-t-roff wrote:

Readable documents are necessary. But the place for them need not be the source repository (https://github.com/n-t-roff/heirloom-doctools). Of course it would be good to just download the source and then have all necessary documentation. But it also increases the repository size. Especially for binary formats like PDF where the whole file needs to be stored for each version. I do already include PS--which is much larger than PDF but allows differences to be stored in the repo. And the only reason I did include them is using them for regression tests. The PDF is stored in https://github.com/n-t-roff/heirloom and honestly I also would like to have your new PDF documents there. Optional PS and source code can be in https://github.com/n-t-roff/heirloom-doctools (actually it would be good to have them there, but it is not necessary if you don't like that).

Is there an issue with putting the PDFs in a different repo? There is a HTML link at top of the source repo to the doc repo anyways.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/n-t-roff/heirloom-doctools/issues/22#issuecomment-283282823, or mute the thread https://github.com/notifications/unsubscribe-auth/AMxHv6u1S1GIRGXT4UzIxYVK_6M443CIks5rhTO0gaJpZM4FbPJg.