paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Propositions-as-types and shared state

命题即类型与共享状态
ICFP 5(ICFP)2021匹配度 3/10 · 论文属于编程语言理论中的类型系统与线性逻辑/会话并发方向,与用户画像中的静态分析、LLM/Agent、浮点或贝叶斯程序分析没有直接交集;仅作为PL形式化基础可能间接相关。引用 13 inbox
Pedro Rocha, Luís Caires
crossref: 2026-09-10

AI 速览

一句话:将共享可变状态融入会话并发语言的命题即类型线性逻辑解释,并保持安全与活性。

本文研究如何将共享可变状态原则性地集成到基于会话的并发编程语言的命题即类型(propositions-as-types)线性逻辑解释中。传统上,函数核心的类型系统常基于命题即类型对应自动保证强安全性和活性,而命令式特性多依赖逻辑外构造。作者受微分线性逻辑规则启发,将非确定性与共享机制纳入逻辑系统,支持可共享的一等引用单元存储任意持久对象。系统保证会话保真、进展、合流与规范化;并证明在自然扩展的一等锁下,保持性和进展仍能成立。文中还通过示例展示其表达能力,包括可共享的并发抽象数据类型。

问题
如何在保持命题即类型与线性逻辑对应所带来的强安全与活性保证的同时,为基于会话的并发语言引入共享可变状态。
方法
受微分线性逻辑中非确定性与共享规则启发,将共享可变状态集成到会话类型线性逻辑解释中,并扩展到一等锁。
评估
通过形式化证明会话保真、进展、合流与规范化,并给出一等锁扩展下的保持性与进展结果。辅以示例展示语言表达力,包括可共享的并发抽象数据类型。
原文摘要(Abstract)

We develop a principled integration of shared mutable state into a proposition-as-types linear logic interpretation of a session-based concurrent programming language. While the foundation of type systems for the functional core of programming languages often builds on the proposition-as-types correspondence, automatically ensuring strong safety and liveness properties, imperative features have mostly been handled by extra-logical constructions. Our system crucially builds on the integration of nondeterminism and sharing, inspired by logical rules of differential linear logic, and ensures session fidelity, progress, confluence and normalisation, while being able to handle first-class shareable reference cells storing any persistent object. We also show how preservation and, perhaps surprisingly, progress, resiliently survive in a natural extension of our language with first-class locks. We illustrate the expressiveness of our language with examples highlighting detailed features, up to simple shareable concurrent ADTs.

链接与引用

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

BibTeX
@article{paperbot1131,
  title = {Propositions-as-types and shared state},
  author = {Pedro Rocha and Luís Caires},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {5},
  number = {ICFP},
  year = {2021},
  doi = {10.1145/3473584}
}