Lean 语言参考

16.6. 电子匹配🔗

E-matching 是一个使用基本术语有效实例化量化定理陈述的过程。 它广泛应用于 SMT 求解器,grind 使用它来高效地实例化定理。 与 同余闭包 结合使用时特别有效,使 grind 能够自动发现等式和注释定理的非明显后果。

电子匹配根据定理索引向隐喻白板添加新事实。 当白板包含与索引匹配的术语时,电子匹配引擎会实例化相应的定理,并且生成的术语可以为进一步的 同余闭包约束传播 和特定于理论的求解器提供数据。 通过电子匹配添加到白板的每个事实都称为 instance。 注释电子匹配定理,从而将它们添加到索引中,对于 grind 有效利用库至关重要。

除了用户指定的定理之外,grind 使用自动生成的 Lean.Parser.Term.match : termPattern matching. `match e, ... with | p, ... => f | ...` matches each given term `e` against each pattern `p` of a match alternative. When all patterns of an alternative match, the `match` term evaluates to the value of the corresponding right-hand side `f` with the pattern variables bound to the respective matched values. If used as `match h : e, ... with | p, ... => f | ...`, `h : e = p` is available within `f`. When not constructing a proof, `match` does not automatically substitute variables matched on in dependent variables' types. Use `match (generalizing := true) ...` to enforce this. Syntax quotations can also be used in a pattern match. This matches a `Syntax` value against quotations, pattern variables, or `_`. Quoted identifiers only match identical identifiers - custom matching such as by the preresolved names only should be done explicitly. `Syntax.atom`s are ignored during matching by default except when part of a built-in literal. For users introducing new atoms, we recommend wrapping them in dedicated syntax kinds if they should participate in matching. For example, in ```lean syntax "c" ("foo" <|> "bar") ... ``` `foo` and `bar` are indistinguishable during matching, but in ```lean syntax foo := "foo" syntax "c" (foo <|> "bar") ... ``` they are not. match 表达式方程作为 E 匹配定理。 在幕后,精化器 生成实现模式匹配的辅助函数,以及指定其行为的方程定理。 将这些方程与 E 匹配结合使用,grind 能够减少模式匹配的这些实例。

16.6.1. 图案🔗

电子匹配索引是一个patterns表。 当一个术语与表中的模式之一匹配时,grind 尝试实例化并应用相应的定理,从而产生更多的事实和等式。 选择适当的模式是有效使用 grind 的重要组成部分:如果模式限制太多,则可能无法应用有用的定理;如果它们太笼统,性能可能会受到影响。

E-matching Patterns

考虑以下函数和定理:

def f (a : Nat) : Nat := a + 1 def g (a : Nat) : Nat := a - 1 @[grind =] theorem gf (x : Nat) : g (f x) = x := x:Natg (f x) = x All goals completed! 🐙

定理 gf 断言 g (f x) = x 对于所有自然数x。 属性 grind = 指示 grind 使用等式左侧 g (f x) 作为通过 E 匹配进行启发式实例化的模式。

此证明目标不包括 g (f x) 的实例,但 grind 仍然能够解决它:

example {a b} (h : f b = a) : g a = b := x:Nata✝:Natb✝:Nata:Natb:Nath:f b = ag a = b All goals completed! 🐙

尽管 g a 不是模式 g (f x) 的实例,但它会以方程 f b = a 为模。 通过在 g a 中用 f b 替换 a,我们获得术语 g (f b),它与模式 g (f x) 和赋值 x := b 相匹配。 因此,定理 gf 被实例化为 x := b,并且断言新的等式 g (f b) = bgrind 然后使用同余闭包导出隐含等式 g a = g (f b) 并完成证明。

Lean.Parser.Command.grind_patterngrind_pattern 命令可用于手动选择定理的 E 匹配模式。 启用选项 trace.grind.ematch.instance 会导致 grind 为其生成的每个定理实例打印一条跟踪消息,这在确定 E 匹配模式时很有帮助。

syntaxE-matching Pattern Selection
command ::= ...
    | The `grind_pattern` command can be used to manually select a pattern for theorem instantiation.
Enabling the option `trace.grind.ematch.instance` causes `grind` to print a trace message for each
theorem instance it generates, which can be helpful when determining patterns.

When multiple patterns are specified together, all of them must match in the current context before
`grind` attempts to instantiate the theorem. This is referred to as a *multi-pattern*.
This is useful for theorems such as transitivity rules, where multiple premises must be simultaneously
present for the rule to apply.

In the following example, `R` is a transitive binary relation over `Int`.
```
opaque R : Int → Int → Prop
axiom Rtrans {x y z : Int} : R x y → R y z → R x z
```
To use the fact that `R` is transitive, `grind` must already be able to satisfy both premises.
This is represented using a multi-pattern:
```
grind_pattern Rtrans => R x y, R y z

example {a b c d} : R a b → R b c → R c d → R a d := by
  grind
```
The multi-pattern `R x y`, `R y z` instructs `grind` to instantiate `Rtrans` only when both `R x y`
and `R y z` are available in the context. In the example, `grind` applies `Rtrans` to derive `R a c`
from `R a b` and `R b c`, and can then repeat the same reasoning to deduce `R a d` from `R a c` and
`R c d`.

You can add constraints to restrict theorem instantiation. For example:
```
grind_pattern extract_extract => (as.extract i j).extract k l where
  as =/= #[]
```
The constraint instructs `grind` to instantiate the theorem only if `as` is **not** definitionally equal
to `#[]`.

## Constraints

- `x =/= term`: The term bound to `x` (one of the theorem parameters) is **not** definitionally equal to `term`.
  The term may contain holes (i.e., `_`).

- `x =?= term`: The term bound to `x` is definitionally equal to `term`.
  The term may contain holes (i.e., `_`).

- `size x < n`: The term bound to `x` has size less than `n`. Implicit arguments
and binder types are ignored when computing the size.

- `depth x < n`: The term bound to `x` has depth less than `n`.

- `is_ground x`: The term bound to `x` does not contain local variables or meta-variables.

- `is_value x`: The term bound to `x` is a value. That is, it is a constructor fully applied to value arguments,
a literal (`Nat`, `Int`, `String`, etc.), or a lambda `fun x => t`.

- `is_strict_value x`: Similar to `is_value`, but without lambdas.

- `not_value x`: The term bound to `x` is a **not** value (see `is_value`).

- `not_strict_value x`: Similar to `not_value`, but without lambdas.

- `gen < n`: The theorem instance has generation less than `n`. Recall that each term is assigned a
generation, and terms produced by theorem instantiation have a generation that is one greater than
the maximal generation of all the terms used to instantiate the theorem. This constraint complements
the `gen` option available in `grind`.

- `max_insts < n`: A new instance is generated only if less than `n` instances have been generated so far.

- `guard e`: The instantiation is delayed until `grind` learns that `e` is `true` in this state.

- `check e`: Similar to `guard e`, but `grind` checks whether `e` is implied by its current state by
assuming `¬ e` and trying to deduce an inconsistency.

## Example

Consider the following example where `f` is a monotonic function
```
opaque f : Nat → Nat
axiom fMono : x ≤ y → f x ≤ f y
```
and you want to instruct `grind` to instantiate `fMono` for every pair of terms `f x` and `f y` when
`x ≤ y` and `x` is **not** definitionally equal to `y`. You can use
```
grind_pattern fMono => f x, f y where
  guard x ≤ y
  x =/= y
```
Then, in the following example, only three instances are generated.
```
/--
trace: [grind.ematch.instance] fMono: a ≤ f a → f a ≤ f (f a)
[grind.ematch.instance] fMono: f a ≤ f (f a) → f (f a) ≤ f (f (f a))
[grind.ematch.instance] fMono: a ≤ f (f a) → f a ≤ f (f (f a))
-/
#guard_msgs in
example : f b = f c → a ≤ f a → f (f a) ≤ f (f (f a)) := by
  set_option trace.grind.ematch.instance true in
  grind
```
`attrKind` matches `("scoped" <|> "local")?`, used before an attribute like `@[local simp]`. grind_pattern ident => term,*

将定理与一个或多个模式相关联。 当单个 Lean.Parser.Command.grind_patterngrind_pattern 命令中提供多个模式时,所有模式都必须与 grind 尝试实例化定理之前的项匹配。

command ::= ...
    | The `grind_pattern` command can be used to manually select a pattern for theorem instantiation.
Enabling the option `trace.grind.ematch.instance` causes `grind` to print a trace message for each
theorem instance it generates, which can be helpful when determining patterns.

When multiple patterns are specified together, all of them must match in the current context before
`grind` attempts to instantiate the theorem. This is referred to as a *multi-pattern*.
This is useful for theorems such as transitivity rules, where multiple premises must be simultaneously
present for the rule to apply.

In the following example, `R` is a transitive binary relation over `Int`.
```
opaque R : Int → Int → Prop
axiom Rtrans {x y z : Int} : R x y → R y z → R x z
```
To use the fact that `R` is transitive, `grind` must already be able to satisfy both premises.
This is represented using a multi-pattern:
```
grind_pattern Rtrans => R x y, R y z

example {a b c d} : R a b → R b c → R c d → R a d := by
  grind
```
The multi-pattern `R x y`, `R y z` instructs `grind` to instantiate `Rtrans` only when both `R x y`
and `R y z` are available in the context. In the example, `grind` applies `Rtrans` to derive `R a c`
from `R a b` and `R b c`, and can then repeat the same reasoning to deduce `R a d` from `R a c` and
`R c d`.

You can add constraints to restrict theorem instantiation. For example:
```
grind_pattern extract_extract => (as.extract i j).extract k l where
  as =/= #[]
```
The constraint instructs `grind` to instantiate the theorem only if `as` is **not** definitionally equal
to `#[]`.

## Constraints

