Beniamino Accattoli ; Ugo Dal Lago ; Gabriele Vanoni - Reasonable Space for the ${\lambda}$-Calculus, Logarithmically

lmcs:10883 - Logical Methods in Computer Science, November 20, 2024, Volume 20, Issue 4 - https://doi.org/10.46298/lmcs-20(4:15)2024
Reasonable Space for the ${\lambda}$-Calculus, LogarithmicallyArticle

Authors: Beniamino Accattoli ; Ugo Dal Lago ; Gabriele Vanoni

    Can the $\lambda$-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 $\lambda$-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 $\lambda$-calculus.


    Volume: Volume 20, Issue 4
    Published on: November 20, 2024
    Accepted on: June 20, 2024
    Submitted on: February 1, 2023
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Computational Complexity,Computer Science - Programming Languages