Read/write factorizable programs
Research output: Contribution to journal › Journal article › Research › peer-review
Documents
- Fulltext
Final published version, 892 KB, PDF document
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.
Original language | English |
---|---|
Article number | e5 |
Journal | Journal of Functional Programming |
Volume | 33 |
Issue number | 4 |
Pages (from-to) | 1-50 |
ISSN | 0956-7968 |
DOIs | |
Publication status | Published - 8 Jun 2023 |
Bibliographical note
Publisher Copyright:
© The Author(s), 2023. Published by Cambridge University Press.
ID: 371657334