Coq

Question

我是 Coq 的新手，希望有更多经验的人可以帮助我解决我面临的问题。

我已经定义了一个关系来表示一个虚构的编程语言中的程序的评估。该语言的目标是在单一语义下统一函数调用和宏调用的受限子集。这是关系的定义，它的第一个构造函数（我省略了其余部分以保存 space 并避免不必要的细节）。

Inductive EvalExpr:
  store ->         (* Store, mapping L-values to R-values *)
  environment ->   (* Local environment, mapping function-local variables names to L-values *)
  environment ->   (* Global environment, mapping global variables names to L-values *) 
  function_table ->(* Mapping function names to function definitions *)
  macro_table ->   (* Mapping macro names to macro definitions *)
  expr ->          (* The expression to evaluate *)
  Z ->             (* The value the expression terminates to *)
  store ->         (* The final state of the program store after evaluation *)
  Prop :=
  (* Numerals evaluate to their integer representation and do not
     change the store *)
  | E_Num : forall S E G F M z,
    EvalExpr S E G F M (Num z) z S
    ...

映射定义如下：

Module Import NatMap := FMapList.Make(OrderedTypeEx.Nat_as_OT).
Module Import StringMap := FMapList.Make(OrderedTypeEx.String_as_OT).

Definition store : Type := NatMap.t Z.
Definition environment : Type := StringMap.t nat.
Definition function_table : Type := StringMap.t function_definition.
Definition macro_table : Type := StringMap.t macro_definition.

我认为其他类型的定义与这个问题无关，但如果需要我可以添加它们。

现在，当我试图证明以下直觉上显而易见的引理时，我陷入了困境：

Lemma S_Equal_EvalExpr_EvalExpr : forall S1 S2,
  NatMap.Equal S1 S2 ->
  forall E G F M e v S',
  EvalExpr S1 E G F M e v S' <-> EvalExpr S2 E G F M e v S'.
Proof.
  intros. split.
  (* -> *)
  - intros. induction H0.
    + (* Num *)
      Fail constructor.
      Abort.

如果我能够在目标中为 S1 重写 S2，证明将是微不足道的；但是，如果我尝试这样做，我会收到以下错误：

H : NatMap.Equal S S2
(* Other premises *)
---------------------
EvalExpr S2 E G F M (Num z) z S


rewrite <- H.

Found no subterm matching "NatMap.find (elt:=Z) ?M2433 S2" in the current goal.

我认为这与有限映射是抽象类型有关，因此不像具体类型那样可重写。但是，我注意到我可以重写 Coq.FSets.FMapFacts 中其他 equations/relations 中的映射。我如何告诉 Coq 让我重写我的 EvalExpr 关系中的映射类型？

更新：Here is a gist 包含我的问题的最小工作示例。为简洁起见，更改了一些映射类型的定义，但问题是一样的。

Answer 1

这里的问题是表示两个映射具有相同绑定的关系 NatMap.Equal 与 Coq 逻辑中的相等概念不相同, =。虽然总是可以用 = 重写，但只有当你能证明你试图显示的属性与它兼容时，才能用其他关系 R 重写。这已经为 FMap 中的关系完成，这就是为什么重写那里有效的原因。

您有两个选择：

将 FMap 替换为预期映射等式与 = 一致的实现，属性通常称为 扩展性 。有很多库提供这样的数据结构，包括我自己的extructures, but also finmap and std++。然后，您永远不需要担心自定义相等关系；地图的所有重要属性都适用于 =.
保留FMap，但使用generalized rewriting机制允许用FMap.Equal重写。为此，您可能需要修改执行关系的定义，使其与 FMap.Equal 兼容。不幸的是，我认为做到这一点的唯一方法是在各处显式添加相等假设，例如
```
Definition EvalExpr' S E G F M e v S' :=
  exists S0 S0', NatMap.Equal S S0 /\
                 NatMap.Equal S' S0' /\
                 EvalExpr S0 E G F M e v S0'.
```
因为这会污染你的定义，我不推荐这种方法。

Answer 2

亚瑟的回答很好的说明了问题

另一种 (?) 方法是修改 EvalExpr 的 Inductive 定义以明确使用您关心的相等性（NatMap.Equal 而不是 Eq） .你必须在每个规则中说两个地图相等就足够了。

例如：

  | E_Num : forall S E G F M z, 
      EvalExpr S E G F M (Num z) z S

变成

  | E_Num : forall S1 S2 E G F M z, 
      NatMap.Equal S1 S2 ->
      EvalExpr S1 E G F M (Num z) z S2

那么当你想证明你的引理并应用构造函数时，你将不得不提供一个证明S1和S2相等。（你必须使用 NatMap.Equal 是一个等价关系进行一些推理）。

Coq - 在关系中重写 FMap

Coq - Rewriting a FMap Within a Relation

programming-languages

proof