arXiv:2505.15002cs.PLcs.AI2025-05

扩展了反向自动微分框架CHAD,支持循环和非终止程序。

Unraveling the iterative CHAD

  • 引入迭代广义索引范畴,统一建模循环与依赖类型语言
  • 确保带循环程序的微分结果正确,保持结构不变性
  • 适合形式化验证与高阶函数编程研究者

组合同态自动微分(CHAD)最初是为终止性函数程序设计的反向自动微分语义驱动源到源转换。本文将其扩展至包含部分(可能非终止)操作、数据依赖条件(如实值判断)和迭代构造(如while循环)的程序,同时保持CHAD的核心结构保真原则。核心贡献是提出迭代广义索引范畴,为依赖类型语言提供迭代的合理集成方式:要求基范畴中的迭代能提升为索引范畴中参数化初等代数,从而在总范畴(对应依赖类型语言的容器范畴)中构建出对偶纤维迭代结构,以建模while循环等迭代构造。基于此,我们证明了在合适意义上,该扩展的CHAD变换是唯一保持结构的函子。具体而言,它是从源语言的迭代Freyd范畴到目标语言容器范畴的唯一迭代Freyd范畴态射,使得每个原语操作映射为其转置导数。通过源语言的语法范畴模型的泛性质,我们建立了该变换的正确性,证明微分后程序可正确计算原始程序的反向模式导数。

原文摘要 · Abstract (English)

Combinatory Homomorphic Automatic Differentiation (CHAD) was originally formulated as a semantics-driven source-to-source transformation for reverse-mode AD of total (terminating) functional programs. In this work, we extend CHAD to encompass programs featuring constructs such as partial (potentially non-terminating) operations, data-dependent conditionals (e.g., real-valued tests), and iteration constructs (i.e. while-loops), while maintaining CHAD's core principle of structure-preserving semantics. A central contribution is the introduction of iteration-extensive indexed categories, which provide a principled integration of iteration into dependently typed programming languages. This integration is achieved by requiring that iteration in the base category lifts to parameterized initial algebras in the indexed category, yielding an op-fibred iterative structure that models while-loops and other iteration constructs in the total category, which corresponds to the category of containers of our dependently typed language. Through the idea of iteration-extensive indexed categories, we extend the CHAD transformation to looping programs as the unique structure-preserving functor in a suitable sense. Specifically, it is the unique iterative Freyd category morphism from the iterative Freyd category corresponding to the source language to the category of containers obtained from the target language, such that each primitive operation is mapped to its (transposed) derivative. We establish the correctness of this extended transformation via the universal property of the syntactic categorical model of the source language, showing that the differentiated programs compute correct reverse-mode derivatives of their originals.

自动微分范畴论函数式编程形式化验证

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。