道具中的牛山羊布道

Question

Bove-Capretta 方法 (http://www.cs.nott.ac.uk/~pszvc/publications/General_Recursion_MSCS_2005.pdf) 是在 Agda 等语言中对非结构递归或部分函数进行建模的巧妙技巧。函数的终止输入以归纳谓词为特征，并且函数被重写以将谓词作为参数。

例如，假设我们想在 Agda 中编写以下以 2 为底的对数的定义（使用模块 Data.Nat）：

log2 : ℕ → ℕ
log2 0 = 0
log2 1 = 0
log2 n = suc (log2 ⌊ n /2⌋)

不幸的是，这个定义没有通过终止检查器。遵循 Bove-Capretta，可以定义以下谓词：

data Loggable : ℕ → Set where
    log-n≡0 : Loggable 0
    log-n≡1 : Loggable 1
    log-n≡n : ∀ {n} → Loggable ⌊ n /2⌋ → Loggable n

然后扩充原始定义以将 Loggable 作为额外参数：

log2 : (n : ℕ) → Loggable n → ℕ
log2 0 _ = 0
log2 1 _ = 1
log2 n (log-n≡n p) = suc (log2 ⌊ n /2⌋ p)

这现在成功地通过了终止检查器，因为 Loggable 谓词用作结构递减的参数。这一切都按预期工作。

现在，由于谓词仅用于说服终止检查器，因此将其移动到排序 Prop 是有意义的，因为它不应该有任何计算效果。事实上，检查我们对 log2 的新定义也表明了这一点，因为谓词不用于进行任何尚未由另一个参数确定的案例拆分。

这就是问题所在。首先，使 Loggable 成为 Prop 禁止在我们按 Set 排序生成某些内容时对其进行大小写拆分，这在我们的新 log2 函数中就是这种情况。正常的解决办法是在排序Prop中引入一个辅助的“求逆引理”，它会破坏谓词并提取我们需要的部分。不幸的是，这引入了一个新问题——log2 的结构终止将被破坏，因为 Agda 无法看到调用“反转引理”的结果在结构上小于其输入。

（请注意，这个问题的等价物可以用 Coq 编写，它不会遇到同样的问题，因为它在检查终止之前对表达式进行规范化，因此提出了“求逆引理”方法成功。)

Answer 1

与 Coq 中的 Prop 不同（但与 sProp 相似），Agda 的 Prop 宇宙支持 定义证明无关性 。这意味着 Prop 中类型的任意两个元素在定义上等于转换检查器。另一方面，这也意味着术语的评估永远不会卡在 Prop 类型的参数上，因此这些参数不能用于证明终止。所以不幸的是，这意味着 Bove-Capretta 方法不适用于 Agda 的 Prop 宇宙。

道具中的牛山羊布道

Bove-Capretta Predicate in Prop

recursion

agda

dependent-type