Should different TeX implementations (e.g. MiKTeX's and TeX Live's) produce identical DVI files?

Question

It is said that TeX is supposed to work identically on all systems. For example, Knuth's TRIP test exists to ensure that any program can be called “TeX” only if it does certain things given certain inputs. And the TeX program itself takes certain measures to prevent system-dependent factors from causing differences in behaviour, e.g. for dimensions, instead of floating-point numbers TeX uses fixed-point numbers: integer multiples of 1 sp (scaled point) which is 1/65536 of 1/72.27 of an inch.

Q1: But (apart from passing the trip test) what does it mean to behave identically?

As the output of TeX is a DVI file containing typesetting instructions (pick up font F, move right by W units, set character 97 there, etc.), one natural interpretation (it seems to me) is that the DVI files must be identical, except of course for the bytes that constitute the timestamp. Equivalently, if we run dvitype on the two files, and compare them after filtering out the timestamp line, they should contain identical instructions (is one interpretation).

But with even rather simple input files, I see discrepancies in the DVI files (i.e. beyond just the timestamp line), between MiKTeX and TeX Live. Specifically, consider the following minimal .tex input file (part of a paragraph from A Gentle Introduction to TeX):

The DVI file is then read by another program (called a
device driver) that produces the output that is readable by
humans. Why the extra file? The same DVI file can be
read by different device drivers to produce output on a dot
matrix printer, a laser printer, a screen viewer, or a
phototypesetter. Once you have

\end

When I run the above file through two programs named TeX, namely:

MiKTeX-TeX 2.9.6300 (3.14159265) (MiKTeX 2.9.6600)

and

TeX 3.14159265 (TeX Live 2017)

both on the same computer (macOS 10.13.3 High Sierra), the output of TeX (the DVI files) look visually identical, but are of different sizes (different number of bytes). When the actual instructions (opcodes) contained in the DVI files are compared (by running dvitype on each file), there are hundreds of minor differences. In this case, the first is

10c10
< Postamble starts at byte 561.
---
> Postamble starts at byte 564.

which is caused by a diff that occurs later below:

< 436: w0 261236 h:=9392617+261236=9653853, hh:=611 
< 437: setchar112 h:=9653853+364090=10017943, hh:=634 
< 438: setchar114 h:=10017943+256683=10274626, hh:=650 
< 439: setchar105 h:=10274626+182045=10456671, hh:=662 
< 440: setchar110 h:=10456671+364090=10820761, hh:=685 
< 441: x2 -18205 h:=10820761-18205=10802556, hh:=684 
< 444: setchar116 h:=10802556+254863=11057419, hh:=700 
< 445: setchar101 h:=11057419+291271=11348690, hh:=718 
< 446: setchar114 h:=11348690+256683=11605373, hh:=734 
< 447: setchar44 h:=11605373+182045=11787418, hh:=746 
< 448: right3 271931 h:=11787418+271931=12059349, hh:=764 
< 452: setchar97 h:=12059349+327681=12387030, hh:=785 
---
> 436: right3 261235 h:=9392617+261235=9653852, hh:=611 
> 440: setchar112 h:=9653852+364090=10017942, hh:=634 
> 441: setchar114 h:=10017942+256683=10274625, hh:=650 
> 442: setchar105 h:=10274625+182045=10456670, hh:=662 
> 443: setchar110 h:=10456670+364090=10820760, hh:=685 
> 444: x2 -18205 h:=10820760-18205=10802555, hh:=684 
> 447: setchar116 h:=10802555+254863=11057418, hh:=700 
> 448: setchar101 h:=11057418+291271=11348689, hh:=718 
> 449: setchar114 h:=11348689+256683=11605372, hh:=734 
> 450: setchar44 h:=11605372+182045=11787417, hh:=746 
> 451: right3 271932 h:=11787417+271932=12059349, hh:=764 
> 455: setchar97 h:=12059349+327681=12387030, hh:=785 

or if you'd like to see it vertically side-by-side:

436: w0 261236 h:=9392617+261236=9653853, hh:=611             | 436: right3 261235 h:=9392617+261235=9653852, hh:=611 
437: setchar112 h:=9653853+364090=10017943, hh:=634           | 440: setchar112 h:=9653852+364090=10017942, hh:=634 
438: setchar114 h:=10017943+256683=10274626, hh:=650          | 441: setchar114 h:=10017942+256683=10274625, hh:=650 
439: setchar105 h:=10274626+182045=10456671, hh:=662          | 442: setchar105 h:=10274625+182045=10456670, hh:=662 
440: setchar110 h:=10456671+364090=10820761, hh:=685          | 443: setchar110 h:=10456670+364090=10820760, hh:=685 
441: x2 -18205 h:=10820761-18205=10802556, hh:=684            | 444: x2 -18205 h:=10820760-18205=10802555, hh:=684 
444: setchar116 h:=10802556+254863=11057419, hh:=700          | 447: setchar116 h:=10802555+254863=11057418, hh:=700 
445: setchar101 h:=11057419+291271=11348690, hh:=718          | 448: setchar101 h:=11057418+291271=11348689, hh:=718 
446: setchar114 h:=11348690+256683=11605373, hh:=734          | 449: setchar114 h:=11348689+256683=11605372, hh:=734 
447: setchar44 h:=11605373+182045=11787418, hh:=746           | 450: setchar44 h:=11605372+182045=11787417, hh:=746 
448: right3 271931 h:=11787418+271931=12059349, hh:=764       | 451: right3 271932 h:=11787417+271932=12059349, hh:=764 
452: setchar97 h:=12059349+327681=12387030, hh:=785           | 455: setchar97 h:=12059349+327681=12387030, hh:=785 

