A simple and efficient implementation of strong call by need by an abstract machine
Journal of Functional Programming · 20.08.2026 · Volume 36
DOI: 10.46298/jfp.17808 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Functional Programming, online erschienen am 20.08.2026. Verfasst von Małgorzata Biernacka und 2 weiteren Autor:innen.
Abstract (Originalsprache)
Strong call-by-need combines full normalization with the sharing discipline of lazy evaluation, yet no prior implementation achieved both simplicity and efficiency. We introduce RKNL, an abstract machine that realizes strong call-by-need with bilinear overhead. The machine has been derived automatically from a higher-order evaluator that uses the technique of memothunks to implement laziness. By employing an off-the-shelf transformation tool implementing the ``functional correspondence'' between higher-order interpreters and abstract machines, we obtained a simple and concise description of the machine. We prove that the resulting machine conservatively extends the lazy version of Krivine machine for the weak call-by-need strategy, and that it simulates the normal-order strategy in a bilinear number of steps, i.e., linear in both the number of beta-reductions and the size of the input term. 39 pages, 4 figures
Zitieren
APA
Biernacka, M., Charatonik, W., & Drab, T. (2026). A simple and efficient implementation of strong call by need by an abstract machine. Journal of Functional Programming, Volume 36. https://doi.org/10.46298/jfp.17808
Vancouver
Biernacka M, Charatonik W, Drab T. A simple and efficient implementation of strong call by need by an abstract machine. Journal of Functional Programming. 2026;Volume 36. doi:10.46298/jfp.17808
BibTeX
@article{Biernacka2026,
author = {Biernacka, Małgorzata and Charatonik, Witold and Drab, Tomasz},
title = {A simple and efficient implementation of strong call by need by an abstract machine},
journal = {Journal of Functional Programming},
year = {2026},
volume = {Volume 36},
doi = {10.46298/jfp.17808}
}
EUVIMED