TY - GEN
T1 - A Diamond Machine for Strong Evaluation
AU - Accattoli, Beniamino
AU - Barenbaum, Pablo
N1 - Publisher Copyright:
© 2023, The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
PY - 2023/1/1
Y1 - 2023/1/1
N2 - 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 machine which avoids backtracking by splitting the run of the machine in smaller jobs, one for argument, and that jumps directly to the next job once one is finished. Usually, machines are also deterministic and implement deterministic strategies. Here we weaken this aspect and consider a light form of non-determinism, namely the diamond property, for both the machine and the strategy. For the machine, this introduces a modular management of jobs, parametric in a scheduling policy. We then show how to obtain various strategies, among which leftmost-outermost evaluation, by instantiating in different ways the scheduling policy.
AB - 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 machine which avoids backtracking by splitting the run of the machine in smaller jobs, one for argument, and that jumps directly to the next job once one is finished. Usually, machines are also deterministic and implement deterministic strategies. Here we weaken this aspect and consider a light form of non-determinism, namely the diamond property, for both the machine and the strategy. For the machine, this introduces a modular management of jobs, parametric in a scheduling policy. We then show how to obtain various strategies, among which leftmost-outermost evaluation, by instantiating in different ways the scheduling policy.
KW - Lambda calculus
KW - abstract machines
KW - strong evaluation
U2 - 10.1007/978-981-99-8311-7_4
DO - 10.1007/978-981-99-8311-7_4
M3 - Conference contribution
AN - SCOPUS:85178628436
SN - 9789819983100
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 69
EP - 90
BT - Programming Languages and Systems - 21st Asian Symposium, APLAS 2023, Proceedings
A2 - Hur, Chung-Kil
PB - Springer Science and Business Media Deutschland GmbH
T2 - 21st Asian Symposium on Programming Languages and Systems, APLAS 2023
Y2 - 26 November 2023 through 29 November 2023
ER -