如何判断依赖匹配两个 nat 是否相等

Question

我正在设计一种使用参数化高阶抽象语法 PHOAS. In it, I'm using bit vectors from the bbv library 的语言，它看起来像 word : nat -> Set。

现在，在经典的 PHOAS 语法中，我为变量创建了一个内部类型，并为该类型提供了一个表示：

Require Import bbv.Word.
Inductive type : Set :=
  | UI : nat -> type.

Definition type_denote (t : type) : Set :=
  match t with
  | UI n => word n
  end.

最终，我希望在此 PHOAS 之上为一种语言提供一个简单的基于堆栈的状态概念，因此我也有 "value"s:

Inductive value :=
| UI_value n : word n -> value.
Definition state := (nat * (nat -> option value))%type.

从转换 一个值是我遇到的问题。这是我想要发生的事情：

Fail Definition fromValue_pseudo := (t : type) (v : value) : option (type_denote t) := match (t,v) as x return option (type_denote (fst x)) with | (UI m1, UI_value m2 n) (* and m1 = m2 *) => Some n | (UI m1, UI_value m2 n) (* and m1 <> m2 *) => None end.

我如何告诉从属匹配如果 m1 = m2，则 Some n 具有类型 word m1 和 word m2 ？

Answer 1

Pattern-match on Nat.dec_eq m2 m1 对m1和m2是否相等进行案例分析，如果相等，则pattern-match on the equality proof到 "transport" n : word m2 到 word m1 （下面是通过 eq_rec 完成的）。

Definition fromValue_pseudo (t : type) (v : value)
  : option (type_denote t) :=
  let '(UI m1) := t in
  let '(UI_value m2 n) := v in
  match Nat.eq_dec m2 m1 with   (* [Nat.eq_rec m1 m2] would require to then flip the equality, or transport a function [word m1 -> word m1] to [word m2 -> word m1], both of which take more typing. *)
  | left e => Some (eq_rec _ word n _ e)
  | right _ => None
  end.

如何判断依赖匹配两个 nat 是否相等

How to tell a dependent match two nats are equal

coq

dependent-type