and after that, everything occurs three bytes later in the latter file (the one generated by TeX Live tex), including finally the postamble. These correspond to the section printer, a, and as we can see, there's a difference of 1 unit between the glue that was used in the two cases, which got back in sync after this run of text, and also a difference of a w0 versus a right3 instruction, which caused all future instructions to start at different bytes.

Q2: Is this discrepancy between MiKTeX and TeX Live a bug in either of them? Evidently the two programs must have implemented rounding differently, somewhere. Is one of them failing to do it the “right” way (if there's one)?

I know that the discrepancy is tiny. A difference of 1 unit in the DVI file (DVI unit?), corresponds, if I remember correctly, to 1 sp, which is a difference of about 5 nanometres, smaller than the wavelength of visible light. Even if the unit is not exactly 1 sp, I've somewhere seen these units called “RSUs”, for “Ridiculously Small Unit”. So unless the DVI files were output at some ridiculous (physically impossible) resolution and/or magnification, the difference wouldn't matter in practice, as far as being able to tell apart the output visually.

Nevertheless, there is a difference, and isn't TeX supposed to produce identical results on all systems? (Note I'm not using pdfTeX or eTeX but just what's supposed to be Knuth's TeX.) This difference makes it hard to know when two TeX implementations are behaving identically. So, the last couple of questions:

Q3: Is some amount of rounding error / floating-point discrepancy acceptable, between TeX implementations? If so, how much exactly is acceptable? The TRIP test document is itself confusing on this matter, as it says things like (emphases mine):

Glue settings in the displays of TeX boxes are subject to system-dependent rounding, so slight deviations are permissible. However, such deviations apply only to the glue set values that appear at the end of an \hbox or \vbox line; all other numbers should agree exactly, since they are computed with integer arithmetic in a prescribed system-independent manner.

…

The resulting file should agree with the master TRIP.TYP file of step 0, except that some of the values might be a little off due to floating-point rounding discrepancies. Furthermore there may be differences between ‘right’ and ‘w’ and ‘x’ commands, and between ‘down’ and ‘y’ and ‘z’; the key thing is that all characters and rules and xxx’s should be in almost the same positions as specified in Appendix F.

Q4: Finally, given that not just the positions but even the commands (and consequently all subsequent bytes) can differ between TeX implementations, how can we test that a new TeX implementation is behaving properly / identically to “real” TeX, in the sense of producing “essentially” identical DVI files? Clearly, simply running diff on the DVI files (after dvitype) is unworkable as it profusely produces evidently insignificant differences. Is there some tool (like the “you may want to write a DVIcompare program” that Knuth mentions), or some other suite of tests?

Answer 1

TeX is concerned with typesetting on a physical medium (eg paper). For Don identical output means a visually equal look and any user-level calculations are exactly identical (which is why you can't get at some internals of TeX and use their values as they might differ from installation to installation). This means that line and page breaks are supposed to be exactly at the same point. However he deliberately used floating point to calculate parts of the glue handling (in a way that it can't change line or page breaks) but when writing to the dvi file the resulting exact positions of the characters may be off by a tiny fraction.

To answer your explicit questions:

Q1: that is really showing what is explained in the TRIP test manual (the part that you cite in Q3).

Q2: no bug (because of what is written in the TRIP test manual)

Q3: not sure what is confusing about that statement. Note that "glue setting" is when finally determining the exact spots in the dvi file, when glue is used inside TeX, eg to determine line breaks it is still used with fixed point so there such differences will not show up.

Q4 you can't by looking at the dvi file (which the trip test doesn't do afaik). I dont think you can even by looking at the "Completed box shipped out" data without masking possible rounding errors in the (glue set ...) parts shown there. But that masking is possible and all other parts of the symbolic output display will be exactly the same and that is what we, for example use in the LaTeX regression test suite to compare output after changes made to the LaTeX code.

Answer 2

For web2c, I documented why all the differences are considered acceptable in web2c/triptrap/README, that is, http://tug.org/svn/texlive/trunk/Build/source/texk/web2c/triptrap/README?view=markup