Strong call-by-value is reasonable, implosively

B Accattoli, A Condoluci… - 2021 36th Annual ACM …, 2021 - ieeexplore.ieee.org
Whether the number of β-steps in the λ-calculus can be taken as a reasonable time cost
model (that is, polynomially related to the one of Turing machines) is a delicate problem …

A derived reasonable abstract machine for strong call by value

M Biernacka, W Charatonik, T Drab - Proceedings of the 23rd …, 2021 - dl.acm.org
We present an efficient implementation of the full-reducing call-by-value strategy for the pure
λ-calculus in the form of an abstract machine. The presented machine has been …

A simple and efficient implementation of strong call by need by an abstract machine

M Biernacka, W Charatonik, T Drab - Proceedings of the ACM on …, 2022 - dl.acm.org
We present an abstract machine for a strong call-by-need strategy in the lambda calculus.
The machine has been derived automatically from a higher-order evaluator that uses the …

An abstract machine for strong call by value

M Biernacka, D Biernacki, W Charatonik… - Asian Symposium on …, 2020 - Springer
We present an abstract machine that implements a full-reducing (aka strong) call-by-value
strategy for pure λ λ-calculus. It is derived using Danvy et al.'s functional correspondence …

Useful open call-by-need

B Accattoli, M Leberle - arXiv preprint arXiv:2107.06591, 2021 - arxiv.org
This paper studies useful sharing, which is a sophisticated optimization for lambda-calculi, in
the context of call-by-need evaluation in presence of open terms. Useful sharing turns out to …

A Diamond Machine for Strong Evaluation

B Accattoli, P Barenbaum - Asian Symposium on Programming …, 2023 - Springer
Abstract machines for strong evaluation of the λ-calculus enter into arguments and have a
set of transitions for backtracking out of an evaluated argument. We study a new abstract …

[PDF][PDF] A strong call-by-need calculus

T Balabonski, A Lanco… - Logical Methods in …, 2023 - lmcs.episciences.org
We present a call-by-need λ-calculus that enables strong reduction (that is, reduction inside
the body of abstractions) and guarantees that arguments are only evaluated if needed and …

Equivalence of eval-readback and eval-apply big-step evaluators by structuring the lambda-calculus's strategy space

P Nogueira, Á García-Pérez - Logical Methods in Computer …, 2024 - lmcs.episciences.org
We study the equivalence between eval-readback and eval-apply big-step evaluators in the
general setting of the pure lambda calculus. We study 'one-step'equivalence (same strategy) …

Coinductive Natural Semantics for Compiler Verification in Coq

A Zúñiga, G Bel-Enguix - Mathematics, 2020 - mdpi.com
(Coinductive) natural semantics is presented as a unifying framework for the verification of
total correctness of compilers in Coq (with the feature that a verified compiler can be …

Stratégies pour la réduction forte

A Lanco - 2023 - theses.hal.science
La sémantique d'un langage de programmation, et d'un langage fonctionnel en particulier,
laisse généralement une certaine liberté quant à l'ordre dans lequel sont effectuées les …