一句话:提出依赖类型理论 Cocon,融合 HOAS 与可计算函数空间,并用 Kripke 模型证明规范化与一致性。
论文提出 Martin-Löf 风格的依赖类型理论 Cocon,目标是在逻辑框架中把用于表示高阶抽象语法(HOAS)的内涵函数空间与描述递归计算的外延函数空间结合起来。Cocon 借助上下文模态类型在 HOAS 表示与计算之间进行中介,并支持无限宇宙层级,从而提供类型级计算、元编程和小规模反射。作者的核心贡献是为 Cocon 构造 Kripke 风格语义模型并证明规范化;由该证明进一步推出主体归约(subject reduction)与一致性。该工作为将逻辑框架方法融入 Agda 等系统、弥合逻辑框架与依赖类型编程语言之间的鸿沟奠定了基础。
We describe a Martin-Lof-style dependent type theory, called Cocon, that allows us to mix the intensional function space that is used to represent higher-order abstract syntax (HOAS) trees with the extensional function space that describes (recursive) computations. We mediate between HOAS representations and computations using contextual modal types. Our type theory also supports an infinite hierarchy of universes and hence supports type-level computation thereby providing metaprogramming and (small-scale) reflection. Our main contribution is the development of a Kripke-style model for Cocon that allows us to prove normalization. From the normalization proof, we derive subject reduction and consistency. Our work lays the foundation to incorporate the methodology of logical frameworks into systems such as Agda and bridges the longstanding gap between these two worlds.