paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Fully abstract module compilation

完全抽象的模块编译
POPL 3(POPL)2019匹配度 1/10 · 该论文属于纯 PL 形式语义与模块编译翻译,核心是完全抽象性与 Coq 形式化证明,不涉及静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析,与用户当前研究画像几乎没有交集。引用 9 inbox
Karl Crary
crossref: 2026-09-10

AI 速览

一句话:提出首个具有动态正确性定理的模块编译翻译,证明其完全抽象并保持源语言抽象性。

现代模块演算通常支持密封、生成性、透明签名、应用式函子、高阶函子和/或一等模块,但为其设计具有动态正确性的编译翻译一直困难。本文给出一种适用于此类模块演算编译的翻译,并证明该翻译产生的目标项在适当意义下与源项上下文等价,因而具有完全抽象性;推论是翻译保持源语言中所有抽象。论文还表明模块可视为底层核心语言的定义式扩展。所有证明均在 Coq 中形式化。

问题
如何为支持密封、生成性、透明签名、应用式/高阶函子和一等模块的现代模块演算提供具有动态正确性的编译翻译,并保持源语言的抽象性。
方法
定义一种模块到核心语言的编译翻译,证明目标项与源项上下文等价,由此推出完全抽象;并展示模块是核心语言的定义式扩展。
评估
在 Coq 中机器化证明全部定理,以建立翻译的动态正确性与完全抽象性。
原文摘要(Abstract)

We give a translation suitable for compilation of modern module calculi supporting sealing, generativity, translucent signatures, applicative functors, higher-order functors and/or first-class modules. Ours is the first module-compilation translation with a dynamic correctness theorem. The theorem states that the translation produces target terms that are contextually equivalent to the source, in an appropriate sense. A corollary of the theorem is that the translation is fully abstract. Consequently, the translation preserves all abstraction present in the source. In passing, we also show that modules are a definitional extension of the underlying core language. All of our proofs are formalized in Coq.

链接与引用

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

BibTeX
@article{paperbot686,
  title = {Fully abstract module compilation},
  author = {Karl Crary},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {3},
  number = {POPL},
  year = {2019},
  doi = {10.1145/3290323}
}