paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Staged compilation with two-level type theory

基于两级类型论的分阶段编译
ICFP 6(ICFP)2022匹配度 2/10 · 该论文属于类型论与分阶段编译的形式化研究,关注依赖类型元编程与正确性证明,与用户画像中的 PL→AI(ML/Agent 静态分析)、AI→PL(LLM 改进静态分析/验证)、浮点程序分析及贝叶斯程序分析均无直接关联。虽然属于程序语言理论且带形式化证明,但并非当前研究问题的核心交叉方向。引用 20 inbox
András Kovács
crossref: 2026-09-10

AI 速览

一句话:提出用两级类型论(2LTT)实现支持依赖类型与类型级无限制分阶段编译,并给出正确性证明。

分阶段编译旨在支持元编程,同时保证生成代码的良构性,并能简洁混合对象层与元层代码。本文观察到原本为综合同伦论设计的两级类型论(2LTT)也可作为依赖类型分阶段编译的系统。2LTT 规范简洁、模型论性质良好,且支持对象层与元层的丰富语言特性。作者首先概述 2LTT 在 staging 中的特性与应用,然后提出一种“按求值分阶段”(staging-by-evaluation)算法,类比 normalization-by-evaluation,并通过在语义域中求值 2LTT 语法完成分阶段;随后证明算法正确性。该正确性同时构成 2LTT 相对于对象理论的强保守性证明。据作者所知,这是首个支持完整依赖类型和类型无限制分阶段的分阶段编译方案。

问题
如何在分阶段编译/元编程中既支持完整依赖类型与类型级无限制分阶段,又保证生成代码的良构性,并提供简洁的对象层与元层混合机制?
方法
将两级类型论(2LTT)用作分阶段编译基础,提出类比 normalization-by-evaluation 的 staging-by-evaluation 算法,在语义域中求值 2LTT 语法,并证明其正确性与强保守性。
评估
以理论证明为评估方式:给出分阶段算法及其正确性证明,证明 2LTT 相对于对象理论的强保守性;摘要未报告实现或实验评估。
原文摘要(Abstract)

The aim of staged compilation is to enable metaprogramming in a way such that we have guarantees about the well-formedness of code output, and we can also mix together object-level and meta-level code in a concise and convenient manner. In this work, we observe that two-level type theory (2LTT), a system originally devised for the purpose of developing synthetic homotopy theory, also serves as a system for staged compilation with dependent types. 2LTT has numerous good properties for this use case: it has a concise specification, well-behaved model theory, and it supports a wide range of language features both at the object and the meta level. First, we give an overview of 2LTT's features and applications in staging. Then, we present a staging algorithm and prove its correctness. Our algorithm is "staging-by-evaluation", analogously to the technique of normalization-by-evaluation, in that staging is given by the evaluation of 2LTT syntax in a semantic domain. The staging algorithm together with its correctness constitutes a proof of strong conservativity of 2LLT over the object theory. To our knowledge, this is the first description of staged compilation which supports full dependent types and unrestricted staging for types.

链接与引用

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

BibTeX
@article{paperbot1506,
  title = {Staged compilation with two-level type theory},
  author = {András Kovács},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {6},
  number = {ICFP},
  year = {2022},
  doi = {10.1145/3547641}
}