paperbot · PL 论文追踪

全部论文 待读 收藏

P2 On Polymorphic Sessions and Functions

论多态会话与函数
TOPLAS 43(2)2021匹配度 2/10 · 该论文是纯 PL 理论工作,研究多态会话π演算与线性 System F 之间的互逆编码,属于类型系统与逻辑基础,不涉及 LLM/Agent、静态分析、浮点程序分析或贝叶斯程序分析,与用户当前核心研究方向距离较远。引用 7 inbox
Bernardo Toninho, Nobuko Yoshida
crossref: 2026-09-10

AI 速览

一句话:建立多态会话π演算与线性System F之间互逆且完全抽象的编码,并由函数理论导出会话类型结果。

本文利用会话类型的逻辑基础,研究何种类型规则能够精确刻画Λ演算行为。基于线性逻辑相继演算与自然演绎可靠性和完备性的证明论内容,作者首次给出多态会话π演算与线性System F之间的相互可逆、完全抽象的过程即函数与函数即过程编码。由此可将Λ演算理论迁移到会话演算:一方面通过System F中的代数表示刻画归纳与余归纳会话类型;另一方面将结果扩展到支持值传递与进程传递,并证明强规范化。

问题
如何确定一种类型纪律,使其精确对应多态会话π演算与线性System F,并在编码下保持行为等价与互逆性。
方法
利用线性逻辑相继演算与自然演绎的证明论,构造多态会话π演算与线性System F之间的双向编码,并证明其互逆与完全抽象。
评估
以证明论定理推导归纳与余归纳会话类型在System F中的代数表示,并扩展至值与进程传递,证明强规范化;属于理论证明而非实证评估。
原文摘要(Abstract)

This work exploits the logical foundation of session types to determine what kind of type discipline for the Λ-calculus can exactly capture, and is captured by, Λ-calculus behaviours. Leveraging the proof theoretic content of the soundness and completeness of sequent calculus and natural deduction presentations of linear logic, we develop the first mutually inverse and fully abstract processes-as-functions and functions-as-processes encodings between a polymorphic session π-calculus and a linear formulation of System F. We are then able to derive results of the session calculus from the theory of the Λ-calculus: (1) we obtain a characterisation of inductive and coinductive session types via their algebraic representations in System F; and (2) we extend our results to account for value and process passing, entailing strong normalisation.

链接与引用

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

BibTeX
@article{paperbot1217,
  title = {On Polymorphic Sessions and Functions},
  author = {Bernardo Toninho and Nobuko Yoshida},
  journal = {ACM Transactions on Programming Languages and Systems},
  volume = {43},
  number = {2},
  year = {2021},
  doi = {10.1145/3457884}
}