Skip to main content

logicaffeine_proof/
development.rs

1//! A formal-development parser: the body of a `## Theory` block — a sequence of `Axiom`
2//! and `Theorem` declarations in formal notation — into the axioms and
3//! [`LibraryTheorem`](crate::verify::LibraryTheorem)s the multi-theorem driver consumes.
4//!
5//! This is the surface for an axiomatic development like Tarski geometry: a shared axiom
6//! base plus dependency-ordered theorems, each citing earlier ones, all discharged and
7//! kernel-certified by [`prove_library_with_axioms`](crate::verify::prove_library_with_axioms).
8//!
9//! ```text
10//! Axiom flip: for all a b, Cong(a, b, b, a).
11//! Axiom inner_trans: for all a b c d e f,
12//!     if Cong(a,b,c,d) and Cong(a,b,e,f) then Cong(c,d,e,f).
13//! Theorem reflexivity: prove for all a b, Cong(a, b, a, b).
14//! Theorem symmetry cites reflexivity:
15//!     prove for all a b c d, if Cong(a,b,c,d) then Cong(c,d,a,b).
16//! Theorem null_segment: given Cong(P, Q, R, R); prove P = Q.
17//! ```
18//!
19//! Grammar (statements terminated by `.`):
20//! * `Axiom <name> : <formula>`
21//! * `Theorem <name> [cites <n1>, <n2>, …] : [given <formula> ;]* prove <formula>`
22//!
23//! Clauses within a theorem are separated by `;`; cited lemma names by `,`. Formulas are
24//! handed to [`parse_formula`](crate::formula::parse_formula).
25
26use crate::formula::{parse_formula, FormulaError};
27use crate::verify::{prove_library_with_axioms, LibraryResult, LibraryTheorem};
28use crate::ProofExpr;
29
30/// A parsed formal development: a shared axiom base and the theorems built on it.
31#[derive(Debug, Clone, PartialEq)]
32pub struct Development {
33    /// Named axioms (the name is for diagnostics/citation; the prover uses the formula).
34    pub axioms: Vec<(String, ProofExpr)>,
35    /// Theorems, in source order, each with its premises, goal, and cited lemma names.
36    pub theorems: Vec<LibraryTheorem>,
37    /// Names of `[simp]`-tagged declarations (axioms and theorems), in source
38    /// order — the development's default rewrite-rule set.
39    pub simp_tagged: Vec<String>,
40}
41
42impl Development {
43    /// The axiom formulas, in declaration order — the shared base for the driver.
44    pub fn axiom_exprs(&self) -> Vec<ProofExpr> {
45        self.axioms.iter().map(|(_, e)| e.clone()).collect()
46    }
47
48    /// The names tagged `[simp]`, in source order.
49    pub fn simp_lemmas(&self) -> &[String] {
50        &self.simp_tagged
51    }
52}
53
54/// Parse a `## Theory` body into a [`Development`].
55pub fn parse_development(body: &str) -> Result<Development, FormulaError> {
56    let mut axioms = Vec::new();
57    let mut theorems = Vec::new();
58
59    let mut simp_tagged = Vec::new();
60
61    for stmt in split_on_top_level(body, '.') {
62        let stmt = stmt.trim();
63        if stmt.is_empty() {
64            continue;
65        }
66        let words: Vec<&str> = stmt.split_whitespace().collect();
67        match words.first().map(|w| w.to_lowercase()).as_deref() {
68            Some("axiom") => {
69                let (decl, simp) = parse_axiom_decl(stmt)?;
70                if simp {
71                    simp_tagged.push(decl.0.clone());
72                }
73                axioms.push(decl);
74            }
75            Some("theorem") => {
76                let (thm, simp) = parse_theorem_decl(stmt)?;
77                if simp {
78                    simp_tagged.push(thm.name.clone());
79                }
80                theorems.push(thm);
81            }
82            other => {
83                return Err(FormulaError::new(format!(
84                    "expected a declaration starting with 'Axiom' or 'Theorem', found {other:?}"
85                )))
86            }
87        }
88    }
89
90    Ok(Development {
91        axioms,
92        theorems,
93        simp_tagged,
94    })
95}
96
97/// Parse a `## Theory` body and discharge every theorem against the development's axioms
98/// (and cited lemmas), in citation order — each kernel-certified. Results are in source
99/// order, paired with the theorem name.
100pub fn prove_development(body: &str) -> Result<Vec<(String, LibraryResult)>, FormulaError> {
101    let dev = parse_development(body)?;
102    let axioms = dev.axiom_exprs();
103    let results = prove_library_with_axioms(&axioms, &dev.theorems);
104    Ok(dev
105        .theorems
106        .iter()
107        .map(|t| t.name.clone())
108        .zip(results)
109        .collect())
110}
111
112// ---------------------------------------------------------------------------
113// Declaration parsing
114// ---------------------------------------------------------------------------
115
116/// The `[simp]` attribute token, written between a declaration's name and the
117/// rest of its header. Returns the header words with the attribute removed and
118/// whether it was present.
119fn strip_simp_attr<'a>(words: &[&'a str]) -> (Vec<&'a str>, bool) {
120    let mut simp = false;
121    let kept = words
122        .iter()
123        .filter(|w| {
124            if w.eq_ignore_ascii_case("[simp]") {
125                simp = true;
126                false
127            } else {
128                true
129            }
130        })
131        .copied()
132        .collect();
133    (kept, simp)
134}
135
136/// `Axiom <name> [simp] : <formula>`
137fn parse_axiom_decl(stmt: &str) -> Result<((String, ProofExpr), bool), FormulaError> {
138    let (header, formula_src) = split_once_top_level(stmt, ':').ok_or_else(|| {
139        FormulaError::new("an 'Axiom' declaration needs a ':' before its formula")
140    })?;
141    let hwords: Vec<&str> = header.split_whitespace().collect();
142    let (hwords, simp) = strip_simp_attr(&hwords);
143    let name = hwords
144        .get(1)
145        .ok_or_else(|| FormulaError::new("'Axiom' declaration is missing a name"))?
146        .to_string();
147    let formula = parse_formula(&formula_src)?;
148    Ok(((name, formula), simp))
149}
150
151/// `Theorem <name> [simp] [cites <n1>, <n2>, …] : [given <formula> ;]* prove <formula>`
152fn parse_theorem_decl(stmt: &str) -> Result<(LibraryTheorem, bool), FormulaError> {
153    let (header, body) = split_once_top_level(stmt, ':').ok_or_else(|| {
154        FormulaError::new("a 'Theorem' declaration needs a ':' before its clauses")
155    })?;
156
157    // Header: `Theorem <name> [simp] [cites/using/from <n1>, <n2>, …]`.
158    let hwords: Vec<&str> = header.split_whitespace().collect();
159    let (hwords, simp) = strip_simp_attr(&hwords);
160    let name = hwords
161        .get(1)
162        .ok_or_else(|| FormulaError::new("'Theorem' declaration is missing a name"))?
163        .to_string();
164    let mut cites = Vec::new();
165    if let Some(kw) = hwords.get(2) {
166        if matches!(kw.to_lowercase().as_str(), "cites" | "using" | "from") {
167            for w in &hwords[3..] {
168                for part in w.split(',') {
169                    let part = part.trim();
170                    if !part.is_empty() {
171                        cites.push(part.to_string());
172                    }
173                }
174            }
175        }
176    }
177
178    // Clauses: `given <formula>` (zero or more) then `prove <formula>`. A new clause
179    // begins at each `given`/`assume`/`prove`/`show` KEYWORD — no separator punctuation is
180    // required, so this is robust to the surface NL lexer dropping a `;` (and any stray
181    // `;`/`.` left in a formula is absorbed by the formula tokenizer). Formal formulas never
182    // contain these keywords, so keyword-delimited splitting is unambiguous.
183    let is_clause_kw = |w: &str| matches!(w, "given" | "assume" | "prove" | "show");
184    let words: Vec<&str> = body.split_whitespace().collect();
185    let mut premises = Vec::new();
186    let mut goal: Option<ProofExpr> = None;
187    let mut i = 0;
188    while i < words.len() {
189        let kw = words[i].to_lowercase();
190        if !is_clause_kw(&kw) {
191            // A stray token before the first clause keyword (e.g. a lone `;`): skip it.
192            i += 1;
193            continue;
194        }
195        i += 1;
196        let start = i;
197        while i < words.len() && !is_clause_kw(&words[i].to_lowercase()) {
198            i += 1;
199        }
200        let formula_src = words[start..i].join(" ");
201        match kw.as_str() {
202            "given" | "assume" => premises.push(parse_formula(&formula_src)?),
203            _ /* prove | show */ => {
204                if goal.is_some() {
205                    return Err(FormulaError::new(format!(
206                        "theorem '{name}' has more than one 'prove' clause"
207                    )));
208                }
209                goal = Some(parse_formula(&formula_src)?);
210            }
211        }
212    }
213
214    let goal =
215        goal.ok_or_else(|| FormulaError::new(format!("theorem '{name}' has no 'prove' clause")))?;
216    Ok((
217        LibraryTheorem {
218            name,
219            premises,
220            goal,
221            cites,
222        },
223        simp,
224    ))
225}
226
227// ---------------------------------------------------------------------------
228// Delimiter splitting (paren-depth aware, so a delimiter inside `(…)` is ignored)
229// ---------------------------------------------------------------------------
230
231/// Split `s` on every top-level (paren-depth 0) occurrence of `delim`.
232fn split_on_top_level(s: &str, delim: char) -> Vec<String> {
233    let mut out = Vec::new();
234    let mut depth = 0i32;
235    let mut cur = String::new();
236    for c in s.chars() {
237        match c {
238            '(' => {
239                depth += 1;
240                cur.push(c);
241            }
242            ')' => {
243                depth -= 1;
244                cur.push(c);
245            }
246            c if c == delim && depth == 0 => {
247                out.push(std::mem::take(&mut cur));
248            }
249            c => cur.push(c),
250        }
251    }
252    out.push(cur);
253    out
254}
255
256/// Split `s` at the FIRST top-level occurrence of `delim` into `(before, after)`.
257fn split_once_top_level(s: &str, delim: char) -> Option<(String, String)> {
258    let mut depth = 0i32;
259    for (i, c) in s.char_indices() {
260        match c {
261            '(' => depth += 1,
262            ')' => depth -= 1,
263            c if c == delim && depth == 0 => {
264                return Some((s[..i].to_string(), s[i + c.len_utf8()..].to_string()));
265            }
266            _ => {}
267        }
268    }
269    None
270}