Multi types and reasonable space
Journal of Functional Programming · 14.08.2026 · Volume 36
DOI: 10.46298/jfp.17809 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Functional Programming, online erschienen am 14.08.2026. Verfasst von Beniamino Accattoli und 2 weiteren Autor:innen. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
Accattoli, Dal Lago, and Vanoni have recently proved that the space used by the Space KAM, a variant of the Krivine abstract machine, is a reasonable space cost model for the lambda-calculus accounting for logarithmic space, solving a longstanding open problem. In this paper, we provide a new system of multi types (a variant of intersection types) and extract from multi type derivations the space used by the Space KAM, capturing into a type system the space complexity of the abstract machine. Additionally, we show how to capture also the time of the Space KAM, which is a reasonable time cost model, via minor changes to the type system.
Zitieren
APA
Accattoli, B., Lago, U. D., & Vanoni, G. (2026). Multi types and reasonable space. Journal of Functional Programming, Volume 36. https://doi.org/10.46298/jfp.17809
Vancouver
Accattoli B, Lago UD, Vanoni G. Multi types and reasonable space. Journal of Functional Programming. 2026;Volume 36. doi:10.46298/jfp.17809
BibTeX
@article{Accattoli2026,
author = {Accattoli, Beniamino and Lago, Ugo Dal and Vanoni, Gabriele},
title = {Multi types and reasonable space},
journal = {Journal of Functional Programming},
year = {2026},
volume = {Volume 36},
doi = {10.46298/jfp.17809}
}
EUVIMED