paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Polymorphic Records for Dynamic Languages

面向动态语言的多态记录
OOPSLA 9(OOPSLA1)2025匹配度 2/10 · 这篇论文属于纯编程语言理论中的行多态与集合论类型系统,并为 Elixir 设计渐进类型系统;它不涉及 LLM/Agent、机器学习系统、浮点程序分析或贝叶斯程序分析,与用户的核心交叉方向几乎无关,仅在“静态分析/类型系统”这一宽泛层面上有很弱的联系。引用 1 inbox
Giuseppe Castagna, Loïc Peyrot
crossref: 2026-09-10

AI 速览

一句话:为带集合论类型(并、交、否定)的记录引入行多态,给出子类型判定与类型检查算法,并证明类型系统可靠。

针对动态语言静态类型化中记录类型难以灵活扩展与删除的问题,本文在具有并、交、否定等集合论类型的系统中研究记录的行多态。作者将记录类型解释为记录值集合,将行变量解释为省略部分键的“行”集合,从而以集合包含定义子类型;形式化一个支持字段扩展、选择与删除的 λ-演算及其操作语义,并给出类型系统,证明其可靠性。论文提供判定类型关系与子类型关系的算法,以及判定两个类型能否通过实例化形成子类型关系的算法。该工作受 Elixir 渐进类型系统等动态语言静态化趋势驱动。

问题
动态语言引入静态/渐进类型时,如何为记录提供支持字段扩展、选择与删除的行多态,并在含并、交、否定的集合论类型下定义子类型。
方法
将记录类型解释为记录值集合、行变量解释为行集合,以集合包含定义子类型;形式化带扩展、选择、删除的 λ-演算与类型系统,证明可靠性,并给出判定 typing、subtyping 及类型可实例化子类型关系的算法。
评估
以类型系统可靠性证明和判定算法为主要评估,摘要未报告实现或实验;动机来自 Elixir 渐进类型系统。
原文摘要(Abstract)

We study row polymorphism for records types in systems with set-theoretic types, specifically, union, intersection, and negation types. We consider record types that embed row variables and define a subtyping relation by interpreting record types into sets of record values, and row variables into sets of rows, that is, “chunks” of record values where some record keys are left out: subtyping is then containment of the interpretations. We define a λ -calculus equipped with operations for field extension, selection, and deletion, its operational semantics, and a type system that we prove to be sound. We provide algorithms for deciding the typing and subtyping relations, and to decide whether two types can be instantiated to make one subtype of the other. This research is motivated by the current trend of defining static type systems for dynamic languages and, in our case, by an ongoing effort of endowing the Elixir programming language with a gradual type system.

链接与引用

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

BibTeX
@article{paperbot3172,
  title = {Polymorphic Records for Dynamic Languages},
  author = {Giuseppe Castagna and Loïc Peyrot},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {9},
  number = {OOPSLA1},
  year = {2025},
  doi = {10.1145/3720497}
}