paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Resource approximation for the λμ-calculus

λμ-演算的资源近似
LICS Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science2022匹配度 2/10 · 论文属于纯形式语义与λμ-演算、Taylor展开资源近似理论,虽与PL理论相关,但未涉及用户核心关注的静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析等方向,匹配度很低。引用 4 inbox
Davide Barbarossa
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:将 Taylor 展开适配到 λμ-演算,建立资源敏感近似理论,并证明稳定性与垂直线性质。

λμ-演算将 Curry-Howard 对应推广到经典逻辑,是程序语言理论中的核心模型,但它不满足 Böhm 定理,也缺少相应的近似概念。本文表明 Ehrhard 与 Regnier 的 Taylor 展开可较容易地适配到 λμ-演算,从而得到一种资源敏感的近似理论。基于该理论可构造合理的 λμ-理论,并证明 λμ-演算的一些高级性质,如 Stability 与 Perpendicular Lines Property;由此还可推出并行计算的不可能性。

问题
λμ-演算虽将 Curry-Howard 对应扩展到经典逻辑,却不满足 Böhm 定理,也缺乏对应的近似理论。
方法
作者将 Ehrhard 与 Regnier 的 Taylor 展开适配到 λμ-演算,建立资源敏感的近似理论,并由此构造合理的 λμ-理论。
评估
在该理论中证明 Stability 和 Perpendicular Lines Property,并由此推出并行计算不可能;评估以理论证明为主。
原文摘要(Abstract)

The λμ-calculus plays a central role in the theory of programming languages as it extends the Curry-Howard correspondence to classical logic. A major drawback is that it does not satisfy Böhm’s Theorem and it lacks the corresponding notion of approximation. On the contrary, we show that Ehrhard and Regnier’s Taylor expansion can be easily adapted, thus providing a resource conscious approximation theory. This produces a sensible λμ-theory with which we prove some advanced properties of the λμ-calculus, such as Stability and Perpendicular Lines Property, from which the impossibility of parallel computations follows.

链接与引用

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

BibTeX
@inproceedings{Barbarossa22,
  title = {Resource approximation for the λμ-calculus},
  author = {Davide Barbarossa},
  booktitle = {LICS},
  year = {2022},
  doi = {10.1145/3531130.3532469}
}