paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Quantitative Behavioural Reasoning for Higher-order Effectful Programs

高阶效应程序的定量行为推理
LICS Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science2018匹配度 2/10 · 论文属于纯形式语义/类型理论,研究带代数效应高阶语言的 quantale 值行为相似与双相似,未涉及 LLM/Agent、静态分析工具、浮点程序分析或贝叶斯程序分析,也不包含 benchmark 或工业落地。与画像中 PL 与 AI 交叉的核心问题几乎不重合,仅在广义程序语义与形式化方法上有间接背景关联。引用 35 inbox
Francesco Gavazzo
crossref: 2026-09-12

AI 速览

一句话:为带代数效应的高阶 λ-演算建立 quantale 值行为相似与双相似,并证明其分别为相容的广义度量与伪度量。

论文研究 Abramsky 应用相似性与双相似性的定量精化,面向 Fuzz 的一个推广:一个可表达程序敏感性的线性类型 call-by-value λ-演算,并加入 Plotkin–Power 风格的代数操作。为统一处理效应与定量行为,作者依据 Lawvere 对广义度量空间的分析,提出取值于 quantale 的行为关系抽象框架;将 Barr 的 relator(lax extension)推广到 quantale 值关系,并借鉴 monoidal topology 的结果。基于此,论文定义 quantale 值效应应用相似性和双相似性,并在温和条件下分别证明它们是相容的广义度量与伪度量。该工作为高阶效应程序提供了定量行为推理的语义基础。

问题
如何对高阶、带代数效应且具线性类型/程序敏感性特征的程序进行定量行为推理,并统一刻画应用相似性与双相似性?
方法
以 Lawvere 广义度量空间为视角,引入 quantale 值行为关系框架,将 Barr relator/lax extension 推广到 quantale 值关系,并定义 quantale 值效应应用相似性与双相似性。
评估
理论结果:在温和条件下证明所定义的相似性与双相似性分别是相容的广义度量与伪度量。
原文摘要(Abstract)

This paper studies quantitative refinements of Abramsky's applicative similarity and bisimilarity in the context of a generalisation of Fuzz, a call-by-value λ-calculus with a linear type system that can express program sensitivity, enriched with algebraic operations à la Plotkin and Power. To do so a general, abstract framework for studying behavioural relations taking values over quantales is introduced according to Lawvere's analysis of generalised metric spaces. Barr's notion of relator (or lax extension) is then extended to quantale-valued relations, adapting and extending results from the field of monoidal topology. Abstract notions of quantale-valued effectful applicative similarity and bisimilarity are then defined and proved to be a compatible generalised metric (in the sense of Lawvere) and pseudometric, respectively, under mild conditions.

链接与引用

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

BibTeX
@inproceedings{paperbot4362,
  title = {Quantitative Behavioural Reasoning for Higher-order Effectful Programs},
  author = {Francesco Gavazzo},
  booktitle = {LICS},
  year = {2018},
  doi = {10.1145/3209108.3209149}
}