paperbot · PL 论文追踪

全部论文 待读 收藏

P2 From Semantics to Syntax: A Type Theory for Comprehension Categories

从语义到句法:一种面向 comprehension 范畴的类型论
POPL 10(POPL)2026匹配度 1/10 · 论文属于纯类型论与范畴语义的理论工作,讨论 comprehension categories 中类型间态射的内化与可靠性,不涉及 LLM/Agent、静态分析、浮点程序分析或贝叶斯程序分析等用户核心方向,仅与形式化验证有非常边缘的关联。引用 4 inbox
Niyousha Najmaei, Niels van der Weide, Benedikt Ahrens, Paige Randall North
crossref: 2026-09-10

AI 速览

一句话:提出一种内化类型间态射、含 Π/Σ/同一类型的类型论,并证明其在 comprehension 范畴语义下的可靠性。

近期内涵类型论的模型常建立在代数弱分解系统(AWFS)之上,由此得到的 comprehension 范畴具有类型之间的非平凡态射,而标准 Martin-Löf 类型论解释并不使用这些态射。本文把这一语义特征反映回语法,发展出一种内化类型间态射的类型论,包含 Π、Σ 与同一类型;并说明它可视为 Coraglia 和 Emmenegger 所勾勒的带强制子类型的 Martin-Löf 类型论扩展。作者定义了相应的语义结构,证明该类型论相对于该语义的可靠性,并给出大量语义结构实例,从而获得丰富的解释。

问题
标准 comprehension 范畴对 Martin-Löf 类型论的解释忽略了 AWFS 模型中类型间的非平凡态射,如何将这些语义结构内化到语法中。
方法
构造一种含 Π、Σ、同一类型并内化类型间态射的类型论,定义其语义结构,并证明可靠性;同时与带强制子类型的 Martin-Löf 类型论扩展相联系。
评估
通过定义语义解释并证明可靠性定理,并展示多个满足该语义结构的例子来验证框架的适用性。
原文摘要(Abstract)

Recent models of intensional type theory have been constructed in algebraic weak factorization systems (AWFSs). AWFSs give rise to comprehension categories that feature non-trivial morphisms between types; these morphisms are not used in the standard interpretation of Martin-Löf type theory in comprehension categories. We develop a type theory that internalizes morphisms between types, reflecting this semantic feature back into syntax. Our type theory comes with Π-, Σ-, and identity types. We discuss how it can be viewed as an extension of Martin-Löf type theory with coercive subtyping, as sketched by Coraglia and Emmenegger. We furthermore define semantic structure that interprets our type theory and prove a soundness result. Finally, we exhibit many examples of the semantic structure, yielding a plethora of interpretations.

链接与引用

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

BibTeX
@article{NajmaeiWAN26,
  title = {From Semantics to Syntax: A Type Theory for Comprehension Categories},
  author = {Niyousha Najmaei and Niels van der Weide and Benedikt Ahrens and Paige Randall North},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {10},
  number = {POPL},
  year = {2026},
  doi = {10.1145/3776725}
}