paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Parametricity and Semi-Cubical Types

参数性与半立方类型
LICS 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2021匹配度 1/10 · 该论文属于类型论与范畴论形式语义的基础研究,讨论参数性与半立方类型的对应,与用户核心方向(ML/Agentic 程序静态分析、LLM 辅助形式化验证、浮点程序分析、贝叶斯程序分析)没有直接交集。仅与形式验证/类型论有非常宽泛的关联,不涉及 LLM 或程序分析工程落地。引用 0 inbox
Hugo Moeneclaey
crossref: 2026-09-12

AI 速览

一句话:从任意类型论模型构造出满足参数性的模型,并揭示参数性与半立方类型的对应。

本文研究如何从任意类型论模型出发构造满足参数性(parametricity)的模型,并建立参数性与立方结构之间的对应。核心思想是把新模型中的类型解释为旧模型中的半立方类型(semi-cubical type)。该构造不仅适用于参数性,也适用于类型论的类似解释,甚至任意广义代数理论的类似解释。更精确地,作者考虑一个遗忘函子,它忘记广义代数理论中的一元操作以及递归定义这些操作的等式,并证明该函子具有右伴随。技术工具包括局部可表现范畴论以及商归纳-归纳类型(quotient inductive-inductive types)。关键结果是得到一种统一的范畴论构造,使参数性与半立方类型之间的对应成为一般现象。

问题
如何为类型论构造满足参数性的模型,并理解参数性与立方结构之间的对应关系。
方法
将新模型中的类型定义为旧模型中的半立方类型;在广义代数理论层面考虑忘记一元操作及其递归定义等式的遗忘函子,并证明其具有右伴随。
评估
通过范畴论构造与伴随性证明建立理论结果,并说明该构造对参数性、类型论类似解释及任意广义代数理论类似解释的普适性。
原文摘要(Abstract)

We construct a model of type theory enjoying parametricity from an arbitrary one. A type in the new model is a semi-cubical type in the old one, illustrating the correspondence between parametricity and cubes.Our construction works not only for parametricity, but also for similar interpretations of type theory and in fact similar interpretations of any generalized algebraic theory. To be precise we consider a functor forgetting unary operations and equations defining them recursively in a generalized algebraic theory. We show that it has a right adjoint.We use techniques from locally presentable category theory, as well as from quotient inductive-inductive types.

链接与引用

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

BibTeX
@inproceedings{paperbot6232,
  title = {Parametricity and Semi-Cubical Types},
  author = {Hugo Moeneclaey},
  booktitle = {LICS},
  year = {2021},
  doi = {10.1109/lics52264.2021.9470728}
}