- `x =/= term`: The term bound to `x` (one of the theorem parameters) is **not** definitionally equal to `term`.
  The term may contain holes (i.e., `_`).

- `x =?= term`: The term bound to `x` is definitionally equal to `term`.
  The term may contain holes (i.e., `_`).

- `size x < n`: The term bound to `x` has size less than `n`. Implicit arguments
and binder types are ignored when computing the size.

- `depth x < n`: The term bound to `x` has depth less than `n`.

- `is_ground x`: The term bound to `x` does not contain local variables or meta-variables.

- `is_value x`: The term bound to `x` is a value. That is, it is a constructor fully applied to value arguments,
a literal (`Nat`, `Int`, `String`, etc.), or a lambda `fun x => t`.

- `is_strict_value x`: Similar to `is_value`, but without lambdas.

- `not_value x`: The term bound to `x` is a **not** value (see `is_value`).

- `not_strict_value x`: Similar to `not_value`, but without lambdas.

- `gen < n`: The theorem instance has generation less than `n`. Recall that each term is assigned a
generation, and terms produced by theorem instantiation have a generation that is one greater than
the maximal generation of all the terms used to instantiate the theorem. This constraint complements
the `gen` option available in `grind`.

- `max_insts < n`: A new instance is generated only if less than `n` instances have been generated so far.

- `guard e`: The instantiation is delayed until `grind` learns that `e` is `true` in this state.

- `check e`: Similar to `guard e`, but `grind` checks whether `e` is implied by its current state by
assuming `¬ e` and trying to deduce an inconsistency.

## Example

Consider the following example where `f` is a monotonic function
```
opaque f : Nat → Nat
axiom fMono : x ≤ y → f x ≤ f y
```
and you want to instruct `grind` to instantiate `fMono` for every pair of terms `f x` and `f y` when
`x ≤ y` and `x` is **not** definitionally equal to `y`. You can use
```
grind_pattern fMono => f x, f y where
  guard x ≤ y
  x =/= y
```
Then, in the following example, only three instances are generated.
```
/--
trace: [grind.ematch.instance] fMono: a ≤ f a → f a ≤ f (f a)
[grind.ematch.instance] fMono: f a ≤ f (f a) → f (f a) ≤ f (f (f a))
[grind.ematch.instance] fMono: a ≤ f (f a) → f a ≤ f (f (f a))
-/
#guard_msgs in
example : f b = f c → a ≤ f a → f (f a) ≤ f (f (f a)) := by
  set_option trace.grind.ematch.instance true in
  grind
```
`attrKind` matches `("scoped" <|> "local")?`, used before an attribute like `@[local simp]`. grind_pattern ident => term,* where (isValue
       | isStrictValue
       | notValue
       | notStrictValue
       | isGround
       | sizeLt
       | depthLt
       | genLt
       | maxInsts
       | guard
       | check
       | notDefEq
       | defEq)

可选的 Lean.Parser.Command.grind_patternwhere 子句指定在 grind 尝试实例化定理之前必须满足的约束。 每个约束的形式为 variable =/= value,防止在为模式变量分配指定值时实例化。 这对于避免有问题的术语的无限制或过度实例化很有用。

Selecting Patterns

grind = 属性使用等式的左侧作为 gf 的 E 匹配模式:

def f (a : Nat) : Nat := a + 1 def g (a : Nat) : Nat := a - 1 @[grind =] theorem gf (x : Nat) : g (f x) = x := x:Natg (f x) = x All goals completed! 🐙

例如,模式 g (f x) 在以下情况下限制过多: 定理 gf 不会被实例化,因为目标甚至没有 包含功能符号 g

在此示例中,grind 失败,因为模式限制太多:目标不包含函数符号 g

example (h₁ : f b = a) (h₂ : f c = a) : b = c := b:Nata:Natc:Nath₁:f b = ah₂:f c = ab = c `grind` failed b a c:Nath₁:f b = ah₂:f c = ah:¬b = cFalse
[grind] Goal diagnostics
  • [facts] Asserted facts
    • [prop] f b = a
    • [prop] f c = a
    • [prop] ¬b = c
  • [eqc] False propositions
    • [prop] b = c
  • [eqc] Equivalence classes
    • [eqc] {a, f b, f c}
All goals completed! 🐙
`grind` failed
b a c:Nath₁:f b = ah₂:f c = ah:¬b = cFalse
[grind] Goal diagnostics
  • [facts] Asserted facts
    • [prop] f b = a
    • [prop] f c = a
    • [prop] ¬b = c
  • [eqc] False propositions
    • [prop] b = c
  • [eqc] Equivalence classes
    • [eqc] {a, f b, f c}

仅使用 f x 作为模式允许 grind 自动解决目标:

grind_pattern gf => f x example {a b c} (h₁ : f b = a) (h₂ : f c = a) : b = c := a:Natb:Natc:Nath₁:f b = ah₂:f c = ab = c All goals completed! 🐙

启用 trace.grind.ematch.instance 可以查看通过 E 匹配找到的等式:

example (h₁ : f b = a) (h₂ : f c = a) : b = c := b:Nata:Natc:Nath₁:f b = ah₂:f c = ab = c set_option trace.grind.ematch.instance true in [grind.ematch.instance] gf: g (f c) = c[grind.ematch.instance] gf: g (f b) = bAll goals completed! 🐙
[grind.ematch.instance] gf: g (f c) = c[grind.ematch.instance] gf: g (f b) = b

E-匹配后,证明成功,因为同余闭包使 g (f c)g (f b) 相等,因为 f bf c 都等于 a。 因此,bc 必须属于同一等价类。

当同时指定多个模式时,在 grind 尝试实例化定理之前,所有模式都必须在当前上下文中匹配。 这称为 multi-pattern。 这对于诸如传递性规则之类的引理很有用,其中必须同时存在多个前提才能应用规则。 通过使用 Lean.Parser.Command.grind_patterngrind_pattern@[grind _=_] 属性的多次调用,单个定理可以与多个单独的模式相关联。 如果这些单独模式中的任何一个匹配,则该定理将被实例化。

Multi-Patterns

RInt 上的传递二元关系:

opaque R : Int Int Prop axiom Rtrans {x y z : Int} : R x y R y z R x z

要利用 R 具有传递性的事实,grind 必须已经能够满足两个前提。 这是使用 多模式 表示的:

grind_pattern Rtrans => R x y, R y z example {a b c d} : R a b R b c R c d R a d := a:Intb:Intc:Intd:IntR a b R b c R c d R a d All goals completed! 🐙

仅当 R x yR y z 在上下文中可用时,多模式 R x y, R y z 才指示 grind 实例化 Rtrans。 在该示例中,grind 应用 RtransR a bR b c 导出 R a c,然后可以重复相同的推理从 R a cR c d 导出 R a d

Pattern Constraints

某些定理组合可能会导致无限实例化,其中 E 匹配会重复生成越来越长的项。 考虑有关 List.flatMapList.reverse 的定理。 如果 List.flatMap_defList.flatMap_reverseList.reverse_flatMap 都用 @[grind =] 进行注释,则一旦实例化 List.flatMap_reverse,就会发生以下实例化链,从而使用 List.reverse 创建逐渐更长的函数组合。 这可以使用 #grind_lint 命令观察到:

attribute [local grind =] List.reverse_flatMap

set_option trace.grind.ematch.instance true in
#grind_lint inspect List.flatMap_reverse

跟踪输出显示无界实例化:

[grind.ematch.instance] List.flatMap_def: List.flatMap (List.reverse ∘ f) l = (List.map (List.reverse ∘ f) l).flatten
[grind.ematch.instance] List.flatMap_def: List.flatMap f l.reverse = (List.map f l.reverse).flatten
[grind.ematch.instance] List.flatMap_reverse: List.flatMap f l.reverse = (List.flatMap (List.reverse ∘ f) l).reverse
[grind.ematch.instance] List.reverse_flatMap: (List.flatMap (List.reverse ∘ f) l).reverse =
  List.flatMap (List.reverse ∘ List.reverse ∘ f) l.reverse
[grind.ematch.instance] List.flatMap_def: List.flatMap (List.reverse ∘ List.reverse ∘ f) l.reverse =
  (List.map (List.reverse ∘ List.reverse ∘ f) l.reverse).flatten

这种模式无限期地持续下去,每次迭代都会向合成中添加另一个 List.reverseLean.Parser.Command.grind_patternwhere 子句通过排除有问题的实例化来防止这种情况:

grind_pattern reverse_flatMap => (l.flatMap f).reverse where
  f =/= List.reverse ∘ _

这指示 grind 使用模式 (l.flatMap f).reverse,但仅当 f 不是与 List.reverse 的组合时,防止无限的实例化链。

您可以使用 #grind_lint check 查找有问题的模式,或使用 #grind_lint check in List#grind_lint check in module Std.Data 在特定命名空间或模块中查找。

