paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Curry and Howard Meet Borel

Curry 与 Howard 遇上 Borel
LICS Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science2022匹配度 3/10 · 该论文属于概率程序语言的 Curry-Howard 语义与交集类型理论研究,与用户关注的'贝叶斯程序分析'在概率与程序语义层面有较弱的间接联系;但它既非面向 ML/Agentic 程序的静态分析,也非 LLM 与静态分析的交叉,更不涉及浮点分析、工业落地或 benchmark,且缺乏工程实现与经验性失效分析。引用 14 inbox
Melissa Antonelli, Ugo Dal Lago, Paolo Pistone
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:建立计数命题逻辑与概率事件 λ 演算的 Curry-Howard 对应,并以交集类型精确刻画概率行为。

论文研究如何将直觉主义计数命题逻辑通过 Curry-Howard 对应解释为概率计算类型系统。作者以概率事件 λ 演算为载体,该演算可模拟离散随机函数式程序的按名与按值求值;在此对应下,证明和类型不再保证有效性或终止性,而是揭示程序结果所服从的概率。为进一步精确刻画 λ 项的完整概率行为,作者为类型系统引入交集算子,得到一个能精确捕获概率语义的系统。该工作把 Borel 概率与证明论、类型论联系起来,为概率程序的逻辑化分析提供新框架。

问题
如何为离散随机函数式程序建立证明/类型与概率之间的 Curry-Howard 对应,并在不保证终止或有效性的情况下揭示其概率行为。
方法
用概率事件 λ 演算作为载体统一模拟按名与按值求值,将直觉主义计数命题逻辑对应到类型系统,并加入交集算子以精确刻画 λ 项的概率语义。
评估
评估以理论证明为主:给出 Curry-Howard 对应,并证明带交集算子的类型系统能精确捕获 λ 项的概率行为。
原文摘要(Abstract)

We show that an intuitionistic version of counting propositional logic corresponds, in the sense of Curry and Howard, to an expressive type system for the probabilistic event λ-calculus, a vehicle calculus in which both call-by-name and call-by-value evaluation of discrete randomized functional programs can be simulated. In this context, proofs (respectively, types) do not guarantee that validity (respectively, termination) holds, but reveal the underlying probability. We finally show how to obtain a system precisely capturing the probabilistic behavior of λ-terms, by endowing the type system with an intersection operator.

链接与引用

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

BibTeX
@inproceedings{AntonelliLP22,
  title = {Curry and Howard Meet Borel},
  author = {Melissa Antonelli and Ugo Dal Lago and Paolo Pistone},
  booktitle = {LICS},
  year = {2022},
  doi = {10.1145/3531130.3533361}
}