paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Monadic compiler calculation (functional pearl)

单子式编译器计算(函数式珍珠)
ICFP 6(ICFP)2022匹配度 2/10 · 该论文属于编译器正确性形式化推导与单子理论,关注发散行为的等式式验证,不涉及 LLM/Agent、静态分析、浮点程序分析或贝叶斯程序分析,与用户画像中 PL 与 AI 交叉的核心方向基本无关。引用 4 inbox
Patrick Bahr, Graham Hutton
crossref: 2026-09-10

AI 速览

一句话:将编译器正确性推导从仅收敛行为扩展到同时处理发散行为,用部分性单子显式表示发散并支持等式式计算。

已有工作提出从正确性规约直接计算正确编译器的方法,但只考虑源语言的收敛行为,因而对发散程序可能生成任意错误代码。本文将该方法自然扩展为同时处理收敛与发散行为,无需分别推理。核心是用部分性单子(partiality monad)把发散显式化,并用强互模拟(strong bisimilarity)支持等式式推导。这样便可在统一框架中从规约计算编译器,且通过替换底层单子可推广到其他效应。论文以函数式珍珠形式展示该方法,说明其能避免为发散单独推理,并保持计算式推导风格。

问题
已有编译器计算/推导方法仅处理源语言的收敛行为,对发散程序无法保证生成代码正确。
方法
用部分性单子显式表示发散,并用强互模拟支持等式式推导,将收敛与发散统一处理;通过更换底层单子可推广到其他效应。
评估
以函数式珍珠形式展示该方法,说明可从正确性规约计算编译器,并避免对发散行为单独推理。
原文摘要(Abstract)

Bahr and Hutton recently developed a new approach to calculating correct compilers directly from specifications of their correctness. However, the methodology only considers converging behaviour of the source language, which means that the compiler could potentially produce arbitrary, erroneous code for source programs that diverge. In this article, we show how the methodology can naturally be extended to support the calculation of compilers that address both convergent and divergent behaviour simultaneously , without the need for separate reasoning for each aspect. Our approach is based on the use of the partiality monad to make divergence explicit, together with the use of strong bisimilarity to support equational-style calculations, but also generalises to other forms of effect by changing the underlying monad.

链接与引用

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

BibTeX
@article{paperbot1481,
  title = {Monadic compiler calculation (functional pearl)},
  author = {Patrick Bahr and Graham Hutton},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {6},
  number = {ICFP},
  year = {2022},
  doi = {10.1145/3547624}
}