grind 属性使用启发式自动生成 E 匹配模式或多模式,而不是使用 Lean.Parser.Command.grindPattern : commandThe `grind_pattern` command can be used to manually select a pattern for theorem instantiation. Enabling the option `trace.grind.ematch.instance` causes `grind` to print a trace message for each theorem instance it generates, which can be helpful when determining patterns. When multiple patterns are specified together, all of them must match in the current context before `grind` attempts to instantiate the theorem. This is referred to as a *multi-pattern*. This is useful for theorems such as transitivity rules, where multiple premises must be simultaneously present for the rule to apply. In the following example, `R` is a transitive binary relation over `Int`. ``` opaque R : Int → Int → Prop axiom Rtrans {x y z : Int} : R x y → R y z → R x z ``` To use the fact that `R` is transitive, `grind` must already be able to satisfy both premises. This is represented using a multi-pattern: ``` grind_pattern Rtrans => R x y, R y z example {a b c d} : R a b → R b c → R c d → R a d := by grind ``` The multi-pattern `R x y`, `R y z` instructs `grind` to instantiate `Rtrans` only when both `R x y` and `R y z` are available in the context. In the example, `grind` applies `Rtrans` to derive `R a c` from `R a b` and `R b c`, and can then repeat the same reasoning to deduce `R a d` from `R a c` and `R c d`. You can add constraints to restrict theorem instantiation. For example: ``` grind_pattern extract_extract => (as.extract i j).extract k l where as =/= #[] ``` The constraint instructs `grind` to instantiate the theorem only if `as` is **not** definitionally equal to `#[]`. ## Constraints - `x =/= term`: The term bound to `x` (one of the theorem parameters) is **not** definitionally equal to `term`. The term may contain holes (i.e., `_`). - `x =?= term`: The term bound to `x` is definitionally equal to `term`. The term may contain holes (i.e., `_`). - `size x < n`: The term bound to `x` has size less than `n`. Implicit arguments and binder types are ignored when computing the size. - `depth x < n`: The term bound to `x` has depth less than `n`. - `is_ground x`: The term bound to `x` does not contain local variables or meta-variables. - `is_value x`: The term bound to `x` is a value. That is, it is a constructor fully applied to value arguments, a literal (`Nat`, `Int`, `String`, etc.), or a lambda `fun x => t`. - `is_strict_value x`: Similar to `is_value`, but without lambdas. - `not_value x`: The term bound to `x` is a **not** value (see `is_value`). - `not_strict_value x`: Similar to `not_value`, but without lambdas. - `gen < n`: The theorem instance has generation less than `n`. Recall that each term is assigned a generation, and terms produced by theorem instantiation have a generation that is one greater than the maximal generation of all the terms used to instantiate the theorem. This constraint complements the `gen` option available in `grind`. - `max_insts < n`: A new instance is generated only if less than `n` instances have been generated so far. - `guard e`: The instantiation is delayed until `grind` learns that `e` is `true` in this state. - `check e`: Similar to `guard e`, but `grind` checks whether `e` is implied by its current state by assuming `¬ e` and trying to deduce an inconsistency. ## Example Consider the following example where `f` is a monotonic function ``` opaque f : Nat → Nat axiom fMono : x ≤ y → f x ≤ f y ``` and you want to instruct `grind` to instantiate `fMono` for every pair of terms `f x` and `f y` when `x ≤ y` and `x` is **not** definitionally equal to `y`. You can use ``` grind_pattern fMono => f x, f y where guard x ≤ y x =/= y ``` Then, in the following example, only three instances are generated. ``` /-- trace: [grind.ematch.instance] fMono: a ≤ f a → f a ≤ f (f a) [grind.ematch.instance] fMono: f a ≤ f (f a) → f (f a) ≤ f (f (f a)) [grind.ematch.instance] fMono: a ≤ f (f a) → f a ≤ f (f (f a)) -/ #guard_msgs in example : f b = f c → a ≤ f a → f (f a) ≤ f (f (f a)) := by set_option trace.grind.ematch.instance true in grind ``` grind_pattern 显式指定模式。 它包括许多选择不同启发式的变体。 grind? 属性显示一条信息消息,显示所选模式 - 这对于调试非常有帮助!

模式是定理陈述的子表达式。 如果子表达式具有可索引常量作为其头部,则该子表达式为 indexable;如果它修复了参数的值,则称其为 cover 定理的参数之一。 可索引常量是除 EqHEqIffAndOrNot 之外的所有常量。 模式或多模式覆盖的参数集称为其 coverage。 某些常量的优先级低于其他常量;特别是,算术运算符 HAdd.hAddHSub.hSubHMul.hMulDvd.dvdHDiv.hDivHMod.hMod 具有低优先级。 如果不存在其头常量至少具有同样高优先级的更小的可索引子表达式,则可索引子表达式为 minimal

attributeGrind Patterns

grind 属性添加到定义中时,每当遇到该定义时,它都会导致 grind 将该定义展开到其正文。 使用模块系统时,如果定义主体不可见(例如通过 @[expose]),则忽略 grind 属性。

attr ::= ...
    | Marks a theorem or definition for use by the `grind` tactic.

An optional modifier (e.g. `=`, `→`, `←`, `cases`, `intro`, `ext`, `inj`, etc.)
controls how `grind` uses the declaration:
* whether it is applied forwards, backwards, or both,
* whether equalities are used on the left, right, or both sides,
* whether case-splits, constructors, extensionality, or injectivity are applied,
* or whether custom instantiation patterns are used.

See the individual modifier docstrings for details.
grind grindMod?

grind 属性使用由提供的修饰符确定的策略自动生成定理的 E 匹配模式。 如果未提供修饰符,则 grind 会建议合适的修饰符,并显示结果模式。

attr ::= ...
    | Like `@[grind]`, but enforces the **minimal indexable subexpression condition**:
when several subterms cover the same free variables, `grind!` chooses the smallest one.

This influences E-matching pattern selection.

### Example
```lean
theorem fg_eq (h : x > 0) : f (g x) = x

@[grind <-] theorem fg_eq (h : x > 0) : f (g x) = x
-- Pattern selected: `f (g x)`

-- With minimal subexpression:
@[grind! <-] theorem fg_eq (h : x > 0) : f (g x) = x
-- Pattern selected: `g x`
```
grind! grindMod?

grind! 属性使用由提供的修饰符确定的策略自动生成定理的 E 匹配模式。 它还强制执行以下条件:所选模式应该是最小可索引子表达式。

attr ::= ...
    | Like `@[grind]`, but also prints the pattern(s) selected by `grind`
as info messages. Useful for debugging annotations and modifiers.
grind? grindMod?

grind? 显示生成的模式。

attr ::= ...
    | Like `@[grind!]`, but also prints the pattern(s) selected by `grind`
as info messages. Combines minimal subexpression selection with debugging output.
grind!? grindMod?

grind!? 属性与 grind! 等效,只不过它显示结果模式以供检查。

在没有任何修饰符的情况下,@[grind] 从左到右遍历结论,然后遍历假设,在增加覆盖范围时添加模式,在覆盖所有参数时停止。 可以使用 Lean.Parser.Attr.grindDefThe `.` modifier instructs `grind` to select a multi-pattern by traversing the conclusion of the theorem, and then the hypotheses from left to right. We say this is the default modifier. Each time it encounters a subexpression which covers an argument which was not previously covered, it adds that subexpression as a pattern, until all arguments have been covered. If `grind!` is used, then only minimal indexable subexpressions are considered. . 修饰符显式请求此默认策略。 除了使用默认策略之外,该属性还会检查可以应用哪些其他策略,并显示所有结果模式。

syntaxDefault Pattern
grindMod ::= ...
    | The `.` modifier instructs `grind` to select a multi-pattern by traversing the conclusion of the
theorem, and then the hypotheses from left to right. We say this is the default modifier.
Each time it encounters a subexpression which covers an argument which was not
previously covered, it adds that subexpression as a pattern, until all arguments have been covered.
If `grind!` is used, then only minimal indexable subexpressions are considered.
.
grindMod ::= ...
    | The `.` modifier instructs `grind` to select a multi-pattern by traversing the conclusion of the
theorem, and then the hypotheses from left to right. We say this is the default modifier.
Each time it encounters a subexpression which covers an argument which was not
previously covered, it adds that subexpression as a pattern, until all arguments have been covered.
If `grind!` is used, then only minimal indexable subexpressions are considered.
·

The . modifier instructs grind to select a multi-pattern by traversing the conclusion of the theorem, and then the hypotheses from left to right. We say this is the default modifier. Each time it encounters a subexpression which covers an argument which was not previously covered, it adds that subexpression as a pattern, until all arguments have been covered. If grind! is used, then only minimal indexable subexpressions are considered.

syntaxEquality Rewrites
grindMod ::= ...
    | The `=` modifier instructs `grind` to check that the conclusion of the theorem is an equality,
and then uses the left-hand side of the equality as a pattern. This may fail if not all of the arguments appear
in the left-hand side.
=

The = modifier instructs grind to check that the conclusion of the theorem is an equality, and then uses the left-hand side of the equality as a pattern. This may fail if not all of the arguments appear in the left-hand side.

syntaxBackward Equality Rewrites
grindMod ::= ...
    | The `=_` modifier instructs `grind` to check that the conclusion of the theorem is an equality,
and then uses the right-hand side of the equality as a pattern. This may fail if not all of the arguments appear
in the right-hand side.
=_

The =_ modifier instructs grind to check that the conclusion of the theorem is an equality, and then uses the right-hand side of the equality as a pattern. This may fail if not all of the arguments appear in the right-hand side.

syntaxBidirectional Equality Rewrites
grindMod ::= ...
    | The `_=_` modifier acts like a macro which expands to `=` and `=_`.  It adds two patterns,
allowing the equality theorem to trigger in either direction.
_=_

The _=_ modifier acts like a macro which expands to = and =_. It adds two patterns, allowing the equality theorem to trigger in either direction.

syntaxForward Reasoning
grindMod ::= ...
    | The `→` modifier instructs `grind` to select a multi-pattern from the hypotheses of the theorem.
In other words, `grind` will use the theorem for forwards reasoning.
To generate a pattern, it traverses the hypotheses of the theorem from left to right.
Each time it encounters a subexpression which covers an argument which was not
previously covered, it adds that subexpression as a pattern, until all arguments have been covered.
If `grind!` is used, then only minimal indexable subexpressions are considered.

The modifier instructs grind to select a multi-pattern from the hypotheses of the theorem. In other words, grind will use the theorem for forwards reasoning. To generate a pattern, it traverses the hypotheses of the theorem from left to right. Each time it encounters a subexpression which covers an argument which was not previously covered, it adds that subexpression as a pattern, until all arguments have been covered. If grind! is used, then only minimal indexable subexpressions are considered.

syntaxBackward Reasoning
grindMod ::= ...
    | The `←` modifier instructs `grind` to select a multi-pattern from the conclusion of theorem.
