Agda中数据结构的导数

Question

我目前正在 Agda 中实现常规数据结构的派生，如 Conor McBride [5] 的 One-Hole 上下文论文中所述

在直接从 OHC 论文中实现它时，Löh 和 Magalhães [3,4] 也完成了它，我们只剩下 ⟦_⟧ 函数以红色突出显示，因为 Agda 无法判断 μ 和 I 情况是否会一起终止。 Löh & Magalhães 在 their repository.

中对此发表了评论

其他论文也在他们的论文[7,8]中包含了类似的实现或定义，但没有有一个回购协议（至少我没能找到它）[1,2,6]，或者他们遵循不同的方法 [9]，其中 μ 是单独定义的来自 Reg、⟦_⟧ 和 derive（或在他们的情况下的剖析），没有环境，并且操作在堆栈上执行。

使用 {-# TERMINATING #-} 或 {-# NON_TERMINATING #-} 标志是不受欢迎的。特别是，任何使用 ⟦_⟧ 的东西都不会正常化，因此我不能用这个函数来证明任何事情。

下面的实现是对 OHC 实现的轻微修改。它删除了作为 Reg 结构定义一部分的弱化和替换。起初，这让 ⟦_⟧ 高兴！但是我在实现的时候发现了类似的问题 derive -- Agda 的终止检查器对 μ 情况不满意。

我没能成功说服 Agda derive 终止。我想知道是否有人成功地实施了 derive 签名 derive : {n : ℕ} → (i : Fin n) → Reg n → Reg n

下面的代码只显示了一些重要的部分。我在其余定义中包含了一个要点，其中包括定义替换和弱化以及无法终止的派生。

 -- Regular universe, multivariate.
 -- n defines the number of variables
 data Reg : ℕ → Set₁ where
   0′    : {n : ℕ} → Reg n
   1′    : {n : ℕ} → Reg n
   I     : {n : ℕ} → Fin n → Reg n 
   _⨁_  : {n : ℕ} → (l r : Reg n) → Reg n
   _⨂_  : {n : ℕ} → (l r : Reg n) → Reg n
   μ′    : {n : ℕ} → Reg (suc n)   → Reg n

 infixl 30 _⨁_
 infixl 40 _⨂_

 data Env : ℕ → Set₁ where
   []  : Env 0
   _,_ : {n : ℕ} → Reg n → Env n → Env (suc n)

 mutual
   ⟦_⟧ : {n : ℕ} → Reg n → Env n → Set
   ⟦ 0′ ⟧  _ = ⊥
   ⟦ 1′ ⟧  _ = ⊤
   ⟦ I zero  ⟧   (X , Xs) = ⟦ X ⟧  Xs   
   ⟦ I (suc n) ⟧ (X , Xs) = ⟦ I n ⟧ Xs  
   ⟦ L ⨁ R ⟧ Xs = ⟦ L ⟧ Xs ⊎ ⟦ R ⟧ Xs
   ⟦ L ⨂ R ⟧ Xs = ⟦ L ⟧ Xs × ⟦ R ⟧ Xs
   ⟦  μ′ F  ⟧ Xs =  μ F Xs

   data μ {n : ℕ} (F : Reg (suc n)) (Xs : Env n) : Set where
     ⟨_⟩ : ⟦ F ⟧ (μ′ F , Xs) → μ F Xs

 infixl 50 _[_]
 infixl 50 ^_

 _[_]  : {n : ℕ} → Reg (suc n) → Reg n → Reg n
 ^_    : {n : ℕ} → Reg n → Reg (suc n)

 derive : {n : ℕ} → (i : Fin n) → Reg n → Reg n
 derive = {!!}

完整代码： https://pastebin.com/awr9Bc0R

[1] Abbott, M.、Altenkirch, T.、Ghani, N. 和 McBride, C.（2003 年）。容器的衍生物。在类型化 Lambda 演算和应用国际会议上，第 16-30 页。施普林格

[2] Abbott, M.、Altenkirch, T.、McBride, C. 和 Ghani, N.（2005 年）。 δ for data：微分数据结构。信息学基础，65(1-2):1–28.

[3] Löh, A. & Magalhães JP (2011)。带索引函子的泛型编程。在第七届 ACM SIGPLAN 泛型编程研讨会 (WGP'11) 的会议记录中。

[4] Magalhães JP。 & Löh, A. (2012) Datatype-Generic 编程方法的正式比较。在第 4 次数学结构化函数式编程研讨会 (MSFP '12) 中。

[5] McBride, C. (2001)。常规类型的导数是其 one-hole 上下文的类型。未发表的手稿，第 74-88 页。

[6] McBride, C. (2008)。我左边的小丑，右边的小丑（珍珠）：剖析数据结构。在 ACM SIGPLAN 通知中，第 43 卷，第 287-295 页。 ACM.

[7] Morris, P.、Altenkirch, T. 和 McBride, C.（2004 年 12 月）。探索常规树类型。在关于证明和程序类型的国际研讨会（第 252-267 页）中。斯普林格，柏林，海德堡。

[8] Sefl, V. (2019)。拉链的性能分析。 arXiv 预印本 arXiv:1908.10926.

[9] Tome Cortinas, C. 和 Swierstra, W. (2018)。从代数到抽象机：经过验证的通用构造。在第 3 届 ACM SIGPLAN Type-Driven 开发国际研讨会论文集，第 78-90 页。 ACM.

Answer 1

derive 的定义终止，您只是改编了 repo incorrectly. If derive is only called on F in the μ′ F case, that's clearly structural. In the code sample 中的代码，您试图在 ^ (F [ μ′ F ]) 上递归。

derive : {n : ℕ} → (i : Fin n) → Reg n → Reg n
derive i 0′ = 0′
derive i 1′ = 0′
derive i (I j) with i ≟ j
derive i (I j) | yes refl = 1′
...            | no _     = 0′
derive i (L ⨁ R) = derive i L ⨁ derive i R
derive i (L ⨂ R) = (derive i L ⨂ R) ⨁ (L ⨂ derive i R)
derive i (μ′ F) = μ′ (    (^ (derive (suc i) F [ μ′ F ]))
                       ⨁ (^ (derive zero F [ μ′ F ])) ⨂ I zero)

我还建议调整 Reg 如下，因为 n 作为索引是不必要的，Set₁ 也是如此。

data Reg (n : ℕ) : Set where
  0′    : Reg n
  1′    : Reg n
  I     : Fin n → Reg n
  _⨁_  : (l r : Reg n) → Reg n
  _⨂_  : (l r : Reg n) → Reg n
  μ′    : Reg (suc n)  → Reg n

Agda中数据结构的导数

Derivatives of data structures in Agda

agda

derivative

dependent-type

termination

zipper