Skip to main content

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}