paperbot · PL 论文追踪

全部论文 待读 收藏

P2 A Metalanguage for Cost-Aware Denotational Semantics

面向代价感知指称语义的元语言
LICS 2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2023匹配度 1/10 · 该论文属于纯程序语言形式语义与代价感知指称语义,关注元语言、合成模型与计算充分性证明,未涉及静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析,与用户当前核心研究方向基本无关。引用 7 inbox
Yue Niu, Robert Harper
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:提出用于代价感知指称语义的元语言,为 STLC 与 Modernized Algol 构造合成模型并证明代价感知计算充分性。

本文研究如何在依赖类型论中合成地开发代价感知的指称语义及其元理论。作者扩展 Niu 等人关于代价与行为验证的工作,定义了两个表达力递进的元语言,用于建立代价感知的指称模型。他们为简单类型 λ 演算以及带一阶存储和 while 循环的 Modernized Algol 构造合成指称模型,并证明其满足经典 Plotkin 型计算充分性定理的代价感知推广。由于证明在区分内涵构造与外延构造的相分离合成语言中完成,相应结果可自然限制为外延定理。该工作正面回答了原工作提出的猜想,并提供了面向代价感知编程、验证与元理论的框架。

问题
如何为编程语言建立兼顾运行代价与行为等价的指称语义及其元理论,并使相关证明可形式化地展开与复用。
方法
在依赖类型论中定义两个表达力递进的元语言,以相分离方式区分内涵与外延构造,并为简单类型 λ 演算与 Modernized Algol 构造合成指称模型。
评估
证明这些模型满足代价感知的 Plotkin 型计算充分性定理,并表明结果可限制为对应外延定理,从而正面回答已有猜想。
原文摘要(Abstract)

We present metalanguages for developing synthetic cost-aware denotational semantics of programming languages. Extending recent advances by Niu et al. in cost and behavioral verification in dependent type theory, we define two successively more expressive metalanguages for studying cost-aware metatheory. We construct synthetic denotational models of the simply-typed lambda calculus and Modernized Algol, a language with first-order store and while loops, and show that they satisfy a cost-aware generalization of the classic Plotkin-type computational adequacy theorem. Moreover, by developing our proofs in a synthetic language of phase-separated constructions of intension and extension, our results easily restrict to the corresponding extensional theorems. Consequently, our work provides a positive answer to the conjecture raised in op. cit. and contributes a framework for cost-aware programming, verification, and metatheory.

链接与引用

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

BibTeX
@inproceedings{abs-2209-12669,
  title = {A Metalanguage for Cost-Aware Denotational Semantics},
  author = {Yue Niu and Robert Harper},
  booktitle = {LICS},
  year = {2023},
  doi = {10.1109/lics56636.2023.10175777}
}