paperbot · PL 论文追踪

全部论文 待读 收藏

P1 Universal Semantics for the Stochastic λ-Calculus

随机 λ-演算的通用语义
LICS 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2021匹配度 5/10 · 该论文研究随机 λ-演算的指称与操作语义,属于概率程序语言和贝叶斯程序分析的理论基础,与用户对贝叶斯程序分析的兴趣有间接关联;但它不涉及静态分析、LLM/Agent、浮点分析或工业落地,也不是问题驱动或带 benchmark 的工作。引用 6 inbox
Pedro H. Azevedo de Amorim, Dexter Kozen, Radu Mardare, Prakash Panangaden, Michael Roberts
crossref: 2026-09-12

AI 速览

一句话:为随机 λ-演算建立可靠且充分的指称语义与操作语义,统一高阶概率程序的语义框架。

本文研究随机 λ-演算的语义基础。该演算通过显式随机源刻画高阶概率程序。作者定义了指称语义与操作语义,并证明二者是可靠(sound)且充分(adequate)的,即操作行为与指称模型在观察等价意义下一致。该工作建立在以往用显式随机性推理高阶概率程序的成果之上,为随机 λ-演算提供统一的语义框架。关键结果是两类语义的对应性,为后续概率程序逻辑与验证奠定基础。

问题
如何为带显式随机源的高阶概率程序(随机 λ-演算)给出具有坚实数学基础的语义?
方法
定义指称语义和操作语义,并基于既有显式随机性模型证明两者的 soundness 和 adequacy。
评估
通过证明指称语义与操作语义的可靠性与充分性(对应性)来评估,而非基于实验基准。
原文摘要(Abstract)

We define sound and adequate denotational and operational semantics for the stochastic lambda calculus. These two semantic approaches build on previous work that used an explicit source of randomness to reason about higher-order probabilistic programs.

链接与引用

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

BibTeX
@inproceedings{paperbot6242,
  title = {Universal Semantics for the Stochastic λ-Calculus},
  author = {Pedro H. Azevedo de Amorim and Dexter Kozen and Radu Mardare and Prakash Panangaden and Michael Roberts},
  booktitle = {LICS},
  year = {2021},
  doi = {10.1109/lics52264.2021.9470747}
}