The Complexity of Abstract Machines

Beniamino Accattoli 1, 2
1 PARSIFAL - Proof search and reasoning with logic specifications
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
Abstract : The λ-calculus is a peculiar computational model whose definition does not come with a notion of machine. Unsurprisingly, implementations of the λ-calculus have been studied for decades. Abstract machines are implementations schemas for fixed evaluation strategies that are a compromise between theory and practice: they are concrete enough to provide a notion of machine and abstract enough to avoid the many intricacies of actual implementations. There is an extensive literature about abstract machines for the λ-calculus, and yet—quite mysteriously—the efficiency of these machines with respect to the strategy that they implement has almost never been studied. This paper provides an unusual introduction to abstract machines, based on the complexity of their overhead with respect to the length of the implemented strategies. It is conceived to be a tutorial, focusing on the case study of implementing the weak head (call-by-name) strategy, and yet it is an original re-elaboration of known results. Moreover, some of the observations contained here never appeared in print before.
Type de document :
Communication dans un congrès
Third International Workshop on Rewriting Techniques for Program Transformations and Evaluation (WPTE 2016), Jun 2016, Porto, Portugal. 235, pp.1 - 15, 2017, 〈https://project.inria.fr/wpte2016/〉. 〈10.4204/EPTCS.235.1〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01425560
Contributeur : Beniamino Accattoli <>
Soumis le : mardi 3 janvier 2017 - 16:07:08
Dernière modification le : mercredi 14 novembre 2018 - 16:14:01
Document(s) archivé(s) le : mardi 4 avril 2017 - 14:37:14

Fichier

Accattoli - The Complexity of ...
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Beniamino Accattoli. The Complexity of Abstract Machines. Third International Workshop on Rewriting Techniques for Program Transformations and Evaluation (WPTE 2016), Jun 2016, Porto, Portugal. 235, pp.1 - 15, 2017, 〈https://project.inria.fr/wpte2016/〉. 〈10.4204/EPTCS.235.1〉. 〈hal-01425560〉

Partager

Métriques

Consultations de la notice

192

Téléchargements de fichiers

31