paperbot · PL 论文追踪

全部论文 待读 收藏

P2 A Denotational Semantics for SPARC TSO

SPARC TSO 的一种指称语义
LMCS vol.Volume 15, Issue 22019匹配度 3/10 · 论文属于程序语言形式语义与弱内存模型方向,与用户对形式化验证的广义兴趣有间接关联,但不涉及 LLM/Agent 改进静态分析或形式化验证、浮点程序分析、贝叶斯程序分析,也未面向 ML/Agentic 程序。引用 1 inbox
Ryan Kavanagh, Stephen Brookes
crossref: 2026-09-10

AI 速览

一句话:为 SPARC TSO 弱内存模型提出可组合的 pomsets 指称语义,并证明其相对公理语义可靠且完备。

SPARC TSO 是广泛使用的弱内存模型,其公理化定义是非组合式的,难以对程序行为进行模块化推理。本文提出一种基于 pomsets(偏序多重集)的指称语义:使用带缓冲的状态与归纳式的执行定义,为 pomsets 赋予输入-输出含义,从而精确刻画 SPARC TSO 所允许的行为。作者证明该指称语义相对于公理语义是可靠且完备的,即二者所允许的行为集合完全一致。该组合式语义便于研究 SPARC TSO,并支持程序行为的模块化分析。

问题
SPARC TSO 弱内存模型的公理化定义不具有组合性,导致难以对程序行为进行模块化推理与分析。
方法
提出基于 pomsets 的指称语义,用带缓冲的状态和归纳式执行定义赋予 pomsets 输入-输出含义,以组合方式刻画 SPARC TSO 允许的行为。
评估
证明该指称语义相对于既有公理语义既可靠又完备,即精确覆盖公理语义所允许的全部行为,并说明其支持 SPARC TSO 的模块化分析。
原文摘要(Abstract)

The SPARC TSO weak memory model is defined axiomatically, with a non-compositional formulation that makes modular reasoning about programs difficult. Our denotational approach uses pomsets to provide a compositional semantics capturing exactly the behaviours permitted by SPARC TSO. It uses buffered states and an inductive definition of execution to assign an input-output meaning to pomsets. We show that our denotational account is sound and complete relative to the axiomatic account, that is, that it captures exactly the behaviours permitted by the axiomatic account. Our compositional approach facilitates the study of SPARC TSO and supports modular analysis of program behaviour.

链接与引用

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

BibTeX
@article{paperbot796,
  title = {A Denotational Semantics for SPARC TSO},
  author = {Ryan Kavanagh and Stephen Brookes},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 15, Issue 2},
  year = {2019},
  doi = {10.23638/lmcs-15(2:10)2019}
}