logicaffeine_proof/tactic_script.rs
1//! A tiny proof-script language over the [`crate::tactic`] combinators — proofs as
2//! TEXT, the way a Lean/Coq proof reads. This is the self-contained seam toward a
3//! full English vernacular: it has no dependency on the surface language, so it
4//! compiles a script string straight into a composed [`Tactic`].
5//!
6//! Grammar (precedence low → high):
7//!
8//! ```text
9//! script := seq
10//! seq := chain (';' chain)* // run in order
11//! chain := atom ('<;>' atom)* // `t1 <;> t2`: t2 on the goals t1 spawned
12//! atom := '(' script ')'
13//! | 'first' '[' script ('|' script)* ']' // first that applies (backtracks)
14//! | 'try' atom // run if it applies, else no-op
15//! | 'repeat' atom // apply until it stops applying
16//! | 'all_goals' atom | 'any_goals' atom // every / at least one open goal
17//! | 'focus' atom // Lean's bullet: must close its goal
18//! | NAME ARG* // a primitive tactic
19//! term := factor (('+'|'-') factor)* // the argument of exact/use/have/refine
20//! factor := app ('*' app)*
21//! app := primary primary* // juxtaposition: application
22//! primary := NAME | '?' NAME? | '(' term (',' term)* ')'
23//! ```
24//!
25//! Primitive tactics: `intro a b`, `exact <term>`, `apply h`, `rfl`, `cases h with a b`,
26//! `rewrite h [at <k> | at <hyp> [<k>]]`, `exists <term>`, `assumption`, `simp only [h]`,
27//! `decide`, `omega`, `linarith`, `ring`, `crush`, `calc h1 h2 …`, `by_rule <Rule>`, `split`,
28//! `left`, `right`, `auto`, `induction n`, `by_contra h`, `have h from <term>`,
29//! `refine <term>`.
30//!
31//! `rewrite`'s `at` clause carries both aspects of positional rewriting: `at <k>` is Lean's
32//! `nth_rewrite` (the POSITION, in the goal) and `at <hyp>` is Lean's `rw … at h` (the
33//! LOCATION); `at <hyp> <k>` is both.
34
35use std::collections::HashMap;
36
37use crate::tactic::combinators as c;
38use crate::tactic::{PTerm, ProofState, Tactic};
39use crate::verify::{citation_order, LibraryResult, LibraryTheorem};
40use crate::ProofExpr;
41
42/// A script parse error, with a human-readable reason.
43#[derive(Debug, Clone, PartialEq)]
44pub struct ScriptError(pub String);
45
46impl std::fmt::Display for ScriptError {
47 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
48 write!(f, "tactic script error: {}", self.0)
49 }
50}
51
52#[derive(Debug, Clone, PartialEq)]
53enum Tok {
54 Word(String),
55 Semi,
56 ThenAll,
57 LParen,
58 RParen,
59 LBracket,
60 RBracket,
61 Bar,
62 /// An arithmetic infix operator, by the `ProofTerm` function it builds.
63 Op(&'static str),
64 /// The `?` that opens a `refine` hole.
65 Question,
66}
67
68fn lex(src: &str) -> Result<Vec<Tok>, ScriptError> {
69 let mut toks = Vec::new();
70 let bytes = src.as_bytes();
71 let mut i = 0;
72 while i < bytes.len() {
73 let ch = bytes[i] as char;
74 match ch {
75 c if c.is_whitespace() => i += 1,
76 // Sentence punctuation reads as a step separator, so prose flows: a proof
77 // can be written `Assume h. By cases on h, …` and parse the same as `;`.
78 ';' | '.' | ',' => {
79 toks.push(Tok::Semi);
80 i += 1;
81 }
82 '(' => {
83 toks.push(Tok::LParen);
84 i += 1;
85 }
86 ')' => {
87 toks.push(Tok::RParen);
88 i += 1;
89 }
90 '[' => {
91 toks.push(Tok::LBracket);
92 i += 1;
93 }
94 ']' => {
95 toks.push(Tok::RBracket);
96 i += 1;
97 }
98 '|' => {
99 toks.push(Tok::Bar);
100 i += 1;
101 }
102 '<' if src[i..].starts_with("<;>") => {
103 toks.push(Tok::ThenAll);
104 i += 3;
105 }
106 // Arithmetic, so a witness can be a compound term (`use (n + 1)`) rather than
107 // only a bare name.
108 '+' => {
109 toks.push(Tok::Op("add"));
110 i += 1;
111 }
112 '-' => {
113 toks.push(Tok::Op("sub"));
114 i += 1;
115 }
116 '*' => {
117 toks.push(Tok::Op("mul"));
118 i += 1;
119 }
120 '?' => {
121 toks.push(Tok::Question);
122 i += 1;
123 }
124 c if c.is_alphanumeric() || c == '_' => {
125 let start = i;
126 while i < bytes.len() {
127 let cc = bytes[i] as char;
128 if cc.is_alphanumeric() || cc == '_' {
129 i += 1;
130 } else {
131 break;
132 }
133 }
134 toks.push(Tok::Word(src[start..i].to_string()));
135 }
136 other => return Err(ScriptError(format!("unexpected character {other:?}"))),
137 }
138 }
139 Ok(toks)
140}
141
142/// A registry of USER-DEFINED tactics (M) — the metaprogramming seam. A user names a
143/// composite tactic (built from primitives and combinators) with [`TacticEnv::define`], and
144/// may then reference it BY NAME in any later script, including from within other
145/// user-defined tactics. This is "write your own tactic in the language", without Rust —
146/// the definitions are stored as source and re-expanded (depth-bounded, so a recursive
147/// definition is rejected rather than looping) wherever the name appears.
148#[derive(Clone, Default)]
149pub struct TacticEnv {
150 defs: std::collections::HashMap<String, String>,
151}
152
153impl TacticEnv {
154 pub fn new() -> Self {
155 Self::default()
156 }
157 /// Define a named tactic from a script source. Names are case-insensitive.
158 pub fn define(&mut self, name: &str, script: &str) {
159 self.defs
160 .insert(name.to_ascii_lowercase(), script.to_string());
161 }
162 fn get(&self, name: &str) -> Option<&String> {
163 self.defs.get(&name.to_ascii_lowercase())
164 }
165}
166
167/// Depth bound on user-tactic expansion — a recursive definition (`t := … t …`) is refused
168/// at this depth rather than looping forever.
169const MAX_TACTIC_DEPTH: usize = 128;
170
171struct Parser {
172 toks: Vec<Tok>,
173 pos: usize,
174 env: TacticEnv,
175 depth: usize,
176}
177
178impl Parser {
179 fn peek(&self) -> Option<&Tok> {
180 self.toks.get(self.pos)
181 }
182 fn bump(&mut self) -> Option<Tok> {
183 let t = self.toks.get(self.pos).cloned();
184 if t.is_some() {
185 self.pos += 1;
186 }
187 t
188 }
189 fn expect(&mut self, t: &Tok) -> Result<(), ScriptError> {
190 match self.bump() {
191 Some(got) if &got == t => Ok(()),
192 other => Err(ScriptError(format!("expected {t:?}, found {other:?}"))),
193 }
194 }
195
196 /// True if the next token ends a step: `;`/`.`/`,` (lexed to `Semi`) or the word
197 /// `then`. Lets prose read `Assume h, then by cases on h.`
198 fn at_separator(&self) -> bool {
199 matches!(self.peek(), Some(Tok::Semi))
200 || matches!(self.peek(), Some(Tok::Word(w)) if w.eq_ignore_ascii_case("then"))
201 }
202
203 /// Skip purely connective filler words (`by`, `the`, `on`, …) so a tactic can be
204 /// stated as `by cases on h` and mean `cases h`.
205 fn skip_filler(&mut self) {
206 while matches!(self.peek(), Some(Tok::Word(w)) if is_filler(w)) {
207 self.bump();
208 }
209 }
210
211 /// Read one IDENTIFIER, looking past connective filler — but never past the last word.
212 ///
213 /// `skip_filler` used to run unconditionally inside the argument reader, so thirteen
214 /// ordinary identifiers (`a`, `an`, `it`, `we`, `on`, `of`, `to`, `the`, `that`, `now`,
215 /// `with`, `by`, `and`) were swallowed before the tactic ever saw them: `exists A` and
216 /// `cases it` were unspellable, and the reported error blamed the tactic for having no
217 /// argument rather than the vocabulary for eating it. A filler word is filler only when
218 /// ANOTHER word still follows to be the argument; the last word standing is the
219 /// argument, whatever it is spelled.
220 fn ident(&mut self) -> Option<String> {
221 let mut i = self.pos;
222 while matches!(self.toks.get(i), Some(Tok::Word(w)) if is_filler(w)) {
223 if matches!(self.toks.get(i + 1), Some(Tok::Word(_))) {
224 i += 1;
225 } else {
226 break;
227 }
228 }
229 match self.toks.get(i) {
230 Some(Tok::Word(w)) => {
231 let w = w.clone();
232 self.pos = i + 1;
233 Some(w)
234 }
235 _ => None,
236 }
237 }
238
239 /// True if the next token could start ANOTHER name in a list (`intro hp hq`,
240 /// `cases h with hp hq`). A word that names a tactic ends the list instead, so a script
241 /// that omits a separator still reads the way it always did.
242 fn at_extra_name(&self) -> bool {
243 match self.peek() {
244 Some(Tok::Word(w)) => {
245 !self.at_separator() && canonical(w).is_none() && !is_combinator_word(w)
246 }
247 _ => false,
248 }
249 }
250
251 /// The rest of a name list, after its first name has been read.
252 fn extra_names(&mut self) -> Vec<String> {
253 let mut names = Vec::new();
254 while self.at_extra_name() {
255 match self.bump() {
256 Some(Tok::Word(w)) => names.push(w),
257 _ => unreachable!("at_extra_name saw a word"),
258 }
259 }
260 names
261 }
262
263 /// An optional `at k` clause naming ONE occurrence to rewrite (0-based). Consumed only
264 /// when both words are there and the second is a number, so `rewrite h` and a following
265 /// step are untouched.
266 fn occurrence_clause(&mut self) -> Option<usize> {
267 match self.where_clause() {
268 Some(RewriteWhere::Goal(k)) => Some(k),
269 _ => None,
270 }
271 }
272
273 /// An optional `at …` clause saying WHERE a rewrite lands.
274 ///
275 /// Positional rewriting has two aspects and Lean spells them separately — `nth_rewrite 2 [h]`
276 /// picks the POSITION, `rw [h] at hp` picks the LOCATION — so this one clause reads both:
277 ///
278 /// * `at 2` — the goal, at occurrence 2. A number is never a hypothesis name in practice.
279 /// * `at hp` — the hypothesis `hp`, at its first occurrence.
280 /// * `at hp 2` — the hypothesis `hp`, at occurrence 2.
281 ///
282 /// `at` is not a filler word and `rewrite` takes no second name of its own, so the position
283 /// is unambiguous; anything else after the equation is left for the next step.
284 fn where_clause(&mut self) -> Option<RewriteWhere> {
285 if !matches!(self.peek(), Some(Tok::Word(w)) if w.eq_ignore_ascii_case("at")) {
286 return None;
287 }
288 let Some(Tok::Word(first)) = self.toks.get(self.pos + 1).cloned() else {
289 return None;
290 };
291 if let Ok(index) = first.parse::<usize>() {
292 self.pos += 2;
293 return Some(RewriteWhere::Goal(index));
294 }
295 // `at <name>` — a hypothesis, with an optional occurrence after it.
296 let index = match self.toks.get(self.pos + 2) {
297 Some(Tok::Word(w)) => w.parse::<usize>().ok(),
298 _ => None,
299 };
300 self.pos += if index.is_some() { 3 } else { 2 };
301 Some(RewriteWhere::Hyp(first, index.unwrap_or(0)))
302 }
303
304 /// An optional `with a b …` clause naming what an elimination binds.
305 fn with_clause(&mut self) -> Vec<String> {
306 if !matches!(self.peek(), Some(Tok::Word(w)) if w.eq_ignore_ascii_case("with")) {
307 return Vec::new();
308 }
309 self.bump();
310 let mut names = Vec::new();
311 if let Some(first) = self.ident() {
312 names.push(first);
313 names.extend(self.extra_names());
314 }
315 names
316 }
317
318 /// `term := factor (('+'|'-') factor)*` — the argument of `exact`/`use`/`have`/`refine`.
319 fn parse_term(&mut self) -> Result<PTerm, ScriptError> {
320 let mut lhs = self.parse_factor()?;
321 while let Some(Tok::Op(op)) = self.peek() {
322 if *op == "mul" {
323 break;
324 }
325 let op = *op;
326 self.bump();
327 let rhs = self.parse_factor()?;
328 lhs = PTerm::Op(op, Box::new(lhs), Box::new(rhs));
329 }
330 Ok(lhs)
331 }
332
333 /// `factor := application ('*' application)*`
334 fn parse_factor(&mut self) -> Result<PTerm, ScriptError> {
335 let mut lhs = self.parse_application()?;
336 while matches!(self.peek(), Some(Tok::Op("mul"))) {
337 self.bump();
338 let rhs = self.parse_application()?;
339 lhs = PTerm::Op("mul", Box::new(lhs), Box::new(rhs));
340 }
341 Ok(lhs)
342 }
343
344 /// `application := primary primary*` — juxtaposition, as in Lean.
345 fn parse_application(&mut self) -> Result<PTerm, ScriptError> {
346 let head = self.parse_primary()?;
347 let mut args = Vec::new();
348 while self.at_primary() {
349 args.push(self.parse_primary()?);
350 }
351 Ok(if args.is_empty() {
352 head
353 } else {
354 PTerm::App(Box::new(head), args)
355 })
356 }
357
358 fn at_primary(&self) -> bool {
359 match self.peek() {
360 Some(Tok::LParen) | Some(Tok::Question) => true,
361 Some(Tok::Word(_)) => !self.at_separator(),
362 _ => false,
363 }
364 }
365
366 /// `primary := NAME | '?' NAME? | '(' term (',' term)* ')'`
367 fn parse_primary(&mut self) -> Result<PTerm, ScriptError> {
368 match self.peek() {
369 Some(Tok::Question) => {
370 self.bump();
371 // `?_` and `?h` name the same thing — a goal the block leaves open.
372 if matches!(self.peek(), Some(Tok::Word(_))) {
373 self.bump();
374 }
375 Ok(PTerm::Hole)
376 }
377 Some(Tok::LParen) => {
378 self.bump();
379 let mut items = vec![self.parse_term()?];
380 // `,` lexes as a step separator everywhere else; INSIDE a term it is the
381 // anonymous constructor's comma.
382 while matches!(self.peek(), Some(Tok::Semi)) {
383 self.bump();
384 if matches!(self.peek(), Some(Tok::RParen)) {
385 break;
386 }
387 items.push(self.parse_term()?);
388 }
389 self.expect(&Tok::RParen)?;
390 Ok(if items.len() == 1 {
391 items.into_iter().next().expect("one item")
392 } else {
393 PTerm::Tuple(items)
394 })
395 }
396 Some(Tok::Word(_)) => self
397 .ident()
398 .map(PTerm::Ident)
399 .ok_or_else(|| ScriptError("expected a term".to_string())),
400 other => Err(ScriptError(format!("expected a term, found {other:?}"))),
401 }
402 }
403
404 /// `script := chain (sep+ chain)*` — a *run* of separators (`.`/`,`/`;`/`then`,
405 /// e.g. the `, then` in `Assume h, then …`) counts as one.
406 fn parse_seq(&mut self) -> Result<Tactic, ScriptError> {
407 let mut steps = vec![self.parse_chain()?];
408 loop {
409 let mut consumed = false;
410 while self.at_separator() {
411 self.bump();
412 consumed = true;
413 }
414 if !consumed {
415 break;
416 }
417 // Allow a trailing separator (a closing `.`) before `)`/`]`/`|`/EOF.
418 if matches!(
419 self.peek(),
420 None | Some(Tok::RParen) | Some(Tok::RBracket) | Some(Tok::Bar)
421 ) {
422 break;
423 }
424 steps.push(self.parse_chain()?);
425 }
426 Ok(if steps.len() == 1 {
427 steps.into_iter().next().unwrap()
428 } else {
429 c::seq(steps)
430 })
431 }
432
433 /// `chain := atom ('<;>' atom)*` — left-associative `then_all`.
434 fn parse_chain(&mut self) -> Result<Tactic, ScriptError> {
435 let mut acc = self.parse_atom()?;
436 while matches!(self.peek(), Some(Tok::ThenAll)) {
437 self.bump();
438 let rhs = self.parse_atom()?;
439 acc = c::then_all(acc, rhs);
440 }
441 Ok(acc)
442 }
443
444 fn parse_atom(&mut self) -> Result<Tactic, ScriptError> {
445 self.skip_filler();
446 match self.peek() {
447 Some(Tok::LParen) => {
448 self.bump();
449 let inner = self.parse_seq()?;
450 self.expect(&Tok::RParen)?;
451 Ok(inner)
452 }
453 Some(Tok::Word(w)) if w == "first" => {
454 self.bump();
455 self.expect(&Tok::LBracket)?;
456 let mut alts = vec![self.parse_seq()?];
457 while matches!(self.peek(), Some(Tok::Bar)) {
458 self.bump();
459 alts.push(self.parse_seq()?);
460 }
461 self.expect(&Tok::RBracket)?;
462 Ok(c::first(alts))
463 }
464 Some(Tok::Word(w)) if w == "try" => {
465 self.bump();
466 Ok(c::try_(self.parse_atom()?))
467 }
468 Some(Tok::Word(w)) if w == "repeat" => {
469 self.bump();
470 Ok(c::repeat(self.parse_atom()?))
471 }
472 // `all_goals <tactic>` — a tactic-TAKING combinator, so it parses like `try`/`repeat`
473 // rather than through `parse_primitive`. `combinators::all_goals` has existed and
474 // certified all along; it simply had no spelling.
475 Some(Tok::Word(w)) if w == "all_goals" || w == "everywhere" => {
476 self.bump();
477 Ok(c::all_goals(self.parse_atom()?))
478 }
479 Some(Tok::Word(w)) if w == "any_goals" || w == "somewhere" => {
480 self.bump();
481 Ok(c::any_goals(self.parse_atom()?))
482 }
483 // Lean's bullet. A focused block must CLOSE the goal it opened, which is the
484 // whole capability: without it the blocks of a flat script silently misalign.
485 Some(Tok::Word(w)) if w == "focus" || w == "next" || w == "bullet" => {
486 self.bump();
487 Ok(c::focus(self.parse_atom()?))
488 }
489 Some(Tok::Word(_)) => self.parse_primitive(),
490 other => Err(ScriptError(format!("expected a tactic, found {other:?}"))),
491 }
492 }
493
494 fn parse_primitive(&mut self) -> Result<Tactic, ScriptError> {
495 let raw = match self.bump() {
496 Some(Tok::Word(w)) => w,
497 other => {
498 return Err(ScriptError(format!(
499 "expected a tactic name, found {other:?}"
500 )))
501 }
502 };
503 // A USER-DEFINED tactic (M) takes PRECEDENCE — an explicit `define` is authoritative,
504 // so a user tactic may even shadow a built-in alias (`both`, `split`, …). Expand its
505 // stored source in place, one level deeper (recursion is depth-bounded).
506 if let Some(src) = self.env.get(&raw).cloned() {
507 if self.depth >= MAX_TACTIC_DEPTH {
508 return Err(ScriptError(format!(
509 "user tactic `{raw}` expands too deeply (recursive definition?)"
510 )));
511 }
512 return parse_with_env(&src, &self.env, self.depth + 1);
513 }
514 let name = canonical(&raw).ok_or_else(|| ScriptError(format!("unknown tactic `{raw}`")))?;
515 // Filler may sit between the verb and its object: `cases on h`, `rewrite with eq`.
516 macro_rules! arg {
517 () => {
518 self.ident()
519 .ok_or_else(|| ScriptError(format!("tactic `{name}` expects an argument")))?
520 };
521 }
522 match name {
523 // Lean's `intro a b c` introduces three binders in ONE step; the one-argument
524 // atom read `b` as the next tactic name and killed the whole script at parse
525 // time, discarding the proof before any step ran.
526 "intro" => {
527 let first = arg!();
528 let rest = self.extra_names();
529 Ok(if rest.is_empty() {
530 c::intro(&first)
531 } else {
532 c::seq(
533 std::iter::once(first)
534 .chain(rest)
535 .map(|n| c::intro(&n))
536 .collect(),
537 )
538 })
539 }
540 "exact" => Ok(c::exact_term(self.parse_term()?)),
541 "apply" => Ok(c::apply(&arg!())),
542 "rfl" => Ok(c::rfl()),
543 "cases" => {
544 let target = arg!();
545 let names = self.with_clause();
546 Ok(if names.is_empty() {
547 c::cases(&target)
548 } else {
549 c::cases_with(&target, names)
550 })
551 }
552 "rewrite" => {
553 let hypothesis = arg!();
554 // `rewrite h at 2` is Lean's occurrence argument and `rewrite h at hp` is its
555 // `rw [h] at hp` — the POSITION and the LOCATION, the two aspects `conv`
556 // exists to express. See `Parser::where_clause`.
557 match self.where_clause() {
558 Some(RewriteWhere::Goal(k)) => Ok(c::rewrite_at(&hypothesis, k)),
559 Some(RewriteWhere::Hyp(target, k)) => {
560 Ok(c::rewrite_hyp_at(&hypothesis, &target, k))
561 }
562 None => Ok(c::rewrite(&hypothesis)),
563 }
564 }
565 "exists" => Ok(c::exists_term(self.parse_term()?)),
566 "assumption" => Ok(c::assumption()),
567 "simp" => {
568 // `simp only [h₁, h₂]` names its rule set exactly; a bare `simp` uses the
569 // whole scope. A list WITHOUT `only` is Lean's "these as well", and since
570 // our default set is already the whole scope, naming them adds nothing —
571 // but the names are still checked, so a typo is not silently ignored.
572 let only =
573 matches!(self.peek(), Some(Tok::Word(w)) if w.eq_ignore_ascii_case("only"));
574 if only {
575 self.bump();
576 }
577 let names = self.bracketed_names()?;
578 Ok(match (only, names) {
579 (_, None) => c::simp(),
580 (true, Some(names)) => c::simp_only(names),
581 (false, Some(names)) => c::simp_with(names),
582 })
583 }
584 // `calc h1 h2 …` — the chain, by the names of its steps. The relation may CHANGE
585 // along it (`=` then `≤`), which is what `calc` and Lean's `Trans` are for.
586 "calc" => {
587 let first = arg!();
588 let mut names = vec![first];
589 names.extend(self.extra_names());
590 Ok(c::calc(names))
591 }
592 // `by_rule R` — the goal is discharged by the NAMED inference rule, in one step.
593 // This is the script spelling of the language AST's `ProofStrategy::ByRule`,
594 // whose documented example (`Proof: ModusPonens.`) had no image in the proof
595 // layer at all.
596 "by_rule" | "byrule" => Ok(c::by_rule(&arg!())),
597 "decide" => Ok(c::decide()),
598 "omega" => Ok(c::omega()),
599 "linarith" => Ok(c::linarith()),
600 "ring" => Ok(c::ring()),
601 "crush" => Ok(c::crush()),
602 "split" => Ok(c::split()),
603 "left" => Ok(c::left()),
604 "right" => Ok(c::right()),
605 "auto" => Ok(c::auto()),
606 "by_contra" => Ok(c::by_contra(&arg!())),
607 "have" => {
608 let bound = arg!();
609 // `have h from e` / `have h by e` — the connective is optional.
610 if matches!(self.peek(), Some(Tok::Word(w)) if is_have_connective(w)) {
611 self.bump();
612 }
613 Ok(c::have(&bound, self.parse_term()?))
614 }
615 "refine" => {
616 let term = self.parse_term()?;
617 if term == PTerm::Hole {
618 return Err(ScriptError(
619 "refine with a bare hole leaves the goal exactly as it was".to_string(),
620 ));
621 }
622 Ok(c::refine(term))
623 }
624 // `induction n` NAMES its target, the way Lean's does. Argumentless, it inducts
625 // on whatever binder happens to be outermost — which against `∀ m n, Q m n`
626 // proves a DIFFERENT theorem, certified, with nothing downstream able to tell.
627 "induction" => Ok(match self.at_extra_name().then(|| self.ident()).flatten() {
628 Some(variable) => c::induction_on(&variable),
629 None => c::induction(),
630 }),
631 _ => Err(ScriptError(format!("unknown tactic `{name}`"))),
632 }
633 }
634
635 /// An optional `[a, b, c]` name list.
636 fn bracketed_names(&mut self) -> Result<Option<Vec<String>>, ScriptError> {
637 if !matches!(self.peek(), Some(Tok::LBracket)) {
638 return Ok(None);
639 }
640 self.bump();
641 let mut names = Vec::new();
642 loop {
643 while matches!(self.peek(), Some(Tok::Semi)) {
644 self.bump();
645 }
646 if matches!(self.peek(), Some(Tok::RBracket)) {
647 break;
648 }
649 match self.bump() {
650 Some(Tok::Word(w)) => names.push(w),
651 other => {
652 return Err(ScriptError(format!(
653 "expected a lemma name, found {other:?}"
654 )))
655 }
656 }
657 }
658 self.expect(&Tok::RBracket)?;
659 Ok(Some(names))
660 }
661}
662
663/// Words that may stand between a `have`'s name and its proof.
664fn is_have_connective(w: &str) -> bool {
665 matches!(
666 w.to_ascii_lowercase().as_str(),
667 "from" | "by" | "using" | "via" | "proved"
668 )
669}
670
671/// Words that introduce a tactic-TAKING combinator rather than naming a binder.
672fn is_combinator_word(w: &str) -> bool {
673 matches!(
674 w,
675 "first"
676 | "try"
677 | "repeat"
678 | "all_goals"
679 | "everywhere"
680 | "any_goals"
681 | "somewhere"
682 | "focus"
683 | "next"
684 | "bullet"
685 )
686}
687
688/// Connective filler words that carry no tactic meaning — skipped so a step can be
689/// phrased as prose (`by cases on h`, `then by assumption`).
690fn is_filler(w: &str) -> bool {
691 matches!(
692 w.to_ascii_lowercase().as_str(),
693 "by" | "the"
694 | "on"
695 | "that"
696 | "now"
697 | "with"
698 | "we"
699 | "it"
700 | "a"
701 | "an"
702 | "of"
703 | "to"
704 | "and"
705 )
706}
707
708/// Where a `rewrite` lands — see [`Parser::where_clause`].
709enum RewriteWhere {
710 /// The goal, at this occurrence.
711 Goal(usize),
712 /// This hypothesis, at this occurrence.
713 Hyp(String, usize),
714}
715
716/// Map an English-esque verb to its canonical tactic name. `Suppose`/`assume`/`let`
717/// all mean `intro`; `automatically`/`trivially` mean `auto`; and so on — the
718/// vocabulary that lets a proof read like prose. Case-insensitive. Public so an editor
719/// highlights exactly the words the engine accepts.
720pub fn canonical(word: &str) -> Option<&'static str> {
721 match word.to_ascii_lowercase().as_str() {
722 "intro" | "assume" | "suppose" | "let" | "introduce" | "given" | "fix" => Some("intro"),
723 "exact" | "from" | "because" => Some("exact"),
724 // `apply` reaches `ProofState::apply_named`; the capability is modus ponens against a
725 // named rule and has always certified — only the spelling was missing.
726 "apply" | "via" => Some("apply"),
727 // `rfl` names the reflexivity closer that previously only `simp` could reach.
728 "rfl" | "reflexivity" => Some("rfl"),
729 "cases" | "destruct" | "consider" | "casework" => Some("cases"),
730 "rewrite" | "rw" | "substitute" | "subst" => Some("rewrite"),
731 "exists" | "use" | "witness" | "choose" | "provide" => Some("exists"),
732 "assumption" | "done" | "trivial" | "established" | "hypothesis" => Some("assumption"),
733 "simp" | "simplify" | "normalize" | "simplification" => Some("simp"),
734 "decide" | "compute" | "evaluate" | "calculate" => Some("decide"),
735 // `linarith` is NO LONGER an alias for `omega`. `omega` tightens `a < b` to `a + 1 ≤ b`,
736 // which is sound over ℤ and unsound over an ordered field — and `ProofExpr` is untyped, so
737 // nothing records the carrier. They are different tactics and now have different names.
738 "omega" | "arithmetic" | "integers" => Some("omega"),
739 "linarith" | "rationals" => Some("linarith"),
740 "crush" | "grind" | "blast" => Some("crush"),
741 "split" | "constructor" | "both" | "conjunction" => Some("split"),
742 "left" => Some("left"),
743 "right" => Some("right"),
744 "auto" | "tauto" | "automatically" | "automation" | "trivially" | "directly" => {
745 Some("auto")
746 }
747 "induction" | "induct" => Some("induction"),
748 // `by_contra h` is a STEP that assumes ¬G and leaves ⊥, so the twenty steps of a
749 // classical proof can be written; the classical reductio was reachable only as one
750 // opaque call inside `auto`'s search before.
751 "by_contra" | "bycontra" | "contra" | "contradiction" => Some("by_contra"),
752 // `ring` was reachable only from the literate kernel surface; the same
753 // commutative-ring oracle now has a name on this one.
754 "ring" | "polynomial" => Some("ring"),
755 // `calc` — a chain whose relation may change along it. Named steps, like
756 // `simp only [h]` names its rule set. ONE spelling deliberately: a canonical word
757 // stops an argument list (`at_extra_name`), so every alias added here is an ordinary
758 // identifier taken out of a user's hands — and `chain`/`compose` are ordinary words.
759 "calc" => Some("calc"),
760 // `by_rule R` — one step, by the name of the rule that takes it.
761 "by_rule" | "byrule" => Some("by_rule"),
762 "have" | "note" | "observe" => Some("have"),
763 "refine" | "partially" => Some("refine"),
764 _ => None,
765 }
766}
767
768/// Compile a proof-script string into a composed [`Tactic`] (no user-defined tactics).
769pub fn parse_script(src: &str) -> Result<Tactic, ScriptError> {
770 parse_with_env(src, &TacticEnv::new(), 0)
771}
772
773/// Compile a proof-script string with USER-DEFINED tactics resolved from `env` (M).
774pub fn parse_script_with_env(src: &str, env: &TacticEnv) -> Result<Tactic, ScriptError> {
775 parse_with_env(src, env, 0)
776}
777
778fn parse_with_env(src: &str, env: &TacticEnv, depth: usize) -> Result<Tactic, ScriptError> {
779 let toks = lex(src)?;
780 if toks.is_empty() {
781 return Err(ScriptError("empty script".to_string()));
782 }
783 let mut p = Parser {
784 toks,
785 pos: 0,
786 env: env.clone(),
787 depth,
788 };
789 let t = p.parse_seq()?;
790 if p.pos != p.toks.len() {
791 return Err(ScriptError(format!(
792 "trailing tokens after the script: {:?}",
793 &p.toks[p.pos..]
794 )));
795 }
796 Ok(t)
797}
798
799impl ProofState {
800 /// Parse and run a proof script against this state. The state is unchanged on a
801 /// parse error; a tactic that fails mid-run leaves whatever it had committed.
802 pub fn run_script(&mut self, src: &str) -> Result<&mut Self, ScriptError> {
803 let tactic = parse_script(src)?;
804 tactic(self).map_err(|e| ScriptError(format!("{e:?}")))?;
805 Ok(self)
806 }
807
808 /// Parse and run a proof script that may reference USER-DEFINED tactics from `env` (M).
809 pub fn run_script_with_env(
810 &mut self,
811 src: &str,
812 env: &TacticEnv,
813 ) -> Result<&mut Self, ScriptError> {
814 let tactic = parse_script_with_env(src, env)?;
815 tactic(self).map_err(|e| ScriptError(format!("{e:?}")))?;
816 Ok(self)
817 }
818}
819
820// =============================================================================
821// The certified scripted library (ROOT R6) — a Mathlib-analog seam: theorems
822// proved BY TACTIC SCRIPTS accumulate into a dependency-ordered library, each
823// proved lemma becoming a citable premise for later ones, every step kernel-checked.
824// =============================================================================
825
826/// One theorem of a scripted library: proved from its own `premises` plus the
827/// conclusions of the theorems it `cites`, by running `script` to a kernel-checked
828/// proof. The unit the [`prove_scripted_library`] driver discharges in citation order.
829pub struct ScriptedTheorem {
830 pub name: String,
831 pub premises: Vec<ProofExpr>,
832 pub goal: ProofExpr,
833 /// An English-esque proof script (see [`parse_script`]).
834 pub script: String,
835 /// Names of earlier theorems whose conclusions this proof relies on.
836 pub cites: Vec<String>,
837 /// `[simp]`-tagged: once proved, this conclusion joins the simp pool and
838 /// is in scope for every LATER theorem's `simp` even without a citation.
839 pub simp: bool,
840}
841
842/// Discharge a library of scripted theorems in citation order, on a shared `axioms`
843/// base. Each theorem is proved by its [`ScriptedTheorem::script`] from its premises,
844/// the axioms, and the conclusions of the theorems it cites (already proved); a proved
845/// conclusion becomes a citable lemma for later theorems — the scraped-Euclid-graph
846/// discipline, now driven by tactic scripts. Results come back in INPUT order.
847pub fn prove_scripted_library(
848 axioms: &[ProofExpr],
849 theorems: &[ScriptedTheorem],
850) -> Vec<LibraryResult> {
851 // `citation_order` works off names + cites; stub the rest.
852 let stubs: Vec<LibraryTheorem> = theorems
853 .iter()
854 .map(|t| LibraryTheorem {
855 name: t.name.clone(),
856 premises: Vec::new(),
857 goal: t.goal.clone(),
858 cites: t.cites.clone(),
859 })
860 .collect();
861
862 let mut proved: HashMap<String, ProofExpr> = HashMap::new();
863 let mut by_name: HashMap<String, LibraryResult> = HashMap::new();
864 // Conclusions of proved `[simp]`-tagged theorems, in proof order: in scope
865 // for every later theorem without an explicit citation.
866 let mut simp_pool: Vec<ProofExpr> = Vec::new();
867
868 for &i in &citation_order(&stubs) {
869 let t = &theorems[i];
870 let mut premises = axioms.to_vec();
871 premises.extend(t.premises.iter().cloned());
872 for cite in &t.cites {
873 if let Some(goal) = proved.get(cite) {
874 premises.push(goal.clone());
875 }
876 }
877 for lemma in &simp_pool {
878 if !premises.contains(lemma) {
879 premises.push(lemma.clone());
880 }
881 }
882
883 let mut st = ProofState::start(premises, t.goal.clone());
884 let (verified, error) = match st.run_script(&t.script).err() {
885 Some(e) => (false, Some(e.0)),
886 None => match st.qed() {
887 Ok(vp) => (vp.verified, vp.verification_error),
888 Err(e) => (false, Some(format!("{e:?}"))),
889 },
890 };
891 if verified {
892 proved.insert(t.name.clone(), t.goal.clone());
893 if t.simp {
894 simp_pool.push(t.goal.clone());
895 }
896 }
897 by_name.insert(
898 t.name.clone(),
899 LibraryResult {
900 name: t.name.clone(),
901 verified,
902 verification_error: error,
903 },
904 );
905 }
906
907 theorems
908 .iter()
909 .map(|t| {
910 by_name
911 .remove(&t.name)
912 .expect("every theorem produces a result")
913 })
914 .collect()
915}