paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Effectful program distancing

带效应的程序距离化
POPL 6(POPL)2022匹配度 2/10 · 该论文属于纯形式语义/类型论方向,研究带效应高阶程序的差分逻辑关系与 quantale 度量,既不涉及静态分析工具、ML/Agentic 程序,也未与 LLM、浮点程序分析或贝叶斯程序分析产生交叉,与用户画像的核心问题基本无关。仅在'程序距离度量'这一抽象概念上与浮点/近似程序分析有非常间接的潜在联系。引用 7 inbox
Ugo Dal Lago, Francesco Gavazzo
crossref: 2026-09-10

AI 速览

一句话:将差分逻辑关系推广到带效应高阶程序,用 quantale 度量值与计算效应之间的距离。

传统语义学关注程序等价,不等价程序通常被视为不可比较。近年出现的程序度量用 quantale 元素衡量不等价程序间的距离,而差分逻辑关系通过随类型复杂度改变底层 quantale,实现上下文敏感的推理。本文把这一框架推广到带效应的高阶程序,不仅对返回值,而且对计算产生的效应也进行有原则的距离化。作者表明该框架具有灵活性,能处理多种形式的效应,并能给出关于程序差异的简洁且信息丰富的判断。

问题
如何在带效应的高阶程序中,统一且上下文敏感地度量不等价程序之间的距离,包括返回值与计算效应。
方法
将 differential logical relations 推广到 effectful higher-order programs,使底层 quantale 随类型复杂度变化,并对值与效应进行距离化。
评估
通过展示该框架能灵活处理多种效应,并给出紧凑、信息丰富的程序差异判断,论证其有效性。
原文摘要(Abstract)

Semantics is traditionally concerned with program equivalence, in which all pairs of programs which are not equivalent are treated the same, and simply dubbed as incomparable. In recent years, various forms of program metrics have been introduced such that the distance between non-equivalent programs is measured as an element of an appropriate quantale. By letting the underlying quantale vary as the type of the compared programs become more complex, the recently introduced framework of differential logical relations allows for a new contextual form of reasoning. In this paper, we show that all this can be generalised to effectful higher-order programs, in which not only the values , but also the effects computations produce can be appropriately distanced in a principled way. We show that the resulting framework is flexible, allowing various forms of effects to be handled, and that it provides compact and informative judgments about program differences.

链接与引用

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

BibTeX
@article{paperbot1572,
  title = {Effectful program distancing},
  author = {Ugo Dal Lago and Francesco Gavazzo},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {6},
  number = {POPL},
  year = {2022},
  doi = {10.1145/3498680}
}