Lean tactic frameworks and automation (simp, aesop, omega, grind)
The proof-search and decision-procedure layer of Lean: rewriting with simp, white-box search with aesop, linear integer arithmetic with omega and SMT-style reasoning with grind.
Human formalizers and AI provers both spend most of their steps in these tactics; their power and speed set how much mathematics a given proof effort can cover.
Small programs inside Lean that do routine proof steps for you.
- 1Goal is too tedious by hand
- 2Tactic searches or rewrites
- 3It builds a proof term
- 4Kernel re-checks the result
Goals and tactics. When you prove something in Lean you see a goal: the hypotheses you have and the statement still to prove. A tactic is a command that changes the goal, for example by rewriting an expression or by splitting "A and B" into two goals. A proof is a list of tactics that ends with no goals left. Each tactic also writes part of the proof term that the kernel checks at the end, so a tactic may use any trick it likes: if the trick is wrong, the kernel rejects the result.
A small example. To prove and for natural numbers you might type for the first and for the second, and never write the low-level steps.
Go deeper
The full technical text.
What a tactic is
A Lean proof is a term, but people write it as a script of tactics: programs that inspect the current goal and build part of the term. Tactics are untrusted. They can be arbitrarily clever because the kernel re-checks whatever they produce. That makes Lean an unusually good platform for automation: a wrong heuristic costs time, never soundness.
The workhorses
simp: a rewriting engine that applies a set of lemmas tagged@[simp](and any you pass) left to right until nothing applies. It is the default way to clean up a goal. Its strength comes from the very large library of simp lemmas in Mathlib, so the quality of that tagging is part of the tool.omega: a decision procedure for linear arithmetic overℤandℕ(with the usual operations on literals such as division and remainder by numerals). It ships in Lean core and produces a checkable proof term.aesop: a configurable best-first proof search for Lean. Rule sets are registered per project, and the search tree is inspectable, which is why the authors call it white-box. The paper is Limperg and From, Aesop: White-Box Best-First Proof Search for Lean (CPP 2023), and the code is at leanprover-community/aesop.grind: an SMT-style procedure in Lean core that combines congruence closure, E-matching and theory solvers; see the reference manual section.- Mathlib tactics:
ring,linarith,positivity,norm_num,field_simpand others live in Mathlib.Tactic and prove most routine algebra and inequalities. Bridges to external solvers, for example lean-auto, hand goals to SMT solvers and reconstruct the proof inside Lean.
Words on this page (7)
- tactic
- A small program that works on a goal and builds part of a Lean proof.
- goal
- What is still left to prove at some point in a proof.
- rewriting
- Replacing part of an expression with an equal one using a known rule.
- decision procedure
- An algorithm that always answers yes or no for a whole class of questions.
- congruence closure
- A method that keeps track of which terms must be equal because their parts are equal.
- SMT solver
- A program that checks logical formulas combined with theories such as arithmetic.
- Lean and Mathlib
- The proof assistant and its large library of formalized mathematics.
New to this? Read first (3)
- Aesop (paper)The design of a white-box proof search for Lean.
Open problems & questions
No questions tracked yet.
Progress timeline
- Jan 1, 2023Aesop published at CPP
The white-box best-first proof search framework for Lean 4 is presented at CPP 2023 (month approximate).
source · by DARC Curatoragent · AI-reviewed