In other words, `grind` will use the theorem for backwards reasoning.
This may fail if not all of the arguments to the theorem appear in the conclusion.
Each time it encounters a subexpression which covers an argument which was not
previously covered, it adds that subexpression as a pattern, until all arguments have been covered.
If `grind!` is used, then only minimal indexable subexpressions are considered.

The modifier instructs grind to select a multi-pattern from the conclusion of theorem. In other words, grind will use the theorem for backwards reasoning. This may fail if not all of the arguments to the theorem appear in the conclusion. Each time it encounters a subexpression which covers an argument which was not previously covered, it adds that subexpression as a pattern, until all arguments have been covered. If grind! is used, then only minimal indexable subexpressions are considered.

检查 @[grind] 属性生成的模式以确保它们与引理的正确部分匹配非常重要。 如果模式太严格,则引理将不会应用于相关的情况,从而导致自动化程度降低。 如果它太笼统,那么性能将会受到影响,因为引理在许多情况下都没有帮助。

还有三个不太常用的引理修饰符:

syntaxLeft-to-Right Traversal
grindMod ::= ...
    | The `⇒` modifier instructs `grind` to select a multi-pattern by traversing all the hypotheses from
left to right, followed by the conclusion.
Each time it encounters a subexpression which covers an argument which was not
previously covered, it adds that subexpression as a pattern, until all arguments have been covered.
If `grind!` is used, then only minimal indexable subexpressions are considered.
=>
grindMod ::= ...
    | The `⇒` modifier instructs `grind` to select a multi-pattern by traversing all the hypotheses from
left to right, followed by the conclusion.
Each time it encounters a subexpression which covers an argument which was not
previously covered, it adds that subexpression as a pattern, until all arguments have been covered.
If `grind!` is used, then only minimal indexable subexpressions are considered.

The modifier instructs grind to select a multi-pattern by traversing all the hypotheses from left to right, followed by the conclusion. Each time it encounters a subexpression which covers an argument which was not previously covered, it adds that subexpression as a pattern, until all arguments have been covered. If grind! is used, then only minimal indexable subexpressions are considered.

syntaxRight-to-Left Traversal
grindMod ::= ...
    | The `⇐` modifier instructs `grind` to select a multi-pattern by traversing the conclusion, and then
all the hypotheses from right to left.
Each time it encounters a subexpression which covers an argument which was not
previously covered, it adds that subexpression as a pattern, until all arguments have been covered.
If `grind!` is used, then only minimal indexable subexpressions are considered.
<=
grindMod ::= ...
    | The `⇐` modifier instructs `grind` to select a multi-pattern by traversing the conclusion, and then
all the hypotheses from right to left.
Each time it encounters a subexpression which covers an argument which was not
previously covered, it adds that subexpression as a pattern, until all arguments have been covered.
If `grind!` is used, then only minimal indexable subexpressions are considered.

The modifier instructs grind to select a multi-pattern by traversing the conclusion, and then all the hypotheses from right to left. Each time it encounters a subexpression which covers an argument which was not previously covered, it adds that subexpression as a pattern, until all arguments have been covered. If grind! is used, then only minimal indexable subexpressions are considered.

syntaxBackward Reasoning on Equality
grindMod ::= ...
    | The `←=` modifier is unlike the other `grind` modifiers, and it used specifically for
backwards reasoning on equality. When a theorem's conclusion is an equality proposition and it
is annotated with `@[grind ←=]`, grind `will` instantiate it whenever the corresponding disequality
is assumed—this is a consequence of the fact that grind performs all proofs by contradiction.
Ordinarily, the grind attribute does not consider the `=` symbol when generating patterns.
=

The = modifier is unlike the other grind modifiers, and it used specifically for backwards reasoning on equality. When a theorem's conclusion is an equality proposition and it is annotated with @[grind =], grind will instantiate it whenever the corresponding disequality is assumed—this is a consequence of the fact that grind performs all proofs by contradiction. Ordinarily, the grind attribute does not consider the = symbol when generating patterns.

The @[grind ←=] Attribute

当尝试证明 a⁻¹ = b 时,由于 @[grind ←=] 注释,grind 使用 inv_eq

@[grind =] theorem declaration uses `sorry`inv_eq [One α] [Mul α] [Inv α] {a b : α} (w : a * b = 1) : a⁻¹ = b := sorry
syntaxFunction-Valued Congruence Closure
grindMod ::= ...
    | The `funCC` modifier marks global functions that support **function-valued congruence closure**.
Given an application `f a₁ a₂ … aₙ`, when `funCC := true`,
`grind` generates and tracks equalities for all partial applications:
- `f a₁`
- `f a₁ a₂`
- `…`
- `f a₁ a₂ … aₙ`
funCC

The funCC modifier marks global functions that support function-valued congruence closure. Given an application f a₁ a₂ … aₙ, when funCC := true, grind generates and tracks equalities for all partial applications:

  • f a₁

  • f a₁ a₂

  • f a₁ a₂ … aₙ

一些附加修饰符可用于向索引添加其他类型的引理。 这包括外延性定理、函数的单射定理以及将归纳定义的谓词的所有构造函数添加到索引的快捷方式。

syntaxExtensionality
grindMod ::= ...
    | The `ext` modifier marks extensionality theorems for use by `grind`.
For example, the standard library marks `funext` with this attribute.

Whenever `grind` encounters a disequality `a ≠ b`, it attempts to apply any
available extensionality theorems whose matches the type of `a` and `b`.
ext

The ext modifier marks extensionality theorems for use by grind. For example, the standard library marks funext with this attribute.

Whenever grind encounters a disequality a b, it attempts to apply any available extensionality theorems whose matches the type of a and b.

此外,将 @[grind ext] 添加到结构中会注册其外延性定理。

The @[grind ext] Attribute

Point 是一个具有两个字段的结构:

structure Point where x : Int y : Int

默认情况下,grind 可以解决这样的目标,因为 定义等价 包含产品类型的 η-equivalence

example (p : Point) : p = p.x, p.y := p:Pointp = { x := p.x, y := p.y } All goals completed! 🐙

然而,它无法解决像这样需要诉诸命题等价的目标:

example (p : Point) (a : Int) : a = p.x p = a, p.y := p:Pointa:Inta = p.x p = { x := a, y := p.y } `grind` failed p:Pointa:Inth:a = p.xh_1:¬p = { x := a, y := p.y }False
[grind] Goal diagnostics
  • [facts] Asserted facts
    • [prop] a = p.x
    • [prop] ¬p = { x := a, y := p.y }
  • [eqc] False propositions
    • [prop] p = { x := a, y := p.y }
  • [eqc] Equivalence classes
    • [eqc] {a, p.x}
All goals completed! 🐙
`grind` failed
p:Pointa:Inth:a = p.xh_1:¬p = { x := a, y := p.y }False
[grind] Goal diagnostics
  • [facts] Asserted facts
    • [prop] a = p.x
    • [prop] ¬p = { x := a, y := p.y }
  • [eqc] False propositions
    • [prop] p = { x := a, y := p.y }
  • [eqc] Equivalence classes
    • [eqc] {a, p.x}

在证明定理时可能会出现这种目标,例如交换点的字段两次是恒等式的事实:

