如何在 Coq 中使用关于此函数类型的已知信息
How to make use of information known about this function type in Coq
假设我有以下类型 typ 表示 bool 或 nat:
Inductive typ : Type := TB | TN.
我还有一个函数可以从 typ 列表和结果类型中提取实际函数类型：
Fixpoint get_types (s: seq typ) (result_type: Type) : Type :=
match s with
| nil => result_type
| x :: xs => match x with
| TN => nat -> get_types xs result_type
| TB => bool -> get_types xs result_type
end
end.
Example get_types_works : get_types (TB :: TN :: nil) nat = bool -> nat -> nat.
Proof. by []. Qed.
现在，我有另一个函数将 typ 的列表 s 和类型为 get_types s:
的函数作为输入
Fixpoint app (s: seq typ) (constructor: get_types s nat) : nat :=
match s with
| nil => 2 (* Not properly handling empty list case for now *)
| TB :: nil => constructor true
| TN :: nil => constructor 2
| TB :: xs => app xs (constructor true)
| TN :: xs => app xs (constructor 2)
end.
在第 | TB :: nil => constructor true 行定义上述函数失败，其中：
Illegal application (Non-functional construction):
The expression "constructor" of type "get_types s nat" cannot be applied to the term
"true" : "bool"
鉴于这里我们知道get_types s nat的类型应该是bool -> nat，因为s的值是TB :: nil，我想知道是否有办法我们可以让 Coq 知道这一点，以便可以定义上面的函数吗？
如果不是，这是 Coq 的限制还是同样适用于其他依赖类型的语言？
编辑：就上下文而言，这不是我要解决的原始问题；这是一个浓缩版，用于显示我在类型系统方面遇到的问题。在实际版本中，与硬编码 2 和 true 不同，类似 typ 的数据结构还携带要从内存片解析的数据索引和验证函数。 app 的目标是一个函数，该函数获取此类 typ 的列表、切片和包含此类类型的记录的构造函数，然后根据类型的索引构造该记录的实例解析，或者 returns None 如果任何验证失败。
原则上你想要什么都没有错。然而，至少在 Coq 中，有一些简单的规则来说明如何对模式匹配进行类型检查，以便可以在类型中使用有关使用哪个构造函数的信息。表面语言（在本例中为 Gallina）通过帮助编译（或 desugar）模式匹配来隐藏这种简单性，因此作为用户，您可以编写比底层系统必须处理的更复杂的模式和。我对 Idris 不是很熟悉，但是基于依赖模式匹配的复杂程度，我怀疑你 运行 在那里有类似的限制，你必须将你的代码放入系统可以输入检查的表单中。
在这里，您 运行 遇到了此模式匹配编译的两个限制。首先是构造函数的类型不是基于 s 上的匹配特化的。这很容易通过从 get_types s nat -> nat 计算一个函数来解决，编译器是正确的。
Require Import List.
Import ListNotations.
Inductive typ : Type := TB | TN.
Fixpoint get_types (s: list typ) (result_type: Type) : Type :=
match s with
| nil => result_type
| x :: xs => match x with
| TN => nat -> get_types xs result_type
| TB => bool -> get_types xs result_type
end
end.
Fail Fixpoint app (s: list typ) : get_types s nat -> nat :=
match s with
| nil => fun constructor => 2
| TB :: nil => fun constructor => constructor true
| TN :: nil => fun constructor => constructor 2
| TB :: xs => fun constructor => app xs (constructor true)
| TN :: xs => fun constructor => app xs (constructor 2)
end.
(* fails due to limitation of termination checker with nested matches *)
...但是你 运行 遇到了终止检查器的第二个问题。请注意，您的匹配很复杂：它分析 s 的结构及其头部和尾部（如果它是用 cons 构建的）。最终，所有模式匹配都被编译为单个归纳类型上的嵌套模式匹配。如果你看一下这个展开，你正在将 s 分解为 t::xs，然后再次将 xs 分解为 t0::xs'，最后在 xs 上递归。不幸的是，Coq 终止检查器只将其视为 t0::xs' 而不会将其识别为 s 的子项（它确实需要 xs）。
我很难以类型检查的方式手动编写您的函数，但这里有一个使用功能正确的策略编写的版本。请注意，它产生的定义比任何普通模式匹配都要复杂得多，因为它必须维护 destruct_with_eqn 产生的证明。但是，该证明对于同时使用 xs 使终止检查器满意并揭示 t0::xs' 对构造函数的应用程序进行类型检查至关重要。它可能很复杂，但您仍然可以 运行 它就好了，如最后一行所示。
Fixpoint app (s: list typ) (constructor: get_types s nat) {struct s} : nat.
destruct s as [|t xs]; simpl in *.
exact 2.
destruct_with_eqn xs; simpl in *.
destruct t; [ exact (constructor true) | exact (constructor 2) ].
destruct t; simpl in *.
- apply (app xs).
subst.
exact (constructor true).
- apply (app xs).
subst.
exact (constructor 2).
Defined.
Eval compute in app [TB; TN] (fun x y => if x then y+2 else y).
(* = 4
: nat
*)
因为你用 Idris 标记了它，这里是它在那里的工作方式：
data Typ = TB | TN
get_types : (args : List Typ) -> (res : Type) -> Type
get_types [] res = res
get_types (TB :: xs) res = Bool -> get_types xs res
get_types (TN :: xs) res = Nat -> get_types xs res
app : (args : List Typ) -> (con : get_types args Nat) -> Nat
app [] con = 2
app (TB :: []) con = con True
app (TN :: []) con = con 2
app (TB :: xs) con = app xs (con True)
app (TN :: xs) con = app xs (con 2)
基本上，您没有问题，因为在 args 上进行匹配，编译器还会推断出 con 的类型。例如，如果您将最后一个案例替换为
app (TN :: xs) con = ?hole
并调查漏洞，您会看到编译器有关于 con:
的新信息
xs : List Typ
con : Nat -> get_types xs Nat
--------------------------------------
hole : Nat
好吧，我不确定你到底想做什么，但是将你的代码提交到 "convoy" 模式的第一步确实是为你的类型解释添加更多的结构。如果你将类型的解释与类型列表的解释分开，你可以很容易地得到一个框架工作：
From mathcomp Require Import all_ssreflect.
Set Implicit Arguments.
Unset Strict Implicit.
Unset Printing Implicit Defensive.
Inductive Typ := TB | TN.
(* Interpretation for types *)
Definition iT w : Type :=
match w with | TB => bool | TN => nat end.
(* Default witness *)
Definition dw w : iT w :=
match w with | TB => true | TN => 2 end.
Definition get_types (res : Type) := fix gt (args : list Typ) :=
match args with
| [::] => res
| [:: w & xs] => iT w -> gt xs
end.
Variable (dt : Typ).
Fixpoint app (args : list Typ) : get_types (iT dt) args -> iT dt :=
match args with
| [::] => fun gt => dw dt
| [:: tw & xs] => fun gt => app (gt (dw tw))
end.
请注意，我也概括了 return 类型，因为没有充分的理由将定义硬编码为 nat。一个有趣的练习是修改上面的 app 函数并证明它等价于 tactic-based 版本的 Tej.
另外两种定义方式app。
第一个使用战术，依靠induction而不是Fixpoint。
Definition app (s: seq typ) (constructor: get_types s nat) : nat.
Proof.
induction s as [|t xs].
- exact 2.
- destruct xs.
+ destruct t.
* exact (constructor true).
* exact (constructor 2).
+ destruct t.
* exact (IHxs (constructor true)).
* exact (IHxs (constructor 2)).
Defined.
第二个使用 Gallina 并复合 pattern-matchings。
Fixpoint app (s: seq typ) : get_types s nat -> nat :=
match s return get_types s nat -> nat with
| nil => fun _ => 2
| x :: xs =>
match xs as xs0 return xs = xs0 -> get_types (x::xs0) nat -> nat with
| nil => fun _ => match x return get_types (x::nil) nat -> nat with
| TB => fun c => c true
| TN => fun c => c 2
end
| _ => fun e => match e in _ = xs1 return get_types (x::xs1) nat -> nat with
| eq_refl =>
match x return get_types (x::xs) nat -> nat with
| TB => fun c => app xs (c true)
| TN => fun c => app xs (c 2)
end
end
end eq_refl
end.
当析构 xs 时，我们记住原始 xs 和它被析构的内容之间的相等性。我们在 nil 分支中不需要这个相等性并用fun _。在另一个分支中，我们 pattern-match 证明等式 (match e)，这对应于使用此等式的重写。在 eq_refl 分支内，我们可以使用原始的 xs 并因此进行终止检查器允许的递归调用。在 pattern-match 之外，我们 return 是 xs 上的 pattern-match 期望的正确类型。最后要做的是提供 xs 和 xs0 相等的证明，但这很简单 eq_refl.
假设我有以下类型 typ 表示 bool 或 nat:
Inductive typ : Type := TB | TN.
我还有一个函数可以从 typ 列表和结果类型中提取实际函数类型：
Fixpoint get_types (s: seq typ) (result_type: Type) : Type :=
match s with
| nil => result_type
| x :: xs => match x with
| TN => nat -> get_types xs result_type
| TB => bool -> get_types xs result_type
end
end.
Example get_types_works : get_types (TB :: TN :: nil) nat = bool -> nat -> nat.
Proof. by []. Qed.
现在，我有另一个函数将 typ 的列表 s 和类型为 get_types s:
Fixpoint app (s: seq typ) (constructor: get_types s nat) : nat :=
match s with
| nil => 2 (* Not properly handling empty list case for now *)
| TB :: nil => constructor true
| TN :: nil => constructor 2
| TB :: xs => app xs (constructor true)
| TN :: xs => app xs (constructor 2)
end.
在第 | TB :: nil => constructor true 行定义上述函数失败，其中：
Illegal application (Non-functional construction):
The expression "constructor" of type "get_types s nat" cannot be applied to the term
"true" : "bool"
鉴于这里我们知道get_types s nat的类型应该是bool -> nat，因为s的值是TB :: nil，我想知道是否有办法我们可以让 Coq 知道这一点，以便可以定义上面的函数吗？
如果不是，这是 Coq 的限制还是同样适用于其他依赖类型的语言？
编辑：就上下文而言，这不是我要解决的原始问题；这是一个浓缩版，用于显示我在类型系统方面遇到的问题。在实际版本中，与硬编码 2 和 true 不同，类似 typ 的数据结构还携带要从内存片解析的数据索引和验证函数。 app 的目标是一个函数，该函数获取此类 typ 的列表、切片和包含此类类型的记录的构造函数，然后根据类型的索引构造该记录的实例解析，或者 returns None 如果任何验证失败。
原则上你想要什么都没有错。然而，至少在 Coq 中，有一些简单的规则来说明如何对模式匹配进行类型检查，以便可以在类型中使用有关使用哪个构造函数的信息。表面语言（在本例中为 Gallina）通过帮助编译（或 desugar）模式匹配来隐藏这种简单性，因此作为用户，您可以编写比底层系统必须处理的更复杂的模式和。我对 Idris 不是很熟悉，但是基于依赖模式匹配的复杂程度，我怀疑你 运行 在那里有类似的限制，你必须将你的代码放入系统可以输入检查的表单中。
在这里，您 运行 遇到了此模式匹配编译的两个限制。首先是构造函数的类型不是基于 s 上的匹配特化的。这很容易通过从 get_types s nat -> nat 计算一个函数来解决，编译器是正确的。
Require Import List.
Import ListNotations.
Inductive typ : Type := TB | TN.
Fixpoint get_types (s: list typ) (result_type: Type) : Type :=
match s with
| nil => result_type
| x :: xs => match x with
| TN => nat -> get_types xs result_type
| TB => bool -> get_types xs result_type
end
end.
Fail Fixpoint app (s: list typ) : get_types s nat -> nat :=
match s with
| nil => fun constructor => 2
| TB :: nil => fun constructor => constructor true
| TN :: nil => fun constructor => constructor 2
| TB :: xs => fun constructor => app xs (constructor true)
| TN :: xs => fun constructor => app xs (constructor 2)
end.
(* fails due to limitation of termination checker with nested matches *)
...但是你 运行 遇到了终止检查器的第二个问题。请注意，您的匹配很复杂：它分析 s 的结构及其头部和尾部（如果它是用 cons 构建的）。最终，所有模式匹配都被编译为单个归纳类型上的嵌套模式匹配。如果你看一下这个展开，你正在将 s 分解为 t::xs，然后再次将 xs 分解为 t0::xs'，最后在 xs 上递归。不幸的是，Coq 终止检查器只将其视为 t0::xs' 而不会将其识别为 s 的子项（它确实需要 xs）。
我很难以类型检查的方式手动编写您的函数，但这里有一个使用功能正确的策略编写的版本。请注意，它产生的定义比任何普通模式匹配都要复杂得多，因为它必须维护 destruct_with_eqn 产生的证明。但是，该证明对于同时使用 xs 使终止检查器满意并揭示 t0::xs' 对构造函数的应用程序进行类型检查至关重要。它可能很复杂，但您仍然可以 运行 它就好了，如最后一行所示。
Fixpoint app (s: list typ) (constructor: get_types s nat) {struct s} : nat.
destruct s as [|t xs]; simpl in *.
exact 2.
destruct_with_eqn xs; simpl in *.
destruct t; [ exact (constructor true) | exact (constructor 2) ].
destruct t; simpl in *.
- apply (app xs).
subst.
exact (constructor true).
- apply (app xs).
subst.
exact (constructor 2).
Defined.
Eval compute in app [TB; TN] (fun x y => if x then y+2 else y).
(* = 4
: nat
*)
因为你用 Idris 标记了它，这里是它在那里的工作方式：
data Typ = TB | TN
get_types : (args : List Typ) -> (res : Type) -> Type
get_types [] res = res
get_types (TB :: xs) res = Bool -> get_types xs res
get_types (TN :: xs) res = Nat -> get_types xs res
app : (args : List Typ) -> (con : get_types args Nat) -> Nat
app [] con = 2
app (TB :: []) con = con True
app (TN :: []) con = con 2
app (TB :: xs) con = app xs (con True)
app (TN :: xs) con = app xs (con 2)
基本上，您没有问题，因为在 args 上进行匹配，编译器还会推断出 con 的类型。例如，如果您将最后一个案例替换为
app (TN :: xs) con = ?hole
并调查漏洞，您会看到编译器有关于 con:
xs : List Typ
con : Nat -> get_types xs Nat
--------------------------------------
hole : Nat
好吧，我不确定你到底想做什么，但是将你的代码提交到 "convoy" 模式的第一步确实是为你的类型解释添加更多的结构。如果你将类型的解释与类型列表的解释分开，你可以很容易地得到一个框架工作：
From mathcomp Require Import all_ssreflect.
Set Implicit Arguments.
Unset Strict Implicit.
Unset Printing Implicit Defensive.
Inductive Typ := TB | TN.
(* Interpretation for types *)
Definition iT w : Type :=
match w with | TB => bool | TN => nat end.
(* Default witness *)
Definition dw w : iT w :=
match w with | TB => true | TN => 2 end.
Definition get_types (res : Type) := fix gt (args : list Typ) :=
match args with
| [::] => res
| [:: w & xs] => iT w -> gt xs
end.
Variable (dt : Typ).
Fixpoint app (args : list Typ) : get_types (iT dt) args -> iT dt :=
match args with
| [::] => fun gt => dw dt
| [:: tw & xs] => fun gt => app (gt (dw tw))
end.
请注意，我也概括了 return 类型，因为没有充分的理由将定义硬编码为 nat。一个有趣的练习是修改上面的 app 函数并证明它等价于 tactic-based 版本的 Tej.
另外两种定义方式app。
第一个使用战术，依靠induction而不是Fixpoint。
Definition app (s: seq typ) (constructor: get_types s nat) : nat.
Proof.
induction s as [|t xs].
- exact 2.
- destruct xs.
+ destruct t.
* exact (constructor true).
* exact (constructor 2).
+ destruct t.
* exact (IHxs (constructor true)).
* exact (IHxs (constructor 2)).
Defined.
第二个使用 Gallina 并复合 pattern-matchings。
Fixpoint app (s: seq typ) : get_types s nat -> nat :=
match s return get_types s nat -> nat with
| nil => fun _ => 2
| x :: xs =>
match xs as xs0 return xs = xs0 -> get_types (x::xs0) nat -> nat with
| nil => fun _ => match x return get_types (x::nil) nat -> nat with
| TB => fun c => c true
| TN => fun c => c 2
end
| _ => fun e => match e in _ = xs1 return get_types (x::xs1) nat -> nat with
| eq_refl =>
match x return get_types (x::xs) nat -> nat with
| TB => fun c => app xs (c true)
| TN => fun c => app xs (c 2)
end
end
end eq_refl
end.
当析构 xs 时，我们记住原始 xs 和它被析构的内容之间的相等性。我们在 nil 分支中不需要这个相等性并用fun _。在另一个分支中，我们 pattern-match 证明等式 (match e)，这对应于使用此等式的重写。在 eq_refl 分支内，我们可以使用原始的 xs 并因此进行终止检查器允许的递归调用。在 pattern-match 之外，我们 return 是 xs 上的 pattern-match 期望的正确类型。最后要做的是提供 xs 和 xs0 相等的证明，但这很简单 eq_refl.