Read/write factorizable programs
Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Dokumenter
- Fulltext
Forlagets udgivne version, 892 KB, PDF-dokument
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.
Originalsprog | Engelsk |
---|---|
Artikelnummer | e5 |
Tidsskrift | Journal of Functional Programming |
Vol/bind | 33 |
Udgave nummer | 4 |
Sider (fra-til) | 1-50 |
ISSN | 0956-7968 |
DOI | |
Status | Udgivet - 8 jun. 2023 |
Bibliografisk note
Publisher Copyright:
© The Author(s), 2023. Published by Cambridge University Press.
ID: 371657334