Abstract
When programming with sublinear space constraints one often needs to use special implementation techniques even for simple tasks, such as function composition. In this paper, we study how such implementation techniques can be supported in a functional programming language. Our approach is based on modelling computation by interaction using the Int construction of Joyal, Street & Verity. We apply this construction to a term model of a first-order programming language and use the resulting structure to derive the functional programming language INTML. INTML can be understood as a programming language simplification of Stratified Bounded Affine Logic. We formulate INTML by means of a type system inspired by Baillot & Terui's Dual Light Affine Logic. We show that it captures the complexity classes FLOGSPACE and NFLOGSPACE. We illustrate its expressiveness by showing how typical graph algorithms, such a test for acyclicity in undirected graphs, can be represented. (C) 2016 ELSEVIER. All rights reserved.
Item Type: | Journal article |
---|---|
Faculties: | Mathematics, Computer Science and Statistics > Computer Science |
Subjects: | 000 Computer science, information and general works > 004 Data processing computer science |
ISSN: | 0890-5401 |
Language: | English |
Item ID: | 47266 |
Date Deposited: | 27. Apr 2018, 08:12 |
Last Modified: | 13. Aug 2024, 12:53 |