Reasonable Space for the λ-Calculus, Logarithmically

Creators: Accattoli, Beniamino; Dal Lago, Ugo; Vanoni, Gabriele

Others:: Automatisation et ReprésenTation: fOndation du calcUl et de la déducTion (PARTOUT) ; Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX) ; École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France ; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria); Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX) ; École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS); Foundations of Component-based Ubiquitous Systems (FOCUS) ; Inria Sophia Antipolis - Méditerranée (CRISAM) ; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Dipartimento di Informatica - Scienza e Ingegneria [Bologna] (DISI) ; Alma Mater Studiorum Università di Bologna [Bologna] (UNIBO)-Alma Mater Studiorum Università di Bologna [Bologna] (UNIBO); University of Bologna/Università di Bologna

Description

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.

Abstract

International audience

Reasonable Space for the λ-Calculus, Logarithmically

Description

Abstract

Additional details