paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Differentials and distances in probabilistic coherence spaces

概率相干空间中的微分与距离
LMCS vol.Volume 18, Issue 32022匹配度 2/10 · 该论文属于概率程序语义与微分逻辑的理论研究,讨论 pPCF 的执行时间期望和 Lipschitz 性质,与用户关注的静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析交叉点较远,且缺乏工程实现、benchmark 或工业落地内容。引用 1 inbox
Thomas Ehrhard
crossref: 2026-09-10

AI 速览

一句话:在概率相干空间中用导数刻画 pPCF 执行时间期望,并证明态射 Lipschitz 性以连接观测距离与模型距离。

概率相干空间是概率函数式语言的指称模型,其态射为解析且光滑。本文研究该模型导数的两个应用。首先,利用导数计算概率 PCF(pPCF)在弱头归约下执行时间的期望,从而把微分结构用于资源/复杂度分析。其次,将态射的“局部”微分概念用于证明这些态射的 Lipschitz 性质,并据此把 pPCF 项上的观测距离与该模型自然携带的距离联系起来。结果表明概率相干空间的微分不仅可刻画执行代价,还能控制程序行为距离,暗示按微分 lambda 演算的思路扩展概率编程语言具有意义。

问题
概率函数式语言的指称模型概率相干空间拥有光滑解析态射,但其导数能否用于分析程序执行时间与行为距离尚待探索。
方法
通过概率相干空间中的导数与“局部”微分,分别推导 pPCF 弱头归约执行时间的期望,并证明态射 Lipschitz 性以建立观测距离与模型距离的关系。
评估
以 pPCF 为案例进行理论推导与证明(非实验评估),展示导数的两个应用并论证扩展概率语言以支持导数的潜在意义。
原文摘要(Abstract)

In probabilistic coherence spaces, a denotational model of probabilistic functional languages, morphisms are analytic and therefore smooth. We explore two related applications of the corresponding derivatives. First we show how derivatives allow to compute the expectation of execution time in the weak head reduction of probabilistic PCF (pPCF). Next we apply a general notion of "local" differential of morphisms to the proof of a Lipschitz property of these morphisms allowing in turn to relate the observational distance on pPCF terms to a distance the model is naturally equipped with. This suggests that extending probabilistic programming languages with derivatives, in the spirit of the differential lambda-calculus, could be quite meaningful.

链接与引用

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

BibTeX
@article{paperbot1671,
  title = {Differentials and distances in probabilistic coherence spaces},
  author = {Thomas Ehrhard},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 18, Issue 3},
  year = {2022},
  doi = {10.46298/lmcs-18(3:2)2022}
}