歧视策略如何运作？

Question

我很好奇 discriminate 战术在幕后是如何运作的。所以我做了一些实验。

首先是一个简单的归纳定义：

Inductive AB:=A|B.

然后是一个简单的引理，可以用 discriminate 策略证明：

Lemma l1: A=B -> False.
intro.
discriminate.
Defined.

让我们看看证明是什么样的：

Print l1.

l1 = 
fun H : A = B =>
(fun H0 : False => False_ind False H0)
  (eq_ind A
     (fun e : AB => match e with
                    | A => True
                    | B => False
                    end) I B H)
     : A = B -> False

这看起来很复杂，我不明白这里发生了什么。因此，我试图更明确地证明相同的引理：

Lemma l2: A=B -> False.
apply (fun e:(A=B) => match e with end).
Defined.

让我们再看看 Coq 用它做了什么：

Print l2.

l2 = 
fun e : A = B =>
match
  e as e0 in (_ = a)
  return
    (match a as x return (A = x -> Type) with
     | A => fun _ : A = A => IDProp
     | B => fun _ : A = B => False
     end e0)
with
| eq_refl => idProp
end
     : A = B -> False

现在我完全糊涂了。这个还是比较复杂的。谁能解释一下这是怎么回事？

Answer 1

让我们回顾一下这个 l1 术语并描述它的每一部分。

l1 : A = B -> False

l1 是一个蕴涵，因此通过 Curry-Howard 对应它是一个抽象（函数）：

fun H : A = B =>

现在我们需要构建抽象的body，它的类型必须是False。 discriminate 策略选择将 body 作为应用程序 f x 实现，其中 f = fun H0 : False => False_ind False H0 只是 False 归纳原理的包装器，它表示如果你有False的证明，你可以得到任何你想要的命题的证明（False_ind : forall P : Prop, False -> P）：

(fun H0 : False => False_ind False H0)
  (eq_ind A
     (fun e : AB => match e with
                    | A => True
                    | B => False
                    end) I B H)

如果我们执行beta-reduction的一步，我们将上面的简化为

False_ind False
          (eq_ind A
             (fun e : AB => match e with
                            | A => True
                            | B => False
                           end) I B H)

False_ind 的第一个参数是我们正在构建的术语的类型。如果要证明A = B -> True，那就是False_ind True (eq_ind A ...).

顺便说一句，很容易看出我们可以进一步简化我们的 body - 要使 False_ind 正常工作，需要提供 False 的证明，但那是正是我们在这里试图构建的！因此，我们可以完全摆脱 False_ind，得到以下内容：

eq_ind A
  (fun e : AB => match e with
                 | A => True
                 | B => False
                 end) I B H

eq_ind是相等的归纳原理，说equals可以代替equals：

eq_ind : forall (A : Type) (x : A) (P : A -> Prop),
   P x -> forall y : A, x = y -> P y

换句话说，如果一个人有 P x 的证明，那么对于所有等于 x 的 y，P y 成立。

现在，让我们使用 eq_ind 创建 step-by-step False 的证明（最终我们应该获得 eq_ind A (fun e : AB ...) 项）。

当然，我们从 eq_ind 开始，然后我们将它应用到某些 x - 让我们为此目的使用 A。接下来，我们需要谓词 P。写下 P 时要记住的一件重要事情是我们必须能够证明 P x。这个目标很容易实现——我们将使用 True 命题，它有一个简单的证明。另一件要记住的事情是我们试图证明的命题 (False) - 如果输入参数不是 A，我们应该返回它。综上所述，谓词几乎是自己写的：

fun x : AB => match x with
              | A => True
              | B => False
              end

我们有 eq_ind 的前两个参数，我们还需要三个：x 分支的证明 A，即 True 的证明]，即 I。一些y，这将引导我们得到我们想要证明的命题，即B，以及A = B的证明，它在最开始被称为H这个答案。将它们堆叠在一起，我们得到

eq_ind A
       (fun x : AB => match x with
                  | A => True
                  | B => False
                  end)
       I
       B
       H

这正是 discriminate 给我们的（模数包装）。

Answer 2

