paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Quantitative semantics of the lambda calculus: Some generalisations of the relational model

λ演算的定量语义:关系模型的一些推广
LICS 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2017匹配度 2/10 · 论文属于纯形式语义与定量语义理论研究,讨论λ演算的关系模型、博弈语义和Taylor展开,未涉及用户核心关注的LLM/Agent、静态分析、浮点程序分析或贝叶斯程序分析;仅与PL理论基础有间接关联。引用 31 inbox
C.-H. Luke Ong
crossref: 2026-09-12dblp: 2026-09-12

AI 速览

一句话:综述λ演算的定量语义,证明关系语义、HO/N博弈语义与Taylor展开语义等价,并讨论两类关系模型推广。

本文综述λ演算定量语义的近期进展,核心问题是刻画带计量的高阶程序语义,并统一不同语义模型。作者以线性逻辑的退化关系模型 MRel 为起点,说明简单类型λ演算的三种定量语义——关系语义、HO/N 博弈语义与 Taylor 展开语义——彼此等价。随后介绍关系模型的两种推广:Laird 等人研究的以完备交换半环 R 为权重的 R-加权关系模型,以及 Fiore 等人提出的广义结构 species。文中还简要讨论这些模型在高层程序定量分析中的应用。

问题
如何为简单类型λ演算建立统一的定量语义,并将关系模型推广到更一般的权重与结构设定。
方法
以关系模型 MRel 为基础,比较并证明其与 HO/N 博弈语义、Taylor 展开语义的等价性,再考察 R-加权关系模型与广义结构 species。
评估
通过理论等价性证明与两类推广模型的应用案例分析,说明这些语义在高层程序定量分析中的用途。
原文摘要(Abstract)

We present an overview of some recent work on the quantitative semantics of the λ-calculus. Our starting point is the fundamental degenerate model of linear logic, the relational model MRel. We show that three quantitative semantics of the simply-typed λ-calculus are equivalent: the relational semantics, HO/N game semantics, and the Taylor expansion semantics. We then consider two recent generalisations of the relational model: first, R-weighted relational models where R is a complete commutative semiring, as studied by Laird et al.; secondly, generalised species of structures, as introduced by Fiore et al. In each case, we briefly discuss some applications to quantitative analysis of higher-order programs.

链接与引用

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

BibTeX
@inproceedings{Ong17,
  title = {Quantitative semantics of the lambda calculus: Some generalisations of the relational model},
  author = {C.-H. Luke Ong},
  booktitle = {LICS},
  year = {2017},
  doi = {10.1109/lics.2017.8005064}
}