paperbot · PL 论文追踪

全部论文 待读 收藏

P1 Skeletal semantics and their interpretations

骨架语义及其解释
POPL 3(POPL)2019匹配度 5/10 · 论文属于形式语义与抽象解释的基础理论,与静态分析理论相关,可为程序分析提供语义基础;但未涉及 LLM/Agent、浮点程序分析或贝叶斯程序分析,也没有 AI 与 PL 的交叉,因此与当前研究画像的核心问题只算间接相关。引用 25 inbox
Martin Bodin, Philippa Gardner, Thomas Jensen, Alan Schmitt
crossref: 2026-09-10

AI 速览

一句话:提出骨架语义,用统一解释从语言构造的语义骨架系统导出具体/抽象语义及一致性结果。

基于结构化操作语义的机械化语言规范开发成本很高,且已有理论框架难以系统连接具体与抽象语义。本文提出语言的骨架语义:每个骨架完整描述一个语言构造的语义行为。作者定义通用的解释概念,以语言无关的方式从骨架语义导出语义判断,并研究四种解释:良构性解释、具体解释、抽象解释,以及面向流敏感分析的约束生成器。核心结果是证明不同解释之间的一般一致性,只需依赖简单的语言相关引理。以简单 While 语言为例展示该方法。

问题
如何系统化地开发机械化语言规范,并在统一框架中连接具体语义与抽象语义,从而服务已验证编译器和可靠程序分析,是本文研究的问题。
方法
提出骨架语义,用骨架描述各语言构造完整语义;定义语言无关的解释机制,并提供良构性、具体、抽象及流敏感分析约束生成四种解释。
评估
以简单 While 语言为例说明方法,并证明解释间的一般一致性结果,这些结果仅依赖简单的语言相关引理。
原文摘要(Abstract)

The development of mechanised language specification based on structured operational semantics, with applications to verified compilers and sound program analysis, requires huge effort. General theory and frameworks have been proposed to help with this effort. However, none of this work provides a systematic way of developing concrete and abstract semantics, connected together by a general consistency result. We introduce a skeletal semantics of a language, where each skeleton describes the complete semantic behaviour of a language construct. We define a general notion of interpretation , which provides a systematic and language-independent way of deriving semantic judgements from the skeletal semantics. We explore four generic interpretations: a simple well-formedness interpretation; a concrete interpretation; an abstract interpretation; and a constraint generator for flow-sensitive analysis. We prove general consistency results between interpretations, depending only on simple language-dependent lemmas. We illustrate our ideas using a simple While language.

链接与引用

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

BibTeX
@article{paperbot661,
  title = {Skeletal semantics and their interpretations},
  author = {Martin Bodin and Philippa Gardner and Thomas Jensen and Alan Schmitt},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {3},
  number = {POPL},
  year = {2019},
  doi = {10.1145/3290357}
}