Reasonable Space for the $λ$-Calculus, Logarithmically
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913585561600000 |
|---|---|
| author | Accattoli, Beniamino Lago, Ugo Dal Vanoni, Gabriele |
| author_facet | Accattoli, Beniamino Lago, Ugo Dal Vanoni, Gabriele |
| contents | Can the $λ$-calculus be considered a reasonable computational model? Can we use it for measuring the time $\textit{and}$ space consumption of algorithms? While the literature contains positive answers about time, much less is known about space. This paper presents a new reasonable space cost model for the $λ$-calculus, based on a variant over the Krivine abstract machine. For the first time, this cost model is able to accommodate logarithmic space. Moreover, we study the time behavior of our machine and show how to transport our results to the call-by-value $λ$-calculus. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2203_00362 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Reasonable Space for the $λ$-Calculus, Logarithmically Accattoli, Beniamino Lago, Ugo Dal Vanoni, Gabriele Logic in Computer Science Computational Complexity Programming Languages Can the $λ$-calculus be considered a reasonable computational model? Can we use it for measuring the time $\textit{and}$ space consumption of algorithms? While the literature contains positive answers about time, much less is known about space. This paper presents a new reasonable space cost model for the $λ$-calculus, based on a variant over the Krivine abstract machine. For the first time, this cost model is able to accommodate logarithmic space. Moreover, we study the time behavior of our machine and show how to transport our results to the call-by-value $λ$-calculus. |
| title | Reasonable Space for the $λ$-Calculus, Logarithmically |
| topic | Logic in Computer Science Computational Complexity Programming Languages |
| url | https://arxiv.org/abs/2203.00362 |