Skip to main content

logicaffeine_proof/
formula.rs

1//! A self-contained parser from formal first-order-logic surface text to [`ProofExpr`].
2//!
3//! The natural-language front end (`logicaffeine_language`) is excellent at English —
4//! unary predicates, simple binary relations from transitive verbs — but a geometry
5//! axiom base needs *formal* relations of higher arity (`Cong(a,b,c,d)`, `Bet(a,b,c)`)
6//! and explicit quantifier prefixes that no English sentence expresses. This module is
7//! the seam: a small recursive-descent parser, deliberately independent of the 12k-line
8//! NL parser (the same self-containment that `tactic_script` has), turning a line like
9//!
10//! ```text
11//! for all a b c d e f, if Cong(a, b, c, d) and Cong(a, b, e, f) then Cong(c, d, e, f)
12//! ```
13//!
14//! directly into the [`ProofExpr`] the prover and the multi-theorem driver already
15//! consume. It is the surface for `## Axiom` / `## Theory` (the seam for Tarski).
16//!
17//! # Conventions
18//!
19//! * An identifier that leads with an uppercase letter or a digit is a CONSTANT
20//!   (`ProofTerm::Constant`) — a fixed point like `P`, `Q`, `A`; one that leads with a
21//!   lowercase letter is a VARIABLE (`ProofTerm::Variable`) — a bound point like `a`,
22//!   `b`. This matches the verifier's standard FOL reading (a lowercase-leading symbol
23//!   is a variable).
24//! * Connectives, lowest precedence first: quantifiers (`for all`, `there exists`) <
25//!   `iff` < implication (`if … then …`, `implies`, `->`) < `or` < `and` < `not` <
26//!   atoms. Implication is right-associative.
27//! * Both an English-flavoured spelling and a symbolic one are accepted: `and`/`∧`,
28//!   `or`/`∨`, `not`/`¬`, `implies`/`->`/`→`, `iff`/`<->`/`↔`, `for all`/`forall`/`∀`,
29//!   `there exists`/`exists`/`∃`.
30
31use crate::{ProofExpr, ProofTerm};
32
33/// A failure to parse formal-logic surface text.
34#[derive(Debug, Clone, PartialEq, Eq)]
35pub struct FormulaError {
36    pub message: String,
37}
38
39impl FormulaError {
40    pub(crate) fn new(message: impl Into<String>) -> Self {
41        FormulaError {
42            message: message.into(),
43        }
44    }
45}
46
47impl std::fmt::Display for FormulaError {
48    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
49        write!(f, "formula parse error: {}", self.message)
50    }
51}
52
53impl std::error::Error for FormulaError {}
54
55/// Parse formal first-order-logic surface text into a [`ProofExpr`].
56///
57/// See the module docs for the grammar and the constant/variable convention. Returns a
58/// [`FormulaError`] on malformed input (the whole string must be consumed).
59pub fn parse_formula(input: &str) -> Result<ProofExpr, FormulaError> {
60    let tokens = tokenize(input)?;
61    let mut p = Parser {
62        tokens: &tokens,
63        pos: 0,
64    };
65    let expr = p.parse_formula()?;
66    if p.pos != p.tokens.len() {
67        return Err(FormulaError::new(format!(
68            "unexpected trailing input near token {:?}",
69            p.tokens.get(p.pos)
70        )));
71    }
72    Ok(expr)
73}
74
75// ---------------------------------------------------------------------------
76// Tokenizer
77// ---------------------------------------------------------------------------
78
79#[derive(Debug, Clone, PartialEq, Eq)]
80enum Tok {
81    Ident(String),
82    LParen,
83    RParen,
84    Comma,
85    Eq,
86    Arrow,  // -> →   (implication)
87    Iff,    // <-> ↔
88    And,    // ∧
89    Or,     // ∨
90    Not,    // ¬
91    Forall, // ∀
92    Exists, // ∃
93}
94
95fn tokenize(input: &str) -> Result<Vec<Tok>, FormulaError> {
96    let chars: Vec<char> = input.chars().collect();
97    let mut toks = Vec::new();
98    let mut i = 0;
99    while i < chars.len() {
100        let c = chars[i];
101        if c.is_whitespace() {
102            i += 1;
103            continue;
104        }
105        match c {
106            '(' => {
107                toks.push(Tok::LParen);
108                i += 1;
109            }
110            ')' => {
111                toks.push(Tok::RParen);
112                i += 1;
113            }
114            ',' => {
115                toks.push(Tok::Comma);
116                i += 1;
117            }
118            // A bare '.' is a benign body/clause terminator (e.g. ending a sentence);
119            // treated as whitespace so `forall a b. P` and `forall a b, P` both parse.
120            '.' | ';' => {
121                i += 1;
122            }
123            '=' => {
124                toks.push(Tok::Eq);
125                i += 1;
126            }
127            '∧' => {
128                toks.push(Tok::And);
129                i += 1;
130            }
131            '∨' => {
132                toks.push(Tok::Or);
133                i += 1;
134            }
135            '¬' => {
136                toks.push(Tok::Not);
137                i += 1;
138            }
139            '∀' => {
140                toks.push(Tok::Forall);
141                i += 1;
142            }
143            '∃' => {
144                toks.push(Tok::Exists);
145                i += 1;
146            }
147            '→' => {
148                toks.push(Tok::Arrow);
149                i += 1;
150            }
151            '↔' => {
152                toks.push(Tok::Iff);
153                i += 1;
154            }
155            '-' if i + 1 < chars.len() && chars[i + 1] == '>' => {
156                toks.push(Tok::Arrow);
157                i += 2;
158            }
159            '<' if i + 2 < chars.len() && chars[i + 1] == '-' && chars[i + 2] == '>' => {
160                toks.push(Tok::Iff);
161                i += 3;
162            }
163            c if c.is_alphanumeric() || c == '_' => {
164                let start = i;
165                while i < chars.len() && (chars[i].is_alphanumeric() || chars[i] == '_') {
166                    i += 1;
167                }
168                toks.push(Tok::Ident(chars[start..i].iter().collect()));
169            }
170            other => {
171                return Err(FormulaError::new(format!("unexpected character '{other}'")));
172            }
173        }
174    }
175    Ok(toks)
176}
177
178// ---------------------------------------------------------------------------
179// Parser
180// ---------------------------------------------------------------------------
181
182struct Parser<'a> {
183    tokens: &'a [Tok],
184    pos: usize,
185}
186
187impl<'a> Parser<'a> {
188    fn peek(&self) -> Option<&Tok> {
189        self.tokens.get(self.pos)
190    }
191
192    fn advance(&mut self) -> Option<&Tok> {
193        let t = self.tokens.get(self.pos);
194        if t.is_some() {
195            self.pos += 1;
196        }
197        t
198    }
199
200    /// A lowercased keyword `Ident` at the cursor, if any (for the English spellings).
201    fn peek_kw(&self) -> Option<String> {
202        match self.peek() {
203            Some(Tok::Ident(s)) => Some(s.to_lowercase()),
204            _ => None,
205        }
206    }
207
208    fn eat_kw(&mut self, kw: &str) -> bool {
209        if self.peek_kw().as_deref() == Some(kw) {
210            self.pos += 1;
211            true
212        } else {
213            false
214        }
215    }
216
217    /// Whether a quantifier prefix begins at the cursor — `for all`/`forall`/`∀`,
218    /// `there exists`/`exists`/`some`/`∃`. A quantifier may appear as an OPERAND (e.g. the
219    /// consequent of `if … then ∃x. …`), not only at the top, so it extends as far right
220    /// as possible from wherever it starts — standard FOL prefix-quantifier scope.
221    fn peek_is_quantifier(&self) -> bool {
222        matches!(self.peek(), Some(Tok::Forall) | Some(Tok::Exists))
223            || matches!(
224                self.peek_kw().as_deref(),
225                Some("forall") | Some("for") | Some("exists") | Some("there") | Some("some")
226            )
227    }
228
229    // formula := quantifier | iff
230    fn parse_formula(&mut self) -> Result<ProofExpr, FormulaError> {
231        // Quantifiers: `for all <vars> , body` / `forall …` / `∀ …`, and the existential
232        // analogues. The variable list is space-separated idents up to `,`/`.` (consumed
233        // as whitespace by the tokenizer) — the comma is optional.
234        if matches!(self.peek(), Some(Tok::Forall)) {
235            self.advance();
236            return self.finish_quantifier(true);
237        }
238        if matches!(self.peek(), Some(Tok::Exists)) {
239            self.advance();
240            return self.finish_quantifier(false);
241        }
242        if self.eat_kw("forall") {
243            return self.finish_quantifier(true);
244        }
245        if self.eat_kw("for") {
246            if !self.eat_kw("all") {
247                return Err(FormulaError::new("expected 'all' after 'for'"));
248            }
249            return self.finish_quantifier(true);
250        }
251        if self.eat_kw("exists") {
252            return self.finish_quantifier(false);
253        }
254        if self.eat_kw("there") {
255            if !(self.eat_kw("exists") || self.eat_kw("is") || self.eat_kw("are")) {
256                return Err(FormulaError::new("expected 'exists' after 'there'"));
257            }
258            return self.finish_quantifier(false);
259        }
260        if self.eat_kw("some") {
261            return self.finish_quantifier(false);
262        }
263        self.parse_iff()
264    }
265
266    /// After a quantifier keyword: read the bound variables, then `,` (optional), then
267    /// the body, nesting so the FIRST variable is the OUTERMOST binder.
268    fn finish_quantifier(&mut self, universal: bool) -> Result<ProofExpr, FormulaError> {
269        let mut vars = Vec::new();
270        while let Some(Tok::Ident(s)) = self.peek() {
271            // Stop if this ident is actually the start of the body (a keyword), not a var.
272            let low = s.to_lowercase();
273            if matches!(low.as_str(), "if" | "not" | "true" | "false") {
274                break;
275            }
276            vars.push(s.clone());
277            self.advance();
278        }
279        if vars.is_empty() {
280            return Err(FormulaError::new("quantifier with no bound variables"));
281        }
282        // An optional separating comma.
283        if matches!(self.peek(), Some(Tok::Comma)) {
284            self.advance();
285        }
286        let body = self.parse_formula()?;
287        Ok(vars.into_iter().rev().fold(body, |acc, var| {
288            if universal {
289                ProofExpr::ForAll {
290                    variable: var,
291                    body: Box::new(acc),
292                }
293            } else {
294                ProofExpr::Exists {
295                    variable: var,
296                    body: Box::new(acc),
297                }
298            }
299        }))
300    }
301
302    // iff := implication (('iff' | '<->') implication)?
303    fn parse_iff(&mut self) -> Result<ProofExpr, FormulaError> {
304        let left = self.parse_implication()?;
305        if matches!(self.peek(), Some(Tok::Iff)) || self.peek_kw().as_deref() == Some("iff") {
306            self.advance();
307            let right = self.parse_implication()?;
308            return Ok(ProofExpr::Iff(Box::new(left), Box::new(right)));
309        }
310        Ok(left)
311    }
312
313    // implication := 'if' disjunction 'then' implication
314    //              | disjunction (('implies'|'->') implication)?     (right-assoc)
315    fn parse_implication(&mut self) -> Result<ProofExpr, FormulaError> {
316        if self.eat_kw("if") {
317            let cond = self.parse_disjunction()?;
318            if !self.eat_kw("then") {
319                return Err(FormulaError::new("expected 'then' to close an 'if'"));
320            }
321            let conseq = self.parse_implication()?;
322            return Ok(ProofExpr::Implies(Box::new(cond), Box::new(conseq)));
323        }
324        let left = self.parse_disjunction()?;
325        if matches!(self.peek(), Some(Tok::Arrow)) || self.peek_kw().as_deref() == Some("implies") {
326            self.advance();
327            let right = self.parse_implication()?;
328            return Ok(ProofExpr::Implies(Box::new(left), Box::new(right)));
329        }
330        Ok(left)
331    }
332
333    // disjunction := conjunction (('or'|'∨') conjunction)*
334    fn parse_disjunction(&mut self) -> Result<ProofExpr, FormulaError> {
335        let mut left = self.parse_conjunction()?;
336        loop {
337            if matches!(self.peek(), Some(Tok::Or)) || self.peek_kw().as_deref() == Some("or") {
338                self.advance();
339                let right = self.parse_conjunction()?;
340                left = ProofExpr::Or(Box::new(left), Box::new(right));
341            } else {
342                break;
343            }
344        }
345        Ok(left)
346    }
347
348    // conjunction := negation (('and'|'∧') negation)*
349    fn parse_conjunction(&mut self) -> Result<ProofExpr, FormulaError> {
350        let mut left = self.parse_negation()?;
351        loop {
352            if matches!(self.peek(), Some(Tok::And)) || self.peek_kw().as_deref() == Some("and") {
353                self.advance();
354                let right = self.parse_negation()?;
355                left = ProofExpr::And(Box::new(left), Box::new(right));
356            } else {
357                break;
358            }
359        }
360        Ok(left)
361    }
362
363    // negation := ('not'|'¬') negation | atom
364    fn parse_negation(&mut self) -> Result<ProofExpr, FormulaError> {
365        if matches!(self.peek(), Some(Tok::Not)) || self.peek_kw().as_deref() == Some("not") {
366            self.advance();
367            let inner = self.parse_negation()?;
368            return Ok(ProofExpr::Not(Box::new(inner)));
369        }
370        self.parse_atom()
371    }
372
373    // atom := '(' formula ')'
374    //       | 'true' | 'false'
375    //       | ident '(' term (',' term)* ')'        (predicate / relation)
376    //       | term '=' term                          (identity)
377    //       | ident                                  (0-ary propositional atom)
378    fn parse_atom(&mut self) -> Result<ProofExpr, FormulaError> {
379        // A quantifier as an operand (`… then ∃x. …`, `… and ∀y. …`) — delegate to the
380        // full-formula entry, which consumes the prefix and grabs its body rightward.
381        if self.peek_is_quantifier() {
382            return self.parse_formula();
383        }
384
385        if matches!(self.peek(), Some(Tok::LParen)) {
386            self.advance();
387            let inner = self.parse_formula()?;
388            if !matches!(self.advance(), Some(Tok::RParen)) {
389                return Err(FormulaError::new("expected ')'"));
390            }
391            return Ok(inner);
392        }
393
394        let name = match self.advance() {
395            Some(Tok::Ident(s)) => s.clone(),
396            other => {
397                return Err(FormulaError::new(format!(
398                    "expected an atom, found {other:?}"
399                )))
400            }
401        };
402
403        match name.to_lowercase().as_str() {
404            "true" => return Ok(ProofExpr::Atom("True".to_string())),
405            "false" => return Ok(ProofExpr::Atom("False".to_string())),
406            _ => {}
407        }
408
409        // Relation application: `Name(t1, t2, …)`.
410        if matches!(self.peek(), Some(Tok::LParen)) {
411            self.advance();
412            let mut args = Vec::new();
413            if !matches!(self.peek(), Some(Tok::RParen)) {
414                loop {
415                    args.push(self.parse_term()?);
416                    if matches!(self.peek(), Some(Tok::Comma)) {
417                        self.advance();
418                        continue;
419                    }
420                    break;
421                }
422            }
423            if !matches!(self.advance(), Some(Tok::RParen)) {
424                return Err(FormulaError::new(
425                    "expected ')' to close a relation's arguments",
426                ));
427            }
428            // An equality between ARITHMETIC terms is a ring identity (the oracle decides it), like the
429            // `a = b` infix form — not an uninterpreted `Eq` relation. Gated on an arithmetic side, so a
430            // general `Eq(x, y)` predicate in a development is untouched.
431            if name.eq_ignore_ascii_case("eq")
432                && args.len() == 2
433                && (is_arith_term(&args[0]) || is_arith_term(&args[1]))
434            {
435                let mut it = args.into_iter();
436                return Ok(ProofExpr::Identity(it.next().unwrap(), it.next().unwrap()));
437            }
438            return Ok(ProofExpr::Predicate {
439                name,
440                args,
441                world: None,
442            });
443        }
444
445        // Identity: `a = b`.
446        if matches!(self.peek(), Some(Tok::Eq)) {
447            self.advance();
448            let rhs = self.parse_term()?;
449            return Ok(ProofExpr::Identity(ident_to_term(&name), rhs));
450        }
451
452        // A bare identifier is a 0-ary propositional atom.
453        Ok(ProofExpr::Atom(name))
454    }
455
456    fn parse_term(&mut self) -> Result<ProofTerm, FormulaError> {
457        let name = match self.advance() {
458            Some(Tok::Ident(s)) => s.clone(),
459            other => {
460                return Err(FormulaError::new(format!(
461                    "expected a term, found {other:?}"
462                )))
463            }
464        };
465        // Function application: `Name(t1, t2, …)` — a nested (possibly arithmetic) function term, so
466        // `Eq(Mul(a, b), Mul(b, a))` parses its `Mul(a, b)` arguments rather than stopping at the `(`.
467        if matches!(self.peek(), Some(Tok::LParen)) {
468            self.advance();
469            let mut args = Vec::new();
470            if !matches!(self.peek(), Some(Tok::RParen)) {
471                loop {
472                    args.push(self.parse_term()?);
473                    if matches!(self.peek(), Some(Tok::Comma)) {
474                        self.advance();
475                        continue;
476                    }
477                    break;
478                }
479            }
480            if !matches!(self.advance(), Some(Tok::RParen)) {
481                return Err(FormulaError::new(
482                    "expected ')' to close a function's arguments",
483                ));
484            }
485            return Ok(ProofTerm::Function(name, args));
486        }
487        Ok(ident_to_term(&name))
488    }
489}
490
491/// Is `t` an arithmetic function term (`Add`/`Mul`/… in either case)? Used to recognise an equality
492/// between ring expressions, which is a proof-layer `Identity` rather than an uninterpreted relation.
493fn is_arith_term(t: &ProofTerm) -> bool {
494    matches!(
495        t,
496        ProofTerm::Function(n, _)
497            if matches!(
498                n.as_str(),
499                "Add" | "Sub" | "Mul" | "Div" | "add" | "sub" | "mul" | "div" | "mod"
500            )
501    )
502}
503
504/// An uppercase- or digit-leading identifier is a CONSTANT; a lowercase-leading one is a
505/// VARIABLE — the standard FOL reading the verifier already uses.
506fn ident_to_term(s: &str) -> ProofTerm {
507    let leads_constant = s
508        .chars()
509        .next()
510        .map(|c| c.is_uppercase() || c.is_ascii_digit())
511        .unwrap_or(false);
512    if leads_constant {
513        ProofTerm::Constant(s.to_string())
514    } else {
515        ProofTerm::Variable(s.to_string())
516    }
517}