Plan, apply and roll back changes to a production ontology, with a blast radius report and a proof an auditor can re-check.
rocq/: an independent third formalisation of the Horn certificate checker
This directory is a third formalisation of the Horn certificate checker and its model
theory, in Rocq 9.2 (the proof assistant formerly called Coq). It exists for the reason
isabelle/ exists: a machine-checked proof rules out a bad argument and says nothing
about a bad definition, and a bad definition is invisible from inside a single
formalisation by construction. A second reading catches a definitional mistake only if the
second reading is genuinely a second one.
It is smaller than either of the other two and it says so throughout. What is covered and what is not is in "Scope" below, and the boundary is stated in the negative, because a third formalisation that overclaims is worse than no third formalisation.
Build
Needs Rocq 9.2 and an OCaml compiler. Both come from brew install rocq on macOS
(rocq 9.2.0 with OCaml 5.5.0 as of this writing) and from apt-get install rocq-prover
or the rocq-prover/rocq Docker image elsewhere.
rocq/build.sh
That regenerates the fixture data, compiles every theory, checks the axiom footprint and
links the extracted checker into rocq/build/oo-horn-rocq. It fails if any audited
theorem is not closed under the global context.
rocq/build.sh --prove-the-gate-can-fail
That copies the tree, replaces one Qed with Admitted, runs the same build, and fails
if the build SUCCEEDS. A gate nobody has watched fail is decoration.
Run the checker
rocq/build/oo-horn-rocq check RULES.tsv ASSERTED.tsv HORN.tsv
Exit 0 accepted, 1 rejected, 2 unreadable or unparseable. One JSON object on stdout. The
CLI shape and the exit codes are lean/HMain.lean's deliberately, so the differential
compares two checkers rather than two ways of being invoked.
How independent is it, exactly
Less independent than isabelle/, and the difference matters enough to be the second
section of this file rather than a footnote.
Read while this was written: docs/lean-certificates.md, decision records 0002, 0003
and 0008, docs/reasoning-systems-inventory.md, isabelle/README.md, the committed
fixture bytes under tests/fixtures/horn/, and lean/HMain.lean for the command line,
the exit codes and the two verdict words.
Not opened: every file under lean/OOCert/, including Horn.lean, HornBuiltin.lean,
HornParse.lean and Parse.lean, and every .thy file under isabelle/. No definition,
no proof and no rule lemma from either was read. Both directories were LISTED, which is how
this paragraph can name the files it did not open, and a file name is not a definition.
Known leakage, stated because it is unavoidable and because a reader should discount
for it: decision 0008 quotes Lean's substOf and Isabelle's distinct (map fst b) in
its own text, so the shape of the two well-formedness conjuncts was known before
Checker.v was written, and Determinacy.v re-derives a property those records describe
rather than discovering it. That part of this development corroborates; it does not
discover. Everything else, the model theory, the premise discipline, the parser's
decisions and all twenty-seven built-in arms, was designed from the specifications and the
fixture data.
Nothing here should ever be edited to agree with lean/ or with isabelle/. If the three
disagree, that is a finding and it belongs in a report before it belongs in a patch.
Scope: what is covered
- The rule-relative soundness theorem, end to end from the bytes.
run_is_soundinRun.vtakes three file contents, and says that if the tool accepts then every conclusion of the parsed certificate is true in every world that satisfies the parsed graph and every parsed rule. - The absolute theorem for the built-in table.
entails_of_builtin_horninBuiltin.v: a certificate over exactly the built-in twenty-seven rows has conclusions true in every model of the asserted graph, with no rule assumed. Each of the twenty-seven arms is derived from the semantic conditions ofInterp.vand each takes exactly the conditions it uses as explicit hypotheses. - What the two well-formedness conjuncts buy, and what they do not.
horn_certificate_sound_without_wellformednessproves the soundness theorem with both conjuncts deleted, so neither carries soundness content, andwellformed_determines_instantiationproves what they do carry. Both halves are refuted with their own hypothesis dropped. - Non-vacuity.
Witness.vexhibits a model of the conditions, exhibits a triple that is not absolutely entailed, and exhibits a one-line user rule table under which that same triple IS relatively entailed. The last of those is decision 0003's point as a theorem: the two verdicts are different claims. - The transcribed table is the committed one.
Fixtures.vparsestests/fixtures/horn/builtin_rules.tsvwith this development's own parser inside the kernel and requires the result to equal the tableBuiltin.vproves things about. - Every shipped fixture's verdict, computed by the kernel. Also in
Fixtures.v, which is the only handle this development has on the extraction step.
Scope: what is NOT covered
- The four non-Horn rules.
cls-int1,cls-int2,cls-uniandcls-ooread an RDF list off the graph, so their premise count is data rather than fixed by the rule. They are outside the Horn family and outside this directory, as they are outside the Lean's Horn layer. - Everything else in
lean/. The mixed certificate layer, refutations, the description-logic model certificates, the first-order model checker, the SHACL evaluator, the institution and comorphism material: none of it is formalised here and none of it is even referred to. - That the conditions in
Interp.vare a subset of the Recommendation's. They are written from the RDF 1.1 and OWL 2 RDF-Based Semantics conditions and each carries the clause it is meant to be, but the correspondence is read cell by cell by a human and is not a theorem. That a subset is the safe direction is the reason it is allowed to be prose; a superset would not be. - The biconditional reading is a strengthening, and fourteen arms depend on it.
R-INT-5 in
Interp.vis the warning. RDFS states its conditions as implications, and no implication in that direction licenses a rule that CONCLUDES asubClassOf,subPropertyOf,domainorrangetriple. The OWL 2 RDF-Based Semantics states the same conditions as biconditionals, which is stronger, which makes the model class smaller and the absolute claim weaker than it looks. The fourteen arms that consume a backward condition are named inBuiltin.vand each one carries the hypothesis in its own statement, so the count is checked against the source text bythe_fourteen_arms_that_need_a_backward_condition_are_the_fourteen_namedrather than counted by hand.R-BLT-3carries the qualification that count needs: six other conditions are biconditionals too, and arms consume their reverse direction, but those are biconditional because that is whatsomeValuesFromandsameAsMEAN rather than because this development strengthened them. The fourteen is the count of arms resting on a reading stronger than the specification they come from, which is the number that matters, and it is not the count of arms that use aniff. - A total denotation. R-INT-2: interpretations in which some literal fails to denote are outside the claim.
- Extraction.
Extract.vuses noExtract Inductiveand noExtract Constant, so the trusted glue is as small as it gets, but the extraction mechanism itself is trusted and is not verified.Fixtures.vcomputes the shipped verdicts inside the kernel and the differential runs the extracted binary over the same files, so a divergence between the two is visible; that is a check, not a proof. - The driver.
driver/main.mlis untrusted, asisabelle/driver/is and aslean/HMain.leanis. It opens files, converts at the boundary, prints JSON and returns an exit code. - Anything about the engine. The theorem is conditional on the asserted graph being
what the file says it is.
docs/trusted-computing-base.mdis where that boundary lives.
Files
| file | what it holds |
|---|---|
theories/Syntax.v |
terms, triples, patterns, rules, steps. No semantics, no checking. |
theories/Semantics.v |
worlds, satisfaction, the rule-relative entailment relation. |
theories/Checker.v |
the executable checker. No semantics. |
theories/Determinacy.v |
what distinct keys and coverage buy, and refutations without each. |
theories/Sound.v |
horn_certificate_sound, and the same theorem with both conjuncts deleted. |
theories/Interp.v |
RDF-based interpretations and the seventeen semantic conditions. |
theories/Builtin.v |
the table as data, the twenty-seven arms, entails_of_builtin_horn. |
theories/Parse.v |
TSV bytes to datatypes, and the rule-table comparison. |
theories/Run.v |
the outcome type and run_is_sound, the end-to-end statement. |
theories/Witness.v |
non-vacuity, and the gap between the two verdicts. |
theories/Fixtures.v |
the checker run on the committed bytes, inside the kernel. |
theories/Audit.v |
Print Assumptions on every advertised theorem. |
theories/Extract.v |
extraction to OCaml, with no mapping of any inductive. |
theories/FixtureData.v |
GENERATED and gitignored. gen_fixture_data.sh writes it. |
driver/main.ml |
the untrusted driver. |
build.sh |
build, audit, link, and the mutation that proves the audit can fail. |
Trust boundary
Inside: the Rocq kernel and the theories above.
Outside: the extraction mechanism, the OCaml compiler, file IO, splitting bytes,
JSON, exit codes, and the claim that asserted.tsv is the store it says it is.
The differential
tests/rocq_kernel_differential_test.rs runs this checker and the Lean one over one
corpus built from tests/fixtures/horn/ and systematic mutations of it, and classifies
every row. THE NUMBERS ARE NOT WRITTEN HERE. cargo test --test rocq_kernel_differential_test -- --nocapture prints them and is the only place they
should be read from. What the comparison found, and what it means, is in
docs/decisions/0015-a-blank-line-is-a-line-or-it-is-not.md.