Skip to main content

logicaffeine_proof/
lemma_index.rs

1//! `exact?` / `apply?` and premise selection: search over a NAMED, certified
2//! lemma library.
3//!
4//! Each lemma is peeled to `∀xs. A₁ → … → Aₖ → C`; its conclusion `C` is indexed
5//! in a discrimination tree ([`crate::discrimination`]). A query matches the
6//! goal against candidate conclusions with the one-sided matcher
7//! ([`crate::unify::match_expr_pattern`]) — so a quantified lemma instantiates
8//! at the (possibly ground) goal for free. `find_exact` reports lemmas whose
9//! conclusion IS the goal; `find_apply` reports lemmas whose conclusion matches
10//! and lists the antecedents you would still owe. `select_premises` ranks the
11//! whole library for relevance, the premise filter that keeps `auto` tractable
12//! on a large axiom base.
13//!
14//! This is the direct answer to Lean's `exact?`/`apply?` and to premise
15//! selection — search over a citable, kernel-checkable library rather than an
16//! opaque model.
17
18use crate::discrimination::DiscTree;
19use crate::unify::{apply_subst_to_expr, match_expr_pattern, Substitution};
20use crate::{ProofExpr, ProofTerm};
21
22/// A search result: which lemma, the suggested tactic text, the instantiation,
23/// and (for `apply?`) the antecedents still to prove.
24#[derive(Debug, Clone)]
25pub struct Suggestion {
26    pub lemma: String,
27    pub tactic_text: String,
28    pub subst: Substitution,
29    pub remaining: Vec<ProofExpr>,
30}
31
32/// A lemma peeled into binders, antecedents, and conclusion.
33struct CompiledLemma {
34    name: String,
35    conclusion: ProofExpr,
36    premises: Vec<ProofExpr>,
37}
38
39/// An index over a named lemma library.
40pub struct LemmaIndex {
41    lemmas: Vec<CompiledLemma>,
42    concl_index: DiscTree<usize>,
43}
44
45impl LemmaIndex {
46    /// Build the index from named lemmas (axioms and proved theorems alike).
47    pub fn build(named: &[(String, ProofExpr)]) -> Self {
48        let mut lemmas = Vec::new();
49        let mut concl_index = DiscTree::new();
50        for (name, formula) in named {
51            let (premises, conclusion) = peel(formula);
52            let idx = lemmas.len();
53            concl_index.insert_expr(&conclusion, idx);
54            lemmas.push(CompiledLemma {
55                name: name.clone(),
56                conclusion,
57                premises,
58            });
59        }
60        LemmaIndex {
61            lemmas,
62            concl_index,
63        }
64    }
65
66    /// Lemmas whose conclusion IS the goal (an instance of it). Ranked most-
67    /// specific first (fewest variable bindings). `exact?`.
68    pub fn find_exact(&self, goal: &ProofExpr) -> Vec<Suggestion> {
69        let mut out = self.matches(goal, "exact");
70        out.sort_by_key(|s| s.subst.len());
71        out
72    }
73
74    /// Lemmas whose conclusion matches the goal AND have antecedents — applying
75    /// them reduces the goal to those (instantiated) antecedents. `apply?`.
76    pub fn find_apply(&self, goal: &ProofExpr) -> Vec<Suggestion> {
77        let mut out: Vec<Suggestion> = self
78            .matches(goal, "apply")
79            .into_iter()
80            .filter(|s| !s.remaining.is_empty())
81            .collect();
82        out.sort_by_key(|s| (s.remaining.len(), s.subst.len()));
83        out
84    }
85
86    /// Rank the whole library by relevance to `goal` and return the top `k`
87    /// names — the premise filter for `auto` on a large base. Relevance is: an
88    /// exact/apply conclusion match first, then head-symbol overlap; lemmas
89    /// sharing no symbol with the goal are dropped entirely.
90    pub fn select_premises(&self, goal: &ProofExpr, k: usize) -> Vec<String> {
91        let goal_syms = expr_symbols(goal);
92        let matching: std::collections::HashSet<usize> = self
93            .concl_index
94            .candidates_expr(goal)
95            .into_iter()
96            .copied()
97            .collect();
98
99        let mut scored: Vec<(i64, usize)> = self
100            .lemmas
101            .iter()
102            .enumerate()
103            .filter_map(|(i, lem)| {
104                let overlap = expr_symbols(&lem.conclusion)
105                    .intersection(&goal_syms)
106                    .count() as i64;
107                if overlap == 0 && !matching.contains(&i) {
108                    return None; // no shared structure — irrelevant
109                }
110                let mut score = overlap;
111                if matching.contains(&i) {
112                    score += 100; // a conclusion match dominates
113                }
114                Some((score, i))
115            })
116            .collect();
117        scored.sort_by(|a, b| b.0.cmp(&a.0));
118        scored.truncate(k);
119        scored
120            .into_iter()
121            .map(|(_, i)| self.lemmas[i].name.clone())
122            .collect()
123    }
124
125    fn matches(&self, goal: &ProofExpr, verb: &str) -> Vec<Suggestion> {
126        let mut out = Vec::new();
127        let mut cand: Vec<usize> = self
128            .concl_index
129            .candidates_expr(goal)
130            .into_iter()
131            .copied()
132            .collect();
133        cand.sort_unstable();
134        cand.dedup();
135        for i in cand {
136            let lem = &self.lemmas[i];
137            if let Some(subst) = match_expr_pattern(&lem.conclusion, goal) {
138                let remaining = lem
139                    .premises
140                    .iter()
141                    .map(|p| apply_subst_to_expr(p, &subst))
142                    .collect();
143                out.push(Suggestion {
144                    lemma: lem.name.clone(),
145                    tactic_text: format!("{verb} {}", lem.name),
146                    subst,
147                    remaining,
148                });
149            }
150        }
151        out
152    }
153}
154
155/// Peel `∀xs. A₁ → … → Aₖ → C` into `([A₁, …, Aₖ], C)`.
156fn peel(formula: &ProofExpr) -> (Vec<ProofExpr>, ProofExpr) {
157    let mut body = formula;
158    while let ProofExpr::ForAll { body: inner, .. } = body {
159        body = inner;
160    }
161    let mut premises = Vec::new();
162    while let ProofExpr::Implies(a, rest) = body {
163        premises.push((**a).clone());
164        body = rest;
165    }
166    (premises, body.clone())
167}
168
169/// The set of predicate/function/atom head symbols mentioned in an expression —
170/// the coarse relevance signature for premise selection.
171fn expr_symbols(e: &ProofExpr) -> std::collections::HashSet<String> {
172    let mut out = std::collections::HashSet::new();
173    collect_expr_symbols(e, &mut out);
174    out
175}
176
177fn collect_expr_symbols(e: &ProofExpr, out: &mut std::collections::HashSet<String>) {
178    match e {
179        ProofExpr::Predicate { name, args, .. } => {
180            out.insert(format!("p:{name}"));
181            for a in args {
182                collect_term_symbols(a, out);
183            }
184        }
185        ProofExpr::Atom(s) => {
186            out.insert(format!("a:{s}"));
187        }
188        ProofExpr::Identity(l, r) => {
189            out.insert("=".to_string());
190            collect_term_symbols(l, out);
191            collect_term_symbols(r, out);
192        }
193        ProofExpr::And(l, r)
194        | ProofExpr::Or(l, r)
195        | ProofExpr::Implies(l, r)
196        | ProofExpr::Iff(l, r) => {
197            collect_expr_symbols(l, out);
198            collect_expr_symbols(r, out);
199        }
200        ProofExpr::Not(p) => collect_expr_symbols(p, out),
201        ProofExpr::ForAll { body, .. } | ProofExpr::Exists { body, .. } => {
202            collect_expr_symbols(body, out)
203        }
204        _ => {}
205    }
206}
207
208fn collect_term_symbols(t: &ProofTerm, out: &mut std::collections::HashSet<String>) {
209    match t {
210        ProofTerm::Constant(s) => {
211            out.insert(format!("c:{s}"));
212        }
213        ProofTerm::Function(name, args) => {
214            out.insert(format!("f:{name}"));
215            for a in args {
216                collect_term_symbols(a, out);
217            }
218        }
219        // Variables carry no relevance signal.
220        _ => {}
221    }
222}