paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Persistent Iterators with Value Semantics

具有值语义的持久迭代器
PLDI 10(PLDI)2026匹配度 1/10 · 该论文属于编程语言设计与持久化数据结构抽象,关注迭代器安全性与值语义,与用户画像中的静态分析、LLM/Agent 交叉、浮点程序分析、贝叶斯程序分析等核心方向均无直接关联。引用 1 inbox
Yihe Li, Gregory J. Duck
crossref: 2026-09-10

AI 速览

一句话:提出持久迭代器抽象,将命令式迭代器风格与持久化数据结构的值语义结合,兼顾安全性与迭代器表达力。

主流命令式语言(如 C++)中可变容器的迭代器存在失效、别名、数据竞争与隐蔽副作用等隐患;而函数式语言采用的不可变数据结构虽规避了变异风险,却依赖递归与 map、foldl、traverse 等高阶组合子,既不适合表达某些算法,又暴露底层结构细节。本文提出持久迭代器(persistent iterators):迭代器在创建时对其底层容器做版本快照,从而免疫失效与别名问题;++、erase 等迭代器操作作用于迭代器本地的容器副本,实现真正的值语义——变量可重新绑定到新的持久值,同时旧版本仍可访问。作者以 LibFpp 实现该设计,这是一个 C++ 容器库,提供持久化 vector、map、set、string 等 STL 对应抽象。评估表明,LibFpp 保留了基于迭代器编程的表达力,消除了迭代器失效,且渐近复杂度与 STL 实现相当,仅因持久化而具有更高的常数因子开销;其目标场景是既需要持久性与安全性、又希望沿用熟悉迭代器模式的开发者。

问题
命令式语言中可变容器的迭代器易发生失效、别名、数据竞争与副作用,而函数式不可变数据结构的递归/组合子风格又不总能自然表达算法并会泄露实现细节。
方法
提出持久迭代器:迭代器创建时对底层容器做版本快照以保证安全,迭代器操作作用于迭代器本地副本,从而实现真正的值语义;并以 C++ 库 LibFpp 实现持久化的 vector、map、set、string 等 STL 对应容器。
评估
通过 LibFpp 的实现与实验评估,展示其保留了迭代器编程的表达力、消除了迭代器失效,并在渐近复杂度上与 STL 实现相当(仅常数因子开销更高)。
原文摘要(Abstract)

Iterators are a fundamental programming abstraction for traversing and modifying elements in containers in mainstream imperative languages such as C++. Iterators provide a uniform access mechanism that hides low-level implementation details of the underlying data structure. However, iterators over mutable containers suffer from well-known hazards including invalidation, aliasing, data races, and subtle side effects. Immutable data structures, as used in functional programming languages, avoid the pitfalls of mutation but rely on a very different programming model based on recursion and higher-order combinators (map, foldl, traverse, etc.) rather than iteration. However, these combinators are not always well-suited to expressing certain algorithms, and recursion can expose implementation details of the underlying data structure. In this paper, we propose persistent iterators---a new abstraction that reconciles the familiar iterator-based programming style of imperative languages with the semantics of persistent data structures. A persistent iterator snapshots the version of its underlying container at creation, ensuring safety against invalidation and aliasing. Iterator operations (++, erase, etc.) operate on the iterator-local copy of the container, giving true value semantics: variables can be rebound to new persistent values while previous versions remain accessible. We implement our approach in the form of LibFpp---a C++ container library providing persistent vectors, maps, sets, strings, and other abstractions as persistent counterparts to the Standard Template Library (STL). Our evaluation shows that LibFpp retains the expressiveness of iterator-based programming, eliminates iterator-invalidation, and achieves asymptotic complexities comparable to STL implementations---albeit with the higher constant-factor overheads of persistence. Our design targets use cases where persistence and safety are desired, while allowing developers to retain familiar iterator-based programming patterns.

链接与引用

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

BibTeX
@article{LiD26,
  title = {Persistent Iterators with Value Semantics},
  author = {Yihe Li and Gregory J. Duck},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {10},
  number = {PLDI},
  year = {2026},
  doi = {10.1145/3808324}
}