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.

@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}
}