| /- | |
| Copyright (c) 2025 Amazon.com, Inc. or its affiliates. All Rights Reserved. | |
| Released under Apache 2.0 license as described in the file LICENSE. | |
| Authors: Leonardo de Moura | |
| -/ | |
| module | |
| prelude | |
| public import Lean.Meta.Sym.AlphaShareBuilder | |
| public import Lean.Meta.Sym.AlphaShareCommon | |
| public import Lean.Meta.Sym.ExprPtr | |
| public import Lean.Meta.Sym.SymM | |
| public import Lean.Meta.Sym.MaxFVar | |
| public import Lean.Meta.Sym.ReplaceS | |
| public import Lean.Meta.Sym.LooseBVarsS | |
| public import Lean.Meta.Sym.InstantiateS | |
| public import Lean.Meta.Sym.IsClass | |
| public import Lean.Meta.Sym.Intro | |
| public import Lean.Meta.Sym.InstantiateMVarsS | |
| public import Lean.Meta.Sym.ProofInstInfo | |
| public import Lean.Meta.Sym.AbstractS | |
| public import Lean.Meta.Sym.Pattern | |
| public import Lean.Meta.Sym.Apply | |
| public import Lean.Meta.Sym.InferType | |
| public import Lean.Meta.Sym.Simp | |
| public import Lean.Meta.Sym.Util | |
| public import Lean.Meta.Sym.Eta | |
| public import Lean.Meta.Sym.Grind | |
| /-! | |
| # Symbolic computation support. | |
| This module provides `SymM`, a monad for implementing symbolic computation (e.g., decision procedures and | |
| verification condition generators) using Lean. The monad addresses performance issues found in symbolic | |
| computation engines built on top of user-facing tactics (e.g., `apply` and `intros`). | |
| ## Overview | |
| The `SymM` monad provides an alternative to tactics built using the `MetaM` monad. Goals are still represented | |
| by metavariables, but with restrictions that enable more efficient implementations. For example, we cannot | |
| revert or clear local declarations. This simpler metavariable management reduces the complexity of key | |
| operations from O(n log n) to O(1). The definitional equality test is more syntactic and cheaper than | |
| the one available in `MetaM`. `SymM` also provides functions for efficiently discharging goals using `GrindM`. | |
| ## Design decisions | |
| ### No `revert` or `clear` | |
| In `SymM`, you cannot revert or clear local declarations, so local contexts grow monotonically. | |
| Each goal is represented by a `Grind.Goal` object which includes a metavariable. | |
| **Why this restriction?** In standard `MetaM`, validating a metavariable assignment `?m := e` requires | |
| traversing `e`, checking free variables occurring in `e`, and checking that every nested metavariable | |
| `?n` in `e` has a local context compatible with `?m`'s local context. This uses `LocalContext.isSubPrefixOf`, | |
| which traverses two `PersistentArray`s with O(log n) lookups per element, expensive when called frequently. | |
| **The key insight:** Since free variable indices increase monotonically and are never reused, a local | |
| context can be identified by its maximal free variable index. To check whether `lctx₁` is a sub-prefix | |
| of `lctx₂`, we only need to verify that `lctx₂` contains the maximal free variable declared in `lctx₁`. | |
| **Implementation:** We maintain a mapping `maxFVar` from expressions to free variables, where `maxFVar[e] = x` | |
| means `x` is the free variable with maximal index occurring in `e`. When assigning `?m := e`, we check | |
| whether `maxFVar[e]` is in `?m.lctx` — a single hash lookup, O(1). | |
| **Maintaining `maxFVar`:** The mapping is automatically updated when we use `getMaxFVar?`. | |
| ### Structural matching and definitional equality | |
| **The problem:** The `isDefEq` predicate in `MetaM` is designed for elaboration and user-facing tactics. | |
| It supports reduction, type-class resolution, and many other features that can be expensive or have | |
| unpredictable running time. For symbolic computation, where pattern matching is called frequently on | |
| large ground terms, these features become performance bottlenecks. | |
| **The solution:** In `SymM`, pattern matching and definitional equality are restricted to a more syntactic, | |
| predictable subset. Key design choices: | |
| 1. **Reducible declarations are abbreviations.** Reducible declarations are eagerly expanded when indexing | |
| terms and when entering symbolic computation mode. During matching, we assume abbreviations have already | |
| been expanded. | |
| **Why `MetaM` `simp` cannot make this assumption**: The simplifier in `MetaM` is designed for interactive use, | |
| where users want to preserve their abstractions. Even reducible definitions may represent meaningful | |
| abstractions that users may not want unfolded. For example, when applying `simp` to `x ≥ y`, users | |
| typically do not want it transformed to `y ≤ x` just because `GE.ge` is a reducible abbreviation. | |
| 2. **Proofs are ignored.** We skip proof arguments during matching due to proof irrelevance. Proofs are | |
| "noisy": they are typically built using different automation or manually, so we can have radically | |
| different proof terms for the same trivial fact. | |
| 3. **Instances are ignored.** Lean's class hierarchy contains many diamonds. For example, `Add Nat` can be | |
| obtained directly from the `Nat` library or derived from the fact that `Nat` is a `Semiring`. Proof | |
| automation like `grind` attempts to canonicalize instances, but this is expensive. Instead, we treat | |
| instances as support terms and skip them during matching, and we check them later using the standard | |
| definitionally equality test in a mode where only reducible and instance declarations are unfolded. | |
| **The implicit assumption:** If two terms have the same instance type, they are definitionally equal. | |
| This holds in well-designed Lean code. For example, the `Add Nat` instance from the `Nat` library is | |
| definitionally equal to the one derived from `Semiring`, and this can be established by unfolding only | |
| reducible and instance declarations. Code that violates this assumption is considered misuse of Lean's | |
| instance system. | |
| 4. **Types must be indexed.** Unlike proofs and instances, types cannot be ignored, without indexing them, | |
| pattern matching produces too many candidates. Like other abbreviations, type abbreviations are expanded. | |
| Note that given `def Foo : Type := Bla`, the terms `Foo` and `Bla` are *not* considered structurally | |
| equal in the symbolic computation framework. | |
| ### Skipping type checks on assignment | |
| **The problem:** In `MetaM`, assigning `?m := v` requires checking that `typeof(?m)` is definitionally | |
| equal to `typeof(v)`. This is necessary when metavariable types contain unassigned universe or expression | |
| metavariables that must be constrained. For example, applying `Exists.intro.{?u} ?α ...` requires the | |
| type check to constrain `?u`. | |
| **The optimization:** When both types are ground (no unassigned metavariables), the check is redundant, | |
| well-typed terms have unique types up to definitional equality, and the types were already checked when | |
| the terms were constructed. `SymM` tracks whether types are ground and skips the check when possible. | |
| Checks are also skipped when nothing new can be learned from them assuming terms are all well-typed. | |
| For domain-specific constructors (e.g., `Exec.seq` in symbolic execution), types are typically ground, | |
| so the check is almost always skipped. | |
| ### `GrindM` state | |
| **The problem:** In symbolic computation, we often want to discharge many goals using proof automation such | |
| as `grind`. Many of these goals share very similar local contexts. If we invoke `grind` on each goal | |
| independently, we repeatedly reprocess the same hypotheses. | |
| **The solution:** In `SymM`, we carry the `GrindM` state across goals and use `Grind.Goal` instead of | |
| bare metavariables. We also provide APIs for incrementally processing local declarations, so hypotheses | |
| are only processed once. | |
| -/ |