paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Probabilistic call by push value

概率化的 Call-By-Push-Value
LMCS vol.Volume 15, Issue 12019匹配度 2/10 · 该论文属于纯程序语言形式语义研究,讨论 Call-By-Push-Value 的概率扩展、指称语义与完全抽象,未涉及静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析与 LLM 的交叉;仅在“概率编程”基础语义层面与部分兴趣有弱关联。引用 15 inbox
Thomas Ehrhard, Christine Tasson
crossref: 2026-09-10

AI 速览

一句话:在概率相干空间模型中为 Call-By-Push-Value 加入随机选择,并证明其可靠性与完全抽象。

本文为 Levy 的 Call-By-Push-Value 引入概率扩展:仅添加一个封闭的“抛硬币”布尔原子表达式,得到可同时涵盖按名调用与按值调用、并支持递归(可能惰性)数据类型的语言,可视为 Scott PCF 的重要推广。作者在既有概率相干空间指称模型中解释该语言;该模型是全经典线性逻辑的范畴模型,将数据类型解释为资源 comonad 的 coalgebra。文章证明该语言的 adequacy 与 full abstraction,将先前结果推广到更现实且更强的编程语言。

问题
如何为同时支持按名/按值调用和递归惰性数据类型的语言提供概率语义,并在统一模型中刻画随机计算。
方法
在 Levy 的 Call-By-Push-Value 上加入抛硬币原子,并用概率相干空间这一全经典线性逻辑范畴模型进行指称解释,数据类型解释为资源 comonad 的 coalgebra。
评估
通过证明该语言的 adequacy 与 full abstraction,并与已有概率相干空间结果对比,表明结论可推广到更强的 CBPV/PCF 类语言。
原文摘要(Abstract)

We introduce a probabilistic extension of Levy's Call-By-Push-Value. This extension consists simply in adding a " flipping coin " boolean closed atomic expression. This language can be understood as a major generalization of Scott's PCF encompassing both call-by-name and call-by-value and featuring recursive (possibly lazy) data types. We interpret the language in the previously introduced denotational model of probabilistic coherence spaces, a categorical model of full classical Linear Logic, interpreting data types as coalgebras for the resource comonad. We prove adequacy and full abstraction, generalizing earlier results to a much more realistic and powerful programming language.

链接与引用

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

BibTeX
@article{paperbot836,
  title = {Probabilistic call by push value},
  author = {Thomas Ehrhard and Christine Tasson},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 15, Issue 1},
  year = {2019},
  doi = {10.23638/lmcs-15(1:3)2019}
}