Skip to content

Stage-Output Diff and Semantic-Equivalence Test

A stage-output comparison test — instantiates Self-Hosted Bootstrap Construction

Diffs a stage's output against a reference and, when the bytes differ for benign reasons, decides whether the two are still the same program.

Stage-Output Diff and Semantic-Equivalence Test compares what a stage produced against a reference — the prior stage, a golden build, or the spec — and, crucially, separates differences that matter from differences that don't. An embedded timestamp, a changed build path, or reordered symbols make the bytes differ while the program behaves identically. Its defining move is a two-tier compare: a byte diff first, then a semantic-equivalence judgment on whatever residue survives normalisation, yielding a promote-or-hold verdict. Where Fixed-Point Build Comparison demands byte-identity, this test is built precisely for the case where bytes legitimately differ and the real question is whether meaning is preserved.

Example

Consider a self-hosting bytecode system — a Lisp or Smalltalk image that recompiles its own compiler. When it rebuilds that compiler, the regenerated bytecode differs from the reference: the constant pool is ordered by a hash seed that changed between runs, and a build timestamp is embedded in the header. A naïve byte diff screams "different" and would block the whole ladder. The semantic-equivalence test instead normalises the known-benign axes — canonicalises constant ordering, strips the timestamp — and then compares, or runs both versions against a behavioural conformance suite, to decide they are observationally equivalent: the same program by every observation that matters.[1] Only then is the new stage marked promotable. If, after normalisation, a real opcode difference remains, the stage is held for investigation rather than waved through.

How it works

The distinguishing logic is classify-then-judge: diff the raw output, sort the differences into benign (representation) and meaningful (behaviour), normalise or behaviourally re-test the benign ones, and rule the residue against an explicit set of invariants a stage transition must preserve. The output is not a raw diff but a verdict — equivalent-and-promotable, or divergent-and-held — carrying the evidence for which it is. That verdict is the readiness signal a promotion step then acts on.

Tuning parameters

  • Normalisation aggressiveness — how many axes you canonicalise (timestamps, ordering, paths) before comparing. More normalisation tolerates benign noise but risks masking a real change.
  • Equivalence oracle — structural (normalise and diff) versus behavioural (run a conformance suite). Behavioural evidence is stronger but only as good as the suite's coverage.
  • Invariant set — which properties must be preserved to count as "equivalent" — output behaviour, ABI, resource bounds. A wider set raises the bar for promotion.
  • Verdict threshold — how clean the compare must be to promote versus hold, and how a residual diff maps to pass or fail.

When it helps, and when it misleads

Its strength is letting a bootstrap tolerate the unavoidable nondeterminism of real builds without either failing on cosmetic diffs or waving through genuine regressions — it is the adjudicator sitting between reproducible-builds strictness and "ship anything that runs." Its limit is that semantic equivalence is undecidable in general, so every test is a heuristic. Over-normalise and you can declare a genuinely changed program "equivalent" — the dangerous false pass; under-normalise and you drown in benign diffs and start ignoring the tool. The classic misuse is tuning the normaliser until the diff disappears, so a promotion already decided gets a green light — the test run backwards to justify the answer. The discipline is to freeze the invariant set and the normalisation rules before the compare, and to prefer behavioural evidence over ever-looser structural normalisation.

How it implements the components

  • stage_transition_invariant_set — it decides equivalence against an explicit set of behavioural invariants that a stage transition must preserve; this is what "the same program" is measured against.
  • independent_stage_verification_path — the diff-and-behaviour compare is a check on a stage separate from the build process that produced it.
  • readiness_criteria — its promote-or-hold verdict is the readiness signal a promotion step consumes.

It does not demand byte-identity or detect convergence to a fixed point (stage_equivalence_and_improvement_test — Fixed-Point Build Comparison), does not make the build deterministic in the first place (bootstrap_provenance_chain — Reproducible Bootstrap Build), and does not perform the promotion or rollback itself (bootstrap_checkpoint_snapshot, fallback_or_rollback_policy — Checkpointed Stage Promotion).

References

[1] Two programs are observationally (behaviourally) equivalent when no observation can distinguish them, even if their representations differ. General semantic equivalence is undecidable, so practical tests approximate it by normalising known-benign differences and comparing behaviour on a conformance suite. ↩