还有一个回答是针对discriminate的部分，我将重点放在manual proof上。您尝试过：

Lemma l2: A=B -> False.
apply (fun e:(A=B) => match e with end).
Defined.

在使用 Coq 时应该注意并且经常让我感到不舒服的是，Coq 接受定义错误的定义，它在内部将这些定义重写为类型良好的术语。这允许不那么冗长，因为 Coq 为自己添加了一些部分。但另一方面，Coq 操纵的项与我们输入的项不同。

这就是你证明的情况。自然地，e 上的模式匹配应该涉及构造函数 eq_refl，它是 eq 类型的单个构造函数。在这里，Coq 检测到不存在等式，因此了解如何修改您的代码，但您输入的不是正确的模式匹配。

有两种成分可以帮助理解这里发生的事情：

eq的定义
完整的模式匹配语法，包含 as、in 和 return 项

首先我们可以看一下eq.

的定义

Inductive eq {A : Type} (x : A) : A -> Prop :=  eq_refl : x = x.

请注意，此定义与看起来更自然（无论如何，更对称）的定义不同。

Inductive eq {A : Type} : A -> A -> Prop :=  eq_refl : forall (x:A), x = x.

这非常重要，因为 eq 是用第一个定义而不是第二个定义定义的。特别是，对于我们的问题，重要的是，在 x = y 中，x 是一个参数，而 y 是一个索引。也就是说，x 在所有构造函数中都是常量，而 y 在每个构造函数中可以不同。你和类型Vector.t有同样的区别。如果添加一个元素，向量元素的类型不会改变，这就是它作为参数实现的原因。但是，它的大小可以改变，这就是它作为索引实现的原因。

现在，让我们看看扩展的模式匹配语法。我在这里对我的理解作一个非常简短的解释。不要犹豫，查看 the reference manual 以获得更安全的信息。 return 子句可以帮助指定每个分支都不同的 return 类型。该子句可以使用模式匹配的 as 和 in 子句中定义的变量，它们分别绑定匹配的术语和类型索引。 return 子句将在每个分支的上下文中进行解释，使用此上下文替换 as 和 in 的变量，逐个检查分支，并使用从外部角度输入 match。

这是一个带有 as 子句的人为示例：

Definition test n :=
  match n as n0 return (match n0 with | 0 => nat | S _ => bool end) with
  | 0 => 17
  | _ => true
  end.

根据 n 的值，我们 return 不是同一类型。 test 的类型是 forall n : nat, match n with | 0 => nat | S _ => bool end。但是当 Coq 可以决定我们在哪种情况下匹配时，它可以简化类型。例如：

Definition test2 n : bool := test (S n).

在这里，Coq 知道，无论 n、S n 给 test 什么，结果都会是 bool.

类型的结果

为了平等，我们可以做类似的事情，这次使用 in 子句。

Definition test3 (e:A=B) : False :=
  match e in (_ = c) return (match c with | B => False | _ => True end) with
  | eq_refl => I
  end.

这是怎么回事？本质上，Coq 分别对 match 的分支和 match 本身进行类型检查。在唯一的分支 eq_refl 中， c 等于 A （因为 eq_refl 的定义将索引实例化为与参数相同的值），因此我们声称我们 return 在此处 I 编辑了一些 True 类型的值。但是从外部来看，c等于B（因为e是A=B类型），而这次return子句声称 match return 是 False 类型的某个值。我们在这里使用 Coq 的功能来简化我们刚刚在 test2 中看到的类型中的模式匹配。请注意，我们在 B 以外的其他情况下使用了 True，但我们不需要特别使用 True。我们只需要一些有人居住的类型，这样我们就可以 return eq_refl 分支中的东西。

回到Coq产生的奇怪术语，Coq使用的方法做了类似的事情，但在这个例子上，肯定更复杂。特别是，Coq 在需要无用的类型和术语时经常使用 IDProp 包含 idProp 的类型。它们对应于上面使用的 True 和 I。

最后，我在 coq-club 上给出了 link 的讨论，它确实帮助我理解了 Coq 中如何输入扩展模式匹配。

歧视策略如何运作？

How does the discriminate tactic work?

coq

coq-tactic