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