paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Ill-Typed Programs Don’t Evaluate

非良类型程序不会求值
POPL 8(POPL)2024匹配度 3/10 · 该论文属于类型系统与程序验证的形式化理论工作,与用户关注的 PL 与 LLM/Agent 交叉(如用 LLM 改进静态分析/形式化验证、分析 Agentic 程序)没有直接关联;仅在“静态分析/形式化验证”大方向上有较弱的理论背景价值。引用 3 inbox
Steven Ramsay, Charlie Walpole
crossref: 2026-09-10

AI 速览

一句话:提出双侧类型系统,可反驳类型公式,从而保证良类型程序不出错、非良类型程序不会求值。

该文提出双侧类型系统,作为类型公式的相继式演算。它允许对复合程序表达式的类型作假设推理,并能反驳类型公式;通过引入“所有值”的类型,系统给出更精细的良类型与非良类型概念。核心保证是:良类型程序不会出错,而非良类型程序不会求值到值。作者将其用于高阶程序验证中的不正确性推理,并在带构造子和模式匹配的语言中实现精确数据流类型标注。最后,文章把元层否定内化为类型上的补算子,并给出替代类型判定语义:它保证非良类型程序不求值,但良类型程序仍可能出错。

问题
如何为高阶程序验证提供不正确性推理,使得不仅能保证良类型程序不出错,还能刻画并保证非良类型程序不会求值到值。
方法
提出双侧类型系统,用相继式演算支持类型公式的假设推理与反驳,引入所有值类型,并研究将元层否定内化为类型补算子。
评估
通过带构造子和模式匹配的语言中的数据流类型标注案例展示其精确性,并分析两种类型判定语义的保证。
原文摘要(Abstract)

We introduce two-sided type systems, which are sequent calculi for typing formulas. Two-sided type systems allow for hypothetical reasoning over the typing of compound program expressions, and the refutation of typing formulas. By incorporating a type of all values, these type systems support more refined notions of well-typing and ill-typing, guaranteeing both that well-typed programs don’t go wrong and that ill-typed programs don’t evaluate - that is, reach a value. This makes two-sided type systems suitable for incorrectness reasoning in higher-order program verification, which we illustrate through an application to precise data-flow typing in a language with constructors and pattern matching. Finally, we investigate the internalisation of the meta-level negation in the system as a complement operator on types. This motivates an alternative semantics for the typing judgement, which guarantees that ill-typed programs don’t evaluate, but in which well-typed programs may yet go wrong.

链接与引用

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

BibTeX
@article{paperbot2578,
  title = {Ill-Typed Programs Don’t Evaluate},
  author = {Steven Ramsay and Charlie Walpole},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {8},
  number = {POPL},
  year = {2024},
  doi = {10.1145/3632909}
}