logicaffeine_proof/tactic.rs
1//! A tactic framework with a first-class goal state — the interactive proof
2//! interface (ROOT R5 of the Lean-competitive architecture).
3//!
4//! A [`ProofState`] holds the open [`Goal`]s; a *tactic* transforms the focused
5//! goal, replacing it with zero or more subgoals and recording the inference rule
6//! used. When no goals remain, [`ProofState::qed`] assembles the recorded steps
7//! into a single [`DerivationTree`] and runs it through the SAME trust door as
8//! every other proof ([`check_derivation`]): the certifier turns it into a kernel
9//! term and the kernel re-checks that term against the goal. So a tactic proof is
10//! exactly as trusted as an automated one — the tactics only *build* the
11//! derivation the kernel validates, they are never themselves trusted.
12//!
13//! The backward chainer is hosted here as the [`ProofState::auto`] tactic, so the
14//! existing automation is one tactic among many rather than the whole story.
15
16use std::collections::VecDeque;
17
18use logicaffeine_kernel::prelude::StandardLibrary;
19
20use crate::engine::BackwardChainer;
21use crate::unify::{
22 apply_subst_to_expr, apply_subst_to_term, instantiate_expr, unify_exprs, Substitution,
23};
24use crate::verify::{check_derivation, VerifiedProof};
25use crate::{DerivationTree, InductionArg, InductionCase, InferenceRule, ProofExpr, ProofTerm};
26
27/// A local hypothesis: its `name`, its proposition `prop`, and `proof` — a
28/// derivation that proves `prop` in the current local context. For a hypothesis
29/// that is directly in scope (a premise, an `intro`-discharged antecedent, or a
30/// branch hypothesis bound by `cases`) the proof is a `PremiseMatch` leaf the
31/// certifier resolves against the bound/registered hypothesis. For a conjunct
32/// extracted by `cases` from `A ∧ B`, the proof is the `ConjunctionElim`
33/// PROJECTION of the parent — so using the conjunct emits the projection, not a
34/// dangling reference. This is what lets elimination compose with the rest.
35#[derive(Debug, Clone)]
36pub struct Hyp {
37 pub name: String,
38 pub prop: ProofExpr,
39 proof: DerivationTree,
40}
41
42/// One constructor of an inductive, as given to [`ProofState::induction_over`]: its
43/// name and, per positional argument, whether that argument is itself of the
44/// inductive type — a recursive position that carries an induction hypothesis.
45/// `Nil` is `CtorSpec { constructor: "Nil", recursive: vec![] }`; `Cons` (head then
46/// tail) is `CtorSpec { constructor: "Cons", recursive: vec![false, true] }`.
47#[derive(Debug, Clone)]
48pub struct CtorSpec {
49 /// The constructor's name, as registered in the kernel (e.g. `"Cons"`).
50 pub constructor: String,
51 /// One flag per argument, in order: `true` iff that argument is recursive.
52 pub recursive: Vec<bool>,
53}
54
55/// A term as a proof SCRIPT writes it — the argument of `exact`, `have`, `refine`, `use`.
56///
57/// One syntax serves two languages, because Lean's does: the same `⟨a, b⟩` is a conjunction
58/// proof against `p ∧ q` and a witness-and-proof pair against `∃x. φ`, and the same bare
59/// name is a hypothesis in a proof position and a variable in a value position. Which
60/// language a term is read in is decided by the position, never by the term
61/// ([`ProofState::exact_term`] checks it as a proof, [`ProofState::value_term`] as a value).
62#[derive(Debug, Clone, PartialEq)]
63pub enum PTerm {
64 /// A bare name: a hypothesis, a bound variable, or a constant.
65 Ident(String),
66 /// Juxtaposition — `f a b`. Modus ponens over an implication, instantiation over a
67 /// universal, a function application in a value position.
68 App(Box<PTerm>, Vec<PTerm>),
69 /// The anonymous constructor `(a, b)` / `⟨a, b⟩`.
70 Tuple(Vec<PTerm>),
71 /// A `?_` / `?name` hole — a subgoal under `refine`, and an error anywhere else.
72 Hole,
73 /// An infix arithmetic operator, by its `ProofTerm` function name (`add`/`sub`/`mul`).
74 Op(&'static str, Box<PTerm>, Box<PTerm>),
75}
76
77/// Elaborate a script term as a VALUE, resolving each bare name against `bound` — the
78/// variables the surrounding proof has in scope.
79fn value_of(
80 term: &PTerm,
81 bound: &std::collections::BTreeSet<String>,
82) -> Result<ProofTerm, TacticError> {
83 match term {
84 PTerm::Ident(name) => Ok(if bound.contains(name) {
85 ProofTerm::Variable(name.clone())
86 } else {
87 ProofTerm::Constant(name.clone())
88 }),
89 PTerm::App(head, args) => {
90 let PTerm::Ident(name) = head.as_ref() else {
91 return Err(TacticError::DoesNotApply(
92 "only a named function can be applied in a term position".to_string(),
93 ));
94 };
95 let args = args
96 .iter()
97 .map(|a| value_of(a, bound))
98 .collect::<Result<Vec<_>, _>>()?;
99 Ok(ProofTerm::Function(name.clone(), args))
100 }
101 PTerm::Op(op, l, r) => Ok(ProofTerm::Function(
102 (*op).to_string(),
103 vec![value_of(l, bound)?, value_of(r, bound)?],
104 )),
105 PTerm::Tuple(items) => Ok(ProofTerm::Group(
106 items
107 .iter()
108 .map(|a| value_of(a, bound))
109 .collect::<Result<Vec<_>, _>>()?,
110 )),
111 PTerm::Hole => Err(TacticError::DoesNotApply(
112 "a hole is not a value — there is nothing for it to stand for".to_string(),
113 )),
114 }
115}
116
117/// Instantiate a `∀`-quantified proposition until it IS the target, extending `proof` with
118/// the `UniversalInstTerm` chain that justifies each step.
119///
120/// This is what lets `exact h` close `P n` from `h : ∀m. P m`, which is ordinary Lean and
121/// the reason a `have` need not restate what it proves.
122fn instantiate_to(
123 prop: &ProofExpr,
124 target: &ProofExpr,
125 proof: DerivationTree,
126) -> Option<DerivationTree> {
127 let (vars, body) = peel_foralls(prop);
128 if vars.is_empty() {
129 return None;
130 }
131 let mut subst = Substitution::new();
132 if !match_expr_with(&body, target, &vars, &mut subst) {
133 return None;
134 }
135 let mut concl = prop.clone();
136 let mut tree = proof;
137 for v in &vars {
138 // A binder the body never pins down could be anything; refusing is the only honest
139 // answer, since picking a witness would prove a different theorem.
140 let witness = subst.get(v)?.clone();
141 concl = instantiate_forall(&concl, &witness)?;
142 tree = DerivationTree::new(
143 concl.clone(),
144 InferenceRule::UniversalInstTerm(witness),
145 vec![tree],
146 );
147 }
148 (concl == *target).then_some(tree)
149}
150
151/// One-sided match of a proposition `pattern` against `target`, where exactly `vars` are
152/// pattern variables.
153fn match_expr_with(
154 pattern: &ProofExpr,
155 target: &ProofExpr,
156 vars: &[String],
157 subst: &mut Substitution,
158) -> bool {
159 let term =
160 |p: &ProofTerm, t: &ProofTerm, s: &mut Substitution| match_term_with(p, t, vars, &[], s);
161 match (pattern, target) {
162 (
163 ProofExpr::Predicate {
164 name: n1,
165 args: a1,
166 world: w1,
167 },
168 ProofExpr::Predicate {
169 name: n2,
170 args: a2,
171 world: w2,
172 },
173 ) => {
174 n1 == n2
175 && w1 == w2
176 && a1.len() == a2.len()
177 && a1.iter().zip(a2).all(|(p, t)| term(p, t, subst))
178 }
179 (ProofExpr::Identity(l1, r1), ProofExpr::Identity(l2, r2)) => {
180 term(l1, l2, subst) && term(r1, r2, subst)
181 }
182 (ProofExpr::And(a, b), ProofExpr::And(c, d))
183 | (ProofExpr::Or(a, b), ProofExpr::Or(c, d))
184 | (ProofExpr::Implies(a, b), ProofExpr::Implies(c, d))
185 | (ProofExpr::Iff(a, b), ProofExpr::Iff(c, d)) => {
186 match_expr_with(a, c, vars, subst) && match_expr_with(b, d, vars, subst)
187 }
188 (ProofExpr::Not(a), ProofExpr::Not(b)) => match_expr_with(a, b, vars, subst),
189 (
190 ProofExpr::ForAll {
191 variable: v1,
192 body: b1,
193 },
194 ProofExpr::ForAll {
195 variable: v2,
196 body: b2,
197 },
198 )
199 | (
200 ProofExpr::Exists {
201 variable: v1,
202 body: b1,
203 },
204 ProofExpr::Exists {
205 variable: v2,
206 body: b2,
207 },
208 ) => v1 == v2 && match_expr_with(b1, b2, vars, subst),
209 (a, b) => a == b,
210 }
211}
212
213/// A single proof obligation: prove `target` under the local `hyps`.
214#[derive(Debug, Clone)]
215pub struct Goal {
216 /// Named local hypotheses in scope (introduced by `intro`/`cases`, or premises).
217 pub hyps: Vec<Hyp>,
218 /// The proposition to prove.
219 pub target: ProofExpr,
220}
221
222/// What went wrong applying a tactic.
223#[derive(Debug, Clone, PartialEq)]
224pub enum TacticError {
225 /// No focused goal — the proof state is already complete.
226 NoOpenGoals,
227 /// The tactic does not apply to the focused goal's shape (e.g. `intro` on an atom).
228 DoesNotApply(String),
229 /// No hypothesis (or premise) matches the goal for `assumption`/`exact`.
230 NoSuchHypothesis(String),
231 /// The backward chainer could not close the goal.
232 AutoFailed,
233 /// `qed` was called with goals still open.
234 GoalsRemain(usize),
235}
236
237/// A child of a refinement: either an already-complete proof or a fresh subgoal.
238enum Child {
239 Closed(DerivationTree),
240 Sub(Goal),
241}
242
243/// A node in the proof under construction.
244#[derive(Clone)]
245enum Node {
246 /// An unproved goal (a metavariable / hole).
247 Hole(Goal),
248 /// A complete sub-derivation (closed by `exact`/`assumption`/`auto`).
249 Done(DerivationTree),
250 /// A refinement: `rule` applied with the given children (indices into `nodes`).
251 Filled {
252 conclusion: ProofExpr,
253 rule: InferenceRule,
254 children: Vec<usize>,
255 },
256}
257
258/// The interactive proof state: the partial derivation plus the queue of open
259/// goals (front = focused). Tactics consume the focused goal and push any subgoals
260/// they create back to the front, so the proof is built depth-first, first-subgoal
261/// first — the order a reader expects. `Clone` is cheap relative to a proof and is
262/// what lets the backtracking combinators (`first`/`try`/`repeat`) speculate.
263#[derive(Clone)]
264pub struct ProofState {
265 premises: Vec<ProofExpr>,
266 goal: ProofExpr,
267 nodes: Vec<Node>,
268 root: usize,
269 open: VecDeque<usize>,
270 fresh: usize,
271}
272
273/// Replace every occurrence of the term `from` with `to` inside a term.
274fn replace_in_term(t: &ProofTerm, from: &ProofTerm, to: &ProofTerm) -> ProofTerm {
275 if t == from {
276 return to.clone();
277 }
278 match t {
279 ProofTerm::Function(n, args) => ProofTerm::Function(
280 n.clone(),
281 args.iter().map(|a| replace_in_term(a, from, to)).collect(),
282 ),
283 ProofTerm::Group(args) => {
284 ProofTerm::Group(args.iter().map(|a| replace_in_term(a, from, to)).collect())
285 }
286 other => other.clone(),
287 }
288}
289
290/// Replace every occurrence of the term `from` with `to` throughout an expression,
291/// IGNORING binding structure.
292///
293/// This is de-Skolemization, not substitution: [`eigen_to_var_tree`] uses it to turn a
294/// freshly-generated eigen-`Constant` back into the `Variable` the certifier's `Match` arm
295/// binds, across a whole derivation whose quantifier structure must survive untouched.
296/// Substituting INTO a scoped proposition is [`substitute_in_expr`], which is
297/// capture-avoiding; nothing else may use this one.
298fn replace_in_expr_raw(e: &ProofExpr, from: &ProofTerm, to: &ProofTerm) -> ProofExpr {
299 let re = |x: &ProofExpr| Box::new(replace_in_expr_raw(x, from, to));
300 let rt = |x: &ProofTerm| replace_in_term(x, from, to);
301 match e {
302 ProofExpr::Predicate { name, args, world } => ProofExpr::Predicate {
303 name: name.clone(),
304 args: args.iter().map(rt).collect(),
305 world: world.clone(),
306 },
307 ProofExpr::Identity(l, r) => ProofExpr::Identity(rt(l), rt(r)),
308 ProofExpr::Atom(s) => ProofExpr::Atom(s.clone()),
309 ProofExpr::And(l, r) => ProofExpr::And(re(l), re(r)),
310 ProofExpr::Or(l, r) => ProofExpr::Or(re(l), re(r)),
311 ProofExpr::Implies(l, r) => ProofExpr::Implies(re(l), re(r)),
312 ProofExpr::Iff(l, r) => ProofExpr::Iff(re(l), re(r)),
313 ProofExpr::Not(p) => ProofExpr::Not(re(p)),
314 ProofExpr::ForAll { variable, body } => ProofExpr::ForAll {
315 variable: variable.clone(),
316 body: re(body),
317 },
318 ProofExpr::Exists { variable, body } => ProofExpr::Exists {
319 variable: variable.clone(),
320 body: re(body),
321 },
322 other => other.clone(),
323 }
324}
325
326/// The variable leaves of a term. `Constant` is a GLOBAL name and binds to nothing; only
327/// `Variable`/`BoundVarRef` are what a `ForAll`/`Exists` binder captures.
328fn term_vars(t: &ProofTerm, out: &mut std::collections::BTreeSet<String>) {
329 match t {
330 ProofTerm::Variable(n) | ProofTerm::BoundVarRef(n) => {
331 out.insert(n.clone());
332 }
333 ProofTerm::Function(_, args) | ProofTerm::Group(args) => {
334 for a in args {
335 term_vars(a, out);
336 }
337 }
338 ProofTerm::Constant(_) => {}
339 }
340}
341
342fn vars_of_term(t: &ProofTerm) -> std::collections::BTreeSet<String> {
343 let mut out = std::collections::BTreeSet::new();
344 term_vars(t, &mut out);
345 out
346}
347
348/// The FREE variables of an expression — binders remove their own variable.
349fn free_vars(e: &ProofExpr, out: &mut std::collections::BTreeSet<String>) {
350 match e {
351 ProofExpr::Predicate { args, .. } => {
352 for a in args {
353 term_vars(a, out);
354 }
355 }
356 ProofExpr::Identity(l, r) => {
357 term_vars(l, out);
358 term_vars(r, out);
359 }
360 ProofExpr::And(l, r)
361 | ProofExpr::Or(l, r)
362 | ProofExpr::Implies(l, r)
363 | ProofExpr::Iff(l, r) => {
364 free_vars(l, out);
365 free_vars(r, out);
366 }
367 ProofExpr::Not(p) => free_vars(p, out),
368 ProofExpr::ForAll { variable, body } | ProofExpr::Exists { variable, body } => {
369 let mut inner = std::collections::BTreeSet::new();
370 free_vars(body, &mut inner);
371 inner.remove(variable);
372 out.extend(inner);
373 }
374 ProofExpr::Term(t) => term_vars(t, out),
375 _ => {}
376 }
377}
378
379/// Every variable name the expression MENTIONS, bound ones included — the set a fresh
380/// binder name must avoid.
381fn all_vars(e: &ProofExpr, out: &mut std::collections::BTreeSet<String>) {
382 match e {
383 ProofExpr::ForAll { variable, body } | ProofExpr::Exists { variable, body } => {
384 out.insert(variable.clone());
385 all_vars(body, out);
386 }
387 ProofExpr::And(l, r)
388 | ProofExpr::Or(l, r)
389 | ProofExpr::Implies(l, r)
390 | ProofExpr::Iff(l, r) => {
391 all_vars(l, out);
392 all_vars(r, out);
393 }
394 ProofExpr::Not(p) => all_vars(p, out),
395 other => free_vars(other, out),
396 }
397}
398
399/// The CONSTANT names an expression mentions — the global symbols, as distinct from the
400/// variables [`all_vars`] collects.
401fn constants_of(e: &ProofExpr, out: &mut std::collections::BTreeSet<String>) {
402 fn term(t: &ProofTerm, out: &mut std::collections::BTreeSet<String>) {
403 match t {
404 ProofTerm::Constant(n) => {
405 out.insert(n.clone());
406 }
407 ProofTerm::Function(n, args) => {
408 out.insert(n.clone());
409 for a in args {
410 term(a, out);
411 }
412 }
413 ProofTerm::Group(args) => {
414 for a in args {
415 term(a, out);
416 }
417 }
418 _ => {}
419 }
420 }
421 match e {
422 ProofExpr::Predicate { args, .. } => {
423 for a in args {
424 term(a, out);
425 }
426 }
427 ProofExpr::Identity(l, r) => {
428 term(l, out);
429 term(r, out);
430 }
431 ProofExpr::Term(t) => term(t, out),
432 ProofExpr::And(l, r)
433 | ProofExpr::Or(l, r)
434 | ProofExpr::Implies(l, r)
435 | ProofExpr::Iff(l, r) => {
436 constants_of(l, out);
437 constants_of(r, out);
438 }
439 ProofExpr::Not(p) => constants_of(p, out),
440 ProofExpr::ForAll { body, .. } | ProofExpr::Exists { body, .. } => constants_of(body, out),
441 _ => {}
442 }
443}
444
445/// A name close to `base` that no name in `taken` uses.
446fn fresh_name(base: &str, taken: &std::collections::BTreeSet<String>) -> String {
447 for i in 1.. {
448 let candidate = format!("{base}_{i}");
449 if !taken.contains(&candidate) {
450 return candidate;
451 }
452 }
453 unreachable!("the integers are not exhausted")
454}
455
456/// α-rename the free occurrences of the variable `old` to `new` inside `e`, stopping at any
457/// binder that re-binds `old`. `new` must be fresh for `e` (see [`fresh_name`]), which is
458/// what makes this rename itself capture-free.
459fn rename_free_var(e: &ProofExpr, old: &str, new: &str) -> ProofExpr {
460 match e {
461 ProofExpr::ForAll { variable, .. } | ProofExpr::Exists { variable, .. }
462 if variable == old =>
463 {
464 e.clone()
465 }
466 ProofExpr::ForAll { variable, body } => ProofExpr::ForAll {
467 variable: variable.clone(),
468 body: Box::new(rename_free_var(body, old, new)),
469 },
470 ProofExpr::Exists { variable, body } => ProofExpr::Exists {
471 variable: variable.clone(),
472 body: Box::new(rename_free_var(body, old, new)),
473 },
474 other => replace_in_expr_shallow(other, old, new),
475 }
476}
477
478/// One non-quantifier layer of [`rename_free_var`].
479fn replace_in_expr_shallow(e: &ProofExpr, old: &str, new: &str) -> ProofExpr {
480 let from = ProofTerm::Variable(old.to_string());
481 let to = ProofTerm::Variable(new.to_string());
482 let rt = |x: &ProofTerm| replace_in_term(x, &from, &to);
483 let re = |x: &ProofExpr| Box::new(rename_free_var(x, old, new));
484 match e {
485 ProofExpr::Predicate { name, args, world } => ProofExpr::Predicate {
486 name: name.clone(),
487 args: args.iter().map(rt).collect(),
488 world: world.clone(),
489 },
490 ProofExpr::Identity(l, r) => ProofExpr::Identity(rt(l), rt(r)),
491 ProofExpr::And(l, r) => ProofExpr::And(re(l), re(r)),
492 ProofExpr::Or(l, r) => ProofExpr::Or(re(l), re(r)),
493 ProofExpr::Implies(l, r) => ProofExpr::Implies(re(l), re(r)),
494 ProofExpr::Iff(l, r) => ProofExpr::Iff(re(l), re(r)),
495 ProofExpr::Not(p) => ProofExpr::Not(re(p)),
496 ProofExpr::Term(t) => ProofExpr::Term(rt(t)),
497 other => other.clone(),
498 }
499}
500
501/// CAPTURE-AVOIDING substitution: replace every FREE occurrence of the term `from` with
502/// `to` throughout a scoped expression. This is the Leibniz substitution `rewrite` and
503/// `simp` perform on a goal, and it is the only substitution either may use.
504///
505/// Two hazards, both handled here rather than by a caller-side refusal:
506///
507/// * **Shadowing.** A binder that re-binds one of `from`'s free variables introduces a
508/// DIFFERENT variable of the same spelling, so the pattern has no occurrence beneath it;
509/// the quantifier is left alone and the free occurrences beside it are still rewritten. A
510/// patch that refused the whole rewrite instead would silently under-rewrite.
511/// * **Capture.** A binder that binds one of `to`'s free variables would capture the
512/// replacement, turning a claim about one entity into a claim about the quantified one.
513/// The binder is α-renamed away first, so the replacement's variable stays free and stays
514/// distinct.
515pub(crate) fn substitute_in_expr(e: &ProofExpr, from: &ProofTerm, to: &ProofTerm) -> ProofExpr {
516 let re = |x: &ProofExpr| Box::new(substitute_in_expr(x, from, to));
517 let rt = |x: &ProofTerm| replace_in_term(x, from, to);
518 match e {
519 ProofExpr::Predicate { name, args, world } => ProofExpr::Predicate {
520 name: name.clone(),
521 args: args.iter().map(rt).collect(),
522 world: world.clone(),
523 },
524 ProofExpr::Identity(l, r) => ProofExpr::Identity(rt(l), rt(r)),
525 ProofExpr::And(l, r) => ProofExpr::And(re(l), re(r)),
526 ProofExpr::Or(l, r) => ProofExpr::Or(re(l), re(r)),
527 ProofExpr::Implies(l, r) => ProofExpr::Implies(re(l), re(r)),
528 ProofExpr::Iff(l, r) => ProofExpr::Iff(re(l), re(r)),
529 ProofExpr::Not(p) => ProofExpr::Not(re(p)),
530 ProofExpr::Term(t) => ProofExpr::Term(rt(t)),
531 ProofExpr::ForAll { .. } | ProofExpr::Exists { .. } => substitute_under_binder(e, from, to),
532 other => other.clone(),
533 }
534}
535
536fn substitute_under_binder(e: &ProofExpr, from: &ProofTerm, to: &ProofTerm) -> ProofExpr {
537 let (variable, body, is_forall) = match e {
538 ProofExpr::ForAll { variable, body } => (variable.clone(), (**body).clone(), true),
539 ProofExpr::Exists { variable, body } => (variable.clone(), (**body).clone(), false),
540 other => return other.clone(),
541 };
542 // Shadowing: beneath this binder `variable` is a different variable, so the pattern
543 // simply does not occur there.
544 if vars_of_term(from).contains(&variable) {
545 return e.clone();
546 }
547 // Capture: α-rename the binder out of the replacement's way first.
548 let (variable, body) = if vars_of_term(to).contains(&variable) {
549 let mut taken = vars_of_term(to);
550 taken.extend(vars_of_term(from));
551 all_vars(&body, &mut taken);
552 let fresh = fresh_name(&variable, &taken);
553 let renamed = rename_free_var(&body, &variable, &fresh);
554 (fresh, renamed)
555 } else {
556 (variable, body)
557 };
558 let body = Box::new(substitute_in_expr(&body, from, to));
559 if is_forall {
560 ProofExpr::ForAll { variable, body }
561 } else {
562 ProofExpr::Exists { variable, body }
563 }
564}
565
566/// POSITIONAL substitution: replace the `target`-th FREE occurrence of `from` with `to`,
567/// leaving every other occurrence alone, and report how many free occurrences there were.
568///
569/// [`substitute_in_expr`] rewrites them all, which is why `rewrite` could only ever turn
570/// `P(a, a)` into `P(b, b)` — and `P(b, a)` is a different goal, frequently the only provable
571/// one. That is the whole reason Lean has `conv` and occurrence arguments.
572///
573/// The binder discipline is EXACTLY [`substitute_under_binder`]'s, and that is load-bearing
574/// in both directions: an occurrence the goal BINDS is not an occurrence of the pattern (so
575/// it is not counted either — the indices a caller passes must mean the same thing as the
576/// ones this counts), and a binder that would capture the replacement's free variable is
577/// α-renamed away first. Counting only free occurrences keeps the index stable under the
578/// α-renaming the capture case performs.
579struct OccurrenceSubst<'a> {
580 from: &'a ProofTerm,
581 to: &'a ProofTerm,
582 target: usize,
583 seen: usize,
584}
585
586impl OccurrenceSubst<'_> {
587 fn term(&mut self, t: &ProofTerm) -> ProofTerm {
588 if t == self.from {
589 let here = self.seen;
590 self.seen += 1;
591 return if here == self.target {
592 self.to.clone()
593 } else {
594 t.clone()
595 };
596 }
597 match t {
598 ProofTerm::Function(n, args) => {
599 let mut out = Vec::with_capacity(args.len());
600 for a in args {
601 out.push(self.term(a));
602 }
603 ProofTerm::Function(n.clone(), out)
604 }
605 ProofTerm::Group(args) => {
606 let mut out = Vec::with_capacity(args.len());
607 for a in args {
608 out.push(self.term(a));
609 }
610 ProofTerm::Group(out)
611 }
612 other => other.clone(),
613 }
614 }
615
616 fn expr(&mut self, e: &ProofExpr) -> ProofExpr {
617 match e {
618 ProofExpr::Predicate { name, args, world } => {
619 let mut out = Vec::with_capacity(args.len());
620 for a in args {
621 out.push(self.term(a));
622 }
623 ProofExpr::Predicate {
624 name: name.clone(),
625 args: out,
626 world: world.clone(),
627 }
628 }
629 ProofExpr::Identity(l, r) => {
630 let l2 = self.term(l);
631 let r2 = self.term(r);
632 ProofExpr::Identity(l2, r2)
633 }
634 ProofExpr::And(l, r) => {
635 let l2 = self.expr(l);
636 let r2 = self.expr(r);
637 ProofExpr::And(Box::new(l2), Box::new(r2))
638 }
639 ProofExpr::Or(l, r) => {
640 let l2 = self.expr(l);
641 let r2 = self.expr(r);
642 ProofExpr::Or(Box::new(l2), Box::new(r2))
643 }
644 ProofExpr::Implies(l, r) => {
645 let l2 = self.expr(l);
646 let r2 = self.expr(r);
647 ProofExpr::Implies(Box::new(l2), Box::new(r2))
648 }
649 ProofExpr::Iff(l, r) => {
650 let l2 = self.expr(l);
651 let r2 = self.expr(r);
652 ProofExpr::Iff(Box::new(l2), Box::new(r2))
653 }
654 ProofExpr::Not(p) => ProofExpr::Not(Box::new(self.expr(p))),
655 ProofExpr::Term(t) => ProofExpr::Term(self.term(t)),
656 ProofExpr::ForAll { .. } | ProofExpr::Exists { .. } => self.under_binder(e),
657 other => other.clone(),
658 }
659 }
660
661 fn under_binder(&mut self, e: &ProofExpr) -> ProofExpr {
662 let (variable, body, is_forall) = match e {
663 ProofExpr::ForAll { variable, body } => (variable.clone(), (**body).clone(), true),
664 ProofExpr::Exists { variable, body } => (variable.clone(), (**body).clone(), false),
665 other => return other.clone(),
666 };
667 // Shadowing: beneath this binder the pattern's variable is a DIFFERENT variable, so
668 // the pattern does not occur here and nothing beneath is counted.
669 if vars_of_term(self.from).contains(&variable) {
670 return e.clone();
671 }
672 // Capture: α-rename the binder out of the replacement's way first.
673 let (variable, body) = if vars_of_term(self.to).contains(&variable) {
674 let mut taken = vars_of_term(self.to);
675 taken.extend(vars_of_term(self.from));
676 all_vars(&body, &mut taken);
677 let fresh = fresh_name(&variable, &taken);
678 let renamed = rename_free_var(&body, &variable, &fresh);
679 (fresh, renamed)
680 } else {
681 (variable, body)
682 };
683 let body = Box::new(self.expr(&body));
684 if is_forall {
685 ProofExpr::ForAll { variable, body }
686 } else {
687 ProofExpr::Exists { variable, body }
688 }
689 }
690}
691
692/// `(rewritten, free occurrences seen)` for the `occurrence`-th free match of `from`.
693/// `occurrence >= seen` means there is no such occurrence and nothing was replaced.
694/// Pass `usize::MAX` to COUNT without replacing anything.
695pub(crate) fn substitute_occurrence_in_expr(
696 e: &ProofExpr,
697 from: &ProofTerm,
698 to: &ProofTerm,
699 occurrence: usize,
700) -> (ProofExpr, usize) {
701 let mut subst = OccurrenceSubst {
702 from,
703 to,
704 target: occurrence,
705 seen: 0,
706 };
707 let out = subst.expr(e);
708 (out, subst.seen)
709}
710
711/// Strip a `∀` prefix, returning the binder names in order and the body beneath them.
712/// The binders are exactly the pattern variables of a quantified rule.
713fn peel_foralls(e: &ProofExpr) -> (Vec<String>, ProofExpr) {
714 let mut vars = Vec::new();
715 let mut cur = e.clone();
716 while let ProofExpr::ForAll { variable, body } = cur {
717 vars.push(variable);
718 cur = *body;
719 }
720 (vars, cur)
721}
722
723/// Move the `∀` binder named `variable` to the FRONT of the goal's quantifier prefix,
724/// keeping the other binders in their relative order. `∀m n. Q m n` at `n` becomes
725/// `∀n m. Q m n` — the same theorem (independent universals commute), stated so that the
726/// variable to induct on is the one a structural-induction motive can abstract.
727fn reorder_forall_prefix(e: &ProofExpr, variable: &str) -> Option<ProofExpr> {
728 let (prefix, body) = peel_foralls(e);
729 if !prefix.iter().any(|v| v == variable) {
730 return None;
731 }
732 let mut order: Vec<&String> = prefix.iter().filter(|v| *v != variable).collect();
733 let moved = variable.to_string();
734 order.insert(0, &moved);
735 let mut out = body;
736 for v in order.into_iter().rev() {
737 out = ProofExpr::ForAll {
738 variable: v.clone(),
739 body: Box::new(out),
740 };
741 }
742 Some(out)
743}
744
745/// Recover the inductive type and its constructor set for a goal `∀x. body` from the
746/// hypotheses in scope — the induction PRINCIPLE stated as premises, which is how a
747/// structural-induction goal reaches the tactic layer in an untyped `ProofExpr`.
748///
749/// A hypothesis `body[x := C]` names the nullary constructor `C`; a hypothesis
750/// `∀a₁…aₙ. body[x := aᵢ] → … → body[x := C(a₁…aₙ)]` names `C`, with a recursive position
751/// at every `aᵢ` that carries an induction hypothesis. Constructors come back in the order
752/// their hypotheses appear, which is the order the subgoals are then presented in. `None`
753/// when the scope names no constructor at all, or names constructors of two different types.
754fn infer_ctors(variable: &str, body: &ProofExpr, hyps: &[Hyp]) -> Option<(String, Vec<CtorSpec>)> {
755 let at = |t: ProofTerm| -> ProofExpr { instantiate_expr(body, variable, &t) };
756 let mut ind_type: Option<String> = None;
757 let mut ctors: Vec<CtorSpec> = Vec::new();
758 for h in hyps {
759 let Some((ctor, recursive)) = constructor_case(&h.prop, &at) else {
760 continue;
761 };
762 let owner = inductive_of_constructor(&ctor)?;
763 match &ind_type {
764 Some(t) if t != &owner => return None,
765 _ => ind_type = Some(owner),
766 }
767 if ctors.iter().any(|c| c.constructor == ctor) {
768 continue;
769 }
770 ctors.push(CtorSpec {
771 constructor: ctor,
772 recursive,
773 });
774 }
775 match ind_type {
776 Some(t) if !ctors.is_empty() => Some((t, ctors)),
777 _ => None,
778 }
779}
780
781/// Read one hypothesis as one constructor case of an induction principle: its constructor
782/// and, per argument position, whether that argument carries an induction hypothesis.
783///
784/// How many of the hypothesis's leading `∀`s are the CONSTRUCTOR's arguments is not known in
785/// advance — the motive may itself be quantified (`∀m. Q(m, Zero)` is the whole base case,
786/// where `∀h t. P(t) → P(ECons h t)` binds two constructor arguments). So each prefix length
787/// is tried in turn and the shortest that yields a confirmed constructor application wins.
788fn constructor_case(
789 prop: &ProofExpr,
790 at: &dyn Fn(ProofTerm) -> ProofExpr,
791) -> Option<(String, Vec<bool>)> {
792 let (prefix, base) = peel_foralls(prop);
793 for depth in 0..=prefix.len() {
794 // Re-wrap the binders this reading does NOT treat as constructor arguments.
795 let mut rest = base.clone();
796 for v in prefix[depth..].iter().rev() {
797 rest = ProofExpr::ForAll {
798 variable: v.clone(),
799 body: Box::new(rest),
800 };
801 }
802 let mut antecedents = Vec::new();
803 while let ProofExpr::Implies(a, b) = rest {
804 antecedents.push(*a);
805 rest = *b;
806 }
807 let Some((ctor, ctor_args)) = constructor_application(&rest, at) else {
808 continue;
809 };
810 // Every argument must be one of the binders this reading claimed, or the conclusion
811 // is some other fact that merely mentions the same symbol.
812 let args = &prefix[..depth];
813 if !ctor_args.iter().all(
814 |a| matches!(a, ProofTerm::Variable(n) | ProofTerm::Constant(n) if args.contains(n)),
815 ) {
816 continue;
817 }
818 let recursive = ctor_args
819 .iter()
820 .map(|arg| antecedents.iter().any(|ant| *ant == at(arg.clone())))
821 .collect();
822 return Some((ctor, recursive));
823 }
824 None
825}
826
827/// If `conclusion` is `body[x := C]` or `body[x := C(ā)]` for some symbol `C`, return `C`
828/// and its arguments. `at` re-substitutes so the guess is CONFIRMED rather than pattern-
829/// matched out of the shape.
830fn constructor_application(
831 conclusion: &ProofExpr,
832 at: &dyn Fn(ProofTerm) -> ProofExpr,
833) -> Option<(String, Vec<ProofTerm>)> {
834 let mut candidates = Vec::new();
835 collect_head_terms(conclusion, &mut candidates);
836 candidates.into_iter().find_map(|candidate| {
837 let (name, args) = match &candidate {
838 ProofTerm::Constant(n) => (n.clone(), Vec::new()),
839 ProofTerm::Function(n, a) => (n.clone(), a.clone()),
840 _ => return None,
841 };
842 (at(candidate) == *conclusion).then_some((name, args))
843 })
844}
845
846/// Every term the expression carries, outermost first — the candidates for "the term the
847/// induction variable was replaced by".
848fn collect_head_terms(e: &ProofExpr, out: &mut Vec<ProofTerm>) {
849 match e {
850 ProofExpr::Predicate { args, .. } => out.extend(args.iter().cloned()),
851 ProofExpr::Identity(l, r) => {
852 out.push(l.clone());
853 out.push(r.clone());
854 }
855 ProofExpr::Term(t) => out.push(t.clone()),
856 ProofExpr::And(l, r)
857 | ProofExpr::Or(l, r)
858 | ProofExpr::Implies(l, r)
859 | ProofExpr::Iff(l, r) => {
860 collect_head_terms(l, out);
861 collect_head_terms(r, out);
862 }
863 ProofExpr::Not(p) => collect_head_terms(p, out),
864 ProofExpr::ForAll { body, .. } | ProofExpr::Exists { body, .. } => {
865 collect_head_terms(body, out)
866 }
867 _ => {}
868 }
869}
870
871/// Instantiate the outermost `∀` of `e` at `witness`, or `None` if `e` is not quantified.
872fn instantiate_forall(e: &ProofExpr, witness: &ProofTerm) -> Option<ProofExpr> {
873 match e {
874 ProofExpr::ForAll { variable, body } => {
875 // Instantiating a binder AT ITSELF is the identity. It must be taken as one:
876 // `apply_subst_to_term` chases `{z ↦ z}` forever, which is why `intro` skips the
877 // rename in exactly this case.
878 if matches!(
879 witness,
880 ProofTerm::Variable(n) | ProofTerm::BoundVarRef(n) if n == variable
881 ) {
882 return Some((**body).clone());
883 }
884 Some(instantiate_expr(body, variable, witness))
885 }
886 _ => None,
887 }
888}
889
890/// One-sided match of `pattern` against `target`, where exactly the names in `vars` are
891/// pattern variables. Every other `Variable` is rigid and matches only itself. A binding
892/// that mentions a name in `rigid` (a variable the GOAL binds at the match site) is
893/// rejected: the instantiation would escape its scope.
894fn match_term_with(
895 pattern: &ProofTerm,
896 target: &ProofTerm,
897 vars: &[String],
898 rigid: &[String],
899 subst: &mut Substitution,
900) -> bool {
901 match pattern {
902 ProofTerm::Variable(n) if vars.iter().any(|v| v == n) => {
903 if vars_of_term(target)
904 .iter()
905 .any(|t| rigid.iter().any(|r| r == t))
906 {
907 return false;
908 }
909 match subst.get(n) {
910 Some(bound) => bound == target,
911 None => {
912 subst.insert(n.clone(), target.clone());
913 true
914 }
915 }
916 }
917 ProofTerm::Function(name, args) => match target {
918 ProofTerm::Function(n2, a2) if name == n2 && args.len() == a2.len() => args
919 .iter()
920 .zip(a2.iter())
921 .all(|(p, t)| match_term_with(p, t, vars, rigid, subst)),
922 _ => false,
923 },
924 ProofTerm::Group(args) => match target {
925 ProofTerm::Group(a2) if args.len() == a2.len() => args
926 .iter()
927 .zip(a2.iter())
928 .all(|(p, t)| match_term_with(p, t, vars, rigid, subst)),
929 _ => false,
930 },
931 other => other == target,
932 }
933}
934
935/// The first subterm of `t` (outermost, then left to right) that `pattern` matches.
936fn first_match_in_term(
937 t: &ProofTerm,
938 pattern: &ProofTerm,
939 vars: &[String],
940 rigid: &[String],
941) -> Option<Substitution> {
942 let mut subst = Substitution::new();
943 if match_term_with(pattern, t, vars, rigid, &mut subst) {
944 return Some(subst);
945 }
946 match t {
947 ProofTerm::Function(_, args) | ProofTerm::Group(args) => args
948 .iter()
949 .find_map(|a| first_match_in_term(a, pattern, vars, rigid)),
950 _ => None,
951 }
952}
953
954/// The first subterm of the EXPRESSION `e` that `pattern` matches, in the reading order a
955/// proof has — outermost before inner, left before right. Beneath a `ForAll`/`Exists` the
956/// binder joins `rigid`, so a match may not bind a pattern variable to something the goal
957/// binds (that instantiation would escape the quantifier).
958fn first_match_in_expr(
959 e: &ProofExpr,
960 pattern: &ProofTerm,
961 vars: &[String],
962) -> Option<Substitution> {
963 fn go(
964 e: &ProofExpr,
965 pattern: &ProofTerm,
966 vars: &[String],
967 rigid: &mut Vec<String>,
968 ) -> Option<Substitution> {
969 let term = |t: &ProofTerm| first_match_in_term(t, pattern, vars, rigid);
970 match e {
971 ProofExpr::Predicate { args, .. } => args.iter().find_map(term),
972 ProofExpr::Identity(l, r) => term(l).or_else(|| term(r)),
973 ProofExpr::Term(t) => term(t),
974 ProofExpr::And(l, r)
975 | ProofExpr::Or(l, r)
976 | ProofExpr::Implies(l, r)
977 | ProofExpr::Iff(l, r) => {
978 go(l, pattern, vars, rigid).or_else(|| go(r, pattern, vars, rigid))
979 }
980 ProofExpr::Not(p) => go(p, pattern, vars, rigid),
981 ProofExpr::ForAll { variable, body } | ProofExpr::Exists { variable, body } => {
982 // A binder that re-binds one of the pattern's OWN rigid variables shadows it:
983 // the pattern does not occur beneath it at all.
984 if vars_of_term(pattern).contains(variable) && !vars.iter().any(|v| v == variable) {
985 return None;
986 }
987 rigid.push(variable.clone());
988 let found = go(body, pattern, vars, rigid);
989 rigid.pop();
990 found
991 }
992 _ => None,
993 }
994 }
995 go(e, pattern, vars, &mut Vec::new())
996}
997
998/// Rewrite the eigen-`Constant` `name` back to `Variable(name)` throughout a
999/// derivation — the generalization step for `induction`'s step case, turning the
1000/// rigid search variable into the one the certifier's `Match` arm binds.
1001fn eigen_to_var_tree(tree: &DerivationTree, name: &str) -> DerivationTree {
1002 let from = ProofTerm::Constant(name.to_string());
1003 let to = ProofTerm::Variable(name.to_string());
1004 // Every payload this rule carries, through the ONE exhaustive mapper — a rule whose
1005 // witness or motive still named the eigenconstant while the conclusion around it was
1006 // renamed is a tree the certifier computes one proposition from and checks another.
1007 let rule = tree.rule.map_payload(
1008 &|n: &str| n.to_string(),
1009 &|t: &ProofTerm| replace_in_term(t, &from, &to),
1010 &|e: &ProofExpr| replace_in_expr_raw(e, &from, &to),
1011 );
1012 DerivationTree {
1013 conclusion: replace_in_expr_raw(&tree.conclusion, &from, &to),
1014 rule,
1015 premises: tree
1016 .premises
1017 .iter()
1018 .map(|p| eigen_to_var_tree(p, name))
1019 .collect(),
1020 depth: tree.depth,
1021 substitution: tree.substitution.clone(),
1022 }
1023}
1024
1025/// A hypothesis directly in scope (premise / `intro` / `cases`-branch): its proof
1026/// is a `PremiseMatch` leaf the certifier resolves against the bound or registered
1027/// hypothesis of the same proposition.
1028/// The ∃-introduction rule for a witness: the NAME-carrying
1029/// [`InferenceRule::ExistentialIntro`] for a bare `Constant`, the TERM-carrying
1030/// [`InferenceRule::ExistentialIntroTerm`] for everything else.
1031///
1032/// The split is not a fast path, it is a FAITHFULNESS one. `ExistentialIntro`'s witness is a
1033/// `String` that the certifier resolves as a local `Var` or a global `Global` by asking
1034/// whether the surrounding traversal has bound that name — which is right for a constant and
1035/// wrong for a `Variable`, whose lowering is unconditionally `Term::Var`: a proof-level
1036/// variable free in the THEOREM (not bound by any `intro`) would resolve to a `Global` while
1037/// the goal type mentions the `Var`, and the two would not match. Carrying the term lowers it
1038/// once, the same way everywhere.
1039fn witness_rule(witness: &ProofTerm, witness_type: String) -> InferenceRule {
1040 match witness {
1041 ProofTerm::Constant(name) => InferenceRule::ExistentialIntro {
1042 witness: name.clone(),
1043 witness_type,
1044 },
1045 other => InferenceRule::ExistentialIntroTerm {
1046 witness: other.clone(),
1047 witness_type,
1048 },
1049 }
1050}
1051
1052fn direct_hyp(name: String, prop: ProofExpr) -> Hyp {
1053 let proof = DerivationTree::leaf(prop.clone(), InferenceRule::PremiseMatch);
1054 Hyp { name, prop, proof }
1055}
1056
1057/// `¬p` and `p → False` are the SAME proposition — `certifier::proof_expr_to_type` lowers both to
1058/// `Π(_:p). False`. The tactic layer compared `ProofExpr`s structurally, so it alone told them
1059/// apart: `intro` had no image on a negation goal, and `assumption` could not see a `¬p` hypothesis
1060/// discharging a `p → False` target or vice versa. Normalising at every comparison point keeps the
1061/// two layers agreeing about what a proposition IS, rather than patching each tactic separately.
1062fn unfold_not(e: &ProofExpr) -> ProofExpr {
1063 match e {
1064 ProofExpr::Not(p) => ProofExpr::Implies(
1065 Box::new(unfold_not(p)),
1066 Box::new(ProofExpr::Atom(FALSUM.to_string())),
1067 ),
1068 // The falsum has three spellings in the wild and `certifier.rs` accepts all three, so a
1069 // comparison that does not canonicalise them tells apart two propositions the kernel
1070 // cannot. Recurse into implications so `¬¬p` and `(p → ⊥) → False` agree too.
1071 ProofExpr::Atom(n) if is_falsum(n) => ProofExpr::Atom(FALSUM.to_string()),
1072 ProofExpr::Implies(a, b) => {
1073 ProofExpr::Implies(Box::new(unfold_not(a)), Box::new(unfold_not(b)))
1074 }
1075 other => other.clone(),
1076 }
1077}
1078
1079/// The canonical spelling of falsum inside [`unfold_not`].
1080const FALSUM: &str = "⊥";
1081
1082/// The three spellings `certifier.rs` treats as falsum.
1083fn is_falsum(name: &str) -> bool {
1084 name == "⊥" || name == "False" || name == "false"
1085}
1086
1087/// Is this proposition the absurdity, under any of its spellings?
1088fn is_falsum_expr(e: &ProofExpr) -> bool {
1089 matches!(e, ProofExpr::Atom(n) if is_falsum(n))
1090}
1091
1092/// Do `l` and `r` denote the same polynomial over the commutative-ring vocabulary?
1093///
1094/// Asks the arithmetic oracle that `InferenceRule::ArithDecision` certifies through, on a
1095/// context carrying the ring axioms — so the tactic's YES and the kernel's YES are the same
1096/// question, put to the same decision procedure, rather than two implementations that can
1097/// drift apart.
1098/// Is `l = r` a formal identity of the commutative ring — the question `ring` and
1099/// `ArithDecision` both answer? Exposed for [`crate::omega_solve`], whose goal-directed half
1100/// discharges an `Int` EQUALITY goal (`n + 0 = n`, an `omega` goal in Lean) through the same
1101/// oracle rather than a second copy of the decision.
1102pub(crate) fn int_identity_holds(l: &ProofTerm, r: &ProofTerm) -> bool {
1103 ring_identity_holds(l, r)
1104}
1105
1106/// Is this term BOOL-valued — a comparison in the canonical `le(a, b) = true` encoding, or a
1107/// Bool literal — rather than an `Int` term?
1108///
1109/// [`crate::arith::prove_int_eq`] answers about VALUES, and `le(2, 3)` computes to `true`, so
1110/// it cheerfully agrees that `le(2, 3) = true` is an identity. The PROPOSITION is true; the
1111/// certificate `ring` would emit is not, because [`InferenceRule::ArithDecision`] lowers to an
1112/// `Eq Int` fact and the kernel then reports "expected Int, found Bool" about a correct
1113/// statement — a tactic reporting success and the trust door refusing it. Comparisons belong
1114/// to `decide` (ground) and `omega` (symbolic), both of which certify them properly.
1115fn is_bool_valued(t: &ProofTerm) -> bool {
1116 match t {
1117 ProofTerm::Constant(c) => c == "true" || c == "false",
1118 ProofTerm::Function(name, _) => {
1119 matches!(
1120 name.as_str(),
1121 "le" | "lt" | "ge" | "gt" | "eq" | "and" | "or" | "not"
1122 )
1123 }
1124 _ => false,
1125 }
1126}
1127
1128fn ring_identity_holds(l: &ProofTerm, r: &ProofTerm) -> bool {
1129 let (Ok(kl), Ok(kr)) = (
1130 crate::certifier::proof_term_to_kernel_term(l),
1131 crate::certifier::proof_term_to_kernel_term(r),
1132 ) else {
1133 return false;
1134 };
1135 crate::arith::prove_int_eq(StandardLibrary::context(), &kl, &kr).is_some()
1136}
1137
1138/// The first NULLARY constructor of a prelude inductive — its closed base point, read off the
1139/// registered constructor signatures rather than a table (`Nat ↦ Zero`, `EList ↦ ENil`).
1140///
1141/// Used by `ProofState::induction_generalizing` to land back on the original goal after a
1142/// VACUOUS generalization: when the induction variable occurs nowhere, `∀v:T. G ⊢ G` needs an
1143/// inhabitant of `T` and nothing else. An inductive with no nullary constructor has no such
1144/// closed point at this layer, and the caller says so instead of guessing one.
1145fn nullary_constructor(ind_type: &str) -> Option<String> {
1146 use logicaffeine_kernel::Term;
1147 StandardLibrary::context()
1148 .get_constructors(ind_type)
1149 .into_iter()
1150 .find(|(_, ty)| !matches!(ty, Term::Pi { .. }))
1151 .map(|(name, _)| name.to_string())
1152}
1153
1154/// The inductive type a prelude CONSTRUCTOR belongs to, read off its registered kernel
1155/// signature (`Π…. Ind`) rather than a table this file would have to keep in step.
1156fn inductive_of_constructor(ctor: &str) -> Option<String> {
1157 use logicaffeine_kernel::Term;
1158 let mut ty = StandardLibrary::context().get_global(ctor)?.clone();
1159 while let Term::Pi { body_type, .. } = ty {
1160 ty = *body_type;
1161 }
1162 match ty {
1163 Term::Global(name) => Some(name),
1164 _ => None,
1165 }
1166}
1167
1168impl ProofState {
1169 /// Begin proving `goal` from `premises`, naming the hypotheses `hp0`, `hp1`, ….
1170 pub fn start(premises: Vec<ProofExpr>, goal: ProofExpr) -> Self {
1171 Self::start_with_names(premises, &[], goal)
1172 }
1173
1174 /// Begin proving `goal` from `premises`, using the given `names` for the
1175 /// hypotheses where present (parallel to `premises`), falling back to the
1176 /// positional `hp{i}` otherwise. Lets a surface `Given (h): …` name a premise so a
1177 /// `Proof:` script can say `cases h` instead of `cases hp0`.
1178 pub fn start_with_names(
1179 premises: Vec<ProofExpr>,
1180 names: &[Option<String>],
1181 goal: ProofExpr,
1182 ) -> Self {
1183 let hyps = premises
1184 .iter()
1185 .enumerate()
1186 .map(|(i, p)| {
1187 let name = names
1188 .get(i)
1189 .and_then(|n| n.as_ref())
1190 .cloned()
1191 .unwrap_or_else(|| format!("hp{i}"));
1192 direct_hyp(name, p.clone())
1193 })
1194 .collect();
1195 let root_goal = Goal {
1196 hyps,
1197 target: goal.clone(),
1198 };
1199 ProofState {
1200 premises,
1201 goal,
1202 nodes: vec![Node::Hole(root_goal)],
1203 root: 0,
1204 open: VecDeque::from([0]),
1205 fresh: 0,
1206 }
1207 }
1208
1209 /// A fresh entity-constant name for an `∃`-elimination witness. Uppercase-leading
1210 /// so the verifier reads it as a constant, not a variable.
1211 fn fresh_witness(&mut self) -> String {
1212 self.fresh += 1;
1213 format!("W{}", self.fresh)
1214 }
1215
1216 /// Replace the focused hole's goal in place (used by `cases` on `∧`, which
1217 /// enriches the hypotheses without splitting the goal).
1218 fn set_focused_goal(&mut self, goal: Goal) {
1219 if let Some(&idx) = self.open.front() {
1220 self.nodes[idx] = Node::Hole(goal);
1221 }
1222 }
1223
1224 /// The focused goal, or `None` if the proof is complete.
1225 pub fn focus(&self) -> Option<&Goal> {
1226 let idx = *self.open.front()?;
1227 match &self.nodes[idx] {
1228 Node::Hole(g) => Some(g),
1229 _ => None,
1230 }
1231 }
1232
1233 /// Number of still-open goals.
1234 pub fn open_goals(&self) -> usize {
1235 self.open.len()
1236 }
1237
1238 /// The focused goal's target, if any goal is open — the tactic-script and
1239 /// IDE surface for inspecting where a proof stands.
1240 pub fn focused_target(&self) -> Option<&ProofExpr> {
1241 self.focus().map(|g| &g.target)
1242 }
1243
1244 /// A [`crate::simp::SimpSet`] compiled from every in-scope hypothesis that
1245 /// orients as a rewrite rule — the default rule set for the script-level
1246 /// `simp` (a premise or cited lemma of rule shape is automatically a rule).
1247 pub fn scope_simp_set(&self) -> crate::simp::SimpSet {
1248 let mut set = crate::simp::SimpSet::new();
1249 if let Some(g) = self.focus() {
1250 for h in &g.hyps {
1251 set.register_lemma(&h.name, &h.prop);
1252 }
1253 }
1254 set
1255 }
1256
1257 /// A [`crate::simp::SimpSet`] combining the in-scope hypotheses with every `@[simp]`
1258 /// lemma REGISTERED in a kernel context — the script-level `simp` of a development whose
1259 /// attribute set is available.
1260 ///
1261 /// The scope set alone is a per-goal accident: a lemma is a rule because it happens to be
1262 /// a hypothesis here. `@[simp]` is the opposite — a declaration, made once, that says this
1263 /// equation is how the simplifier should normalise from now on. Both feed the same
1264 /// rewriter, which is the point: one notion of a rule, two ways to reach it.
1265 pub fn context_simp_set(&self, ctx: &logicaffeine_kernel::Context) -> crate::simp::SimpSet {
1266 let mut set = self.scope_simp_set();
1267 set.register_context_lemmas(ctx);
1268 set
1269 }
1270
1271 /// A [`crate::simp::SimpSet`] built from EXACTLY the named hypotheses — the rule set of
1272 /// Lean's `simp only [h₁, h₂]`.
1273 ///
1274 /// Selection is the whole point of `only`: the default set is every in-scope hypothesis
1275 /// that orients, so two `simp only` calls meant to stop at different normal forms
1276 /// collapse into one, and the collapse runs in the dangerous direction (MORE rules than
1277 /// the source asked for). An unknown name, or one that does not orient as a rewrite
1278 /// rule, is an error rather than a silently empty set.
1279 pub fn named_simp_set(&self, names: &[String]) -> Result<crate::simp::SimpSet, TacticError> {
1280 let g = self.focus().ok_or(TacticError::NoOpenGoals)?;
1281 let mut set = crate::simp::SimpSet::new();
1282 for name in names {
1283 let h = g
1284 .hyps
1285 .iter()
1286 .find(|h| &h.name == name)
1287 .ok_or_else(|| TacticError::NoSuchHypothesis(name.clone()))?;
1288 if !set.register_lemma(&h.name, &h.prop) {
1289 return Err(TacticError::DoesNotApply(format!(
1290 "simp only [{name}]: `{name}` does not orient as a rewrite rule"
1291 )));
1292 }
1293 }
1294 Ok(set)
1295 }
1296
1297 fn focused_goal(&self) -> Result<Goal, TacticError> {
1298 self.focus().cloned().ok_or(TacticError::NoOpenGoals)
1299 }
1300
1301 /// Every NAME a goal is already committed to — hypothesis names, the variables the
1302 /// target and its scope mention (bound ones included), and the constants they name.
1303 /// A fresh eigen-constant must avoid all of them.
1304 fn scope_names(&self, g: &Goal) -> std::collections::BTreeSet<String> {
1305 let mut taken = std::collections::BTreeSet::new();
1306 let absorb = |e: &ProofExpr, taken: &mut std::collections::BTreeSet<String>| {
1307 all_vars(e, taken);
1308 constants_of(e, taken);
1309 };
1310 absorb(&g.target, &mut taken);
1311 for h in &g.hyps {
1312 taken.insert(h.name.clone());
1313 absorb(&h.prop, &mut taken);
1314 }
1315 taken
1316 }
1317
1318 /// The names free in the focused goal that stand for TERM VARIABLES rather than global
1319 /// constants — what an `intro`-bound `n` is, and what a witness spelled `n` must BE.
1320 fn scope_free_vars(&self) -> std::collections::BTreeSet<String> {
1321 let mut vars = std::collections::BTreeSet::new();
1322 if let Some(g) = self.focus() {
1323 free_vars(&g.target, &mut vars);
1324 for h in &g.hyps {
1325 free_vars(&h.prop, &mut vars);
1326 }
1327 }
1328 vars
1329 }
1330
1331 /// Replace the focused hole with a refinement node whose children are the given
1332 /// closed proofs / subgoals (in order). New subgoals are focused next, in order.
1333 fn refine(&mut self, conclusion: ProofExpr, rule: InferenceRule, children: Vec<Child>) {
1334 let idx = self.open.pop_front().expect("a focused goal");
1335 let mut child_indices = Vec::with_capacity(children.len());
1336 let mut new_holes = Vec::new();
1337 for child in children {
1338 let cidx = self.nodes.len();
1339 match child {
1340 Child::Closed(tree) => self.nodes.push(Node::Done(tree)),
1341 Child::Sub(goal) => {
1342 self.nodes.push(Node::Hole(goal));
1343 new_holes.push(cidx);
1344 }
1345 }
1346 child_indices.push(cidx);
1347 }
1348 // Focus the new subgoals next, first one at the front.
1349 for &h in new_holes.iter().rev() {
1350 self.open.push_front(h);
1351 }
1352 self.nodes[idx] = Node::Filled {
1353 conclusion,
1354 rule,
1355 children: child_indices,
1356 };
1357 }
1358
1359 /// Close the focused goal with an already-complete derivation.
1360 ///
1361 /// Every closer commits through here — `auto`'s engine tree, `crush`, the decision
1362 /// procedures, a hypothesis's proof — so this is where "prove it or decline it" is held:
1363 /// a derivation holding a node [`certifier::certify`](crate::certifier::certify) cannot
1364 /// build (an SMT oracle's verdict, a dead modal or temporal rule) is refused BEFORE the
1365 /// goal is consumed. The tactic declines with the offending rule and the reason, and the
1366 /// proof state is left exactly as it was, instead of reporting a success that `qed` would
1367 /// later refuse.
1368 fn close(&mut self, tree: DerivationTree) -> Result<(), TacticError> {
1369 if let Some((rule, why)) = tree.uncertifiable_rules().into_iter().next() {
1370 return Err(TacticError::DoesNotApply(format!(
1371 "the derivation for {} contains {rule}, which cannot be certified: {why}",
1372 tree.conclusion
1373 )));
1374 }
1375 let idx = self.open.pop_front().expect("a focused goal");
1376 self.nodes[idx] = Node::Done(tree);
1377 Ok(())
1378 }
1379
1380 // === Tactics ===
1381
1382 /// `intro name`: for a goal `P → Q`, assume `P` as hypothesis `name` and reduce
1383 /// to `Q`; for `∀x. φ(x)`, introduce the bound variable under `name` and reduce
1384 /// to `φ(name)`. Mirrors Lean's `intro`.
1385 pub fn intro(&mut self, name: &str) -> Result<&mut Self, TacticError> {
1386 let g = self.focused_goal()?;
1387 match &unfold_not(&g.target) {
1388 ProofExpr::Implies(p, q) => {
1389 let mut hyps = g.hyps.clone();
1390 hyps.push(direct_hyp(name.to_string(), (**p).clone()));
1391 let sub = Goal {
1392 hyps,
1393 target: (**q).clone(),
1394 };
1395 self.refine(
1396 g.target.clone(),
1397 InferenceRule::ImpliesIntro,
1398 vec![Child::Sub(sub)],
1399 );
1400 Ok(self)
1401 }
1402 ProofExpr::ForAll { variable, body } => {
1403 // Introduce the bound variable under `name`. When `name` already IS the
1404 // binder, skip the rename — substituting `{z ↦ z}` would chase its own
1405 // chain forever in `apply_subst_to_term`. The eigenvariable soundness
1406 // worry of search does not apply here: the user constructs the proof,
1407 // they never *instantiate* the introduced variable.
1408 let (conclusion, renamed) = if name == variable {
1409 (g.target.clone(), (**body).clone())
1410 } else {
1411 let renamed =
1412 instantiate_expr(body, variable, &ProofTerm::Variable(name.to_string()));
1413 let conclusion = ProofExpr::ForAll {
1414 variable: name.to_string(),
1415 body: Box::new(renamed.clone()),
1416 };
1417 (conclusion, renamed)
1418 };
1419 let sub = Goal {
1420 hyps: g.hyps.clone(),
1421 target: renamed,
1422 };
1423 self.refine(
1424 conclusion,
1425 InferenceRule::UniversalIntro {
1426 variable: name.to_string(),
1427 var_type: "Entity".to_string(),
1428 },
1429 vec![Child::Sub(sub)],
1430 );
1431 Ok(self)
1432 }
1433 other => Err(TacticError::DoesNotApply(format!(
1434 "intro expects → or ∀, got {other:?}"
1435 ))),
1436 }
1437 }
1438
1439 /// `assumption`: close the goal with any hypothesis whose proposition is exactly
1440 /// the target, emitting THAT hypothesis's proof (a direct reference, or a
1441 /// `ConjunctionElim` projection for a conjunct extracted by `cases`).
1442 pub fn assumption(&mut self) -> Result<&mut Self, TacticError> {
1443 let g = self.focused_goal()?;
1444 let want = unfold_not(&g.target);
1445 if let Some(h) = g
1446 .hyps
1447 .iter()
1448 .find(|h| h.prop == g.target || unfold_not(&h.prop) == want)
1449 {
1450 let proof = h.proof.clone();
1451 self.close(proof)?;
1452 Ok(self)
1453 } else {
1454 Err(TacticError::NoSuchHypothesis(format!(
1455 "no hypothesis proves {:?}",
1456 g.target
1457 )))
1458 }
1459 }
1460
1461 /// `exact name`: close the goal with the specifically-named hypothesis, which
1462 /// must prove the target.
1463 pub fn exact(&mut self, name: &str) -> Result<&mut Self, TacticError> {
1464 let g = self.focused_goal()?;
1465 match g.hyps.iter().find(|h| h.name == name) {
1466 Some(h) if h.prop == g.target || unfold_not(&h.prop) == unfold_not(&g.target) => {
1467 let proof = h.proof.clone();
1468 self.close(proof)?;
1469 Ok(self)
1470 }
1471 Some(h) => Err(TacticError::DoesNotApply(format!(
1472 "hypothesis {name} : {:?} does not prove {:?}",
1473 h.prop, g.target
1474 ))),
1475 None => Err(TacticError::NoSuchHypothesis(name.to_string())),
1476 }
1477 }
1478
1479 /// `constructor` / `split`: for a goal `A ∧ B`, reduce to the two subgoals `A`
1480 /// and `B`.
1481 pub fn split(&mut self) -> Result<&mut Self, TacticError> {
1482 let g = self.focused_goal()?;
1483 match &g.target {
1484 ProofExpr::And(a, b) => {
1485 let ga = Goal {
1486 hyps: g.hyps.clone(),
1487 target: (**a).clone(),
1488 };
1489 let gb = Goal {
1490 hyps: g.hyps.clone(),
1491 target: (**b).clone(),
1492 };
1493 self.refine(
1494 g.target.clone(),
1495 InferenceRule::ConjunctionIntro,
1496 vec![Child::Sub(ga), Child::Sub(gb)],
1497 );
1498 Ok(self)
1499 }
1500 // `A ↔ B` splits into its two implications. `InferenceRule::BicondIntro` and its
1501 // certifier arm (certifier.rs) have existed all along — no tactic ever CONSTRUCTED
1502 // one, so the rule was reachable only by hand-building a `DerivationTree`. Lean spells
1503 // this `constructor`, which is already one of `split`'s aliases.
1504 ProofExpr::Iff(a, b) => {
1505 let fwd = Goal {
1506 hyps: g.hyps.clone(),
1507 target: ProofExpr::Implies(a.clone(), b.clone()),
1508 };
1509 let bwd = Goal {
1510 hyps: g.hyps.clone(),
1511 target: ProofExpr::Implies(b.clone(), a.clone()),
1512 };
1513 self.refine(
1514 g.target.clone(),
1515 InferenceRule::BicondIntro,
1516 vec![Child::Sub(fwd), Child::Sub(bwd)],
1517 );
1518 Ok(self)
1519 }
1520 other => Err(TacticError::DoesNotApply(format!(
1521 "split expects ∧ or ↔, got {other:?}"
1522 ))),
1523 }
1524 }
1525
1526 /// `left`: prove `A ∨ B` by proving `A`.
1527 pub fn left(&mut self) -> Result<&mut Self, TacticError> {
1528 self.disjunct(true)
1529 }
1530
1531 /// `right`: prove `A ∨ B` by proving `B`.
1532 pub fn right(&mut self) -> Result<&mut Self, TacticError> {
1533 self.disjunct(false)
1534 }
1535
1536 fn disjunct(&mut self, take_left: bool) -> Result<&mut Self, TacticError> {
1537 let g = self.focused_goal()?;
1538 match &g.target {
1539 ProofExpr::Or(a, b) => {
1540 let chosen = if take_left {
1541 (**a).clone()
1542 } else {
1543 (**b).clone()
1544 };
1545 let sub = Goal {
1546 hyps: g.hyps.clone(),
1547 target: chosen,
1548 };
1549 self.refine(
1550 g.target.clone(),
1551 InferenceRule::DisjunctionIntro,
1552 vec![Child::Sub(sub)],
1553 );
1554 Ok(self)
1555 }
1556 other => Err(TacticError::DoesNotApply(format!(
1557 "left/right expects ∨, got {other:?}"
1558 ))),
1559 }
1560 }
1561
1562 /// `exists w`: prove `∃x. φ(x)` by exhibiting the witness `w` and reducing to
1563 /// `φ(w)`.
1564 ///
1565 /// The witness is an arbitrary TERM — `use (n + 1)`, `use (f x)` — which is what Lean's
1566 /// `exists`/`use` takes. A compound witness used to be REFUSED here, because
1567 /// `InferenceRule::ExistentialIntro` carries its witness as a `String` that the certifier
1568 /// resolves as one name: `add(n, 1)` certified to a global literally called
1569 /// `"add(n, 1)"`, which no context declares, so the kernel rejected the artefact at
1570 /// `qed` — a failure arriving so far from the mistake that it read as "the theorem is
1571 /// false". The rule now carries the term ([`InferenceRule::ExistentialIntroTerm`],
1572 /// exactly as `UniversalInstTerm` sits beside `UniversalInst` for the dual quantifier),
1573 /// so the honest answer is to take the step.
1574 ///
1575 /// A bare NAME still emits `ExistentialIntro`, which is not a fast path but a
1576 /// COMPATIBILITY one: producers and consumers of that rule (including the eigenconstant
1577 /// renaming in `engine::rewrite_tree_const_to_var`) match on its `String` witness.
1578 ///
1579 /// The ∃-binder's DOMAIN is computed, not assumed: `certifier::existential_domain` reads
1580 /// it off the body, and `proof_expr_to_type` builds the goal type with the same function,
1581 /// so an arithmetic existential is `Ex Int (λm:Int. …)` on both sides of the trust door.
1582 /// Stamping the FOL default `Entity` on `∃m. m = n + 1` produced `Eq Int m` with
1583 /// `m : Entity`, which is not well-typed at all.
1584 pub fn exists(&mut self, witness: ProofTerm) -> Result<&mut Self, TacticError> {
1585 if matches!(witness, ProofTerm::Group(_)) {
1586 return Err(TacticError::DoesNotApply(format!(
1587 "exists {witness}: a tuple is not one witness — supply the components with \
1588 the anonymous constructor `exact (w, h)`, which nests the ∃-introductions"
1589 )));
1590 }
1591 let g = self.focused_goal()?;
1592 match &g.target {
1593 ProofExpr::Exists { variable, body } => {
1594 let instantiated = instantiate_expr(body, variable, &witness);
1595 let sub = Goal {
1596 hyps: g.hyps.clone(),
1597 target: instantiated,
1598 };
1599 let witness_type = crate::certifier::existential_domain(variable, body);
1600 let rule = witness_rule(&witness, witness_type);
1601 self.refine(g.target.clone(), rule, vec![Child::Sub(sub)]);
1602 Ok(self)
1603 }
1604 other => Err(TacticError::DoesNotApply(format!(
1605 "exists expects ∃, got {other:?}"
1606 ))),
1607 }
1608 }
1609
1610 /// `rfl`: close a goal `t = t` by reflexivity.
1611 ///
1612 /// The closer itself is not new — `simp` has always ended with it — but it had no name of its
1613 /// own, so a script could only reach reflexivity by asking for simplification and hoping. One
1614 /// closer, two names: `simp` now delegates here rather than carrying a second copy.
1615 pub fn rfl(&mut self) -> Result<&mut Self, TacticError> {
1616 let g = self.focused_goal()?;
1617 if let ProofExpr::Identity(l, r) = &g.target {
1618 if l == r {
1619 let target = g.target.clone();
1620 self.close(DerivationTree::leaf(target, InferenceRule::Reflexivity))?;
1621 return Ok(self);
1622 }
1623 return Err(TacticError::DoesNotApply(format!(
1624 "rfl: the two sides differ — {l:?} vs {r:?}"
1625 )));
1626 }
1627 Err(TacticError::DoesNotApply(format!(
1628 "rfl expects an equality goal, got {:?}",
1629 g.target
1630 )))
1631 }
1632
1633 // === Proof TERMS ===
1634
1635 /// `exact e`: close the goal with a proof TERM, not merely a hypothesis name.
1636 ///
1637 /// `exact (hpq hp)`, `exact (hp, hq)`, `exact h` where `h : ∀m. P m` against `P n` — all
1638 /// ordinary Lean, and all of them elaborate here against the goal. A term carrying a
1639 /// hole is refused: leaving goals open is [`refine`](Self::refine_term)'s job, and an
1640 /// `exact` that quietly did that would report a proof it had not finished.
1641 pub fn exact_term(&mut self, term: &PTerm) -> Result<&mut Self, TacticError> {
1642 self.build_from_term(term, false)
1643 }
1644
1645 /// `refine e`: elaborate a proof term against the goal, and leave one SUBGOAL per hole,
1646 /// in the order the holes appear.
1647 ///
1648 /// The holes are proof-state goals (`Node::Hole`), never kernel term holes: the kernel's
1649 /// `types_equal` matches `Term::Hole` against ANYTHING, so a term with a hole in it
1650 /// typechecks and the resulting certificate is indistinguishable from a real one. A hole
1651 /// that is the WHOLE term is refused — it leaves the goal exactly as it was, so it is a
1652 /// step that claims to have done something and has not.
1653 pub fn refine_term(&mut self, term: &PTerm) -> Result<&mut Self, TacticError> {
1654 self.build_from_term(term, true)
1655 }
1656
1657 /// `have h from e`: add `h`, proved by the term `e`, to the local scope.
1658 ///
1659 /// Nothing among the primitives introduced a hypothesis with an accompanying proof:
1660 /// `intro` takes one from the goal's antecedent, `cases` from an existing hypothesis's
1661 /// shape, and that was the complete set of ways a name entered a goal's scope. The
1662 /// hypothesis carries the elaborated derivation itself, so each USE emits that proof —
1663 /// no new rule, no lifted theorem, and a `have` whose statement mentions an
1664 /// `intro`-bound variable works like any other.
1665 pub fn have_term(&mut self, name: &str, term: &PTerm) -> Result<&mut Self, TacticError> {
1666 let g = self.focused_goal()?;
1667 let (prop, proof) = self.synthesize(term, &g.hyps)?;
1668 let mut hyps = g.hyps.clone();
1669 hyps.push(Hyp {
1670 name: name.to_string(),
1671 prop,
1672 proof,
1673 });
1674 self.set_focused_goal(Goal {
1675 hyps,
1676 target: g.target,
1677 });
1678 Ok(self)
1679 }
1680
1681 fn build_from_term(
1682 &mut self,
1683 term: &PTerm,
1684 allow_holes: bool,
1685 ) -> Result<&mut Self, TacticError> {
1686 let g = self.focused_goal()?;
1687 if allow_holes && matches!(term, PTerm::Hole) {
1688 return Err(TacticError::DoesNotApply(
1689 "refine: a bare hole leaves the goal exactly as it was".to_string(),
1690 ));
1691 }
1692 let (node, holes) = self.elaborate(term, &g.hyps, &g.target, allow_holes)?;
1693 let idx = self.open.pop_front().expect("a focused goal");
1694 self.nodes[idx] = node;
1695 for &h in holes.iter().rev() {
1696 self.open.push_front(h);
1697 }
1698 Ok(self)
1699 }
1700
1701 /// CHECK a proof term against an expected proposition, pushing its children into the
1702 /// node arena. Returns the root node (not yet placed) and the indices of the holes it
1703 /// spawned, in source order.
1704 fn elaborate(
1705 &mut self,
1706 term: &PTerm,
1707 hyps: &[Hyp],
1708 target: &ProofExpr,
1709 allow_holes: bool,
1710 ) -> Result<(Node, Vec<usize>), TacticError> {
1711 match term {
1712 PTerm::Hole => {
1713 if !allow_holes {
1714 return Err(TacticError::DoesNotApply(
1715 "a hole is only meaningful under `refine`".to_string(),
1716 ));
1717 }
1718 Ok((
1719 Node::Hole(Goal {
1720 hyps: hyps.to_vec(),
1721 target: target.clone(),
1722 }),
1723 Vec::new(),
1724 ))
1725 }
1726 // The anonymous constructor: which introduction rule it is comes from the
1727 // expected proposition, exactly as Lean's `⟨…⟩` does.
1728 PTerm::Tuple(items) => self.elaborate_anonymous(items, hyps, target, allow_holes),
1729 _ => {
1730 let (prop, tree) = self.synthesize(term, hyps)?;
1731 if prop == *target || unfold_not(&prop) == unfold_not(target) {
1732 Ok((Node::Done(tree), Vec::new()))
1733 } else {
1734 match instantiate_to(&prop, target, tree.clone()) {
1735 Some(instantiated) => Ok((Node::Done(instantiated), Vec::new())),
1736 None => Err(TacticError::DoesNotApply(format!(
1737 "the term proves {prop:?}, which is not the goal {target:?}"
1738 ))),
1739 }
1740 }
1741 }
1742 }
1743 }
1744
1745 fn elaborate_anonymous(
1746 &mut self,
1747 items: &[PTerm],
1748 hyps: &[Hyp],
1749 target: &ProofExpr,
1750 allow_holes: bool,
1751 ) -> Result<(Node, Vec<usize>), TacticError> {
1752 if items.len() < 2 {
1753 return Err(TacticError::DoesNotApply(
1754 "an anonymous constructor needs at least two components".to_string(),
1755 ));
1756 }
1757 // `⟨a, b, c⟩` against a right-nested shape is `⟨a, ⟨b, c⟩⟩`.
1758 let (head, rest) = items.split_first().expect("at least two components");
1759 let tail = if rest.len() == 1 {
1760 rest[0].clone()
1761 } else {
1762 PTerm::Tuple(rest.to_vec())
1763 };
1764 let (rule, left, right) = match target {
1765 ProofExpr::And(a, b) => (
1766 InferenceRule::ConjunctionIntro,
1767 (**a).clone(),
1768 (**b).clone(),
1769 ),
1770 ProofExpr::Iff(a, b) => (
1771 InferenceRule::BicondIntro,
1772 ProofExpr::Implies(a.clone(), b.clone()),
1773 ProofExpr::Implies(b.clone(), a.clone()),
1774 ),
1775 // `⟨w, hw⟩` for an existential: the first component is the WITNESS TERM, not a
1776 // proof, so it elaborates through the value language.
1777 ProofExpr::Exists { variable, body } => {
1778 let witness = self.value_term(head)?;
1779 let instantiated = instantiate_expr(body, variable, &witness);
1780 let (child, holes) =
1781 self.elaborate_child(&tail, hyps, &instantiated, allow_holes)?;
1782 let witness_type = crate::certifier::existential_domain(variable, body);
1783 let rule = witness_rule(&witness, witness_type);
1784 return Ok((
1785 Node::Filled {
1786 conclusion: target.clone(),
1787 rule,
1788 children: vec![child],
1789 },
1790 holes,
1791 ));
1792 }
1793 other => {
1794 return Err(TacticError::DoesNotApply(format!(
1795 "an anonymous constructor expects ∧, ↔ or ∃, got {other:?}"
1796 )))
1797 }
1798 };
1799 let (left_idx, mut holes) = self.elaborate_child(head, hyps, &left, allow_holes)?;
1800 let (right_idx, right_holes) = self.elaborate_child(&tail, hyps, &right, allow_holes)?;
1801 holes.extend(right_holes);
1802 Ok((
1803 Node::Filled {
1804 conclusion: target.clone(),
1805 rule,
1806 children: vec![left_idx, right_idx],
1807 },
1808 holes,
1809 ))
1810 }
1811
1812 /// [`elaborate`](Self::elaborate) into a fresh arena slot, reporting its index.
1813 fn elaborate_child(
1814 &mut self,
1815 term: &PTerm,
1816 hyps: &[Hyp],
1817 target: &ProofExpr,
1818 allow_holes: bool,
1819 ) -> Result<(usize, Vec<usize>), TacticError> {
1820 let (node, holes) = self.elaborate(term, hyps, target, allow_holes)?;
1821 let is_hole = matches!(node, Node::Hole(_));
1822 let idx = self.nodes.len();
1823 self.nodes.push(node);
1824 Ok((idx, if is_hole { vec![idx] } else { holes }))
1825 }
1826
1827 /// SYNTHESIZE a proof term's proposition. Terms whose type is determined by the term
1828 /// itself — a name, or an application of one — go this way; the anonymous constructor
1829 /// and the hole do not, because only the expected proposition decides what they mean.
1830 fn synthesize(
1831 &mut self,
1832 term: &PTerm,
1833 hyps: &[Hyp],
1834 ) -> Result<(ProofExpr, DerivationTree), TacticError> {
1835 match term {
1836 PTerm::Ident(name) => hyps
1837 .iter()
1838 .find(|h| &h.name == name)
1839 .map(|h| (h.prop.clone(), h.proof.clone()))
1840 .ok_or_else(|| TacticError::NoSuchHypothesis(name.clone())),
1841 PTerm::App(head, args) => {
1842 let (mut prop, mut proof) = self.synthesize(head, hyps)?;
1843 for arg in args {
1844 let (next_prop, next_proof) = match unfold_not(&prop) {
1845 // A universal applied to a term is INSTANTIATION; an implication
1846 // applied to a proof is modus ponens. The head's own shape decides.
1847 ProofExpr::Implies(ant, con) => {
1848 let (node, holes) = self.elaborate(arg, hyps, &ant, false)?;
1849 debug_assert!(holes.is_empty(), "checked without holes");
1850 let Node::Done(arg_proof) = node else {
1851 return Err(TacticError::DoesNotApply(
1852 "an applied argument must be a complete proof".to_string(),
1853 ));
1854 };
1855 (
1856 (*con).clone(),
1857 DerivationTree::new(
1858 (*con).clone(),
1859 InferenceRule::ModusPonens,
1860 vec![proof, arg_proof],
1861 ),
1862 )
1863 }
1864 ProofExpr::ForAll { .. } => {
1865 let witness = self.value_term(arg)?;
1866 let instantiated = instantiate_forall(&prop, &witness)
1867 .expect("the proposition is universally quantified");
1868 (
1869 instantiated.clone(),
1870 DerivationTree::new(
1871 instantiated,
1872 InferenceRule::UniversalInstTerm(witness),
1873 vec![proof],
1874 ),
1875 )
1876 }
1877 other => {
1878 return Err(TacticError::DoesNotApply(format!(
1879 "{other:?} is neither an implication nor a universal, so it \
1880 cannot be applied"
1881 )))
1882 }
1883 };
1884 prop = next_prop;
1885 proof = next_proof;
1886 }
1887 Ok((prop, proof))
1888 }
1889 PTerm::Hole => Err(TacticError::DoesNotApply(
1890 "a hole's proposition cannot be inferred — it is only meaningful where the \
1891 goal supplies one"
1892 .to_string(),
1893 )),
1894 PTerm::Tuple(_) => Err(TacticError::DoesNotApply(
1895 "an anonymous constructor's proposition cannot be inferred — it is only \
1896 meaningful against a known goal"
1897 .to_string(),
1898 )),
1899 PTerm::Op(op, _, _) => Err(TacticError::DoesNotApply(format!(
1900 "`{op}` builds a VALUE, not a proof"
1901 ))),
1902 }
1903 }
1904
1905 /// Elaborate a script term as a VALUE — an `∃` witness, or the argument of a universal.
1906 ///
1907 /// A bare name is the `Variable` the surrounding proof bound if the goal's scope has one
1908 /// of that name, and a `Constant` otherwise. That distinction is invisible in every
1909 /// diagnostic a user sees (both `Display` as the bare name) and decides whether the
1910 /// instantiated goal matches its context at all, so it is READ OFF the scope rather than
1911 /// guessed: `intro n . exists n` must produce the `n` that `intro` bound.
1912 pub fn value_term(&self, term: &PTerm) -> Result<ProofTerm, TacticError> {
1913 let bound = self.scope_free_vars();
1914 value_of(term, &bound)
1915 }
1916
1917 /// `by_contra h`: assume the goal is FALSE under the name `h` and leave `⊥` to derive.
1918 ///
1919 /// Lean's `by_contra` is a STEP, and that is the whole point: a proof shaped
1920 /// `intro x; by_contra h; <twenty steps>` needs the twenty steps to be writable. The
1921 /// classical reductio itself is not new — `auto`'s search reaches it — but only as one
1922 /// opaque call with no way to help it along. Certified as `ClassicalReductio`, which
1923 /// discharges through the single classical axiom `dne`, so the axiom footprint of the
1924 /// theorem still records that it went classical.
1925 pub fn by_contra(&mut self, name: &str) -> Result<&mut Self, TacticError> {
1926 let g = self.focused_goal()?;
1927 if is_falsum_expr(&g.target) {
1928 return Err(TacticError::DoesNotApply(
1929 "by_contra: the goal is already ⊥, so there is nothing to negate".to_string(),
1930 ));
1931 }
1932 let mut hyps = g.hyps.clone();
1933 hyps.push(direct_hyp(
1934 name.to_string(),
1935 ProofExpr::Not(Box::new(g.target.clone())),
1936 ));
1937 let sub = Goal {
1938 hyps,
1939 target: ProofExpr::Atom(FALSUM.to_string()),
1940 };
1941 self.refine(
1942 g.target.clone(),
1943 InferenceRule::ClassicalReductio,
1944 vec![Child::Sub(sub)],
1945 );
1946 Ok(self)
1947 }
1948
1949 /// `ring`: close a polynomial identity over the commutative-ring vocabulary
1950 /// (`add`/`sub`/`mul` over literals and opaque atoms).
1951 ///
1952 /// The normaliser is not new — it is [`crate::arith::prove_int_eq`], the same
1953 /// proof-PRODUCING oracle `InferenceRule::ArithDecision` certifies through, whose
1954 /// trusted base is the seven registered ring axioms. What was missing was a name on the
1955 /// tactic-script surface: `ring` was reachable only from the literate kernel surface,
1956 /// and the three vernacular surfaces did not interoperate.
1957 ///
1958 /// The oracle is consulted HERE, not only at `qed`: its polynomial layer is a COMPLETE
1959 /// negative decision, so a goal that is not a formal ring identity is declined by the
1960 /// tactic rather than accepted and blown up at the trust door.
1961 pub fn ring(&mut self) -> Result<&mut Self, TacticError> {
1962 let g = self.focused_goal()?;
1963 let ProofExpr::Identity(l, r) = &g.target else {
1964 return Err(TacticError::DoesNotApply(format!(
1965 "ring expects an equality goal, got {:?}",
1966 g.target
1967 )));
1968 };
1969 if is_bool_valued(l) || is_bool_valued(r) {
1970 return Err(TacticError::DoesNotApply(format!(
1971 "ring proves a RING identity over `Int`; `{}` is a Bool fact — a ground one is `decide`'s and a symbolic one is `omega`'s",
1972 g.target
1973 )));
1974 }
1975 if !ring_identity_holds(l, r) {
1976 return Err(TacticError::DoesNotApply(
1977 "ring: the two sides are not the same polynomial".to_string(),
1978 ));
1979 }
1980 let target = g.target.clone();
1981 self.close(DerivationTree::leaf(target, InferenceRule::ArithDecision))?;
1982 Ok(self)
1983 }
1984
1985 /// `apply h`: look the rule up by hypothesis NAME, then reduce the goal by modus ponens.
1986 ///
1987 /// [`ProofState::apply`] takes the rule as a `ProofExpr`, which a proof script has no way to
1988 /// write — that is the whole reason `apply` was unreachable from script text despite working.
1989 /// This is the name-taking door, mirroring [`ProofState::exact`].
1990 pub fn apply_named(&mut self, name: &str) -> Result<&mut Self, TacticError> {
1991 let g = self.focused_goal()?;
1992 let rule = match g.hyps.iter().find(|h| h.name == name) {
1993 Some(h) => h.prop.clone(),
1994 None => return Err(TacticError::NoSuchHypothesis(name.to_string())),
1995 };
1996 self.apply(&rule)
1997 }
1998
1999 /// `apply rule`: `rule` is `P → Goal` (a hypothesis or premise). Reduce the goal
2000 /// to its antecedent `P` by modus ponens.
2001 pub fn apply(&mut self, rule: &ProofExpr) -> Result<&mut Self, TacticError> {
2002 let g = self.focused_goal()?;
2003 if let ProofExpr::Implies(ant, con) = rule {
2004 if unify_exprs(&g.target, con).is_ok() {
2005 let rule_leaf = DerivationTree::leaf(rule.clone(), InferenceRule::PremiseMatch);
2006 let sub = Goal {
2007 hyps: g.hyps.clone(),
2008 target: (**ant).clone(),
2009 };
2010 self.refine(
2011 g.target.clone(),
2012 InferenceRule::ModusPonens,
2013 vec![Child::Closed(rule_leaf), Child::Sub(sub)],
2014 );
2015 return Ok(self);
2016 }
2017 }
2018 Err(TacticError::DoesNotApply(format!(
2019 "apply: {rule:?} is not an implication whose conclusion is the goal"
2020 )))
2021 }
2022
2023 /// `cases h` / `destruct h`: eliminate a hypothesis by its shape.
2024 /// - `A ∧ B`: add `h_1 : A` and `h_2 : B` to the goal, each backed by the
2025 /// `ConjunctionElim` projection of `h` — so using a conjunct emits the
2026 /// projection, never a dangling reference.
2027 /// - `A ∨ B`: split into two goals, one assuming `A`, one assuming `B`
2028 /// (`DisjunctionCases`).
2029 /// - `∃x. φ`: introduce a fresh witness `c` and the hypothesis `φ(c)`
2030 /// (`ExistentialElim`); the goal must not mention `c`, which holds since it is
2031 /// fresh.
2032 pub fn cases(&mut self, name: &str) -> Result<&mut Self, TacticError> {
2033 self.cases_with(name, &[])
2034 }
2035
2036 /// `cases h with a b` / `obtain ⟨a, b⟩ := h`: [`cases`](Self::cases), with the components
2037 /// bound under the names the PROOF chose instead of the generated
2038 /// `h_1`/`h_2`/`h_l`/`h_r`/`h_w`.
2039 ///
2040 /// A Lean proof names what it destructures and every later step cites those names; a
2041 /// translator forced to renumber them is rewriting the proof. The arity is checked
2042 /// against the shape, because `cases h with hp` on a conjunction is a mistake about what
2043 /// `h` IS, not a shorthand.
2044 ///
2045 /// The ∃ branch takes `with w hw`: `w` names the fresh eigen-constant and `hw` the
2046 /// instantiated body. A chosen witness name is REFUSED when it is already in play in the
2047 /// goal or its scope — the eigenvariable condition is what makes ∃-elimination sound,
2048 /// and a name the surrounding proof already uses is not fresh.
2049 pub fn cases_with(&mut self, name: &str, names: &[String]) -> Result<&mut Self, TacticError> {
2050 let g = self.focused_goal()?;
2051 let hyp = g
2052 .hyps
2053 .iter()
2054 .find(|h| h.name == name)
2055 .cloned()
2056 .ok_or_else(|| TacticError::NoSuchHypothesis(name.to_string()))?;
2057 let want = |n: usize, shape: &str| -> Result<(), TacticError> {
2058 if names.is_empty() || names.len() == n {
2059 Ok(())
2060 } else {
2061 Err(TacticError::DoesNotApply(format!(
2062 "cases {name} with …: {shape} binds {n} name(s), {} given",
2063 names.len()
2064 )))
2065 }
2066 };
2067 let pick =
2068 |i: usize, fallback: String| -> String { names.get(i).cloned().unwrap_or(fallback) };
2069 match &hyp.prop {
2070 ProofExpr::And(a, b) => {
2071 want(2, "a conjunction")?;
2072 let proj_a = DerivationTree::new(
2073 (**a).clone(),
2074 InferenceRule::ConjunctionElim,
2075 vec![hyp.proof.clone()],
2076 );
2077 let proj_b = DerivationTree::new(
2078 (**b).clone(),
2079 InferenceRule::ConjunctionElim,
2080 vec![hyp.proof.clone()],
2081 );
2082 let mut hyps = g.hyps.clone();
2083 hyps.push(Hyp {
2084 name: pick(0, format!("{name}_1")),
2085 prop: (**a).clone(),
2086 proof: proj_a,
2087 });
2088 hyps.push(Hyp {
2089 name: pick(1, format!("{name}_2")),
2090 prop: (**b).clone(),
2091 proof: proj_b,
2092 });
2093 self.set_focused_goal(Goal {
2094 hyps,
2095 target: g.target.clone(),
2096 });
2097 Ok(self)
2098 }
2099 ProofExpr::Or(a, b) => {
2100 want(2, "a disjunction")?;
2101 let mut ha = g.hyps.clone();
2102 ha.push(direct_hyp(pick(0, format!("{name}_l")), (**a).clone()));
2103 let ga = Goal {
2104 hyps: ha,
2105 target: g.target.clone(),
2106 };
2107 let mut hb = g.hyps.clone();
2108 hb.push(direct_hyp(pick(1, format!("{name}_r")), (**b).clone()));
2109 let gb = Goal {
2110 hyps: hb,
2111 target: g.target.clone(),
2112 };
2113 self.refine(
2114 g.target.clone(),
2115 InferenceRule::DisjunctionCases,
2116 vec![
2117 Child::Closed(hyp.proof.clone()),
2118 Child::Sub(ga),
2119 Child::Sub(gb),
2120 ],
2121 );
2122 Ok(self)
2123 }
2124 ProofExpr::Exists { variable, body } => {
2125 want(2, "an existential")?;
2126 let witness = match names.first() {
2127 Some(chosen) => {
2128 if self.scope_names(&g).contains(chosen) {
2129 return Err(TacticError::DoesNotApply(format!(
2130 "cases {name} with {chosen} …: `{chosen}` is already in scope, \
2131 so it is not a fresh witness"
2132 )));
2133 }
2134 self.fresh += 1;
2135 chosen.clone()
2136 }
2137 None => self.fresh_witness(),
2138 };
2139 let phi_c = instantiate_expr(body, variable, &ProofTerm::Constant(witness.clone()));
2140 let mut hyps = g.hyps.clone();
2141 hyps.push(direct_hyp(pick(1, format!("{name}_w")), phi_c));
2142 let gbody = Goal {
2143 hyps,
2144 target: g.target.clone(),
2145 };
2146 self.refine(
2147 g.target.clone(),
2148 InferenceRule::ExistentialElim { witness },
2149 vec![Child::Closed(hyp.proof.clone()), Child::Sub(gbody)],
2150 );
2151 Ok(self)
2152 }
2153 other => Err(TacticError::DoesNotApply(format!(
2154 "cases expects ∧/∨/∃ hypothesis, got {other:?}"
2155 ))),
2156 }
2157 }
2158
2159 /// `induction`: structural induction on the goal's OUTERMOST `∀` binder.
2160 ///
2161 /// The scheme is READ OFF the scope rather than hard-wired: a hypothesis `P(C)` names a
2162 /// nullary constructor and a hypothesis `∀ā. (P(aᵢ) → …) → P(C ā)` names a constructor
2163 /// with induction hypotheses at the `aᵢ`, so a goal over a list whose ENil/ECons
2164 /// premises are in scope splits on ENil and ECons — where the hard-wired Peano scheme
2165 /// substituted `Zero`/`Succ k` into a list-valued position and produced syntactically
2166 /// well-formed nonsense that the automation would then happily "prove". Nat keeps the
2167 /// specialised path, whose `Fix`/`Match` certifies over the kernel's own `Nat` recursor;
2168 /// everything else routes to the dependent [`induction_over`](Self::induction_over).
2169 pub fn induction(&mut self) -> Result<&mut Self, TacticError> {
2170 let g = self.focused_goal()?;
2171 let (variable, body) = match &g.target {
2172 ProofExpr::ForAll { variable, body } => (variable.clone(), (**body).clone()),
2173 other => {
2174 return Err(TacticError::DoesNotApply(format!(
2175 "induction expects a ∀ goal, got {other:?}"
2176 )))
2177 }
2178 };
2179 // A scheme recovered from the scope wins, unless it IS the Peano scheme — for which
2180 // the specialised Nat recursor below is the better certified object.
2181 if let Some((ind_type, ctors)) = infer_ctors(&variable, &body, &g.hyps) {
2182 if ind_type != "Nat" {
2183 return self.induction_over(&ind_type, ctors);
2184 }
2185 }
2186 self.fresh += 1;
2187 // Uppercase so the search treats the step variable as a rigid eigen-CONSTANT
2188 // (never a unifiable metavariable, which the backward chainer would either
2189 // ground to `Zero` or expand into an infinite `P(Succ^n k)` chain). It is
2190 // remapped back to a bound `Variable` when the proof is assembled (see
2191 // `assemble`), which is what the certifier's `Match` arm binds.
2192 let step_var = format!("K{}", self.fresh);
2193 let subst_to = |term: ProofTerm| instantiate_expr(&body, &variable, &term);
2194 let base_target = subst_to(ProofTerm::Constant("Zero".to_string()));
2195 let succ_k = ProofTerm::Function(
2196 "Succ".to_string(),
2197 vec![ProofTerm::Constant(step_var.clone())],
2198 );
2199 let step_target = subst_to(succ_k);
2200 let ih_prop = subst_to(ProofTerm::Constant(step_var.clone()));
2201
2202 let base_goal = Goal {
2203 hyps: g.hyps.clone(),
2204 target: base_target,
2205 };
2206 // Put the induction hypothesis FIRST so `auto`/`assumption` discharge the step's
2207 // recursive obligation `P(k)` against the IH (keeping `k` symbolic) rather than
2208 // against a base fact like `P(Zero)` (which would unsoundly ground `k := Zero`).
2209 let mut step_hyps = vec![direct_hyp("ih".to_string(), ih_prop)];
2210 step_hyps.extend(g.hyps.clone());
2211 let step_goal = Goal {
2212 hyps: step_hyps,
2213 target: step_target,
2214 };
2215
2216 self.refine(
2217 g.target.clone(),
2218 InferenceRule::StructuralInduction {
2219 variable,
2220 ind_type: "Nat".to_string(),
2221 step_var,
2222 },
2223 vec![Child::Sub(base_goal), Child::Sub(step_goal)],
2224 );
2225 Ok(self)
2226 }
2227
2228 /// `induction n`: structural induction on the NAMED variable, wherever it sits in the
2229 /// goal's `∀` prefix.
2230 ///
2231 /// The argumentless [`induction`](Self::induction) takes whatever binder happens to be
2232 /// outermost, so against `∀m n. Q m n` it and Lean's `induction n` prove DIFFERENT
2233 /// theorems — both certified, and nothing downstream can tell. Naming the variable is
2234 /// how a translator says which one it meant.
2235 ///
2236 /// For an inner variable the goal is first GENERALIZED: `∀ō. ∀v. body` is proved from
2237 /// `∀v. ∀ō. body` — the motive `λv. ∀ō. body`, which is the strengthened induction
2238 /// hypothesis a proof by induction on an inner variable needs. The bridge between the
2239 /// two orders is built from `UniversalIntro` and `UniversalInst` alone (introduce the
2240 /// prefix, then instantiate the reordered theorem at the introduced variables), so it
2241 /// certifies through rules that already existed — no new axiom, no new rule.
2242 ///
2243 /// When the prefix does not bind `v` at all the tactic does NOT refuse: it takes Lean's
2244 /// reading and generalizes — see `induction_generalizing`.
2245 pub fn induction_on(&mut self, variable: &str) -> Result<&mut Self, TacticError> {
2246 let g = self.focused_goal()?;
2247 let (prefix, _) = peel_foralls(&g.target);
2248 let Some(position) = prefix.iter().position(|v| v == variable) else {
2249 return self.induction_generalizing(variable);
2250 };
2251 if position == 0 {
2252 return self.induction();
2253 }
2254 // The reordered statement `∀v. ∀ō. body`, and the bridge down to the body.
2255 let outer: Vec<String> = prefix[..position].to_vec();
2256 let reordered = reorder_forall_prefix(&g.target, variable).ok_or_else(|| {
2257 TacticError::DoesNotApply(format!(
2258 "induction {variable}: the goal's ∀ prefix could not be reordered"
2259 ))
2260 })?;
2261
2262 // The induction variable's DOMAIN: the structural-induction node below types its
2263 // binder as the inductive, so the λ that binds `v` above must agree or the
2264 // application the bridge builds does not typecheck.
2265 let reordered_body = match &reordered {
2266 ProofExpr::ForAll { body, .. } => (**body).clone(),
2267 _ => unreachable!("reorder_forall_prefix returns a universal"),
2268 };
2269 let ind_type = infer_ctors(variable, &reordered_body, &g.hyps)
2270 .map(|(t, _)| t)
2271 .unwrap_or_else(|| "Nat".to_string());
2272
2273 // Downward: introduce ō, then v at the inductive's domain, landing on the bare body.
2274 for name in &outer {
2275 self.intro(name)?;
2276 }
2277 let focused = self.focused_goal()?;
2278 let ProofExpr::ForAll { body, .. } = &focused.target else {
2279 return Err(TacticError::DoesNotApply(format!(
2280 "induction {variable}: the prefix did not strip down to the binder"
2281 )));
2282 };
2283 let sub = Goal {
2284 hyps: focused.hyps.clone(),
2285 target: (**body).clone(),
2286 };
2287 self.refine(
2288 focused.target.clone(),
2289 InferenceRule::UniversalIntro {
2290 variable: variable.to_string(),
2291 var_type: ind_type,
2292 },
2293 vec![Child::Sub(sub)],
2294 );
2295 // Upward: the body follows from the reordered theorem instantiated at v, then at
2296 // each ō in turn. `witnesses[i]` justifies `conclusions[i]` from `conclusions[i-1]`,
2297 // with the reordered theorem itself below the bottom of the chain.
2298 let witnesses: Vec<String> = std::iter::once(variable.to_string())
2299 .chain(outer.iter().cloned())
2300 .collect();
2301 let mut conclusions = Vec::with_capacity(witnesses.len());
2302 let mut concl = reordered.clone();
2303 for name in &witnesses {
2304 concl = instantiate_forall(&concl, &ProofTerm::Variable(name.clone())).ok_or_else(
2305 || {
2306 TacticError::DoesNotApply(
2307 "induction: the reordered goal lost a binder".to_string(),
2308 )
2309 },
2310 )?;
2311 conclusions.push(concl.clone());
2312 }
2313 // The derivation nests the other way round: the focused hole IS the last
2314 // conclusion, and each refinement exposes the one below it.
2315 let hyps = self.focused_goal()?.hyps;
2316 for i in (0..witnesses.len()).rev() {
2317 let below = if i == 0 {
2318 reordered.clone()
2319 } else {
2320 conclusions[i - 1].clone()
2321 };
2322 self.refine(
2323 conclusions[i].clone(),
2324 InferenceRule::UniversalInst(witnesses[i].clone()),
2325 vec![Child::Sub(Goal {
2326 hyps: hyps.clone(),
2327 target: below,
2328 })],
2329 );
2330 }
2331 self.induction()
2332 }
2333
2334 /// `induction n` where the goal's `∀` prefix does not bind `n`.
2335 ///
2336 /// Three readings are possible and they are told apart by what `n` can be TALKING about —
2337 /// which is the same question Lean answers with its local context, and all an untyped
2338 /// `ProofExpr` can answer without one:
2339 ///
2340 /// * **`n` is a free local** of the goal or of a hypothesis. This is Lean's `induction n` on
2341 /// a local: REVERT every hypothesis that mentions `n`, generalize the goal over `n`, apply
2342 /// the eliminator, and re-introduce what was reverted in each branch.
2343 /// * **`n` is nothing at all, and the goal QUANTIFIES.** Then a binder was plainly meant and
2344 /// this one is not it; taking a different binder is how two theorems get proved under one
2345 /// name, so this REFUSES and says which binders exist.
2346 /// * **`n` is nothing at all, and the goal does not quantify.** There is no binder that could
2347 /// have been meant, and the generalization is vacuous: `n ∉ FV(G)`, so `∀n:T. G ⊢ G` needs
2348 /// only an inhabitant of `T`. This is the case our own `ProofStrategy::Induction` doc
2349 /// comment teaches verbatim (`Proof: Induction on n.` against `Given: Bob is happy. Prove:
2350 /// Bob is happy.`), and refusing it left the documentation teaching a spelling that does
2351 /// not work — worse than an undocumented gap, because a producer copies it.
2352 ///
2353 /// Nothing new is assumed anywhere in this. The reverted hypotheses come back by one
2354 /// `ModusPonens` against the leaf each already carried, and the generalization descends by
2355 /// `UniversalInstTerm` — at `n` itself when `n` is a local, and at the inductive's closed
2356 /// base point when it is vacuous.
2357 ///
2358 /// The revert is not bookkeeping. A hypothesis stated about the LOCAL `n` left in scope would
2359 /// sit under the eliminator's own `λn`, which SHADOWS that local: the branch would be reading
2360 /// a hypothesis about a different `n` than the one it was stated about.
2361 ///
2362 /// The two live cases differ in what they must KNOW. A vacuous generalization binds a variable
2363 /// the motive never mentions, so any inhabited inductive serves and `Nat` is taken. A
2364 /// generalization over a local COMMITS the eliminator to that local's domain, and `ProofExpr`
2365 /// carries no types — so the domain has to come from the scope, via the induction principle
2366 /// stated as premises ([`infer_ctors`]). When the scope does not say, this refuses rather than
2367 /// guess `Nat`: the guess would build a tree naming a domain nothing supports, and a tactic
2368 /// that returns `Ok` with an object the kernel must refuse is a claim, not a tactic.
2369 fn induction_generalizing(&mut self, variable: &str) -> Result<&mut Self, TacticError> {
2370 let g = self.focused_goal()?;
2371 let mentions = |e: &ProofExpr| {
2372 let mut fv = std::collections::BTreeSet::new();
2373 free_vars(e, &mut fv);
2374 fv.contains(variable)
2375 };
2376 let (reverted, kept): (Vec<Hyp>, Vec<Hyp>) =
2377 g.hyps.iter().cloned().partition(|h| mentions(&h.prop));
2378 let is_local = mentions(&g.target) || !reverted.is_empty();
2379 if !is_local {
2380 let (prefix, _) = peel_foralls(&g.target);
2381 if !prefix.is_empty() {
2382 return Err(TacticError::DoesNotApply(format!(
2383 "induction {variable}: the goal's ∀ prefix binds {prefix:?}, not `{variable}` \
2384 — a goal that quantifies has a binder this tactic was meant for, and taking \
2385 a different one proves a different theorem under the same name"
2386 )));
2387 }
2388 }
2389 // The scheme is read off the ORIGINAL goal: the reverted form below is an implication,
2390 // and a constructor case stated as a premise matches the goal's shape, not that one.
2391 let scheme = infer_ctors(variable, &g.target, &g.hyps);
2392 let ind_type = match (&scheme, is_local) {
2393 (Some((t, _)), _) => t.clone(),
2394 (None, false) => "Nat".to_string(),
2395 (None, true) => {
2396 return Err(TacticError::DoesNotApply(format!(
2397 "induction {variable}: `{variable}` is a free local, not a bound variable, \
2398 and nothing in scope says what it ranges over — state the induction \
2399 principle for its type as premises (`P(C)` and `∀ā. P(aᵢ) → P(C ā)`) and \
2400 the domain is read off them"
2401 )));
2402 }
2403 };
2404
2405 // REVERT: `Γ, r̄ ⊢ G` becomes `Γ ⊢ r̄ → G`.
2406 let mut reverted_target = g.target.clone();
2407 for h in reverted.iter().rev() {
2408 reverted_target =
2409 ProofExpr::Implies(Box::new(h.prop.clone()), Box::new(reverted_target));
2410 }
2411 let generalized = ProofExpr::ForAll {
2412 variable: variable.to_string(),
2413 body: Box::new(reverted_target.clone()),
2414 };
2415 // Where to land back on the original goal. A local is instantiated at ITSELF; a vacuous
2416 // variable at the inductive's closed base point.
2417 let witness = if is_local {
2418 ProofTerm::Variable(variable.to_string())
2419 } else {
2420 let base = nullary_constructor(&ind_type).ok_or_else(|| {
2421 TacticError::DoesNotApply(format!(
2422 "induction {variable}: `{variable}` occurs nowhere in the goal, and \
2423 `{ind_type}` has no nullary constructor to instantiate the generalization \
2424 back down at"
2425 ))
2426 })?;
2427 ProofTerm::Constant(base)
2428 };
2429
2430 // Downward, innermost first: the focused hole is `G`, discharged by one `ModusPonens`
2431 // per reverted hypothesis (the implication is the SUBGOAL, the hypothesis is the leaf it
2432 // already carried), and the last of those holes is `r̄ → G`, discharged by instantiating
2433 // the generalization.
2434 let mut concl = g.target.clone();
2435 for h in reverted.iter().rev() {
2436 let imp = ProofExpr::Implies(Box::new(h.prop.clone()), Box::new(concl.clone()));
2437 self.refine(
2438 concl,
2439 InferenceRule::ModusPonens,
2440 vec![
2441 Child::Sub(Goal {
2442 hyps: kept.clone(),
2443 target: imp.clone(),
2444 }),
2445 Child::Closed(h.proof.clone()),
2446 ],
2447 );
2448 concl = imp;
2449 }
2450 self.refine(
2451 concl,
2452 InferenceRule::UniversalInstTerm(witness),
2453 vec![Child::Sub(Goal {
2454 hyps: kept.clone(),
2455 target: generalized,
2456 })],
2457 );
2458
2459 // The eliminator. `induction` re-reads the scheme from the goal it is handed, and the
2460 // reverted goal no longer has the shape a premise-stated constructor case matches, so a
2461 // non-Nat scheme is dispatched here from what was read off the original.
2462 let before: std::collections::BTreeSet<usize> = self.open.iter().copied().collect();
2463 match scheme {
2464 Some((t, ctors)) if t != "Nat" => self.induction_over(&t, ctors)?,
2465 _ => self.induction()?,
2466 };
2467
2468 // …then every branch it produced gets its reverted hypotheses back, under their
2469 // ORIGINAL names, so a script written before the revert still reads.
2470 if reverted.is_empty() {
2471 return Ok(self);
2472 }
2473 let produced: VecDeque<usize> = self.open.clone();
2474 let mut new_open = VecDeque::new();
2475 for idx in produced {
2476 if before.contains(&idx) {
2477 new_open.push_back(idx);
2478 continue;
2479 }
2480 self.open = VecDeque::from([idx]);
2481 for h in &reverted {
2482 self.intro(&h.name)?;
2483 }
2484 new_open.extend(self.open.iter().copied());
2485 }
2486 self.open = new_open;
2487 Ok(self)
2488 }
2489
2490 /// `induction_over`: generic structural induction over ANY inductive `ind_type`,
2491 /// one subgoal per constructor. On a goal `∀x. P(x)`, each constructor `C a₀…aₙ`
2492 /// yields the subgoal `P(C a₀ … aₙ)`; every recursive argument `aᵢ` (one of the
2493 /// inductive type) contributes an induction hypothesis `P(aᵢ)`, placed FIRST so
2494 /// `auto`/`assumption` discharge the recursive obligation against the IH rather
2495 /// than a base fact. Generalizes [`induction`](Self::induction) (fixed to the
2496 /// nullary-base + unary-step Nat shape) to constructors with several — or zero —
2497 /// recursive positions (`Nil`/`Cons`, `Leaf`/`Node`, an N-way enum). Assembled as
2498 /// the dependent `InductionScheme` eliminator (`fix rec. λx. match x { … }`), which
2499 /// the kernel re-checks for coverage, case types, and termination.
2500 ///
2501 /// The constructor arguments run the search as rigid eigen-CONSTANTS (so the
2502 /// backward chainer neither grounds nor unrolls them); `assemble`
2503 /// remaps each back to the bound `Variable` the certifier's `match` arm binds.
2504 pub fn induction_over(
2505 &mut self,
2506 ind_type: &str,
2507 ctors: Vec<CtorSpec>,
2508 ) -> Result<&mut Self, TacticError> {
2509 let g = self.focused_goal()?;
2510 let (variable, body) = match &g.target {
2511 ProofExpr::ForAll { variable, body } => (variable.clone(), (**body).clone()),
2512 other => {
2513 return Err(TacticError::DoesNotApply(format!(
2514 "induction expects a ∀ goal, got {other:?}"
2515 )))
2516 }
2517 };
2518 let subst_to = |term: ProofTerm| instantiate_expr(&body, &variable, &term);
2519
2520 let mut cases = Vec::with_capacity(ctors.len());
2521 let mut children = Vec::with_capacity(ctors.len());
2522 for ctor in &ctors {
2523 // A fresh rigid eigenconstant per constructor argument.
2524 let arg_names: Vec<String> = ctor
2525 .recursive
2526 .iter()
2527 .map(|_| {
2528 self.fresh += 1;
2529 format!("K{}", self.fresh)
2530 })
2531 .collect();
2532
2533 // The constructor applied to its eigenconstant arguments — `C` (a bare
2534 // `Constant`) when nullary, else `C(a₀, …, aₙ)`.
2535 let ctor_term = if arg_names.is_empty() {
2536 ProofTerm::Constant(ctor.constructor.clone())
2537 } else {
2538 ProofTerm::Function(
2539 ctor.constructor.clone(),
2540 arg_names
2541 .iter()
2542 .map(|n| ProofTerm::Constant(n.clone()))
2543 .collect(),
2544 )
2545 };
2546 let case_target = subst_to(ctor_term);
2547
2548 // IHs for the recursive arguments, FIRST (see the Nat induction rationale).
2549 let mut hyps = Vec::new();
2550 for (arg, &is_rec) in arg_names.iter().zip(ctor.recursive.iter()) {
2551 if is_rec {
2552 let ih_prop = subst_to(ProofTerm::Constant(arg.clone()));
2553 hyps.push(direct_hyp(format!("ih_{arg}"), ih_prop));
2554 }
2555 }
2556 hyps.extend(g.hyps.clone());
2557 children.push(Child::Sub(Goal {
2558 hyps,
2559 target: case_target,
2560 }));
2561
2562 cases.push(InductionCase {
2563 constructor: ctor.constructor.clone(),
2564 args: arg_names
2565 .iter()
2566 .zip(ctor.recursive.iter())
2567 .map(|(name, &recursive)| InductionArg {
2568 name: name.clone(),
2569 recursive,
2570 })
2571 .collect(),
2572 });
2573 }
2574
2575 self.refine(
2576 g.target.clone(),
2577 InferenceRule::InductionScheme {
2578 variable,
2579 ind_type: ind_type.to_string(),
2580 cases,
2581 },
2582 children,
2583 );
2584 Ok(self)
2585 }
2586
2587 /// `rewrite h`: rewrite the goal left-to-right by the equation `h`.
2588 ///
2589 /// `h` may be GROUND (`lhs = rhs`) or ∀-QUANTIFIED (`∀x̄. lhs = rhs`), which is the
2590 /// commonest kind in real mathematics and had no image at all before. A quantified
2591 /// equation is instantiated the way Lean's `rw` instantiates it: the first (outermost,
2592 /// leftmost) subterm of the goal that matches `lhs` fixes the pattern variables, and the
2593 /// rewrite then replaces that INSTANTIATED left-hand side — so `∀x. f x = g x` against
2594 /// `f 1 = g 1 ∧ f 2 = g 2` touches the `f 1` and leaves the `f 2` alone.
2595 ///
2596 /// Substitution is capture-avoiding (`substitute_in_expr`), so an occurrence the goal
2597 /// BINDS is not an occurrence of the pattern and a replacement mentioning a free
2598 /// variable is not captured by a binder that happens to share its spelling.
2599 ///
2600 /// Certified by `Eq_rec` (Leibniz): the node concludes the original goal, its equality
2601 /// premise proves `rhs = lhs` (the ∀-instantiation chain over `h`, then symmetry), and
2602 /// its source premise is the rewritten subgoal. Fails if the pattern does not occur.
2603 ///
2604 /// ONE occurrence — the first. `rw` used to rewrite every structural match, so a goal
2605 /// `P(a, a)` with `h : a = b` could only become `P(b, b)`, and the frequently-provable
2606 /// `P(b, a)` was unreachable from any surface: `InferenceRule::Rewrite` carried no
2607 /// position either, so even a Rust caller had nowhere to say which one it meant. Use
2608 /// [`ProofState::rewrite_at`] to name another occurrence; `repeat (rewrite h)` recovers
2609 /// the all-occurrences sweep, one certified step per occurrence.
2610 pub fn rewrite(&mut self, name: &str) -> Result<&mut Self, TacticError> {
2611 self.rewrite_at(name, 0)
2612 }
2613
2614 /// `rewrite h at k`: [`ProofState::rewrite`] aimed at the `k`-th (0-based) FREE
2615 /// occurrence of the equation's left-hand side, counted left to right. Lean's `conv`
2616 /// and its occurrence arguments exist for exactly this, and the occurrence travels all
2617 /// the way to the trust door as `InferenceRule::RewriteAt` — the `Eq_rec` motive
2618 /// abstracts that one position, so the kernel re-checks the choice rather than taking
2619 /// the tactic's word for it.
2620 pub fn rewrite_at(&mut self, name: &str, occurrence: usize) -> Result<&mut Self, TacticError> {
2621 let g = self.focused_goal()?;
2622 let hyp = g
2623 .hyps
2624 .iter()
2625 .find(|h| h.name == name)
2626 .cloned()
2627 .ok_or_else(|| TacticError::NoSuchHypothesis(name.to_string()))?;
2628 let (pattern_vars, equation) = peel_foralls(&hyp.prop);
2629 let (lhs, rhs) = match equation {
2630 ProofExpr::Identity(l, r) => (l, r),
2631 other => {
2632 return Err(TacticError::DoesNotApply(format!(
2633 "rewrite expects an equality hypothesis, got {other:?}"
2634 )))
2635 }
2636 };
2637
2638 // Instantiate a quantified equation at its first match in the goal.
2639 let mut instantiation = Vec::new();
2640 let (lhs, rhs) = if pattern_vars.is_empty() {
2641 (lhs, rhs)
2642 } else {
2643 let subst = first_match_in_expr(&g.target, &lhs, &pattern_vars).ok_or_else(|| {
2644 TacticError::DoesNotApply(format!("rewrite: no subterm of the goal matches {lhs}"))
2645 })?;
2646 for v in &pattern_vars {
2647 match subst.get(v) {
2648 Some(t) => instantiation.push(t.clone()),
2649 // A variable the left-hand side never mentions is undetermined, so the
2650 // instantiated right-hand side would carry a free metavariable.
2651 None => {
2652 return Err(TacticError::DoesNotApply(format!(
2653 "rewrite: the match does not determine `{v}`"
2654 )))
2655 }
2656 }
2657 }
2658 (
2659 apply_subst_to_term(&lhs, &subst),
2660 apply_subst_to_term(&rhs, &subst),
2661 )
2662 };
2663
2664 let (subgoal_target, occurrences) =
2665 substitute_occurrence_in_expr(&g.target, &lhs, &rhs, occurrence);
2666 if occurrences == 0 {
2667 return Err(TacticError::DoesNotApply(format!(
2668 "rewrite: {lhs} does not occur FREE in the goal"
2669 )));
2670 }
2671 if occurrence >= occurrences {
2672 return Err(TacticError::DoesNotApply(format!(
2673 "rewrite: the goal has {occurrences} free occurrence(s) of {lhs}, so there is \
2674 no occurrence {occurrence}"
2675 )));
2676 }
2677 if subgoal_target == g.target {
2678 return Err(TacticError::DoesNotApply(format!(
2679 "rewrite: replacing occurrence {occurrence} of {lhs} by {rhs} leaves the goal \
2680 unchanged, so the step proves nothing"
2681 )));
2682 }
2683
2684 // The equality premise: instantiate the rule at the matched terms, then symmetrise —
2685 // the premise must conclude `rhs = lhs`.
2686 let mut eq_proof = hyp.proof.clone();
2687 let mut concl = hyp.prop.clone();
2688 for witness in instantiation {
2689 concl = instantiate_forall(&concl, &witness).ok_or_else(|| {
2690 TacticError::DoesNotApply(
2691 "rewrite: the equation has fewer binders than the match".to_string(),
2692 )
2693 })?;
2694 eq_proof = DerivationTree::new(
2695 concl.clone(),
2696 InferenceRule::UniversalInstTerm(witness),
2697 vec![eq_proof],
2698 );
2699 }
2700 let eq_sym = DerivationTree::new(
2701 ProofExpr::Identity(rhs.clone(), lhs.clone()),
2702 InferenceRule::EqualitySymmetry,
2703 vec![eq_proof],
2704 );
2705 let sub = Goal {
2706 hyps: g.hyps.clone(),
2707 target: subgoal_target,
2708 };
2709 self.refine(
2710 g.target.clone(),
2711 InferenceRule::RewriteAt {
2712 from: rhs,
2713 to: lhs,
2714 occurrence,
2715 },
2716 vec![Child::Closed(eq_sym), Child::Sub(sub)],
2717 );
2718 Ok(self)
2719 }
2720
2721 /// `rewrite h at hp`: rewrite the HYPOTHESIS `hp` with the equation `h` — Lean's
2722 /// `rw [h] at hp`, and the LOCATION half of positional rewriting.
2723 ///
2724 /// [`ProofState::rewrite_at`] reads and writes the GOAL only, so a Lean proof that
2725 /// normalises a hypothesis before using it had no image at all. The corpus case for `conv`
2726 /// makes the point sharply: positional rewriting has two aspects, the POSITION and the
2727 /// LOCATION, and "a translator that fixes only one of them has fixed nothing".
2728 ///
2729 /// The step runs FORWARD, where the goal rewrite runs backward: the hypothesis's own
2730 /// derivation is the SOURCE premise and the rewritten proposition is the conclusion, so the
2731 /// goal is untouched and only the context moves. Nothing is ASSUMED — the new hypothesis
2732 /// carries a complete `Eq_rec` derivation built from the old one, which `assumption` and
2733 /// `exact` splice in and which `qed` re-checks like any other step. That is why no
2734 /// refinement node is needed: a hypothesis in this proof state is a proposition WITH its
2735 /// proof, and this replaces both at once.
2736 ///
2737 /// The motive's position is CHOSEN by `crate::engine::leibniz_step` rather than taken
2738 /// from the caller's index: the tactic layer counts occurrences in a `ProofExpr` and the
2739 /// kernel counts them in a `Term`, the two agree on the leftmost and can differ deeper, and
2740 /// the kernel is the one that decides.
2741 pub fn rewrite_hyp_at(
2742 &mut self,
2743 eq_name: &str,
2744 hyp_name: &str,
2745 occurrence: usize,
2746 ) -> Result<&mut Self, TacticError> {
2747 let g = self.focused_goal()?;
2748 if eq_name == hyp_name {
2749 return Err(TacticError::DoesNotApply(format!(
2750 "rewrite {eq_name} at {hyp_name}: an equation cannot rewrite itself"
2751 )));
2752 }
2753 let eq_hyp = g
2754 .hyps
2755 .iter()
2756 .find(|h| h.name == eq_name)
2757 .cloned()
2758 .ok_or_else(|| TacticError::NoSuchHypothesis(eq_name.to_string()))?;
2759 let target_hyp = g
2760 .hyps
2761 .iter()
2762 .find(|h| h.name == hyp_name)
2763 .cloned()
2764 .ok_or_else(|| TacticError::NoSuchHypothesis(hyp_name.to_string()))?;
2765 let (pattern_vars, equation) = peel_foralls(&eq_hyp.prop);
2766 let ProofExpr::Identity(lhs, rhs) = equation else {
2767 return Err(TacticError::DoesNotApply(format!(
2768 "rewrite expects an equality hypothesis, got {:?}",
2769 eq_hyp.prop
2770 )));
2771 };
2772
2773 // Instantiate a quantified equation at its first match IN THE HYPOTHESIS — the
2774 // location decides where the pattern is looked for, not just where it is replaced.
2775 let mut instantiation = Vec::new();
2776 let (lhs, rhs) = if pattern_vars.is_empty() {
2777 (lhs, rhs)
2778 } else {
2779 let subst =
2780 first_match_in_expr(&target_hyp.prop, &lhs, &pattern_vars).ok_or_else(|| {
2781 TacticError::DoesNotApply(format!(
2782 "rewrite: no subterm of `{hyp_name}` matches {lhs}"
2783 ))
2784 })?;
2785 for v in &pattern_vars {
2786 match subst.get(v) {
2787 Some(t) => instantiation.push(t.clone()),
2788 None => {
2789 return Err(TacticError::DoesNotApply(format!(
2790 "rewrite: the match does not determine `{v}`"
2791 )))
2792 }
2793 }
2794 }
2795 (
2796 apply_subst_to_term(&lhs, &subst),
2797 apply_subst_to_term(&rhs, &subst),
2798 )
2799 };
2800
2801 let (new_prop, occurrences) =
2802 substitute_occurrence_in_expr(&target_hyp.prop, &lhs, &rhs, occurrence);
2803 if occurrences == 0 {
2804 return Err(TacticError::DoesNotApply(format!(
2805 "rewrite: {lhs} does not occur FREE in `{hyp_name}`"
2806 )));
2807 }
2808 if occurrence >= occurrences {
2809 return Err(TacticError::DoesNotApply(format!(
2810 "rewrite: `{hyp_name}` has {occurrences} free occurrence(s) of {lhs}, so there \
2811 is no occurrence {occurrence}"
2812 )));
2813 }
2814 if new_prop == target_hyp.prop {
2815 return Err(TacticError::DoesNotApply(format!(
2816 "rewrite: replacing occurrence {occurrence} of {lhs} by {rhs} leaves \
2817 `{hyp_name}` unchanged, so the step proves nothing"
2818 )));
2819 }
2820
2821 // The equality premise, instantiated at the match. FORWARD, so — unlike the goal
2822 // rewrite — it is NOT symmetrised: the hypothesis travels from `lhs` to `rhs`.
2823 let mut eq_proof = eq_hyp.proof.clone();
2824 let mut concl = eq_hyp.prop.clone();
2825 for witness in instantiation {
2826 concl = instantiate_forall(&concl, &witness).ok_or_else(|| {
2827 TacticError::DoesNotApply(
2828 "rewrite: the equation has fewer binders than the match".to_string(),
2829 )
2830 })?;
2831 eq_proof = DerivationTree::new(
2832 concl.clone(),
2833 InferenceRule::UniversalInstTerm(witness),
2834 vec![eq_proof],
2835 );
2836 }
2837 let proof = crate::engine::leibniz_step(
2838 new_prop.clone(),
2839 &lhs,
2840 &rhs,
2841 eq_proof,
2842 target_hyp.proof.clone(),
2843 )
2844 .ok_or_else(|| {
2845 TacticError::DoesNotApply(format!(
2846 "rewrite {eq_name} at {hyp_name}: no `Eq_rec` motive abstracts exactly the \
2847 occurrence this step carried, so there is no certificate to build and the \
2848 step is refused rather than left for the trust door"
2849 ))
2850 })?;
2851
2852 let idx = *self.open.front().ok_or(TacticError::NoOpenGoals)?;
2853 if let Node::Hole(goal) = &mut self.nodes[idx] {
2854 if let Some(h) = goal.hyps.iter_mut().find(|h| h.name == hyp_name) {
2855 h.prop = new_prop;
2856 h.proof = proof;
2857 }
2858 }
2859 Ok(self)
2860 }
2861
2862 /// `rewrite h at hp` at the FIRST occurrence — the spelling a script writes.
2863 pub fn rewrite_hyp(&mut self, eq_name: &str, hyp_name: &str) -> Result<&mut Self, TacticError> {
2864 self.rewrite_hyp_at(eq_name, hyp_name, 0)
2865 }
2866
2867 /// `simp`: normalize the focused goal by the rule set, left-to-right to a
2868 /// fixpoint, then close it if it became trivial (reflexivity or an exact
2869 /// hypothesis). Mirrors Lean's `simp`.
2870 ///
2871 /// Each rewrite is one certified `Rewrite` refinement — the instantiated
2872 /// rule equality (a `UniversalInstTerm` chain over the lemma, conditions
2873 /// discharged by `ModusPonens`) is the closed premise, the rewritten goal
2874 /// the open one — so `qed` re-checks every step in the kernel. Loop
2875 /// protection is a step budget plus a seen-goal set (commuting rules like
2876 /// `a = b, b = a` terminate instead of ping-ponging). Fails only if it
2877 /// neither rewrote nor closed anything.
2878 pub fn simp(&mut self, set: &crate::simp::SimpSet) -> Result<&mut Self, TacticError> {
2879 const BUDGET: usize = 1000;
2880 let mut progress = false;
2881 let mut seen: std::collections::HashSet<String> = std::collections::HashSet::new();
2882 seen.insert(self.focused_goal()?.target.to_string());
2883
2884 for _ in 0..BUDGET {
2885 let g = self.focused_goal()?;
2886 let hyp_view: Vec<(&ProofExpr, &DerivationTree)> =
2887 g.hyps.iter().map(|h| (&h.prop, &h.proof)).collect();
2888
2889 // One term rewrite (rule step or ground arithmetic fold).
2890 let step = set
2891 .find_term_step(&g.target, &hyp_view)
2892 .or_else(|| crate::simp::find_ground_fold(&g.target));
2893 if let Some(step) = step {
2894 let new_target = substitute_in_expr(&g.target, &step.from, &step.to);
2895 if new_target == g.target || !seen.insert(new_target.to_string()) {
2896 break;
2897 }
2898 // Same shape as `rewrite`: the equality premise proves
2899 // `to = from` (the symmetric of the step equality).
2900 let eq_sym = DerivationTree::new(
2901 ProofExpr::Identity(step.to.clone(), step.from.clone()),
2902 InferenceRule::EqualitySymmetry,
2903 vec![step.eq],
2904 );
2905 let sub = Goal {
2906 hyps: g.hyps.clone(),
2907 target: new_target,
2908 };
2909 self.refine(
2910 g.target.clone(),
2911 InferenceRule::Rewrite {
2912 from: step.to,
2913 to: step.from,
2914 },
2915 vec![Child::Closed(eq_sym), Child::Sub(sub)],
2916 );
2917 progress = true;
2918 continue;
2919 }
2920
2921 // A top-level propositional step: an iff rule matching the whole
2922 // goal reduces it to the rule's right-hand side via ModusPonens.
2923 if let Some(iff) = set.find_iff_step(&g.target, &hyp_view) {
2924 if !seen.insert(iff.rhs.to_string()) {
2925 break;
2926 }
2927 let sub = Goal {
2928 hyps: g.hyps.clone(),
2929 target: iff.rhs,
2930 };
2931 self.refine(
2932 g.target.clone(),
2933 InferenceRule::ModusPonens,
2934 vec![Child::Closed(iff.imp), Child::Sub(sub)],
2935 );
2936 progress = true;
2937 continue;
2938 }
2939
2940 break;
2941 }
2942
2943 // Closing attempts on the normalized goal.
2944 if self.rfl().is_ok() {
2945 return Ok(self);
2946 }
2947 if self.assumption().is_ok() {
2948 return Ok(self);
2949 }
2950 if progress {
2951 Ok(self)
2952 } else {
2953 Err(TacticError::DoesNotApply(
2954 "simp: no rule rewrites the goal and it is not closable".to_string(),
2955 ))
2956 }
2957 }
2958
2959 /// `decide`: close the focused goal by evaluation, if it is a closed decidable
2960 /// proposition that evaluates TRUE — ground arithmetic (at ARBITRARY precision, the
2961 /// kernel's own), comparisons, `Bool` equalities, a ground DISEQUALITY, and ∧/∨/→/¬ over
2962 /// them. Mirrors Lean's `decide`. A false or open goal is declined.
2963 ///
2964 /// The two ways this declines are now two different messages. They used to be one — "not
2965 /// a closed decidable goal (or it is false)" — and that conflation is dangerous in one
2966 /// direction: a caller that reads `DoesNotApply` as "try another tactic" keeps searching
2967 /// past a goal that is actually FALSE, and may eventually close it from an unrelated
2968 /// contradiction by ex falso, producing a certified proof of a statement nobody asserted.
2969 /// `decide` knows the difference; now it says it.
2970 pub fn decide(&mut self) -> Result<&mut Self, TacticError> {
2971 let g = self.focused_goal()?;
2972 match crate::decide::decide_verdict(&g.target) {
2973 crate::decide::Verdict::True(tree) => {
2974 self.close(tree)?;
2975 Ok(self)
2976 }
2977 crate::decide::Verdict::False => Err(TacticError::DoesNotApply(format!(
2978 "decide: the goal is closed and decidable, and it is FALSE — `{}` evaluates \
2979 false, so no tactic can prove it and a search that keeps going is searching \
2980 for a proof of something untrue",
2981 g.target
2982 ))),
2983 crate::decide::Verdict::Undecided => Err(TacticError::DoesNotApply(format!(
2984 "decide: `{}` is not a CLOSED goal in the decidable fragment (ground Int/Bool \
2985 arithmetic, comparisons, and ¬/∧/∨/→ over them) — its truth was not \
2986 determined either way",
2987 g.target
2988 ))),
2989 }
2990 }
2991
2992 /// `omega`: linear INTEGER arithmetic. When the in-scope `≤`/`<` hypotheses
2993 /// are jointly unsatisfiable over ℤ — using discreteness (`a < b ⟹ a+1 ≤ b`),
2994 /// the fact rational solvers lack — refute them and discharge ANY goal by
2995 /// ex-falso. Proves `x < y ∧ y < x+1 ⊢ Q`, which `linarith` cannot (that
2996 /// system is rationally satisfiable). Mirrors the refutation half of Lean's
2997 /// `omega`. Declines when the hypotheses have an integer model.
2998 /// `linarith`: refute the arithmetic hypotheses over the RATIONALS, by Fourier-Motzkin with
2999 /// a Farkas certificate — and decline anything that needs integrality.
3000 ///
3001 /// `linarith` was an ALIAS for `omega`, which tightens `a < b` to `a + 1 ≤ b`. That is sound
3002 /// over ℤ and **unsound over an ordered field**: `ProofExpr` is untyped, so nothing records the
3003 /// carrier, and a goal false over ℚ could be certified because the integer step found a
3004 /// refutation the rationals do not have. Routing here — `engine::cert_farkas`, the same
3005 /// rational core the backward chainer already uses, *without* the discreteness step — makes
3006 /// `linarith` mean what its name means. `omega` keeps the integer reasoning under its own name.
3007 pub fn linarith(&mut self) -> Result<&mut Self, TacticError> {
3008 let g = self.focused_goal()?;
3009 let known: Vec<(ProofExpr, DerivationTree)> = g
3010 .hyps
3011 .iter()
3012 .map(|h| (h.prop.clone(), h.proof.clone()))
3013 .collect();
3014 if !crate::omega_solve::has_arith_facts(&known) {
3015 return Err(TacticError::DoesNotApply(
3016 "linarith: no arithmetic (≤ / <) hypotheses in scope".to_string(),
3017 ));
3018 }
3019 match crate::engine::cert_farkas(&known) {
3020 Some(bot) => {
3021 let tree =
3022 DerivationTree::new(g.target.clone(), InferenceRule::ExFalso, vec![bot]);
3023 self.close(tree)?;
3024 Ok(self)
3025 }
3026 None => Err(TacticError::DoesNotApply(
3027 "linarith: no rational Farkas certificate — the hypotheses are satisfiable over an \
3028 ordered field. If the refutation needs integrality, that is `omega`, not `linarith`"
3029 .to_string(),
3030 )),
3031 }
3032 }
3033
3034 /// A DECISION PROCEDURE for the goal, not only a refutation of the hypotheses.
3035 ///
3036 /// Lean's `omega` negates the goal, adds it to the hypothesis set, and refutes; ours
3037 /// only ever refuted `g.hyps`, so `x ≤ 3 ⊢ x ≤ 4` — the shape most real uses have —
3038 /// was DECLINED with a message ("the integer hypotheses are satisfiable") that described
3039 /// the hypotheses when the problem was that there was no way to attack the goal at all.
3040 /// Three halves now, in order:
3041 ///
3042 /// 1. **Refute the hypotheses.** Unchanged, and still first: contradictory bounds
3043 /// discharge ANY goal by ex falso.
3044 /// 2. **Prove the goal directly.** A ground comparison by computation; a `≤` goal by
3045 /// chaining the in-scope `≤` facts (`le_trans`/`le_refl`); an `Int` EQUALITY goal
3046 /// through the ring oracle, which is how `n + 0 = n` — an `omega` goal in Lean with no
3047 /// hypotheses whatever — gets proved.
3048 /// 3. **Split on totality and refute the other side.** `le_total a b` is already in the
3049 /// trusted base, and its own comment names this use. For a `≤` goal, take the goal
3050 /// itself in the left branch and refute `hyps ∪ {b ≤ a}` in the right.
3051 ///
3052 /// Half 3 is deliberately the SOUND, axiom-free approximation of "negate the goal":
3053 /// `¬(a ≤ b)` is `b + 1 ≤ a` over ℤ, one unit stronger than the `b ≤ a` totality gives,
3054 /// and the extra unit needs an axiom (`¬(a ≤ b) → b + 1 ≤ a`, or antisymmetry) that the
3055 /// trusted base does not have. Adding one to widen a tactic would trade a visible
3056 /// capability gap for an invisible trust cost, so it is NOT done here; the fragment this
3057 /// reaches is "every goal whose negation-by-totality is refutable", which covers every
3058 /// goal with slack. The gate is likewise relaxed: an arithmetic GOAL admits the tactic
3059 /// even with no arithmetic hypothesis in scope, which is the no-hypothesis Lean case.
3060 pub fn omega(&mut self) -> Result<&mut Self, TacticError> {
3061 let g = self.focused_goal()?;
3062 let known: Vec<(ProofExpr, DerivationTree)> = g
3063 .hyps
3064 .iter()
3065 .map(|h| (h.prop.clone(), h.proof.clone()))
3066 .collect();
3067 let arith_goal = crate::omega_solve::is_arith_goal(&g.target);
3068 if !crate::omega_solve::has_arith_facts(&known) && !arith_goal {
3069 return Err(TacticError::DoesNotApply(format!(
3070 "omega: no arithmetic (≤ / <) hypotheses in scope and `{}` is not an \
3071 arithmetic goal either, so there is nothing linear to decide",
3072 g.target
3073 )));
3074 }
3075 // 1. The rational core FIRST. `omega_close` returns `None` unless it tightened at
3076 // least one STRICT hypothesis, on the assumption that its caller already tried the
3077 // rationals — so a PURELY non-strict contradiction (`5 ≤ x`, `x ≤ 3`) was declined
3078 // with the message "the integer hypotheses are satisfiable" about a system that is
3079 // not. Integrality is a strengthening of the rational theory, never a weakening:
3080 // anything Farkas refutes over ℚ is refuted over ℤ too.
3081 if let Some(bot) =
3082 crate::engine::cert_farkas(&known).or_else(|| crate::omega_solve::omega_close(&known))
3083 {
3084 let tree = DerivationTree::new(g.target.clone(), InferenceRule::ExFalso, vec![bot]);
3085 self.close(tree)?;
3086 return Ok(self);
3087 }
3088 // 2 + 3. Goal-directed.
3089 if let Some(tree) = crate::omega_solve::omega_prove(&known, &g.target) {
3090 self.close(tree)?;
3091 return Ok(self);
3092 }
3093 Err(TacticError::DoesNotApply(format!(
3094 "omega: the hypotheses have an integer model, and `{}` does not follow from them \
3095 — neither directly nor by refuting its negation-by-totality",
3096 g.target
3097 )))
3098 }
3099
3100 /// `calc h₁ h₂ …`: compose the NAMED order/equality facts into the goal — Lean's `calc`,
3101 /// whose job is a chain whose RELATION CHANGES along it.
3102 ///
3103 /// `calc` existed on no LOGOS surface. The pure-`=` chain had an expansion (three
3104 /// `rewrite`s), but a MIXED chain did not: the order graph walked `≤` edges alone, with no
3105 /// arm that could consume an equality, so a single `=` step anywhere made the chain
3106 /// unreachable. The composition now lives in `engine::cert_le_chain` — `≤` edges,
3107 /// discreteness-tightened `<` edges, and equality edges including their CONGRUENT images
3108 /// (`a = b` bridging `a + 1` to `b + 1`) — and this is its name on the surface.
3109 ///
3110 /// Naming the facts is the point, exactly as `simp only [h]` names its rule set: `auto`
3111 /// searches everything in scope, while a `calc` block says which steps, in which order,
3112 /// and fails if they do not compose. A goal `a ≤ d` composes through the chain; an
3113 /// equality goal composes through congruence closure over the named equations.
3114 ///
3115 /// The relation the chain CONCLUDES is `=` or `≤`. A strict `<` conclusion is not
3116 /// certifiable at all: of the eight `Int` order axioms none concludes a `lt` (`lt_succ_le`
3117 /// and `lt_add1_le` both take one as a premise), so the composition can state its result
3118 /// only in the tightened form `a + 1 ≤ d`. The missing primitive is the converse
3119 /// `le_succ_lt : Π a b. (a + 1) ≤ b → a < b`, one new `Int` axiom — named here rather than
3120 /// assumed, because widening a tactic by growing the trusted base is the one trade this
3121 /// campaign forbids.
3122 pub fn calc(&mut self, names: &[String]) -> Result<&mut Self, TacticError> {
3123 let g = self.focused_goal()?;
3124 let mut steps: Vec<(ProofExpr, DerivationTree)> = Vec::new();
3125 for name in names {
3126 let hyp = g
3127 .hyps
3128 .iter()
3129 .find(|h| &h.name == name)
3130 .ok_or_else(|| TacticError::NoSuchHypothesis(name.clone()))?;
3131 steps.push((hyp.prop.clone(), hyp.proof.clone()));
3132 }
3133 if steps.is_empty() {
3134 return Err(TacticError::DoesNotApply(
3135 "calc: name the steps of the chain — `calc h1 h2 h3`".to_string(),
3136 ));
3137 }
3138 // A step may be a QUANTIFIED equation. Lean writes the application into the block
3139 // (`_ = g b := h₂ b`); a named block has to find it, so each `∀x̄. lhs = rhs` is
3140 // E-matched at the chain's own terms and travels on as its ground instances.
3141 let steps = crate::crush::instantiate_steps(&steps, &g.target);
3142 if let Some((a, b)) = crate::engine::as_le_pair(&g.target) {
3143 if let Some(tree) = crate::engine::cert_le_chain(&steps, &a, &b) {
3144 self.close(tree)?;
3145 return Ok(self);
3146 }
3147 return Err(TacticError::DoesNotApply(format!(
3148 "calc: the named steps do not compose into `{}`",
3149 g.target
3150 )));
3151 }
3152 if let Some((a, b)) = crate::omega_solve::as_lt_pair(&g.target) {
3153 if let Some(tree) = crate::engine::cert_lt_chain(&steps, &a, &b) {
3154 self.close(tree)?;
3155 return Ok(self);
3156 }
3157 if !crate::engine::strict_conclusions_available() {
3158 return Err(TacticError::DoesNotApply(format!(
3159 "calc: a STRICT conclusion `{}` has no certifiable image — of the `Int` \
3160 order axioms none concludes a `lt` (`lt_succ_le` and `lt_add1_le` both \
3161 take one as a premise). The chain composes; only the last step is \
3162 missing, and it is the axiom `le_succ_lt : Π a b. (a + 1) ≤ b → a < b` \
3163 (or, better, DEFINING `lt a b := le (add a 1) b`, which removes two \
3164 axioms instead of adding one). State the goal as `a + 1 ≤ b` meanwhile",
3165 g.target
3166 )));
3167 }
3168 return Err(TacticError::DoesNotApply(format!(
3169 "calc: the named steps do not compose into `{}`",
3170 g.target
3171 )));
3172 }
3173 if let ProofExpr::Identity(l, r) = &g.target {
3174 if let Some(tree) = crate::engine::cert_equality_chain(&steps, l, r) {
3175 self.close(tree)?;
3176 return Ok(self);
3177 }
3178 return Err(TacticError::DoesNotApply(format!(
3179 "calc: the named equations do not chain into `{}`",
3180 g.target
3181 )));
3182 }
3183 Err(TacticError::DoesNotApply(format!(
3184 "calc composes an `=` or `≤` chain; `{}` is neither",
3185 g.target
3186 )))
3187 }
3188
3189 /// `by_rule R`: discharge the focused goal in ONE step with the NAMED inference rule,
3190 /// from the facts already in scope.
3191 ///
3192 /// The language AST has carried a public `ProofStrategy::ByRule(name)` variant — with
3193 /// `Proof: ModusPonens.` as its own documented example — that nothing in the workspace
3194 /// constructs and no driver has an arm for, because the proof layer offered no way to
3195 /// apply a rule by its name. This is that door.
3196 ///
3197 /// It is a real tactic and not a label, and three things make it one:
3198 ///
3199 /// * A name that is not a rule is a NAME error, listing the rules that are — a translator
3200 /// handing us a Lean rule name needs to know which of the two kinds of failure it hit.
3201 /// * A rule that is declared but has no certifier arm reports
3202 /// [`InferenceRule::uncertifiable_reason`] — the list exists precisely so a PRODUCER can
3203 /// consult it before emitting a tree, and this is the one place in the crate that does.
3204 /// * The node is certified BEFORE success is reported. `by_rule R` succeeds only when the
3205 /// kernel agrees that R, applied to facts in scope, proves this goal — so it can never
3206 /// hand `qed` a derivation the trust door must refuse.
3207 ///
3208 /// The premises are drawn from the hypotheses in scope and nowhere else: `by_rule` is one
3209 /// step, not a search. A goal needing a subproof is `auto`'s, or is written out.
3210 pub fn by_rule(&mut self, name: &str) -> Result<&mut Self, TacticError> {
3211 /// The widest rule in the enum takes three premises (`DisjunctionElim`: the
3212 /// disjunction and one implication per side), so a one-step application never needs
3213 /// a longer tuple.
3214 const BY_RULE_MAX_ARITY: usize = 3;
3215 let g = self.focused_goal()?;
3216 let Some(rule) = InferenceRule::from_name(name) else {
3217 let known: Vec<String> = InferenceRule::NAMEABLE
3218 .iter()
3219 .map(|r| r.canonical_name())
3220 .collect();
3221 return Err(TacticError::DoesNotApply(format!(
3222 "by_rule: `{name}` is not an inference rule that can be applied from a name \
3223 alone. A rule carrying an ARGUMENT (a rewrite's equation, an instantiation's \
3224 witness, an induction's variable) has its own tactic — `rewrite`, `exists`, \
3225 `induction`. The nameable rules are: {}",
3226 known.join(", ")
3227 )));
3228 };
3229 if let Some(reason) = rule.uncertifiable_reason() {
3230 return Err(TacticError::DoesNotApply(format!(
3231 "by_rule {}: {reason}",
3232 rule.canonical_name()
3233 )));
3234 }
3235 let props: Vec<ProofExpr> = g.hyps.iter().map(|h| h.prop.clone()).collect();
3236 let pool: Vec<DerivationTree> = g.hyps.iter().map(|h| h.proof.clone()).collect();
3237 let checker = crate::verify::ScopedChecker::new(&props, &g.target);
3238 // Candidate premise tuples, shortest first: a leaf rule is one question, and a rule
3239 // that needs two facts is not asked about until the cheaper readings are exhausted.
3240 // The budget bounds the cubic tier, which is the only one that can grow.
3241 const BUDGET: usize = 512;
3242 let mut asked = 0usize;
3243 let mut arity_tuples: Vec<Vec<DerivationTree>> = vec![Vec::new()];
3244 for _ in 0..=BY_RULE_MAX_ARITY {
3245 for combo in &arity_tuples {
3246 if asked >= BUDGET {
3247 break;
3248 }
3249 asked += 1;
3250 let tree = DerivationTree::new(g.target.clone(), rule.clone(), combo.clone());
3251 if checker.certifies(tree.clone()) {
3252 self.close(tree)?;
3253 return Ok(self);
3254 }
3255 }
3256 arity_tuples = arity_tuples
3257 .iter()
3258 .flat_map(|combo| {
3259 pool.iter().map(move |p| {
3260 let mut next = combo.clone();
3261 next.push(p.clone());
3262 next
3263 })
3264 })
3265 .collect();
3266 if arity_tuples.len() > BUDGET {
3267 arity_tuples.truncate(BUDGET);
3268 }
3269 }
3270 Err(TacticError::DoesNotApply(format!(
3271 "by_rule {}: that rule does not discharge `{}` from the {} hypothes{} in scope",
3272 rule.canonical_name(),
3273 g.target,
3274 pool.len(),
3275 if pool.len() == 1 { "is" } else { "es" }
3276 )))
3277 }
3278
3279 /// `crush`: the grind-style closer. E-matches the in-scope `∀`-equality
3280 /// lemmas at the goal's ground terms, then discharges the goal by certified
3281 /// congruence closure. Proves goals plain `auto` cannot — e.g.
3282 /// `∀x. f(x)=g(x), a=b, P(g(b)) ⊢ P(f(a))` — and every step is kernel-checked.
3283 pub fn crush(&mut self) -> Result<&mut Self, TacticError> {
3284 let g = self.focused_goal()?;
3285 let premises: Vec<ProofExpr> = g.hyps.iter().map(|h| h.prop.clone()).collect();
3286 match crate::crush::crush_prove(&premises, &g.target) {
3287 Some(tree) => {
3288 self.close(tree)?;
3289 Ok(self)
3290 }
3291 None => Err(TacticError::DoesNotApply(
3292 "crush: could not close the goal by e-matching + congruence".to_string(),
3293 )),
3294 }
3295 }
3296
3297 /// `auto`: discharge the focused goal with the backward chainer (the existing
3298 /// automation, hosted as one tactic). Its hypotheses and the premises are the
3299 /// available knowledge base.
3300 ///
3301 /// With the `verification` feature the chainer's last resort is the Z3 oracle, whose
3302 /// `OracleVerification` leaf attests a goal without a proof term. The chainer reaches
3303 /// it only after every certifiable strategy failed, so such a tree means `auto` found
3304 /// no proof: `close` refuses it and `auto` declines.
3305 pub fn auto(&mut self) -> Result<&mut Self, TacticError> {
3306 let g = self.focused_goal()?;
3307 let mut engine = BackwardChainer::new();
3308 // A tactic's hypotheses ARE kernel hypotheses: the trust door registers each as a
3309 // declaration whose type mentions the statement's free variables as context LOCALS.
3310 // So a step that used one AT AN INSTANCE would cite a proposition no context carries,
3311 // and `qed` would refuse a tree `auto` had already called a proof. Saying so here is
3312 // what makes the honest answer STRUCTURAL — in this reading the search cannot build
3313 // the step at all, so there is nothing for a later check to catch.
3314 engine.set_premise_variables(crate::PremiseVariables::Local);
3315 for h in &g.hyps {
3316 engine.add_axiom(h.prop.clone());
3317 }
3318 match engine.prove(g.target.clone()) {
3319 Ok(tree) => {
3320 self.close(tree)?;
3321 Ok(self)
3322 }
3323 Err(_) => Err(TacticError::AutoFailed),
3324 }
3325 }
3326
3327 fn assemble(&self, idx: usize) -> Result<DerivationTree, TacticError> {
3328 match &self.nodes[idx] {
3329 Node::Done(tree) => Ok(tree.clone()),
3330 Node::Filled {
3331 conclusion,
3332 rule,
3333 children,
3334 } => {
3335 let mut kids = children
3336 .iter()
3337 .map(|&c| self.assemble(c))
3338 .collect::<Result<Vec<_>, _>>()?;
3339 // Generalize the step case: the eigenconstant the search ran under
3340 // becomes the `Variable` the certifier's `Match` binds.
3341 if let InferenceRule::StructuralInduction { step_var, .. } = rule {
3342 if kids.len() == 2 {
3343 kids[1] = eigen_to_var_tree(&kids[1], step_var);
3344 }
3345 }
3346 // Generic induction: each case ran under its own rigid eigenconstants
3347 // (one per constructor argument); remap each back to the bound
3348 // `Variable` the certifier's `match` arm binds and the IH cites.
3349 if let InferenceRule::InductionScheme { cases, .. } = rule {
3350 for (kid, case) in kids.iter_mut().zip(cases.iter()) {
3351 for arg in &case.args {
3352 *kid = eigen_to_var_tree(kid, &arg.name);
3353 }
3354 }
3355 }
3356 Ok(DerivationTree::new(conclusion.clone(), rule.clone(), kids))
3357 }
3358 Node::Hole(_) => Err(TacticError::GoalsRemain(1)),
3359 }
3360 }
3361
3362 /// Assemble the current proof tree, if every goal is closed (for inspection/debug).
3363 pub fn assembled(&self) -> Option<DerivationTree> {
3364 if self.open.is_empty() {
3365 self.assemble(self.root).ok()
3366 } else {
3367 None
3368 }
3369 }
3370
3371 /// Run a composed [`Tactic`] against this state, for fluent chaining with the
3372 /// primitive methods.
3373 pub fn run(&mut self, t: &Tactic) -> Result<&mut Self, TacticError> {
3374 t(self)?;
3375 Ok(self)
3376 }
3377
3378 /// Finish the proof: every goal must be closed. Assembles the recorded tactic
3379 /// steps into one derivation and runs it through the kernel trust door — the
3380 /// returned [`VerifiedProof`] is `verified` only if the kernel accepts the term.
3381 pub fn qed(&self) -> Result<VerifiedProof, TacticError> {
3382 if !self.open.is_empty() {
3383 return Err(TacticError::GoalsRemain(self.open.len()));
3384 }
3385 let tree = self.assemble(self.root)?;
3386 Ok(check_derivation(&self.premises, &self.goal, tree))
3387 }
3388}
3389
3390/// A first-class tactic: a transformation of the proof state that either makes
3391/// progress (`Ok`) or does not apply (`Err`). Tactics are values, so they compose
3392/// with the [`combinators`].
3393pub type Tactic = Box<dyn Fn(&mut ProofState) -> Result<(), TacticError>>;
3394
3395/// Tactic *values* and the combinators that compose them — the language layer over
3396/// the primitive [`ProofState`] methods. The backtracking combinators (`first`,
3397/// `try_`, `repeat`) speculate on a clone of the state and commit only on success,
3398/// so a partial failure never corrupts the proof.
3399pub mod combinators {
3400 use super::{ProofState, ProofTerm, Tactic, TacticError};
3401
3402 /// `intro name` as a tactic value.
3403 pub fn intro(name: &str) -> Tactic {
3404 let name = name.to_string();
3405 Box::new(move |st: &mut ProofState| st.intro(&name).map(|_| ()))
3406 }
3407 /// `assumption` as a tactic value.
3408 pub fn assumption() -> Tactic {
3409 Box::new(|st: &mut ProofState| st.assumption().map(|_| ()))
3410 }
3411 /// `simp` as a tactic value, its rule set drawn from everything in scope
3412 /// (premises, intro'd hypotheses, cited lemmas) — the script-level default.
3413 pub fn simp() -> Tactic {
3414 Box::new(|st: &mut ProofState| {
3415 let set = st.scope_simp_set();
3416 st.simp(&set).map(|_| ())
3417 })
3418 }
3419 /// `decide` as a tactic value.
3420 pub fn decide() -> Tactic {
3421 Box::new(|st: &mut ProofState| st.decide().map(|_| ()))
3422 }
3423 /// `omega` as a tactic value.
3424 /// `linarith` (rational Fourier-Motzkin with a Farkas certificate) as a tactic value.
3425 pub fn linarith() -> Tactic {
3426 Box::new(|st: &mut ProofState| st.linarith().map(|_| ()))
3427 }
3428 pub fn omega() -> Tactic {
3429 Box::new(|st: &mut ProofState| st.omega().map(|_| ()))
3430 }
3431 /// `crush` as a tactic value.
3432 pub fn crush() -> Tactic {
3433 Box::new(|st: &mut ProofState| st.crush().map(|_| ()))
3434 }
3435 /// `exact name` as a tactic value.
3436 pub fn exact(name: &str) -> Tactic {
3437 let name = name.to_string();
3438 Box::new(move |st: &mut ProofState| st.exact(&name).map(|_| ()))
3439 }
3440 /// `split` (∧I) as a tactic value.
3441 pub fn split() -> Tactic {
3442 Box::new(|st: &mut ProofState| st.split().map(|_| ()))
3443 }
3444 /// `left` (∨I) as a tactic value.
3445 pub fn left() -> Tactic {
3446 Box::new(|st: &mut ProofState| st.left().map(|_| ()))
3447 }
3448 /// `right` (∨I) as a tactic value.
3449 pub fn right() -> Tactic {
3450 Box::new(|st: &mut ProofState| st.right().map(|_| ()))
3451 }
3452 /// `exists witness` (∃I) as a tactic value.
3453 pub fn exists(witness: ProofTerm) -> Tactic {
3454 Box::new(move |st: &mut ProofState| st.exists(witness.clone()).map(|_| ()))
3455 }
3456 /// `cases name` (∧/∨/∃ elimination) as a tactic value.
3457 pub fn cases(name: &str) -> Tactic {
3458 let name = name.to_string();
3459 Box::new(move |st: &mut ProofState| st.cases(&name).map(|_| ()))
3460 }
3461 /// `rewrite name` (Leibniz substitution by an equality) as a tactic value.
3462 /// `rewrite h at k` as a tactic value — the `k`-th occurrence, 0-based.
3463 pub fn rewrite_at(name: &str, occurrence: usize) -> Tactic {
3464 let name = name.to_string();
3465 Box::new(move |st: &mut ProofState| st.rewrite_at(&name, occurrence).map(|_| ()))
3466 }
3467 pub fn rewrite(name: &str) -> Tactic {
3468 let name = name.to_string();
3469 Box::new(move |st: &mut ProofState| st.rewrite(&name).map(|_| ()))
3470 }
3471 /// `rewrite h at hp` — the LOCATION form, rewriting a HYPOTHESIS rather than the goal.
3472 pub fn rewrite_hyp_at(eq: &str, hyp: &str, occurrence: usize) -> Tactic {
3473 let (eq, hyp) = (eq.to_string(), hyp.to_string());
3474 Box::new(move |st: &mut ProofState| st.rewrite_hyp_at(&eq, &hyp, occurrence).map(|_| ()))
3475 }
3476 /// `apply name` (modus ponens against a named rule) as a tactic value.
3477 pub fn apply(name: &str) -> Tactic {
3478 let name = name.to_string();
3479 Box::new(move |st: &mut ProofState| st.apply_named(&name).map(|_| ()))
3480 }
3481 /// `rfl` (close `t = t` by reflexivity) as a tactic value.
3482 pub fn rfl() -> Tactic {
3483 Box::new(|st: &mut ProofState| st.rfl().map(|_| ()))
3484 }
3485 /// `induction` (structural induction over `Nat`) as a tactic value.
3486 pub fn induction() -> Tactic {
3487 Box::new(|st: &mut ProofState| st.induction().map(|_| ()))
3488 }
3489 /// `induction_over` (generic structural induction over `ind_type`) as a tactic value.
3490 pub fn induction_over(ind_type: &str, ctors: Vec<super::CtorSpec>) -> Tactic {
3491 let ind_type = ind_type.to_string();
3492 Box::new(move |st: &mut ProofState| st.induction_over(&ind_type, ctors.clone()).map(|_| ()))
3493 }
3494 /// `auto` (the backward chainer) as a tactic value.
3495 pub fn auto() -> Tactic {
3496 Box::new(|st: &mut ProofState| st.auto().map(|_| ()))
3497 }
3498
3499 /// `t1; t2; …`: run each tactic in turn; fail (without committing the rest) at
3500 /// the first that does not apply.
3501 pub fn seq(tactics: Vec<Tactic>) -> Tactic {
3502 Box::new(move |st: &mut ProofState| {
3503 for t in &tactics {
3504 t(st)?;
3505 }
3506 Ok(())
3507 })
3508 }
3509
3510 /// `first [t1, t2, …]`: try each tactic on a speculative copy and commit the
3511 /// first that succeeds; fail only if none apply.
3512 pub fn first(tactics: Vec<Tactic>) -> Tactic {
3513 Box::new(move |st: &mut ProofState| {
3514 for t in &tactics {
3515 let mut trial = st.clone();
3516 if t(&mut trial).is_ok() {
3517 *st = trial;
3518 return Ok(());
3519 }
3520 }
3521 Err(TacticError::DoesNotApply(
3522 "first: no alternative applied".to_string(),
3523 ))
3524 })
3525 }
3526
3527 /// `try t`: run `t` if it applies, otherwise leave the state unchanged. Always
3528 /// succeeds.
3529 pub fn try_(t: Tactic) -> Tactic {
3530 Box::new(move |st: &mut ProofState| {
3531 let mut trial = st.clone();
3532 if t(&mut trial).is_ok() {
3533 *st = trial;
3534 }
3535 Ok(())
3536 })
3537 }
3538
3539 /// `repeat t`: apply `t` as long as it keeps applying (committing each success),
3540 /// then stop. Always succeeds. Bounded to avoid a non-progressing tactic looping
3541 /// forever.
3542 pub fn repeat(t: Tactic) -> Tactic {
3543 Box::new(move |st: &mut ProofState| {
3544 for _ in 0..100_000 {
3545 let mut trial = st.clone();
3546 if t(&mut trial).is_ok() {
3547 *st = trial;
3548 } else {
3549 break;
3550 }
3551 if st.open.is_empty() {
3552 break;
3553 }
3554 }
3555 Ok(())
3556 })
3557 }
3558
3559 /// `t1 <;> t2`-style: apply `t` to EVERY goal currently open (not just the
3560 /// focused one). Each goal is focused in turn; the subgoals `t` produces for it
3561 /// become the new open set, in original goal order.
3562 /// `any_goals t`: run `t` on every open goal, keeping the goals it left and the goals it
3563 /// declined alike, and succeed iff it succeeded on AT LEAST ONE.
3564 ///
3565 /// The permissive sibling of [`all_goals`], and the one Lean scripts actually reach for after a
3566 /// `constructor` splits a goal into branches only some of which `t` can discharge. Unlike
3567 /// `all_goals` it does not abort the whole combinator when `t` fails on one branch — that
3568 /// branch is simply carried forward unchanged.
3569 pub fn any_goals(t: Tactic) -> Tactic {
3570 Box::new(move |st: &mut ProofState| {
3571 let current: Vec<usize> = st.open.iter().copied().collect();
3572 let mut new_open = std::collections::VecDeque::new();
3573 let mut any_succeeded = false;
3574 for goal_idx in current {
3575 st.open = std::collections::VecDeque::from([goal_idx]);
3576 match t(st) {
3577 Ok(()) => {
3578 any_succeeded = true;
3579 new_open.extend(st.open.iter().copied());
3580 }
3581 // `t` declined this branch: keep the goal exactly as it was and move on.
3582 Err(_) => new_open.push_back(goal_idx),
3583 }
3584 }
3585 st.open = new_open;
3586 if any_succeeded {
3587 Ok(())
3588 } else {
3589 Err(TacticError::DoesNotApply(
3590 "any_goals: the tactic applied to no open goal".to_string(),
3591 ))
3592 }
3593 })
3594 }
3595
3596 pub fn all_goals(t: Tactic) -> Tactic {
3597 Box::new(move |st: &mut ProofState| {
3598 let current: Vec<usize> = st.open.iter().copied().collect();
3599 let mut new_open = std::collections::VecDeque::new();
3600 for goal_idx in current {
3601 st.open = std::collections::VecDeque::from([goal_idx]);
3602 t(st)?;
3603 new_open.extend(st.open.iter().copied());
3604 }
3605 st.open = new_open;
3606 Ok(())
3607 })
3608 }
3609
3610 /// `t1 <;> t2`: run `t1` on the focused goal, then `t2` on exactly the goals `t1`
3611 /// PRODUCED — not on every goal that happens to be open.
3612 ///
3613 /// The difference is invisible when `<;>` is the first branching step, which almost every
3614 /// textbook use is, and that is why running `all_goals` here survived a large test suite.
3615 /// It is not invisible after an earlier step left a goal waiting: `split . left <;>
3616 /// assumption` must leave the `split`'s right conjunct alone. When `t2` happened to
3617 /// discharge that goal too, the script succeeded one goal further along than the proof
3618 /// believed; when it did not, the failure was reported for a goal the source never asked
3619 /// it to look at. A goal `t1` produced is one that was not open before it ran — node
3620 /// indices only ever grow, so the two sets are told apart exactly.
3621 pub fn then_all(t1: Tactic, t2: Tactic) -> Tactic {
3622 Box::new(move |st: &mut ProofState| {
3623 let before: std::collections::HashSet<usize> = st.open.iter().copied().collect();
3624 t1(st)?;
3625 let after: Vec<usize> = st.open.iter().copied().collect();
3626 let mut new_open = std::collections::VecDeque::new();
3627 for goal_idx in after {
3628 if before.contains(&goal_idx) {
3629 new_open.push_back(goal_idx);
3630 continue;
3631 }
3632 st.open = std::collections::VecDeque::from([goal_idx]);
3633 t2(st)?;
3634 new_open.extend(st.open.iter().copied());
3635 }
3636 st.open = new_open;
3637 Ok(())
3638 })
3639 }
3640
3641 /// `· t` / `focus t` / `next t`: run `t` on the focused goal ALONE, and make it an error
3642 /// for the block to leave that goal open.
3643 ///
3644 /// A script is otherwise a flat list of chains, and because subgoals are pushed to the
3645 /// front, stripping Lean's bullets and concatenating the blocks WORKS — right up until a
3646 /// block leaves a goal open or closes two, at which point the blocks silently misalign
3647 /// and, with generic enough tactics, the proof still succeeds having proved the goals in
3648 /// a pairing the source never specified. The bullet is what makes that impossible, so it
3649 /// is the ERROR, not the focusing, that is the capability here.
3650 pub fn focus(t: Tactic) -> Tactic {
3651 Box::new(move |st: &mut ProofState| {
3652 let original: std::collections::VecDeque<usize> = st.open.clone();
3653 let Some(&idx) = st.open.front() else {
3654 return Err(TacticError::NoOpenGoals);
3655 };
3656 let rest: std::collections::VecDeque<usize> = st.open.iter().skip(1).copied().collect();
3657 st.open = std::collections::VecDeque::from([idx]);
3658 match t(st) {
3659 Ok(()) if st.open.is_empty() => {
3660 st.open = rest;
3661 Ok(())
3662 }
3663 Ok(()) => {
3664 let left = st.open.len();
3665 st.open = original;
3666 Err(TacticError::DoesNotApply(format!(
3667 "focus: the block left {left} goal(s) open — a focused block must \
3668 close exactly the goal it opened"
3669 )))
3670 }
3671 Err(e) => {
3672 st.open = original;
3673 Err(e)
3674 }
3675 }
3676 })
3677 }
3678
3679 /// `by_contra h` as a tactic value.
3680 pub fn by_contra(name: &str) -> Tactic {
3681 let name = name.to_string();
3682 Box::new(move |st: &mut ProofState| st.by_contra(&name).map(|_| ()))
3683 }
3684 /// `ring` (commutative-ring normalisation) as a tactic value.
3685 pub fn ring() -> Tactic {
3686 Box::new(|st: &mut ProofState| st.ring().map(|_| ()))
3687 }
3688 /// `exact <term>` as a tactic value.
3689 pub fn exact_term(term: super::PTerm) -> Tactic {
3690 Box::new(move |st: &mut ProofState| st.exact_term(&term).map(|_| ()))
3691 }
3692 /// `refine <term>` as a tactic value.
3693 pub fn refine(term: super::PTerm) -> Tactic {
3694 Box::new(move |st: &mut ProofState| st.refine_term(&term).map(|_| ()))
3695 }
3696 /// `have name from <term>` as a tactic value.
3697 pub fn have(name: &str, term: super::PTerm) -> Tactic {
3698 let name = name.to_string();
3699 Box::new(move |st: &mut ProofState| st.have_term(&name, &term).map(|_| ()))
3700 }
3701 /// `exists <term>` as a tactic value, with the witness resolved against the goal's scope.
3702 pub fn exists_term(term: super::PTerm) -> Tactic {
3703 Box::new(move |st: &mut ProofState| {
3704 let witness = st.value_term(&term)?;
3705 st.exists(witness).map(|_| ())
3706 })
3707 }
3708 /// `cases name with a b` as a tactic value.
3709 pub fn cases_with(name: &str, names: Vec<String>) -> Tactic {
3710 let name = name.to_string();
3711 Box::new(move |st: &mut ProofState| st.cases_with(&name, &names).map(|_| ()))
3712 }
3713 /// `by_rule R` as a tactic value — discharge the goal with the NAMED inference rule.
3714 pub fn by_rule(name: &str) -> Tactic {
3715 let name = name.to_string();
3716 Box::new(move |st: &mut ProofState| st.by_rule(&name).map(|_| ()))
3717 }
3718
3719 /// `calc h1 h2 …` as a tactic value — compose the named chain.
3720 pub fn calc(names: Vec<String>) -> Tactic {
3721 Box::new(move |st: &mut ProofState| st.calc(&names).map(|_| ()))
3722 }
3723 /// `induction name` as a tactic value.
3724 pub fn induction_on(name: &str) -> Tactic {
3725 let name = name.to_string();
3726 Box::new(move |st: &mut ProofState| st.induction_on(&name).map(|_| ()))
3727 }
3728 /// `simp only [a, b]` as a tactic value — the rule set is exactly the named hypotheses.
3729 pub fn simp_only(names: Vec<String>) -> Tactic {
3730 Box::new(move |st: &mut ProofState| {
3731 let set = st.named_simp_set(&names)?;
3732 st.simp(&set).map(|_| ())
3733 })
3734 }
3735 /// `simp [a, b]` as a tactic value — Lean's "these AS WELL", which for a default set
3736 /// that is already the whole scope adds nothing. The names are still resolved, so a
3737 /// typo is an error rather than a silently ignored rule.
3738 pub fn simp_with(names: Vec<String>) -> Tactic {
3739 Box::new(move |st: &mut ProofState| {
3740 st.named_simp_set(&names)?;
3741 let set = st.scope_simp_set();
3742 st.simp(&set).map(|_| ())
3743 })
3744 }
3745}