paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Calculating dependently-typed compilers (functional pearl)

计算依赖类型的编译器(函数式珍珠)
ICFP 5(ICFP)2021匹配度 2/10 · 该论文属于依赖类型、编译器正确性计算与证明助手方向,虽与形式化验证相关,但未涉及用户核心关注的 LLM/Agent 与程序分析交叉、浮点程序分析或贝叶斯程序分析。引用 7 inbox
Mitchell Pickard, Graham Hutton
crossref: 2026-09-10

AI 速览

一句话:将编译器计算技术推广到依赖类型设置,以支持类型化源语言并保证编译组件类型安全、便于机器验证。

编译器难以编写且难以保证正确。Bahr 与 Hutton 提出从正确性规约直接计算编译器,使编译器构造即正确,但此前仅适用于无类型源语言。本文把该技术扩展到依赖类型环境:利用依赖类型自然地表达类型化源语言及其编译正确性规约,确保所有编译组件类型安全,并使计算过程更容易在证明助手中进行机器检查。文章以函数式珍珠形式展示,表明依赖类型设置不仅支持类型化源语言,还提升正确性论证的可验证性,为构造即正确的类型化编译器提供了一条新路径。

问题
如何把 Bahr-Hutton 的从正确性规约计算编译器的技术推广到类型化源语言,同时保证编译组件类型安全且正确性论证可机械检查。
方法
在依赖类型设置中重新形式化编译器计算,利用依赖类型表达类型化源语言和正确性规约,并用证明助手辅助检查计算。
评估
评估方式主要是通过依赖类型形式化和证明助手机械检查来论证方法的可行性;摘要未提及基准测试或实证评估。
原文摘要(Abstract)

Compilers are difficult to write, and difficult to get right. Bahr and Hutton recently developed a new technique for calculating compilers directly from specifications of their correctness, which ensures that the resulting compilers are correct-by-construction. To date, however, this technique has only been applicable to source languages that are untyped. In this article, we show that moving to a dependently-typed setting allows us to naturally support typed source languages, ensure that all compilation components are type-safe, and make the resulting calculations easier to mechanically check using a proof assistant.

链接与引用

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

BibTeX
@article{paperbot1128,
  title = {Calculating dependently-typed compilers (functional pearl)},
  author = {Mitchell Pickard and Graham Hutton},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {5},
  number = {ICFP},
  year = {2021},
  doi = {10.1145/3473587}
}