paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Read/write factorizable programs

读/写可因子化程序
JFP vol.332023匹配度 2/10 · 论文属于编程语言理论与类型系统方向,研究 cons-free 范式和函数复杂度类刻画,虽然与 PL 相关,但未涉及用户关注的静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析,也缺乏工程落地与工业应用。引用 0 inbox
SIDDHARTH BHASKAR, JAKOB GRUE SIMONSEN
crossref: 2026-09-10

AI 速览

一句话:通过类型系统区分只可析构与只可构造的数据,提出 RW-可因子化程序,将 cons-free 范式扩展到函数复杂度类。

在 cons-free 编程范式中,程序不使用构造子而只用析构子;已有工作表明,简单一阶语言中的 cons-free 字符串程序恰好刻画 P 等判定复杂度类,但由于根本性原因,该范式无法刻画任何函数复杂度类。本文将其扩展为读/写可因子化程序:通过程序变量上的类型系统,规定数据要么只能被析构,要么只能被构造。作者证明,RW-可因子化的字符串程序恰好刻画多项式时间函数类 FP,尾递归的 RW-可因子化程序恰好刻画对数空间函数类 FL。最后,论文提出并解决了两个 RW-可因子化程序进行语法组合这一非平凡问题。

问题
cons-free 范式能刻画若干判定复杂度类,却因根本原因无法刻画函数复杂度类;本文要扩展该范式以覆盖 FP、FL 等函数复杂度类。
方法
在程序变量上引入类型系统,将数据限制为只可析构或只可构造,定义读/写可因子化程序,并研究其语法组合。
评估
通过证明 RW-可因子化字符串程序恰好刻画 FP、尾递归版本恰好刻画 FL,并给出两个程序语法组合的解法来评估。
原文摘要(Abstract)

Abstract In the cons-free programming paradigm, we eschew constructors and program using only destructors. Cons-free programs in a simple first-order language with string data capture exactly P, the class of polynomial-time relations. By varying the underlying language and considering other data types, we can capture several other complexity classes. However, no cons-free programming language captures any functional complexity class for fundamental reasons. In this paper, we cleanly extend the cons-free paradigm to encompass functional complexity classes. Namely, we introduce programs with data that can either only be destructed or only be constructed, which we enforce by a type system on the program variables. We call the resulting programs read/write - (or RW -)factorizable, show that RW-factorizable string programs capture exactly the class FP of polynomial-time functions, and that tail-recursive RW-factorizable programs capture exactly the class FL of logarithmic-space functions. Finally, we state and solve the nontrivial problem of syntactic composition of two RW-factorizable programs.

链接与引用

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

BibTeX
@article{paperbot2149,
  title = {Read/write factorizable programs},
  author = {SIDDHARTH BHASKAR and JAKOB GRUE SIMONSEN},
  journal = {Journal of Functional Programming},
  volume = {33},
  year = {2023},
  doi = {10.1017/s0956796823000023}
}