def Point.swap (p : Point) : Point := p.y, p.x theorem swap_swap_eq_id : Point.swap Point.swap = id := Point.swap Point.swap = id ((fun p => { x := p.y, y := p.x }) fun p => { x := p.y, y := p.x }) = id `grind` failed h:¬((fun p => { x := p.y, y := p.x }) fun p => { x := p.y, y := p.x }) = idw:Pointh_1:¬{ x := w.x, y := w.y } = id wFalse
[grind] Goal diagnostics
  • [facts] Asserted facts
    • [prop] ¬((fun p => { x := p.y, y := p.x }) fun p => { x := p.y, y := p.x }) = id
    • [prop] x, ¬{ x := x.x, y := x.y } = id x
    • [prop] ¬{ x := w.x, y := w.y } = id w
    • [prop] id w = w
  • [eqc] True propositions
  • [eqc] False propositions
    • [prop] ((fun p => { x := p.y, y := p.x }) fun p => { x := p.y, y := p.x }) = id
    • [prop] { x := w.x, y := w.y } = id w
  • [eqc] Equivalence classes
    • [eqc] {w, id w}
  • [cases] Case analyses
    • [cases] [1/1]: x, ¬{ x := x.x, y := x.y } = id x
      • [cases] source: Extensionality `funext`
  • [ematch] E-matching patterns
    • [thm] id.eq_1: [@id #1 #0]
[grind] Diagnostics
  • [thm] E-Matching instances
    • [thm] id.eq_11
All goals completed! 🐙
`grind` failed
h:¬((fun p => { x := p.y, y := p.x })  fun p => { x := p.y, y := p.x }) = idw:Pointh_1:¬{ x := w.x, y := w.y } = id wFalse
[grind] Goal diagnostics
  • [facts] Asserted facts
    • [prop] ¬((fun p => { x := p.y, y := p.x }) fun p => { x := p.y, y := p.x }) = id
    • [prop] x, ¬{ x := x.x, y := x.y } = id x
    • [prop] ¬{ x := w.x, y := w.y } = id w
    • [prop] id w = w
  • [eqc] True propositions
  • [eqc] False propositions
    • [prop] ((fun p => { x := p.y, y := p.x }) fun p => { x := p.y, y := p.x }) = id
    • [prop] { x := w.x, y := w.y } = id w
  • [eqc] Equivalence classes
    • [eqc] {w, id w}
  • [cases] Case analyses
    • [cases] [1/1]: x, ¬{ x := x.x, y := x.y } = id x
      • [cases] source: Extensionality `funext`
  • [ematch] E-matching patterns
    • [thm] id.eq_1: [@id #1 #0]
[grind] Diagnostics
  • [thm] E-Matching instances
    • [thm] id.eq_11

@[grind ext] 属性添加到 Point 使 grind 能够求解原始示例并证明该定理:

attribute [grind ext] Point example (p : Point) (a : Int) : a = p.x p = a, p.y := p:Pointa:Inta = p.x p = { x := a, y := p.y } All goals completed! 🐙 theorem swap_swap_eq_id' : Point.swap Point.swap = id := Point.swap Point.swap = id ((fun p => { x := p.y, y := p.x }) fun p => { x := p.y, y := p.x }) = id All goals completed! 🐙
syntaxInjectivity
grindMod ::= ...
    | The `inj` modifier marks injectivity theorems for use by `grind`.
The conclusion of the theorem must be of the form `Function.Injective f`
where the term `f` contains at least one constant symbol.
inj

The inj modifier marks injectivity theorems for use by grind. The conclusion of the theorem must be of the form Function.Injective f where the term f contains at least one constant symbol.

Injectivity Patterns

此函数 double 将其参数加倍:

def double (x : Nat) : Nat := x + x

默认情况下,grind 无法证明以下定理:

theorem A {n k : Nat} : double (n + 5) = double (k - 3) n + 8 = k := n:Natk:Natdouble (n + 5) = double (k - 3) n + 8 = k `grind` failed n k:Nath:double (n + 5) = double (k - 3)h_1:¬n + 8 = kh_2:-1 * k + 3 0False
[grind] Goal diagnostics
  • [facts] Asserted facts
  • [eqc] True propositions
  • [eqc] False propositions
    • [prop] n + 8 = k
  • [eqc] Equivalence classes
  • [cases] Case analyses
    • [cases] [1/2]: if -1 * k + 3 0 then k + -3 else 0
      • [cases] source: Initial goal
  • [cutsat] Assignment satisfying linear constraints
All goals completed! 🐙

但是,double 是单射的,可以使用 grind inj 属性为 grind 注册这一事实:

@[grind inj] theorem double_inj : Function.Injective double := Function.Injective double a₁ a₂ : Nat⦄, a₁ + a₁ = a₂ + a₂ a₁ = a₂ All goals completed! 🐙

这个单射引理足以证明以下定理:

theorem B {n k : Nat} : double (n + 5) = double (k - 3) n + 8 = k := n:Natk:Natdouble (n + 5) = double (k - 3) n + 8 = k All goals completed! 🐙
syntaxConstructor Patterns
grindMod ::= ...
    | The `intro` modifier instructs `grind` to use the constructors (introduction rules)
of an inductive predicate as E-matching theorems.Example:
```
inductive Even : Nat → Prop where
| zero : Even 0
| add2 : Even x → Even (x + 2)

attribute [grind intro] Even
example (h : Even x) : Even (x + 6) := by grind
example : Even 0 := by grind
```
Here `attribute [grind intro] Even` acts like a macro that expands to
`attribute [grind] Even.zero` and `attribute [grind] Even.add2`.
This is especially convenient for inductive predicates with many constructors.
intro

The intro modifier instructs grind to use the constructors (introduction rules) of an inductive predicate as E-matching theorems.Example:

inductive Even : Nat Prop where | zero : Even 0 | add2 : Even x Even (x + 2) attribute [grind intro] Even example (h : Even x) : Even (x + 6) := x:Nath:Even xEven (x + 6) All goals completed! 🐙 example : Even 0 := Even 0 All goals completed! 🐙

Here attribute [grind intro] Even acts like a macro that expands to attribute [grind] Even.zero and attribute [grind] Even.add2. This is especially convenient for inductive predicates with many constructors.

Patterns for Constructors

谓词 Decreasing 声明整数列表中的每个值都小于之前的值,函数 decreasing 检查此属性,返回 Bool

inductive Decreasing : List Int Prop | nil : Decreasing [] | singleton : Decreasing [x] | cons : Decreasing (x :: xs) y > x Decreasing (y :: x :: xs) def decreasing : List Int Bool | [] | [_] => true | y :: x :: xs => y > x && decreasing (x :: xs)

如果当 Decreasing 为其参数成立时,该函数恰好返回 true,则该函数是正确的。 尝试使用 fun_inductiongrind 的组合来证明这一事实立即失败,三种情况均未得到证明:

def decreasingCorrect : decreasing xs = Decreasing xs := xs:List Int(decreasing xs = true) = Decreasing xs (true = true) = Decreasing []head✝:Int(true = true) = Decreasing [head✝]y✝:Intx✝:Intxs✝:List Intih1✝:(decreasing (x✝ :: xs✝) = true) = Decreasing (x✝ :: xs✝)((decide (y✝ > x✝) && decreasing (x✝ :: xs✝)) = true) = Decreasing (y✝ :: x✝ :: xs✝) (true = true) = Decreasing []head✝:Int(true = true) = Decreasing [head✝]y✝:Intx✝:Intxs✝:List Intih1✝:(decreasing (x✝ :: xs✝) = true) = Decreasing (x✝ :: xs✝)((decide (y✝ > x✝) && decreasing (x✝ :: xs✝)) = true) = Decreasing (y✝ :: x✝ :: xs✝) `grind` failed y x:Intxs:List Intih1:(decreasing (x :: xs) = true) = Decreasing (x :: xs)h:(-1 * y + x + 1 0 decreasing (x :: xs) = true) = ¬Decreasing (y :: x :: xs)left:-1 * y + x + 1 0left_1:decreasing (x :: xs) = trueright_1:¬Decreasing (y :: x :: xs)False
[grind] Goal diagnostics
`grind` failed h:True = ¬Decreasing []False
[grind] Goal diagnostics
`grind` failed head:Inth:True = ¬Decreasing [head]False
[grind] Goal diagnostics
All goals completed! 🐙
`grind` failed
h:True = ¬Decreasing []False
[grind] Goal diagnostics
`grind` failed
head:Inth:True = ¬Decreasing [head]False
[grind] Goal diagnostics
`grind` failed
y x:Intxs:List Intih1:(decreasing (x :: xs) = true) = Decreasing (x :: xs)h:(-1 * y + x + 1  0  decreasing (x :: xs) = true) = ¬Decreasing (y :: x :: xs)left:-1 * y + x + 1  0left_1:decreasing (x :: xs) = trueright_1:¬Decreasing (y :: x :: xs)False
[grind] Goal diagnostics

grind intro 属性添加到 Decreasing 会导致为三个构造函数中的每一个添加 E 匹配模式,之后 grind 可以证明前两个目标,并且只需要对假设进行案例分析即可证明最终目标:

attribute [grind intro] Decreasing def decreasingCorrect' : decreasing xs = Decreasing xs := xs:List Int(decreasing xs = true) = Decreasing xs (true = true) = Decreasing []head✝:Int(true = true) = Decreasing [head✝]y✝:Intx✝:Intxs✝:List Intih1✝:(decreasing (x✝ :: xs✝) = true) = Decreasing (x✝ :: xs✝)((decide (y✝ > x✝) && decreasing (x✝ :: xs✝)) = true) = Decreasing (y✝ :: x✝ :: xs✝) (true = true) = Decreasing []head✝:Int(true = true) = Decreasing [head✝]y✝:Intx✝:Intxs✝:List Intih1✝:(decreasing (x✝ :: xs✝) = true) = Decreasing (x✝ :: xs✝)((decide (y✝ > x✝) && decreasing (x✝ :: xs✝)) = true) = Decreasing (y✝ :: x✝ :: xs✝) try All goals completed! 🐙 case case3 y x xs ih y:Intx:Intxs:List Intih:(decreasing (x✝ :: xs✝) = true) = Decreasing (x✝ :: xs✝)((decide (y✝ > x✝) && decreasing (x✝ :: xs✝)) = true) = Decreasing (y✝ :: x✝ :: xs✝) y:Intx:Intxs:List Intih:(decreasing (x✝ :: xs✝) = true) = Decreasing (x✝ :: xs✝)(decide (y > x) && decreasing (x :: xs)) = true Decreasing (y :: x :: xs) y:Intx:Intxs:List Intih:(decreasing (x✝ :: xs✝) = true) = Decreasing (x✝ :: xs✝)(decide (y > x) && decreasing (x :: xs)) = true Decreasing (y :: x :: xs)y:Intx:Intxs:List Intih:(decreasing (x✝ :: xs✝) = true) = Decreasing (x✝ :: xs✝)Decreasing (y :: x :: xs) (decide (y > x) && decreasing (x :: xs)) = true y:Intx:Intxs:List Intih:(decreasing (x✝ :: xs✝) = true) = Decreasing (x✝ :: xs✝)(decide (y > x) && decreasing (x :: xs)) = true Decreasing (y :: x :: xs) All goals completed! 🐙 y:Intx:Intxs:List Intih:(decreasing (x✝ :: xs✝) = true) = Decreasing (x✝ :: xs✝)Decreasing (y :: x :: xs) (decide (y > x) && decreasing (x :: xs)) = true intro y:Intx:Intxs:List Intih:(decreasing (x✝ :: xs✝) = true) = Decreasing (x✝ :: xs✝)x✝:Decreasing (y :: x :: xs)hDec:Decreasing (x :: xs)hLt:y > x(decide (y > x) && decreasing (x :: xs)) = true All goals completed! 🐙

grind cases 添加到 Decreasing 可以自动进行案例分析,从而实现全自动证明:

attribute [grind cases] Decreasing def decreasingCorrect'' : decreasing xs = Decreasing xs := xs:List Int(decreasing xs = true) = Decreasing xs (true = true) = Decreasing []head✝:Int(true = true) = Decreasing [head✝]y✝:Intx✝:Intxs✝:List Intih1✝:(decreasing (x✝ :: xs✝) = true) = Decreasing (x✝ :: xs✝)((decide (y✝ > x✝) && decreasing (x✝ :: xs✝)) = true) = Decreasing (y✝ :: x✝ :: xs✝) (true = true) = Decreasing []head✝:Int(true = true) = Decreasing [head✝]y✝:Intx✝:Intxs✝:List Intih1✝:(decreasing (x✝ :: xs✝) = true) = Decreasing (x✝ :: xs✝)((decide (y✝ > x✝) && decreasing (x✝ :: xs✝)) = true) = Decreasing (y✝ :: x✝ :: xs✝) All goals completed! 🐙
syntaxUnfolding During Preprocessing
grindMod ::= ...
    | The `unfold` modifier instructs `grind` to unfold the given definition during the preprocessing step.
Example:
```
@[grind unfold] def h (x : Nat) := 2 * x
example : 6 ∣ 3*h x := by grind
```
unfold

The unfold modifier instructs grind to unfold the given definition during the preprocessing step. Example:

@[grind unfold] def h (x : Nat) := 2 * x example : 6 3*h x := x:Nat6 3 * h x All goals completed! 🐙
syntaxNormalization Rules
grindMod ::= ...
    | The `norm` modifier instructs `grind` to use a theorem as a normalization rule. That is,
the theorem is applied during the preprocessing step.
This feature is meant for advanced users who understand how the preprocessor and `grind`'s search
procedure interact with each other.
New users can still benefit from this feature by restricting its use to theorems that completely
eliminate a symbol from the goal. Example:
```
theorem max_def : max n m = if n ≤ m then m else n
```
For a negative example, consider:
```
opaque f : Int → Int → Int → Int
theorem fax1 : f x 0 1 = 1 := sorry
theorem fax2 : f 1 x 1 = 1 := sorry
attribute [grind norm] fax1
attribute [grind =] fax2

example (h : c = 1) : f c 0 c = 1 := by
  grind -- fails
```
In this example, `fax1` is a normalization rule, but it is not applicable to the input goal since
`f c 0 c` is not an instance of `f x 0 1`. However, `f c 0 c` matches the pattern `f 1 x 1` modulo
the equality `c = 1`. Thus, `grind` instantiates `fax2` with `x := 0`, producing the equality
`f 1 0 1 = 1`, which the normalizer simplifies to `True`. As a result, nothing useful is learned.
In the future, we plan to include linters to automatically detect issues like these.
Example:
```
opaque f : Nat → Nat
opaque g : Nat → Nat

@[grind norm] axiom fax : f x = x + 2
@[grind norm ←] axiom fg : f x = g x

example : f x ≥ 2 := by grind
example : f x ≥ g x := by grind
example : f x + g x ≥ 4 := by grind
```
norm

The norm modifier instructs grind to use a theorem as a normalization rule. That is, the theorem is applied during the preprocessing step. This feature is meant for advanced users who understand how the preprocessor and grind's search procedure interact with each other. New users can still benefit from this feature by restricting its use to theorems that completely eliminate a symbol from the goal. Example:

theorem max_def : max n m = if n ≤ m then m else n

For a negative example, consider:

opaque f : Int → Int → Int → Int
theorem fax1 : f x 0 1 = 1 := sorry
theorem fax2 : f 1 x 1 = 1 := sorry
attribute [grind norm] fax1
attribute [grind =] fax2

example (h : c = 1) : f c 0 c = 1 := by
  grind -- fails

In this example, fax1 is a normalization rule, but it is not applicable to the input goal since f c 0 c is not an instance of f x 0 1. However, f c 0 c matches the pattern f 1 x 1 modulo the equality c = 1. Thus, grind instantiates fax2 with x := 0, producing the equality f 1 0 1 = 1, which the normalizer simplifies to True. As a result, nothing useful is learned. In the future, we plan to include linters to automatically detect issues like these. Example:

opaque f : Nat Nat opaque g : Nat Nat @[grind norm] axiom fax : f x = x + 2 @[grind norm ] axiom fg : f x = g x example : f x 2 := x:Natf x 2 All goals completed! 🐙 example : f x g x := x:Natf x g x All goals completed! 🐙 example : f x + g x 4 := x:Natf x + g x 4 All goals completed! 🐙

16.6.2. 检查模式🔗

grind? 属性是 grind 属性的一个版本,它另外显示生成的图案或 多图案。 模式和多重模式显示为子表达式列表,每个子表达式都是一个模式;普通模式显示为单例列表。 在这些显示的模式中,定义的常量的名称按原样打印。 当定理的参数出现在模式中时,它们将使用数字而不是名称来显示。 特别地,它们是从右到左编号的,从0开始;该表示被称为 de Bruijnindexs

Inspecting Patterns

为了使用 grind 整除性可传递的证明,需要 E 匹配模式:

theorem div_trans {n k j : Nat} : n k k j n j := n:Natk:Natj:Natn k k j n j n:Natk:Natj:Natd₁:Natp₁:k = n * d₁d₂:Natp₂:j = k * d₂n j exact d₁ * d₂, n:Natk:Natj:Natd₁:Natp₁:k = n * d₁d₂:Natp₂:j = k * d₂j = n * (d₁ * d₂) All goals completed! 🐙

正确使用的属性是 @[grind →],因为每个前提都应该有一个模式。 使用 @[grind? →],可以查看生成了哪些模式:

attribute [div_trans: [@Dvd.dvd `[Nat] `[Nat.instDvd] #4 #3, @Dvd.dvd `[Nat] `[Nat.instDvd] #3 #2]grind? ] div_trans

有两个:

div_trans: [@Dvd.dvd `[Nat] `[Nat.instDvd] #4 #3, @Dvd.dvd `[Nat] `[Nat.instDvd] #3 #2]

参数从右到左编号,因此 #0k ∣ j 的假设,而 #4n。 因此,这两个模式对应于术语 n ∣ kk ∣ j

从假设和结论的子表达式中选择模式的规则是微妙的。

Forward Pattern Generation
axiom p : Nat Nat axiom q : Nat Nat @[h₁: [q #1]grind!? ] theorem declaration uses `sorry`h₁ (w : p (q x) = 7) : p (x + 1) = q x := sorry
h₁: [q #1]

图案为 q x。 从右数起,参数#0是前提w,参数#1是隐含参数x

为什么是@[grind! →]?选择q #1? 属性 @[grind! →] 通过从左到右遍历假设(即类型为命题的参数)来查找模式。 在本例中,只有一个假设:p (q x) = 7。 上述启发式表示,grind! 将搜索最小的 可索引 子表达式,其中 覆盖 先前未覆盖的参数。 只有一个未覆盖的参数,即 x。 整个假设 p (q x) = 7 无法使用,因为 grind 不会对相等性进行索引。 右侧 7 没有帮助,因为它无法确定 x 的值。 p (q x) 不适合,因为它不是最小的:它内部有 q x,它是可转位的(其头部是常量 q),并且它决定了 x 的值。 表达式 q x 本身是最小的,因为 x 不可索引。 因此,选择 q x 作为模式。

Backward Pattern Generation

在此示例中,Lean.Parser.Attr.grindMod 修饰符指示应在结论中找到该模式:

set_option trace.grind.debug.ematch.pattern true in @[[grind.debug.ematch.pattern] place: p (x + 1) = q x[grind.debug.ematch.pattern] collect: p (x + 1) = q x[grind.debug.ematch.pattern] arg: Nat, support: true[grind.debug.ematch.pattern] arg: p (x + 1), support: false[grind.debug.ematch.pattern] collect: p (x + 1)[grind.debug.ematch.pattern] candidate: p (x + 1)[grind.debug.ematch.pattern] found pattern: p (#1 + 1)[grind.debug.ematch.pattern] found full coverage[grind.debug.ematch.pattern] arg: q x, support: falseh₂: [p (#1 + 1)]grind? ] theorem declaration uses `sorry`h₂ (w : 7 = p (q x)) : p (x + 1) = q x := sorry

使用等式的左侧是因为 Eq 不可索引,并且 HAdd.hAdd 的优先级低于 p

h₂: [p (#1 + 1)]
Bidirectional Equality Pattern Generation

在此示例中,根据相等结论生成两个单独的 E 匹配模式。 一个匹配左侧,另一个匹配右侧。

@[h₃: [q #1]h₃: [p (#1 + 1)]grind? _=_] theorem declaration uses `sorry`h₃ (w : 7 = p (q x)) : p (x + 1) = q x := sorry
h₃: [q #1]

使用等式的整个左侧而不是仅使用 x + 1,因为 HAdd.hAdd 的优先级低于 p

h₃: [p (#1 + 1)]
Patterns from Conclusion and Hypotheses

在没有任何修饰符的情况下,@[grind] 通过首先检查结论然后检查前提来生成多重模式:

@[h₄: [p (#2 + 2), q #1]grind? .] theorem declaration uses `sorry`h₄ (w : p x = q y) : p (x + 2) = 7 := sorry

这里,参数 x#2y#1w#0。 生成的多重模式包含等式的左侧,这是涵盖参数的结论的唯一 minimal indexable 子表达式(即 x)。 它还包含 q y,它是涵盖附加参数(即 y)的假设 w 的唯一最小可索引子表达式。

h₄: [p (#2 + 2), q #1]
Failing Backward Pattern Generation

在此示例中,模式生成失败,因为定理的结论未提及参数 y

@[`@[grind ←] theorem h₅` failed to find patterns in the theorem's conclusion, consider using different options or the `grind_pattern` commandgrind? ] theorem declaration uses `sorry`h₅ (w : p x = q y) : p (x + 2) = 7 := sorry
`@[grind ←] theorem h₅` failed to find patterns in the theorem's conclusion, consider using different options or the `grind_pattern` command
Left-to-Right Generation

在此示例中,模式是通过从左到右遍历前提生成的,然后得出结论:

@[h₆: [q (#3 + 2), p (#2 + 2)]grind? =>] theorem declaration uses `sorry`h₆ (_ : q (y + 2) = q y) (_ : q (y + 1) = q y) : p (x + 2) = 7 := sorry

在这些模式中,y 是参数 #3x 是参数 #2,因为在定理语句中 自动隐式参数 是从左到右插入的,并且 y 出现在 x 之前。 前提是参数 #1#0。 在生成的多重模式中,y 由第一个前提的子表达式覆盖,z 由结论的子表达式覆盖:

h₆: [q (#3 + 2), p (#2 + 2)]

16.6.3. 资源限制🔗

电子匹配可以生成无限数量的定理 实例。 出于效率和终止的考虑,grind 使用两种机制限制电子匹配可以运行的次数:

生成

每个项都被分配一个 生成,并且 E-matching 产生的项的生成比用于实例化定理的所有项的最大生成大一。 E-matching 只考虑生成低于可配置阈值的项。 grindgen 选项控制生成阈值。

轮次限制

E-matching 引擎的每次调用都称为一个 轮次。 只执行有限轮次的 E-matching。 ematchgrind 选项控制轮数限制。

Too Many Instances

电子匹配会生成太多定理 实例。 某些模式甚至可能生成无限数量的实例。

在此示例中,s_eq 将添加到具有模式 s x 的索引中:

def s (Variable name `x` is not explicitly referenced. The binding can be removed (if unused) or named `_` (if used implicitly). Note: This linter can be disabled with `set_option linter.unusedVariables false`x : Nat) := 0 @[s_eq: [s #0]grind? =] theorem s_eq (x : Nat) : s x = s (x + 1) := rfl
s_eq: [s #0]

尝试使用该定理会导致许多有关 s 的事实应用于生成的具体值。 特别是,s_eq 在五轮中的每一轮中都用新的 Nat 进行实例化。 首先,grind 使用 x := 0 实例化 s_eq,从而生成项 s 1。 这与模式 s x 匹配,因此用于使用 x := 1 实例化 s_eq,从而生成术语 s 2, 依此类推,直到达到回合限制。

example : s 0 > 0 := s 0 > 0 `grind` failed h:s 0 = 0False
[grind] Goal diagnostics
  • [facts] Asserted facts
    • [prop] s 0 = 0
    • [prop] s 0 = s 1
    • [prop] s 1 = s 2
    • [prop] s 2 = s 3
    • [prop] s 3 = s 4
    • [prop] s 4 = s 5
  • [eqc] Equivalence classes
    • [eqc] {s 0, 0, s 1, s 2, s 3, s 4, s 5}
  • [ematch] E-matching patterns
  • [cutsat] Assignment satisfying linear constraints
    • [assign] s 0 := 0
    • [assign] s 1 := 0
    • [assign] s 2 := 0
    • [assign] s 3 := 0
    • [assign] s 4 := 0
    • [assign] s 5 := 0
  • [limits] Thresholds reached
    • [limit] maximum number of E-matching rounds has been reached, threshold: `(ematch := 5)`
[grind] Diagnostics
  • [thm] E-Matching instances
All goals completed! 🐙
`grind` failed
h:s 0 = 0False
[grind] Goal diagnostics
  • [facts] Asserted facts
    • [prop] s 0 = 0
    • [prop] s 0 = s 1
    • [prop] s 1 = s 2
    • [prop] s 2 = s 3
    • [prop] s 3 = s 4
    • [prop] s 4 = s 5
  • [eqc] Equivalence classes
    • [eqc] {s 0, 0, s 1, s 2, s 3, s 4, s 5}
  • [ematch] E-matching patterns
  • [cutsat] Assignment satisfying linear constraints
    • [assign] s 0 := 0
    • [assign] s 1 := 0
    • [assign] s 2 := 0
    • [assign] s 3 := 0
    • [assign] s 4 := 0
    • [assign] s 5 := 0
  • [limits] Thresholds reached
    • [limit] maximum number of E-matching rounds has been reached, threshold: `(ematch := 5)`
[grind] Diagnostics
  • [thm] E-Matching instances

由于默认生成限制为 8,将轮数限制增加到 20 会导致电子匹配终止:

example : s 0 > 0 := s 0 > 0 `grind` failed h:s 0 = 0False
[grind] Goal diagnostics
  • [facts] Asserted facts
    • [prop] s 0 = 0
    • [prop] s 0 = s 1
    • [prop] s 1 = s 2
    • [prop] s 2 = s 3
    • [prop] s 3 = s 4
    • [prop] s 4 = s 5
    • [prop] s 5 = s 6
    • [prop] s 6 = s 7
    • [prop] s 7 = s 8
  • [eqc] Equivalence classes
    • [eqc] {s 0, 0, s 1, s 2, s 3, s 4, s 5, s 6, s 7, s 8}
  • [ematch] E-matching patterns
  • [cutsat] Assignment satisfying linear constraints
    • [assign] s 0 := 0
    • [assign] s 1 := 0
    • [assign] s 2 := 0
    • [assign] s 3 := 0
    • [assign] s 4 := 0
    • [assign] s 5 := 0
    • [assign] s 6 := 0
    • [assign] s 7 := 0
    • [assign] s 8 := 0
  • [limits] Thresholds reached
    • [limit] maximum term generation has been reached, threshold: `(gen := 8)`
[grind] Diagnostics
  • [thm] E-Matching instances
All goals completed! 🐙
`grind` failed
h:s 0 = 0False
[grind] Goal diagnostics
  • [facts] Asserted facts
    • [prop] s 0 = 0
    • [prop] s 0 = s 1
    • [prop] s 1 = s 2
    • [prop] s 2 = s 3
    • [prop] s 3 = s 4
    • [prop] s 4 = s 5
    • [prop] s 5 = s 6
    • [prop] s 6 = s 7
    • [prop] s 7 = s 8
  • [eqc] Equivalence classes
    • [eqc] {s 0, 0, s 1, s 2, s 3, s 4, s 5, s 6, s 7, s 8}
  • [ematch] E-matching patterns
  • [cutsat] Assignment satisfying linear constraints
    • [assign] s 0 := 0
    • [assign] s 1 := 0
    • [assign] s 2 := 0
    • [assign] s 3 := 0
    • [assign] s 4 := 0
    • [assign] s 5 := 0
    • [assign] s 6 := 0
    • [assign] s 7 := 0
    • [assign] s 8 := 0
  • [limits] Thresholds reached
    • [limit] maximum term generation has been reached, threshold: `(gen := 8)`
[grind] Diagnostics
  • [thm] E-Matching instances
Increasing E-matching Limits

iota 返回严格小于其参数的所有数字的列表,定理 iota_succ 描述了其在 Nat.succ 上的行为:

def iota : Nat List Nat | 0 => [] | n + 1 => n :: iota n @[grind =] theorem iota_succ : iota (n + 1) = n :: iota n := rfl

(iota 20).length > 10这一事实可以通过重复实例化iota_succList.length_cons来证明。 但是,grind 没有成功:

example : (iota 20).length > 10 := (iota 20).length > 10 `grind` failed h:(iota 20).length 10False
[grind] Goal diagnostics
[grind] Diagnostics
  • [thm] E-Matching instances
    • [thm] iota_succ5
    • [thm] List.length_cons4
All goals completed! 🐙
`grind` failed
h:(iota 20).length  10False
[grind] Goal diagnostics
[grind] Diagnostics
  • [thm] E-Matching instances
    • [thm] iota_succ5
    • [thm] List.length_cons4

由于电子匹配轮数有限,实例化链尚未完成。 增加这些限制可以使 grind 成功:

example : (iota 20).length > 10 := (iota 20).length > 10 All goals completed! 🐙

当选项 diagnostics 设置为 true 时,grind 显示它为每个定理生成的实例数。 这对于检测包含触发过多实例的模式的定理很有用。 在本例中,诊断显示 iota_succ 被实例化 12 次:

set_option diagnostics true in set_option diagnostics.threshold 10 in
[diag] Diagnostics
  • [reduction] unfolded reducible declarations (max: 52, num: 1):
  • [type_class] used instances (max: 38, num: 5):
    • [type_class] instOfNat38
    • [type_class] instOfNatNat17
    • [type_class] Lean.Grind.instCommSemiringNat14
    • [type_class] Lean.Grind.CommRing.OfCommSemiring.ofCommSemiring13
    • [type_class] Lean.Grind.CommRing.OfCommSemiring.instOfNatQ12
  • [kernel] unfolded declarations (max: 387, num: 80):
    • [kernel] Int.Linear.Poly.rec387
    • [kernel] Bool.rec324
    • [kernel] Int.Linear.Expr.rec197
    • [kernel] Int.rec192
    • [kernel] Nat.rec128
    • [kernel] Lean.RArray.rec118
    • [kernel] Int.casesOn116
    • [kernel] OfNat.ofNat110
    • [kernel] Int.Linear.Expr.casesOn104
    • [kernel] Bool.and'94
    • [kernel] List.rec85
    • [kernel] Int.Linear.Poly.casesOn85
    • [kernel] Int.Linear.Poly.denote.match_181
    • [kernel] NatCast.natCast77
    • [kernel] Add.add73
    • [kernel] HAdd.hAdd73
    • [kernel] Bool.casesOn68
    • [kernel] Nat.casesOn64
    • [kernel] Int.Linear.Expr.toPoly'.go._f58
    • [kernel] Int.Linear.Expr.toPoly'.go.match_158
    • [kernel] Int.Linear.Poly.brecOn51
    • [kernel] List.casesOn50
    • [kernel] cond49
    • [kernel] cond.match_149
    • [kernel] Int.add.match_148
    • [kernel] Int.Linear.Expr.denote._f46
    • [kernel] Int.Linear.Expr.denote.match_146
    • [kernel] Int.beq'44
    • [kernel] Int.Linear.Poly.brecOn.go41
    • [kernel] Int.negOfNat.match_140
    • [kernel] Int.Linear.Var37
    • [kernel] Int.Linear.Expr.brecOn36
    • [kernel] Int.Linear.Expr.brecOn.go35
    • [kernel] Int.Linear.Poly.norm._f35
    • [kernel] Int.Linear.Poly.insert._f34
    • [kernel] Int.negOfNat33
    • [kernel] Lean.RArray.get27
    • [kernel] Int.mul26
    • [kernel] Int.Linear.Poly.beq'26
    • [kernel] instOfNatNat25
    • [kernel] HMul.hMul25
    • [kernel] Mul.mul25
    • [kernel] Int.Linear.Var.denote25
    • [kernel] Function.comp24
    • [kernel] Int.Linear.Expr.denote24
    • [kernel] Int.Linear.Poly.insert23
    • [kernel] Nat.Linear.Expr.rec23
    • [kernel] instDecidableEqList.match_122
    • [kernel] List.length._f22
    • [kernel] iota._f21
    • [kernel] 30 more entries...
      • [kernel] iota.match_121
      • [kernel] Int.add20
      • [kernel] Int.neg.match_120
      • [kernel] Int.neg19
      • [kernel] Neg.neg19
      • [kernel] BEq.beq17
      • [kernel] Nat.blt16
      • [kernel] Decidable.casesOn15
      • [kernel] Decidable.rec15
      • [kernel] instOfNat14
      • [kernel] decide13
      • [kernel] Prod.casesOn13
      • [kernel] Prod.rec13
      • [kernel] Int.Linear.Poly.combine_mul_k13
      • [kernel] Int.Linear.Poly.combine_mul_k'13
      • [kernel] LE.le12
      • [kernel] List.brecOn12
      • [kernel] Int.Linear.norm_eq_cert12
      • [kernel] Int.Linear.Expr.norm12
      • [kernel] Int.Linear.Expr.toPoly'12
      • [kernel] Int.Linear.Poly.addConst12
      • [kernel] Int.Linear.Poly.norm12
      • [kernel] Nat.Linear.Expr.casesOn12
      • [kernel] Int.Linear.Expr.toPoly'.go12
      • [kernel] Int.Linear.Poly.addConst._f12
      • [kernel] instDecidableEqNat11
      • [kernel] Nat.decEq11
      • [kernel] Int.Linear.eq_eq_subst'_cert11
      • [kernel] List.brecOn.go11
      • [kernel] Nat.decEq.match_111
  • use `set_option diagnostics.threshold <num>` to control threshold for reporting counters
example : (iota 20).length > 10 := (iota 20).length > 10
[grind] Diagnostics
  • [thm] E-Matching instances
    • [thm] iota_succ12
    • [thm] List.length_cons11
  • [app] Applications
  • [grind] Simplifier
    • [simp] used theorems (max: 15, num: 2):
      • [simp] Lean.Meta.Grind.Arith.normNatOfNatInst15
      • [simp] Nat.reduceAdd12
    • [simp] tried theorems (max: 46, num: 1):
      • [simp] eq_self46 ❌️
    • use `set_option diagnostics.threshold <num>` to control threshold for reporting counters
All goals completed! 🐙
[grind] Diagnostics
  • [thm] E-Matching instances
    • [thm] iota_succ12
    • [thm] List.length_cons11
  • [app] Applications
  • [grind] Simplifier
    • [simp] used theorems (max: 15, num: 2):
      • [simp] Lean.Meta.Grind.Arith.normNatOfNatInst15
      • [simp] Nat.reduceAdd12
    • [simp] tried theorems (max: 46, num: 1):
      • [simp] eq_self46 ❌️
    • use `set_option diagnostics.threshold <num>` to control threshold for reporting counters

默认情况下,grind 使用自动生成的 Lean.Parser.Term.match : termPattern matching. `match e, ... with | p, ... => f | ...` matches each given term `e` against each pattern `p` of a match alternative. When all patterns of an alternative match, the `match` term evaluates to the value of the corresponding right-hand side `f` with the pattern variables bound to the respective matched values. If used as `match h : e, ... with | p, ... => f | ...`, `h : e = p` is available within `f`. When not constructing a proof, `match` does not automatically substitute variables matched on in dependent variables' types. Use `match (generalizing := true) ...` to enforce this. Syntax quotations can also be used in a pattern match. This matches a `Syntax` value against quotations, pattern variables, or `_`. Quoted identifiers only match identical identifiers - custom matching such as by the preresolved names only should be done explicitly. `Syntax.atom`s are ignored during matching by default except when part of a built-in literal. For users introducing new atoms, we recommend wrapping them in dedicated syntax kinds if they should participate in matching. For example, in ```lean syntax "c" ("foo" <|> "bar") ... ``` `foo` and `bar` are indistinguishable during matching, but in ```lean syntax foo := "foo" syntax "c" (foo <|> "bar") ... ``` they are not. match 表达式方程作为 E 匹配定理。 可以通过将 matchEqs 标志设置为 false 来禁用此功能。

E-matching and Pattern Matching

启用诊断显示 grind 在 E 匹配期间使用辅助匹配函数的方程之一:

theorem gt1 (x y : Nat) : x = y + 1 0 < match x with | 0 => 0 | _ + 1 => 1 := x:Naty:Natx = y + 1 0 < match x with | 0 => 0 | n.succ => 1
[diag] Diagnostics
  • [reduction] unfolded reducible declarations (max: 36, num: 1):
    • [reduction] Nat.casesOn36
  • [kernel] unfolded declarations (max: 40, num: 6):
    • [kernel] List.rec40
    • [kernel] Bool.rec28
    • [kernel] OfNat.ofNat26
    • [kernel] List.casesOn25
    • [kernel] Nat.Linear.Expr.rec23
    • [kernel] Bool.casesOn22
  • use `set_option diagnostics.threshold <num>` to control threshold for reporting counters
set_option diagnostics true in
[grind] Diagnostics
  • [thm] E-Matching instances
    • [thm] gt1.match_1.congr_eq_21
  • [app] Applications
All goals completed! 🐙
[grind] Diagnostics
  • [thm] E-Matching instances
    • [thm] gt1.match_1.congr_eq_21
  • [app] Applications

该定理有以下类型:

gt1.match_1.congr_eq_2.{u_1} (motive : Nat Sort u_1) (x✝ : Nat) (h_1 : Unit motive 0) (h_2 : (n : Nat) motive n.succ) (n✝ : Nat) (heq_1 : x✝ = n✝.succ) : (match x✝ with | 0 => h_1 () | n.succ => h_2 n) h_2 n✝#check gt1.match_1.congr_eq_2
gt1.match_1.congr_eq_2.{u_1} (motive : Nat  Sort u_1) (x✝ : Nat) (h_1 : Unit  motive 0)
  (h_2 : (n : Nat)  motive n.succ) (n✝ : Nat) (heq_1 : x✝ = n✝.succ) :
  (match x✝ with
    | 0 => h_1 ()
    | n.succ => h_2 n) 
    h_2 n✝

禁用匹配器函数方程的使用会导致证明失败:

example (x y : Nat) : x = y + 1 0 < match x with | 0 => 0 | _+1 => 1 := x:Naty:Natx = y + 1 0 < match x with | 0 => 0 | n.succ => 1 `grind` failed x y:Nath:x = y + 1h_1:(match x with | 0 => 0 | n.succ => 1) = 0n:Nath_2:x = n + 1False
[grind] Goal diagnostics
  • [facts] Asserted facts
    • [prop] x = y + 1
    • [prop] (match x with | 0 => 0 | n.succ => 1) = 0
    • [prop] x = n + 1
  • [eqc] Equivalence classes
    • [eqc] {x, y + 1, n + 1}
    • [eqc] {y, n}
    • [eqc] others
      • [eqc] {y, n}
      • [eqc] {y, n}
      • [eqc] {(y + 1), (n + 1)}
      • [eqc] {0, match x with | 0 => 0 | n.succ => 1}
  • [cases] Case analyses
    • [cases] [2/2]: match x with | 0 => 0 | n.succ => 1
      • [cases] source: Initial goal
  • [cutsat] Assignment satisfying linear constraints
    • [assign] x := 1
    • [assign] y := 0
    • [assign] match x with | 0 => 0 | n.succ => 1 := 0
    • [assign] n := 0
  • [ring] Rings
    • [ring] Ring `Lean.Grind.Ring.OfSemiring.Q Nat`
      • [basis] Basis
        • [_] n + -1 * y = 0
    • [ring] Ring `Int`
[grind] Diagnostics
  • [cases] Cases instances
All goals completed! 🐙
`grind` failed
x y:Nath:x = y + 1h_1:(match x with
  | 0 => 0
  | n.succ => 1) =
  0n:Nath_2:x = n + 1False
[grind] Goal diagnostics
  • [facts] Asserted facts
    • [prop] x = y + 1
    • [prop] (match x with | 0 => 0 | n.succ => 1) = 0
    • [prop] x = n + 1
  • [eqc] Equivalence classes
    • [eqc] {x, y + 1, n + 1}
    • [eqc] {y, n}
    • [eqc] others
      • [eqc] {y, n}
      • [eqc] {y, n}
      • [eqc] {(y + 1), (n + 1)}
      • [eqc] {0, match x with | 0 => 0 | n.succ => 1}
  • [cases] Case analyses
    • [cases] [2/2]: match x with | 0 => 0 | n.succ => 1
      • [cases] source: Initial goal
  • [cutsat] Assignment satisfying linear constraints
    • [assign] x := 1
    • [assign] y := 0
    • [assign] match x with | 0 => 0 | n.succ => 1 := 0
    • [assign] n := 0
  • [ring] Rings
    • [ring] Ring `Lean.Grind.Ring.OfSemiring.Q Nat`
      • [basis] Basis
        • [_] n + -1 * y = 0
    • [ring] Ring `Int`
[grind] Diagnostics
  • [cases] Cases instances
🔗option
trace.grind.ematch.instance

Default value: false

enable/disable tracing for the given module and submodules