Plan, apply and roll back changes to a production ontology, with a blast radius report and a proof an auditor can re-check.
Rust ai-nativedescription-logicsformal-verificationinfrastructure-as-codeisabelle-languageknowledge-graphleanlean4mcpmcp-serverontologyowlowl2reasoningrustshaclsparqltheorem-proving
import Dl.All
import SelfId.All
/-!
`oo-dlrefute AXIOMS.tsv REFUTATION.cert`
Reads an axiom set and a closed tableau, replays the tableau, and prints one
JSON object.
Exit codes, matching the convention `oo-cert` and `oo-dlmodel` use:
* `0` the tableau is closed, so the axiom set has NO MODEL, of any size, finite
or infinite. The statement covering that is `Dl.unsatisfiable_of_check`, and
`Dl.no_model_of_check` is the same verdict in the finite form the rest of the
repository states its answers in.
* `1` the tableau is not closed. That is a statement about the certificate and
NOT about the ontology: a producer can fail to find a refutation that exists,
and this exit code never means the ontology is consistent.
* `2` a file could not be read or parsed. No verdict either way.
This is the other half of `oo-dlmodel`. That one certifies SATISFIABILITY by
exhibiting a model; this one certifies UNSATISFIABILITY by exhibiting a
refutation, and the two are asymmetric on purpose. A model is a finite object
that can be checked by evaluation. A refutation cannot be, because the thing it
denies is a claim about every interpretation including the infinite ones, which
is why `Dl/General.lean` exists at all: the finite semantics literally cannot
state the conclusion.
What exit 0 does NOT say:
* it says nothing about whether `AXIOMS.tsv` is your ontology. The OWL parser in
`src/tableaux.rs` is outside the theorem, exactly as the N-Triples parser is
outside `Shacl.validate_spec`. What is certified is a relation between two
files;
* it says nothing about transitive, symmetric, inverse or inverse-functional
roles. The calculus has no rules for them, so an ontology inconsistent only
through those cannot be refuted here. The emitter declines rather than
guessing, and "no certificate" is not a verdict.
The diagnostic that names the failing step is unverified and runs only after the
verified checker has already said no. It restates the side conditions a second
time, so it can be wrong about WHICH step failed; it cannot be wrong about THAT
one did, because the verified checker decided that.
-/
open Dl
def jsonStr (s : String) : String :=
let escaped := s.foldl (fun acc c =>
match c with
| '"' => acc ++ "\\\""
| '\\' => acc ++ "\\\\"
| '\n' => acc ++ "\\n"
| '\t' => acc ++ "\\t"
| c => acc.push c) ""
"\"" ++ escaped ++ "\""
def stepKind : Cert → String
| .botC .. => "bot-clash"
| .negC .. => "negation-clash"
| .diffC .. => "inequality-clash"
| .disjC .. => "disjointness-clash"
| .minmaxC .. => "bound-clash"
| .maxC .. => "cardinality-clash"
| .instS .. => "assertion"
| .relS .. => "role-assertion"
| .subS .. => "subsumption"
| .domS .. => "domain"
| .rngS .. => "range"
| .subroleS .. => "role-hierarchy"
| .nonemptyS .. => "non-emptiness"
| .andS .. => "conjunction"
| .allS .. => "universal"
| .exS .. => "existential"
| .minS .. => "at-least"
| .orS .. => "disjunction"
def steps : Cert → Nat
| .botC .. | .negC .. | .diffC .. | .disjC .. | .minmaxC .. | .maxC .. => 1
| .instS _ _ k | .relS _ _ _ k | .subS _ _ _ k | .domS _ _ _ _ k
| .rngS _ _ _ _ k | .subroleS _ _ _ _ k | .nonemptyS _ _ k | .andS _ _ _ k
| .allS _ _ _ _ k | .exS _ _ _ _ k | .minS _ _ _ _ _ k => 1 + steps k
| .orS _ _ _ l r => 1 + steps l + steps r
/-- The children of a step, each with the branch it is checked against. Mirrors
`Dl.check` and is not proved to; it is read only by the diagnostic. -/
def children : Cert → List Constraint → List (Cert × List Constraint)
| .instS a c k, Γ => [(k, Constraint.conc a c :: Γ)]
| .relS a r b k, Γ => [(k, Constraint.role r a b :: Γ)]
| .subS x _ d k, Γ => [(k, Constraint.conc x d :: Γ)]
| .domS x _ _ c k, Γ => [(k, Constraint.conc x c :: Γ)]
| .rngS _ y _ c k, Γ => [(k, Constraint.conc y c :: Γ)]
| .subroleS x y _ t k, Γ => [(k, Constraint.role t x y :: Γ)]
| .nonemptyS y c k, Γ => [(k, Constraint.conc y c :: Γ)]
| .andS x c d k, Γ => [(k, Constraint.conc x c :: Constraint.conc x d :: Γ)]
| .allS _ y _ c k, Γ => [(k, Constraint.conc y c :: Γ)]
| .exS x y r c k, Γ => [(k, Constraint.role r x y :: Constraint.conc y c :: Γ)]
| .minS x r c _ ys k, Γ => [(k, minExpand r x c ys ++ Γ)]
| .orS x c d l r, Γ => [(l, Constraint.conc x c :: Γ), (r, Constraint.conc x d :: Γ)]
| _, _ => []
/-- Descend to the shallowest step whose own side conditions fail, or to the
shallowest step none of whose children check. Fuel is the tree size. -/
def firstBad (A : List Axiom) : Nat → Cert → List Constraint → String
| 0, t, _ => stepKind t
| fuel + 1, t, Γ =>
match (children t Γ).find? (fun p => !check A p.1 p.2) with
| some p => firstBad A fuel p.1 p.2
| none => stepKind t
def readOrFail (path : String) : IO (Except UInt32 String) := do
try
return .ok (← IO.FS.readFile path)
catch e =>
IO.eprintln s!"cannot read {path}: {e}"
return .error 2
def run (axPath cPath : String) : IO UInt32 := do
let axTxt ← match ← readOrFail axPath with
| .ok s => pure s
| .error c => return c
let cTxt ← match ← readOrFail cPath with
| .ok s => pure s
| .error c => return c
match Parse.parseAxioms axTxt, Parse.parseCert cTxt with
| .ok A, .ok t =>
if check A t [] then
SelfId.println ("{\"ok\":true,\"axioms\":" ++ toString A.length ++
",\"steps\":" ++ toString (steps t) ++
",\"verdict\":\"unsatisfiable\"" ++
",\"theorem\":\"Dl.unsatisfiable_of_check\"}")
return 0
else
IO.println ("{\"ok\":false,\"axioms\":" ++ toString A.length ++
",\"steps\":" ++ toString (steps t) ++
",\"first_rejected\":" ++ jsonStr (firstBad A (steps t) t []) ++
",\"note\":\"a rejected refutation says nothing about the ontology\"}")
return 1
| .error e, _ =>
IO.eprintln e
return 2
| _, .error e =>
IO.eprintln e
return 2
def main (args : List String) : IO UInt32 := do
match args with
-- FIRST, because `oo-resolution` and friends take a single positional
-- argument and a later arm would swallow `--version` as a path (#204).
| ["--version"] => SelfId.emitVersion
| [a, c] => run a c
| _ =>
IO.eprintln "usage: oo-dlrefute AXIOMS.tsv REFUTATION.cert"
return 2