logicaffeine_proof/decide.rs
1//! `decide` — proof by evaluation for closed decidable goals.
2//!
3//! The router below is untrusted: it evaluates the goal with exact integer
4//! arithmetic and, only when the goal is TRUE, builds the derivation whose
5//! leaves re-derive that truth through certified channels — `ArithDecision`
6//! (the proof-producing arithmetic oracle) for ground `Int` identities,
7//! `NativeDecide` (the kernel's trusted-evaluator route via the `reduceBool`
8//! hook and a `Decidable` instance) for ground comparisons and Bool
9//! equalities, and `GroundRefutation` (the `Bool` no-confusion discriminator,
10//! after transport for `Int`) for a NEGATION whose subject computes false.
11//! Propositional structure recurses through the ordinary intro rules. A false,
12//! open, or unsupported goal yields `Verdict::Undecided` — decide DECLINES,
13//! it never guesses — and a goal it evaluated and found FALSE says so, which
14//! is a different answer and must not be conflated with the first.
15//!
16//! The evaluator is arbitrary-precision, through `crate::numeral`: both
17//! kernels compute integers exactly, so the router's own window must not be
18//! the system's arithmetic ceiling.
19
20use logicaffeine_base::BigInt;
21
22use crate::numeral::int_of_constant;
23use crate::{DerivationTree, InferenceRule, ProofExpr, ProofTerm};
24
25/// What `decide` found. The old single `Option` conflated "I cannot evaluate
26/// this" with "I evaluated it and it is FALSE" — and a caller that treats the
27/// second as the first keeps searching past a goal that is not true, until some
28/// unrelated contradiction discharges it by ex falso. The distinction is the
29/// capability, so it is in the type.
30#[derive(Debug, Clone)]
31pub(crate) enum Verdict {
32 /// The goal evaluates TRUE and here is the certificate for it.
33 True(DerivationTree),
34 /// The goal was fully evaluated and is FALSE. Nothing to build, and nothing
35 /// else will prove it either.
36 False,
37 /// Not a closed goal in the decidable fragment — no verdict either way.
38 Undecided,
39}
40
41/// `div`/`mod` at arbitrary precision, in Lean's EUCLIDEAN convention, and TOTAL.
42///
43/// THE SPECIFICATION is the one written out in
44/// `logicaffeine_kernel::reduction::ediv_emod_i64`'s doc comment, which every engine that
45/// folds division on literals implements FROM THE TEXT:
46///
47/// ```text
48/// b ≠ 0 ⟹ a = b·q + r ∧ 0 ≤ r < |b| (the unique such pair)
49/// b = 0 ⟹ q = 0 ∧ r = a
50/// ```
51///
52/// This router is the FIFTH such engine — beside `reduction::try_primitive_reduce`, the second
53/// kernel's `recheck::try_builtin`, `eval::prim_arith` and `simp::try_arithmetic` — and it is
54/// written by its OWN derivation, never by copying one of the other four, so a slip in one
55/// derivation cannot hide in another.
56///
57/// `BigInt::div_rem` is TRUNCATED (the quotient rounds toward zero and the remainder carries
58/// the dividend's sign), so it is used only where the two conventions provably cannot differ:
59/// on the MAGNITUDES, which are non-negative. The signs are then reconstructed from the
60/// division identity itself. Writing `|a| = q₀·|b| + r₀` with `0 ≤ r₀ < |b|`:
61///
62/// * `a ≥ 0` — `r₀` is already in range, and `a = q₀·|b|`, so `q = q₀·sgn b`.
63/// * `a < 0` and `r₀ = 0` — `a = -q₀·|b|` exactly, so `r = 0` and `q = -q₀·sgn b`.
64/// * `a < 0` and `r₀ > 0` — negating `r₀` would leave the range, so take the COMPLEMENT
65/// `r = |b| - r₀`, which lies in `(0, |b|)`; then
66/// `a = -q₀|b| - r₀ = -(q₀+1)·|b| + (|b| - r₀)`, so `q = -(q₀+1)·sgn b`.
67///
68/// The truncating router this replaces answered `div(-7, 2) = -3` where all four kernel engines
69/// answer `-4`, and got STUCK at a zero divisor where they answer `0` — so it called a true
70/// goal [`Verdict::False`], whose documented meaning is "nothing else will prove it either",
71/// and handed a false one to the trust door as an `ArithDecision` the arithmetic oracle then
72/// refused, which is a tactic reporting success without a checkable object.
73fn ediv_emod(a: &BigInt, b: &BigInt) -> (BigInt, BigInt) {
74 if b.is_zero() {
75 return (BigInt::zero(), a.clone());
76 }
77 let magnitude = b.abs();
78 let (q0, r0) = a
79 .abs()
80 .div_rem(&magnitude)
81 .expect("a non-zero divisor has a quotient");
82 let (unsigned_q, remainder) = if !a.is_negative() {
83 (q0, r0)
84 } else if r0.is_zero() {
85 (q0.negated(), r0)
86 } else {
87 (q0.add(&BigInt::from_i64(1)).negated(), magnitude.sub(&r0))
88 };
89 let quotient = if b.is_negative() {
90 unsigned_q.negated()
91 } else {
92 unsigned_q
93 };
94 (quotient, remainder)
95}
96
97/// Evaluate a ground integer term: numeric constants and `add`/`sub`/`mul`/
98/// `div`/`mod` trees over them, at ARBITRARY precision. Division is
99/// [`ediv_emod`] — Euclidean and total, the answer both kernels give.
100fn eval_int(t: &ProofTerm) -> Option<BigInt> {
101 match t {
102 ProofTerm::Constant(s) => int_of_constant(s),
103 ProofTerm::Function(op, args) if args.len() == 2 => {
104 let a = eval_int(&args[0])?;
105 let b = eval_int(&args[1])?;
106 match op.as_str() {
107 "add" | "Add" => Some(a.add(&b)),
108 "sub" | "Sub" => Some(a.sub(&b)),
109 "mul" | "Mul" => Some(a.mul(&b)),
110 "div" | "Div" => Some(ediv_emod(&a, &b).0),
111 "mod" => Some(ediv_emod(&a, &b).1),
112 _ => None,
113 }
114 }
115 _ => None,
116 }
117}
118
119fn ground_bool(t: &ProofTerm) -> Option<bool> {
120 match t {
121 ProofTerm::Constant(s) if s == "true" => Some(true),
122 ProofTerm::Constant(s) if s == "false" => Some(false),
123 _ => None,
124 }
125}
126
127/// Evaluate a ground comparison term `le(a, b)`/`lt`/`ge`/`gt` to its truth.
128fn eval_comparison(t: &ProofTerm) -> Option<bool> {
129 let ProofTerm::Function(name, args) = t else {
130 return None;
131 };
132 if args.len() != 2 {
133 return None;
134 }
135 let a = eval_int(&args[0])?;
136 let b = eval_int(&args[1])?;
137 match name.as_str() {
138 "le" => Some(a <= b),
139 "lt" => Some(a < b),
140 "ge" => Some(a >= b),
141 "gt" => Some(a > b),
142 _ => None,
143 }
144}
145
146/// The truth value of a ground `Identity`, when every operand evaluates —
147/// `None` when the identity is not closed in the fragment. Returns the rule
148/// that re-derives it too, because which certified channel applies is decided
149/// by the same case split that decides the truth.
150fn eval_identity(l: &ProofTerm, r: &ProofTerm) -> Option<(bool, InferenceRule)> {
151 // Ground comparison in the canonical encoding `le(a, b) = true` (or
152 // `= false`): the kernel evaluator re-derives it.
153 if let (Some(truth), Some(claimed)) = (eval_comparison(l), ground_bool(r)) {
154 return Some((truth == claimed, InferenceRule::NativeDecide));
155 }
156 // …and the mirrored encoding `true = le(a, b)`, which a translator writes
157 // just as readily and which the old router declined outright.
158 if let (Some(claimed), Some(truth)) = (ground_bool(l), eval_comparison(r)) {
159 return Some((truth == claimed, InferenceRule::NativeDecide));
160 }
161 // Ground Int identity: the arithmetic oracle re-derives it.
162 if let (Some(a), Some(b)) = (eval_int(l), eval_int(r)) {
163 return Some((a == b, InferenceRule::ArithDecision));
164 }
165 // Ground Bool identity: the kernel evaluator re-derives it.
166 if let (Some(a), Some(b)) = (ground_bool(l), ground_bool(r)) {
167 return Some((a == b, InferenceRule::NativeDecide));
168 }
169 None
170}
171
172/// Decide a closed goal. See [`Verdict`] — `True` carries a derivation whose
173/// leaves certify through `ArithDecision`/`NativeDecide`/`GroundRefutation` and
174/// whose structure goes through the intro rules.
175pub(crate) fn decide_verdict(goal: &ProofExpr) -> Verdict {
176 match goal {
177 ProofExpr::Identity(l, r) => match eval_identity(l, r) {
178 Some((true, rule)) => Verdict::True(DerivationTree::leaf(goal.clone(), rule)),
179 Some((false, _)) => Verdict::False,
180 None => Verdict::Undecided,
181 },
182 // ¬P for a P that COMPUTES FALSE. The dual `Decidable` instances give
183 // only through `of_decide_eq_true`; this goes through `Bool`'s
184 // no-confusion discriminator instead, which the trusted base already
185 // has — see `InferenceRule::GroundRefutation`.
186 ProofExpr::Not(inner) => match decide_verdict(inner) {
187 Verdict::False => {
188 // Only a ground (dis)equality has a refutation channel; the
189 // certifier re-checks that, but declining here keeps the
190 // tactic's answer honest instead of deferring it to `qed`.
191 if matches!(inner.as_ref(), ProofExpr::Identity(_, _)) {
192 Verdict::True(DerivationTree::leaf(
193 goal.clone(),
194 InferenceRule::GroundRefutation,
195 ))
196 } else {
197 Verdict::Undecided
198 }
199 }
200 // ¬P where P is TRUE: the goal is false, decidedly.
201 Verdict::True(_) => Verdict::False,
202 Verdict::Undecided => Verdict::Undecided,
203 },
204 ProofExpr::And(l, r) => match (decide_verdict(l), decide_verdict(r)) {
205 (Verdict::True(lt), Verdict::True(rt)) => Verdict::True(DerivationTree::new(
206 goal.clone(),
207 InferenceRule::ConjunctionIntro,
208 vec![lt, rt],
209 )),
210 (Verdict::False, _) | (_, Verdict::False) => Verdict::False,
211 _ => Verdict::Undecided,
212 },
213 ProofExpr::Or(l, r) => match (decide_verdict(l), decide_verdict(r)) {
214 (Verdict::True(side), _) | (Verdict::Undecided, Verdict::True(side)) => Verdict::True(
215 DerivationTree::new(goal.clone(), InferenceRule::DisjunctionIntro, vec![side]),
216 ),
217 (Verdict::False, Verdict::True(side)) => Verdict::True(DerivationTree::new(
218 goal.clone(),
219 InferenceRule::DisjunctionIntro,
220 vec![side],
221 )),
222 (Verdict::False, Verdict::False) => Verdict::False,
223 _ => Verdict::Undecided,
224 },
225 // An implication holds by weakening whenever its consequent decides
226 // true. A FALSE consequent is not a false implication — the antecedent
227 // may be unsatisfiable — so that case is `Undecided`, not `False`.
228 ProofExpr::Implies(_, r) => match decide_verdict(r) {
229 Verdict::True(rt) => Verdict::True(DerivationTree::new(
230 goal.clone(),
231 InferenceRule::ImpliesIntro,
232 vec![rt],
233 )),
234 _ => Verdict::Undecided,
235 },
236 _ => Verdict::Undecided,
237 }
238}
239
240/// The historical shape: `Some(tree)` iff the goal decides TRUE. Kept because
241/// callers that only want the certificate should not have to match three ways.
242pub(crate) fn decide_expr(goal: &ProofExpr) -> Option<DerivationTree> {
243 match decide_verdict(goal) {
244 Verdict::True(tree) => Some(tree),
245 _ => None,
246 }
247}