什么是阳性检查?

What is positivity checking?

显然,Agda 中有一些称为积极性检查的功能,它显然可以保持系统正常运行 even if type-in-type is enabled

我很想知道这是怎么回事,但是 the Agda Manual fails to answer the question, and only explains how to turn it off

在午餐时 table 我无意中听说这是关于 polarity in type theory,但我所知道的就这些。我没能在网上找到任何解释这个概念的东西,以及为什么它对保持稳健性有用。任何可理解的解释将不胜感激。

首先,我必须澄清一个误解:当输入类型启用时,积极性检查并不能保证可靠性。因此,数据类型必须同时满足正性检查和全域检查以保持稳健性。

现在,为了解释正性检查,让我们先看一个没有正性检查的反例:

-- the empty type
data ⊥ : Set where

-- a non-positive type
data Bad : Set where
  bad : (Bad → ⊥) → Bad

假设这个数据类型是允许的,那么你可以很容易地证明 :

bad-is-false : Bad → ⊥
bad-is-false (bad f) = f (bad f)

bad-is-true : Bad
bad-is-true = bad bad-is-false

boom : ⊥
boom = bad-is-false bad-is-true

在 Curry-Howard 对应关系下,Bad 的定义是:当且仅当 Bad 为假时,Bad 为真。所以导致不一致也就不足为奇了。

阳性检查排除了 Bad 等数据类型。通常,(严格的)正性标准表示数据类型 D 的每个构造函数 c 应该具有形式

的类型
c : (x1 : A1)(x2 : A2) ... (xn : An) → D xs

其中每个参数的类型 Ai 要么是非递归的(即它不引用 D),要么是 (y1 : B1)(y2 : B2) ... (ym : Bm) → D ys 的形式,其中每个 Bj 都不是参考D

Bad 不满足此条件,因为构造函数 bad 的参数具有类型 Bad → ⊥,这两种形式都不是。

'positivity checking' 这个名字(就像类型论中的许多东西一样)来自范畴论,特别是正内函子的概念。满足正性标准的数据类型的每个定义都是类型类别上的正内函子。这意味着我们可以构造那个内函子的 initial algebra ,它可以在构造类型理论模型(用于证明可靠性)时用于对数据类型建模。