paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Type-directed operational semantics for gradual typing

渐进类型的类型导向操作语义
JFP vol.342024匹配度 1/10 · 论文研究渐进类型语言的形式语义与类型安全证明,属于纯 PL 形式语义/类型系统工作,与用户关注的 LLM/Agent 与静态分析、形式化验证交叉,以及浮点程序分析、贝叶斯程序分析均无直接关系。引用 0 inbox
WENJIA YE, BRUNO C. D. S. OLIVEIRA
crossref: 2026-09-10

AI 速览

一句话:提出类型导向操作语义(TDOS),直接给出渐进类型语言的语义,避免经强制转换演算间接编码。

渐进类型语言的语义通常通过精化到强制转换演算(cast calculus)间接给出,这与直接定义操作语义的传统方式不同。本文提出用类型导向操作语义(TDOS)直接刻画渐进类型语言:类型标注在操作上相关,可触发基于类型的值转换。作者构造两个演算:λB^g 受 blame calculus 启发但具有隐式类型转换,λe 则基于 TDOS 探索急切求值语义。两者均证明类型安全;λB^g 还给出带 blame 标签的变体,并证明其相对于 blame calculus 的语义是可靠且完备的;两个演算均满足渐进保证。所有结果在 Coq 中形式化。

问题
渐进类型语言的语义通常间接地通过精化到强制转换演算给出;本文关注如何直接以操作语义定义此类语言。
方法
采用类型导向操作语义(TDOS),让类型标注在操作上相关并触发基于类型的值转换;构造 λB^g 与 λe 两个演算,并处理 blame 标签。
评估
证明两个演算的类型安全与渐进保证,证明带 blame 标签的 λB^g 相对 blame calculus 的可靠性与完备性,并在 Coq 中形式化所有结果。
原文摘要(Abstract)

Abstract The semantics of gradually typed languages is typically given indirectly via an elaboration into a cast calculus. This contrasts with more conventional formulations of programming language semantics, where the semantics of a language is given directly using, for instance, an operational semantics. This paper presents a new approach to give the semantics of gradually typed languages directly. We use a recently proposed variant of small-step operational semantics called type-directed operational semantics (TDOS). In a TDOS, type annotations become operationally relevant and can affect the result of a program. In the context of a gradually typed language, type annotations are used to trigger type-based conversions on values. We illustrate how to employ a TDOS on gradually typed languages using two calculi. The first calculus, called $\lambda B^{g}$ , is inspired by the semantics of the blame calculus, but it has implicit type conversions, enabling it to be used as a gradually typed language. The second calculus, called $\lambda e$ , explores an eager semantics for gradually typed languages using a TDOS. For both calculi, type safety is proved. For the $\lambda B^{g}$ calculus, we also present a variant with blame labels and illustrate how the TDOS can also deal with such an important feature of gradually typed languages. We also show that the semantics of $\lambda B^{g}$ with blame labels is sound and complete with respect to the semantics of the blame calculus, and that both calculi come with a gradual guarantee . All the results have been formalized in the Coq theorem prover.

链接与引用

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

BibTeX
@article{paperbot2689,
  title = {Type-directed operational semantics for gradual typing},
  author = {WENJIA YE and BRUNO C. D. S. OLIVEIRA},
  journal = {Journal of Functional Programming},
  volume = {34},
  year = {2024},
  doi = {10.1017/s0956796824000078}
}