Can the λ-calculus be considered a reasonable computational model? Can we use it for measuring the time 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.

Beniamino Accattoli, Ugo Dal Lago, Gabriele Vanoni (2022). Reasonable Space for the Lambda-Calculus, Logarithmically. New York : Association for Computing Machinery [10.1145/3531130.3533362].

Reasonable Space for the Lambda-Calculus, Logarithmically

Ugo Dal Lago
;
Gabriele Vanoni
2022

Abstract

Can the λ-calculus be considered a reasonable computational model? Can we use it for measuring the time 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.
2022
Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS '22).
1
13
Beniamino Accattoli, Ugo Dal Lago, Gabriele Vanoni (2022). Reasonable Space for the Lambda-Calculus, Logarithmically. New York : Association for Computing Machinery [10.1145/3531130.3533362].
Beniamino Accattoli; Ugo Dal Lago; Gabriele Vanoni
File in questo prodotto:
File Dimensione Formato  
lics2022b.pdf

accesso aperto

Tipo: Versione (PDF) editoriale
Licenza: Licenza per accesso libero gratuito
Dimensione 689.56 kB
Formato Adobe PDF
689.56 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/904339
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? ND
social impact