paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Transpension: The Right Adjoint to the Pi-type

Transpension:Π 类型的右伴随
LMCS vol.Volume 20, Issue 22024匹配度 2/10 · 论文属于依赖类型论与 presheaf 语义的基础研究,讨论 transpension 类型及其内部化算子,与用户关注的 LLM/Agent 静态分析、浮点程序分析、贝叶斯程序分析均无直接交集;仅在形式化验证/类型系统理论层面有非常间接的关联。引用 4 inbox
Andreas Nuyts, Dominique Devriese
crossref: 2026-09-10

AI 速览

一句话:提出 transpension 类型作为 shape 上全称量化的右伴随,并给出类型规则与 presheaf 语义。

依赖类型论的 presheaf 模型广泛用于 HoTT、参数性以及 directed/guarded/nominal 类型论,但已有内部 presheaf 算子(√、extent、Gel、Glue、Weld、mill、strictness axiom 等)表达力关系不清,且 shape 变量常需 affine 使用。本文提出 transpension 类型:它是 shape 上全称量化的右伴随,可视为 HoTT 中 suspension 的依赖版本。作者给出一般类型规则与基于 multiplier(基范畴函子)的 presheaf 语义,其中结构规则取决于 multiplier 特征。结果表明,与 strictness axiom 结合可实现并改进多种内部化算子(locally fresh names 除外,未作形式化断言)。

问题
文献中多种内部 presheaf 算子缺乏统一表达力比较,且 shape 变量有时需仿射使用。
方法
提出 transpension 类型作为 shape 上全称量化的右伴随,给出一般类型规则及基于 multiplier 的 presheaf 语义。
评估
通过展示该类型与 strictness axiom 结合能实现并改进已有内部化算子来体现表达力;对 locally fresh names 不作形式化断言。
原文摘要(Abstract)

Presheaf models of dependent type theory have been successfully applied to model HoTT, parametricity, and directed, guarded and nominal type theory. There has been considerable interest in internalizing aspects of these presheaf models, either to make the resulting language more expressive, or in order to carry out further reasoning internally, allowing greater abstraction and sometimes automated verification. While the constructions of presheaf models largely follow a common pattern, approaches towards internalization do not. Throughout the literature, various internal presheaf operators ($\surd$, $\Phi/\mathsf{extent}$, $\Psi/\mathsf{Gel}$, $\mathsf{Glue}$, $\mathsf{Weld}$, $\mathsf{mill}$, the strictness axiom and locally fresh names) can be found and little is known about their relative expressivenes. Moreover, some of these require that variables whose type is a shape (representable presheaf, e.g. an interval) be used affinely. We propose a novel type former, the transpension type, which is right adjoint to universal quantification over a shape. Its structure resembles a dependent version of the suspension type in HoTT. We give general typing rules and a presheaf semantics in terms of base category functors dubbed multipliers. Structural rules for shape variables and certain aspects of the transpension type depend on characteristics of the multiplier. We demonstrate how the transpension type and the strictness axiom can be combined to implement all and improve some of the aforementioned internalization operators (without formal claim in the case of locally fresh names).

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@article{paperbot2752,
  title = {Transpension: The Right Adjoint to the Pi-type},
  author = {Andreas Nuyts and Dominique Devriese},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 20, Issue 2},
  year = {2024},
  doi = {10.46298/lmcs-20(2:16)2024}
}