paperbot · PL 论文追踪

全部论文 待读 收藏

P2 A Probabilistic and Non-Deterministic Call-by-Push-Value Language

一个概率与非确定性的 Call-by-Push-Value 语言
LICS 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2019匹配度 2/10 · 论文研究概率与非确定性 CBPV 语言的指称语义、操作语义及完全抽象,属于编程语言形式语义基础,不涉及静态分析、Agent/LLM、浮点程序分析或贝叶斯程序分析与 LLM 的交叉;与用户画像仅在概率语言理论层面存在弱相关。引用 0 inbox
Jean Goubault-Larrecq
crossref: 2026-09-12

AI 速览

一句话:提出概率与非确定性 CBPV 语言,用两类类型绕开连续 domain 语义障碍,并证明可靠、充分与完全抽象。

论文针对高阶概率语言难以获得域论语义的问题:通常要求涉及的 domain 连续或拟连续,但已知方法无法做到。作者指出,若语言具有两类类型(值类型与计算类型),问题会自然消失:值类型在连续 dcpo 的笛卡尔闭范畴中解释,计算类型在对概率 powerdomain 函子封闭的范畴中解释;这一框架来自 Levy 的 call-by-push-value。基于此,论文定义一个 CBPV 语言,概率选择位于值类型内,而从值类型到计算类型的转换引入 demonic 非确定性。作者给出域论语义与操作语义,证明二者可靠且充分;进一步加入 statistical termination testers 与 parallel if 后,证明语言完全抽象,并说明这两个原语不可或缺。

问题
如何为高阶概率语言给出域论语义,并使涉及的 domain 保持连续或拟连续?此前没有已知方法。
方法
利用 call-by-push-value 的两类类型:值类型解释于连续 dcpo 的笛卡尔闭范畴,计算类型解释于对概率 powerdomain 函子封闭的范畴;概率选择置于值类型,值到计算的转换引入 demonic 非确定性。
评估
给出域论语义与操作语义,并证明二者可靠且充分;在加入 statistical termination testers 与 parallel if 后证明完全抽象,且说明这两个原语是必要的。
原文摘要(Abstract)

There is no known way of giving a domain-theoretic semantics to higher-order probabilistic languages, in such a way that the involved domains are continuous or quasi-continuous. We argue that the problem naturally disappears for languages with two kinds of types, where one kind is interpreted in a Cartesian-closed category of continuous dcpos, and the other is interpreted in a category that is closed under the probabilistic powerdomain functor. Such a setting is provided by Paul B. Levy's call-by-push-value paradigm. Following this insight, we define a call-by-push-value language, with probabilistic choice sitting inside the value types, and where conversion from a value type to a computation type involves demonic non-determinism. We give both a domain-theoretic semantics and an operational semantics for the resulting language, and we show that they are sound and adequate. With the addition of statistical termination testers and parallel if, we show that the language is even fully abstract-and those two primitives are required for that.

链接与引用

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

BibTeX
@inproceedings{paperbot4985,
  title = {A Probabilistic and Non-Deterministic Call-by-Push-Value Language},
  author = {Jean Goubault-Larrecq},
  booktitle = {LICS},
  year = {2019},
  doi = {10.1109/lics.2019.8785809}
}