paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Concrete categories and higher-order recursion

具体范畴与高阶递归
LICS Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science2022匹配度 3/10 · 论文属于概率与可微编程的形式语义、sheaf 模型和递归充分性定理,与用户核心关注的“静态分析/Agentic 程序/LLM 交叉”没有直接关联;仅在概率编程语义基础层面可能有间接联系,且缺乏工程实现与工业落地内容。引用 8 inbox
Cristina Matache, Sean Moss, Sam Staton
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:提出一类具体层模型,统一概率与可微编程等语义,并证明通用计算充分性定理。

本文研究带递归的按值调用高阶语言的指称语义。作者提出“具体层(concrete sheaf)模型”族,将概率编程、可微编程以及完全抽象逻辑关系模型等文献中的例子统一为特例。处理递归时采用合成域论(synthetic domain theory)的思路:从层范畴的 site 上一类可允许单态射出发,一般性地构造 lifting 单子,从而得到由具体 site 和单态射类参数化的模型族。主要结果是证明该模型族满足通用的计算充分性(computational adequacy)定理,即操作语义与指称语义在观察上一致。这为多种效应语言提供统一语义框架。

问题
如何为带递归的按值调用高阶语言提供统一指称语义模型,并覆盖概率编程、可微编程等文献中的具体例子。
方法
在具体层范畴上,从 site 的可允许单态射类出发一般性地构造 lifting 单子,得到由具体 site 和单态射类参数化的模型族。
评估
通过理论证明给出通用的计算充分性定理,验证模型族与操作语义在观察上一致。
原文摘要(Abstract)

We study concrete sheaf models for a call-by-value higher-order language with recursion. Our family of sheaf models is a generalization of many examples from the literature, such as models for probabilistic and differentiable programming, and fully abstract logical relations models. We treat recursion in the spirit of synthetic domain theory. We provide a general construction of a lifting monad starting from a class of admissible monomorphisms in the site of the sheaf category. In this way, we obtain a family of models parametrized by a concrete site and a class of monomorphisms, for which we prove a general computational adequacy theorem.

链接与引用

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

BibTeX
@inproceedings{MatacheMS22,
  title = {Concrete categories and higher-order recursion},
  author = {Cristina Matache and Sean Moss and Sam Staton},
  booktitle = {LICS},
  year = {2022},
  doi = {10.1145/3531130.3533370}
}