paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Typing Records, Maps, and Structs

记录、映射与结构体的类型化
ICFP 7(ICFP)2023匹配度 1/10 · 该论文属于纯类型论/编程语言理论,研究记录类型的子类型与类型算子,与用户主攻的 PL×AI、浮点程序分析、贝叶斯程序分析均无直接交集;仅在最宽泛的静态分析/类型系统背景上有一丝关联。引用 3 inbox
Giuseppe Castagna
crossref: 2026-09-10

AI 速览

一句话:提出统一支持 struct 与 map 两种用法的记录类型理论,含语义子类型、无回溯子类型判定算法与记录操作类型算子。

记录是键到值的有限函数,却有两种用法:struct 用不同键指向不同类型的值、按名访问且缺失键报错;map 的键由表达式计算、所有值同类型、缺失键返回 Null 等默认值。本文提出统一覆盖两者的类型理论:记录类型既可对单个键(struct 式)也可对键集合(map 式)指定不同类型,同一记录表达式能以两种风格访问。针对动态类型语言,该理论包含由子类型刻画的联合与交集类型;作者用语义解释定义记录子类型,导出分解规则,给出无回溯子类型算法并证明其正确,还为记录类型提供规范表示,用以定义选择、拼接、字段删除等操作的类型算子。

问题
记录在语言中有 struct 式(不同键对应不同类型的值、名义访问、缺失键报错)与 map 式(键由表达式计算、值类型统一、缺失键返回默认值)两种截然不同的用法,如何用统一的类型理论同时刻画二者。
方法
提出面向动态类型语言的统一记录类型理论,记录类型可对单个键或键集合指定类型,并包含由子类型关系刻画的联合与交集类型;用语义解释定义记录子类型并导出分解规则,据此设计无回溯的子类型算法,并给出记录类型的规范表示以定义选择、拼接、字段删除等操作所需的类型算子。
评估
以形式化定义与证明为主:证明所给无回溯子类型算法的正确性,并以规范表示支撑各类记录操作的类型算子定义;摘要未报告实现或实验评估。
原文摘要(Abstract)

Records are finite functions from keys to values. In this work we focus on two main distinct usages of records: structs and maps. The former associate different keys to values of different types, they are accessed by providing nominal keys, and trying to access a non-existent key yields an error. The latter associate all keys to values of the same type, they are accessed by providing expressions that compute a key, and trying to access a non-existent key usually yields some default value such as Null or nil. Here, we propose a type theory that covers both kinds of usage, where record types may associate to different types either single keys (as for structs) or sets of keys (as for maps) and where the same record expression can be accessed and used both in the struct-like style and in the map-like style we just described. Since we target dynamically-typed languages our type theory includes union and intersection types, characterized by a subtyping relation. We define the subtyping relation for our record types via a semantic interpretation and derive the decomposition rules to decide it, define a backtracking-free subtyping algorithm that we prove to be correct, and provide a canonical representation for record types that is used to define various type operators needed to type record operations such as selection, concatenation, and field deletion.

链接与引用

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

BibTeX
@article{paperbot1901,
  title = {Typing Records, Maps, and Structs},
  author = {Giuseppe Castagna},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {7},
  number = {ICFP},
  year = {2023},
  doi = {10.1145/3607838}
}