paperbot · PL 论文追踪

全部论文 待读 收藏

P2 A Theorem Proving Approach to Programming Language Semantics

程序语言语义的定理证明方法
ICSE 2023 IEEE/ACM 45th International Conference on Software Engineering: Software Engineering Education and Training (ICSE-SEET)2023匹配度 2/10 · 论文属于编程语言形式语义与定理证明,虽与形式化验证有间接关联,但主要面向语义教学与F*编码,并未涉及静态分析、LLM/Agent、浮点或贝叶斯程序分析等用户核心方向。引用 0 inbox
Subhajit Roy
crossref: 2026-09-12dblp: 2026-09-12

AI 速览

一句话:在 F* 证明助手中编码 WHILE 语言的操作、指称与公理语义,展示定理证明可辅助语义教学与研究。

程序语言语义是计算机科学的核心课题,但形式化程度极高,学生往往需要反复手写大量证明才能深入理解,过程繁琐且易出错。本文主张将现代定理证明器引入语义的教学与研究:作者在流行的 F* 证明助手中,对 WHILE 语言的操作语义、指称语义与公理语义三种风格分别进行编码,并在同一框架下机器化验证。案例表明,一旦程序及其语义被编码,现代证明助手只需极少人工干预即可证明若干有趣的程序语言性质。作者认为,以证明助手为工具教授程序语言语义,不仅能带来更具体的理解,也能培养未来研究者把定理证明器当作研究中的基础工具,而非事后补充。

问题
程序语言语义形式化程度高,纸笔证明繁琐,学生难以借助大量证明获得深入理解,研究者的证明工作也缺乏机器支持。
方法
在 F* 证明助手中对 WHILE 语言的操作语义、指称语义与公理语义三种风格进行编码,并以机器化证明验证语言性质。
评估
以 F* 中 WHILE 语言语义编码与语言性质的机器化证明作为案例研究,显示所需人工干预极少;属于教学与工具实践层面的经验论证,而非基准评测。
原文摘要(Abstract)

The semantics of programming languages is one of the core topics in computer science. This topic is formalism-heavy and requires the student to attempt numerous proofs for a deep understanding. We argue that modern theorem provers are excellent aids to teaching and understanding programming language semantics. As pen-and-paper proofs get automated via the theorem prover, it allows an experiment-driven strategy at exploring this topic. This article provides an encoding of the semantics of the WHILE language in the most popular styles—operational, denotational, and axiomatic—within the F* proof assistant. We show that once the program and its semantics are encoded, modern proof assistants can prove exciting language features with minimal human assistance. We believe that teaching programming languages via proof assistants will not only provide a more concrete understanding of this topic but also prepare future programming language researchers to use theorem provers as fundamental tools in their research and not as an afterthought.

链接与引用

DOI 原文 · DBLP

BibTeX
@inproceedings{Roy23,
  title = {A Theorem Proving Approach to Programming Language Semantics},
  author = {Subhajit Roy},
  booktitle = {ICSE},
  year = {2023},
  doi = {10.1109/icse-seet58685.2023.00021}
}