paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Convexity and Order in Probabilistic Call-by-Name FPC

概率 call-by-name FPC 中的凸性与序
LMCS vol.Volume 16, Issue 42020匹配度 3/10 · 该论文属于概率程序语言的形式语义与指称语义研究,与用户核心关注的静态分析、Agentic/LLM 交叉、浮点程序分析以及贝叶斯程序分析距离较远;仅在概率编程语言理论层面有间接关联。引用 5 inbox
Mathys Rennela
dblp: 2026-09-10crossref: 2026-09-10arxiv: 2026-09-10

AI 速览

一句话:证明 Kegelspitzen 构成概率 call-by-name FPC/pPCF 的指称模型,并讨论概率递归类型解释。

本文研究 Kegelspitzen(Keimel 与 Plotkin 提出、同时刻画凸集与 dcpo 的结构)究竟为何种语言提供模型。作者从范畴论视角出发,证明 Kegelspitzen 可将随机矩阵建模到域范畴上,从而构成 pPCF(一种面向概率计算的抽象函数式语言)的指称模型。文末进一步讨论概率递归类型——如列表与树等可能包含同类型实体的类型——的解释。该工作为概率函数式语言提供了基于凸性与序结构的语义基础,并沟通了概率计算与域理论。

问题
Kegelspitzen 这类同时具有凸集与 dcpo 结构的数学对象究竟能为什么语言或计算现象提供模型,尚待明确。
方法
采用范畴论方法,将 Kegelspitzen 解释为从随机矩阵到域范畴的模型构造,并据此给出 pPCF 的指称语义。
评估
理论性评估:证明 Kegelspitzen 构成 pPCF 的指称模型,并讨论概率递归类型的解释;未涉及实现或实验。
原文摘要(Abstract)

Kegelspitzen are mathematical structures coined by Keimel and Plotkin, in order to encompass the structure of a convex set and the structure of a dcpo. In this paper, we ask ourselves what are Kegelspitzen the model of. We adopt a categorical viewpoint and show that Kegelspitzen model stochastic matrices onto a category of domains. Consequently, Kegelspitzen form a denotational model of pPCF, an abstract functional programming language for probabilistic computing. We conclude the present work with a discussion of the interpretation of (probabilistic) recursive types, which are types for entities which might contain other entities of the same type, such as lists and trees.

链接与引用

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

BibTeX
@article{Rennela16,
  title = {Convexity and Order in Probabilistic Call-by-Name FPC},
  author = {Mathys Rennela},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 16, Issue 4},
  year = {2020},
  doi = {10.23638/lmcs-16(4:10)2020}
}