选择要重写的子项的惯用方法

Question

假设我们有一个形式的结论：a + b + c + d + e.
我们还有一个引理：plus_assoc : forall n m p : nat, n + (m + p) = n + m + p.

任意 "insert a pair of parentheses" 成术语的惯用方法是什么？也就是说，如果有多个可用的地方，我们如何轻松地选择在哪里重写。

我通常最终会做以下事情：

replace (a + b + c + d + e)
with (a + b + c + (d + e))
by now rewrite <- ?plus_assoc

虽然这个公式确实说明了我想做的事情，对于比 "a b c...".

更复杂的公式，它变得非常啰嗦

Answer 1

IMO 你最好的选择是使用 ssreflect 模式选择语言，在 Coq 8.7 中可用，或者通过在早期版本中安装 math-comp。该语言记录在手册中：https://hal.inria.fr/inria-00258384

示例（针对 Coq 8.7）：

(* Replace with From mathcomp Require ... in Coq < 8.7 *)
From Coq Require Import ssreflect ssrfun ssrbool.

Lemma addnC n m : m + n = n + m. Admitted.
Lemma addnA m n o : m + (n + o) = m + n + o. Admitted.

Lemma example m n o p : n + o + p + m = m + n + o + p.
Proof. by rewrite -[_ + _ + o]addnA -[m + _ + p]addnA [m + _]addnC.
Qed.

Answer 2

rewrite <- lemma 期望 lemma 是等式，即类型为 something1 = something2 形式的项。与大多数其他策略一样，您也可以向它传递一个 returns 等式的函数，即类型为 forall param1 … paramN, something1 = something2 形式的项，在这种情况下，Coq 将寻找它所在的位置可以将引理应用于参数以形成目标的子项。 Coq 的算法是确定性的，但让它选择并不是特别有用，除非执行重复重写最终耗尽所有可能性。这里 Coq 碰巧用 rewrite <- plus_assoc 选择了你想要的目标，但我认为这只是一个例子，你正在追求一般技术。

您可以通过向引理提供更多参数来更好地控制在何处执行重写，以获得更具体的相等性。例如，如果你想指定 (((a + b) + c) + d) + e 应该变成 ((a + b) + c) + (d + e)，即关联性引理应该应用于参数 (a + b) + c、d 和 e, 你可以写

rewrite <- (plus_assoc ((a + b) + c) d e).

您无需提供所有参数，只需提供足够精确定位要应用引理的位置即可。例如，在这里，将 d 指定为第二个参数就足够了。您可以通过完全省略第三个参数并将通配符 _ 指定为第一个参数来完成此操作。

rewrite <- (plus_assoc _ d).

偶尔会有相同的子项，而您只想重写其中一个。在这种情况下，您不能单独使用 rewrite 策略系列。一种方法是使用 replace 和更大的术语，您可以在其中选择要更改的内容，或者使用事件 assert 来替换整个目标。另一种方法是使用 set 策略，它让您为特定出现的子项命名，然后依靠该名称来识别特定的子项，最后调用 subst 摆脱完成后命名。

另一种方法是忘记应用哪些引理，只需指定您希望如何使用 assert 或普通 replace … with …. 之类的内容来更改目标。然后让 congruence、omega、solve [firstorder] 等自动化策略找到使证明有效的参数。使用这种方法，您确实必须写下目标的大部分内容，但可以节省指定引理的时间。哪种方法最有效取决于你在大证明上的位置以及在开发过程中什么趋于稳定而什么不是。

Answer 3

如果您不想证明辅助引理，那么您的选择之一是使用 Ltac 对您手上的等式结构进行模式匹配。这样您就可以将任意复杂的子表达式绑定到模式变量：

Require Import Coq.Arith.Arith.

Goal forall a b c d e,
    (a + 1 + 2) + b + c + d + e = (a + 1 + 2) + (b + c + d) + e -> True.
  intros a b c d e H.
  match type of H with ?a + ?b + ?c + ?d + ?e = _ =>
    replace (a + b + c + d + e)
       with (a + (b + c + d) + e)
    in H
    by now rewrite <- ?plus_assoc
  end.
Abort.

上面这段代码中?a代表a + 1 + 2。当然，如果您处理的是简单变量，这不会有任何改善，只有当您处理复杂的嵌套表达式时，它才会有所帮助。

此外，如果你需要重写目标中的东西，那么你可以使用这样的东西：

match goal with
  | |- ?a + ?b + ?c + ?d + ?e = _ => <call your tactics here>

选择要重写的子项的惯用方法

Idiomatic ways of selecting subterm to rewrite

coq