依赖强制语言的一致性是什么意思？

Question

来自 https://ghc.haskell.org/trac/ghc/wiki/DependentHaskell,

unlike Coq and Agda, Haskell relies on the consistency of a coercion language, which is not threatened by * :: *. See the paper for more details.

引用的 "paper" 是 broken link，但是，通过谷歌搜索和阅读，我注意到它描述了如何向系统 FC 添加显式种类相等性，但没有直接解决隐式问题: 依赖强制语言的一致性是什么意思?

Answer 1

Coq 和 Agda 是依赖类型总种语言。他们受到相关类型理论基础的启发，这些基础涉及（类型化的）lambda 演算，它是（强）归一化的。这意味着减少任何 lambda 项最终必须停止。

这属性使得使用 Coq 和 Agda 作为证明系统成为可能：人们可以使用它们来证明数学事实。事实上，根据 Curry-Howard 对应关系，if

someExpression :: someType

那么someType对应一个逻辑（直觉）重言式

在Haskell中不是这样，因为任何类型都可以"proved"被

undefined :: someType

即我们可以使用 "bottom" 值作弊。这使得 Haskell 作为逻辑不一致。例如，我们可以证明 undefined :: Data.Void.Void，它对应于逻辑命题 "false"。这很糟糕，但这是为无限递归付出的必要代价，它允许非终止程序。

相比之下，Coq 和 Agda 只有原始递归（永远不会永远递归）。

现在，进入正题。众所周知，在 Coq / Agda 中添加公理 * :: * 会使逻辑不再一致。我们可以使用吉拉德悖论推导出 "false" 的证明。那将是非常糟糕的，因为我们甚至可以证明 lemma :: Int :~: String 之类的东西，并推导出一个强制函数 coerce :: Int -> String.

lemma :: Int :~: String
lemma = -- exploit Girard's paradox here

-- using Haskell syntax:
coerce :: Int -> String
coerce x = case lemma of Refl -> x

如果我们天真地实现它，coerce 将简单地执行一个不安全的转换，重新解释底层位——毕竟，lemma 证明了这些类型正是相同的！那样的话，我们甚至会失去运行时类型安全性。末日在等着我们。

在Haskell中，即使我们不加* :: *也是不一致的，所以我们可以简单地有

lemma = undefined

并得出 coerce 无论如何！所以，添加 * :: * 并没有真正增加问题的数量。这只是不一致的另一个来源。

然后有人可能想知道为什么 Haskell coerce 是类型安全的。那么，在 Haskell 中 case lemma of Refl ->... 强制评估 lemma。这只能触发异常，或无法终止，因此永远不会到达 ... 部分。 Haskell 可以不能优化 coerce 作为不安全的转换，不像 Agda / Coq。

引用的段落提到了 Haskell 的另一个方面：强制语言。在内部，当我们写

case lemma1 of
  Refl -> case lemma2 of
    Refl -> ...
      ...
        Refl -> expression

我们引入了许多必须利用的类型等式来证明 expression 确实具有所需的类型。在 Coq 中，程序员必须使用复杂的匹配形式（依赖匹配）来证明在何处以及如何利用类型等式。在 Haskell 中，编译器为我们编写了这个证明（在 Coq 中，类型系统更丰富，这将涉及更高阶的统一，我认为，这是不可判定的）。这个证明不是用 Haskell 写的！事实上，Haskell 是不一致的，所以我们不能依赖它。相反，Haskell 为此使用了另一种自定义强制转换语言，它保证是一致的。我们只需要依靠它。

如果我们转储 Core，我们可以看到一些内部强制语言的一瞥。例如，编译传递性证明

trans :: a :~: b -> b :~: c -> a :~: c
trans Refl Refl = Refl

我们得到

GADTtransitivity.trans
  :: forall a_au9 b_aua c_aub.
     a_au9 :~: b_aua -> b_aua :~: c_aub -> a_au9 :~: c_aub
[GblId, Arity=2, Caf=NoCafRefs, Str=DmdType]
GADTtransitivity.trans =
  \ (@ a_auB)
    (@ b_auC)
    (@ c_auD)
    (ds_dLB :: a_auB :~: b_auC)
    (ds1_dLC :: b_auC :~: c_auD) ->
    case ds_dLB of _ [Occ=Dead] { Refl cobox0_auF ->
    case ds1_dLC of _ [Occ=Dead] { Refl cobox1_auG ->
    (Data.Type.Equality.$WRefl @ * @ a_auB)
    `cast` ((<a_auB>_N :~: (Sym cobox0_auF ; Sym cobox1_auG))_R
            :: ((a_auB :~: a_auB) :: *) ~R# ((a_auB :~: c_auD) :: *))
    }
    }

注意最后的cast，它利用了强制语言中的证明

(<a_auB>_N :~: (Sym cobox0_auF ; Sym cobox1_auG))_R

在这个证明中，我们可以看到 Sym cobox0_auF ; Sym cobox1_auG 我猜它使用对称性 Sym 和传递性 ; 来达到想要的目标：证明 Refl :: a_auB :~: a_auB 确实可以安全地投射到想要的 a_auB :~: c_auD.

最后，请注意，我很确定这些证明在 GHC 编译期间会被丢弃，并且 cast 最终会在运行时减少为不安全的转换（case 仍然评估两个输入证明，以保持类型安全）。但是，拥有中间证明可以有力地确保编译器做正确的事情。

依赖强制语言的一致性是什么意思？

What does it mean to rely on the consistency of a coercion language?

haskell

functional-programming

coercion