The Useful MAM, a Reasonable Implementation of the Strong $\lambda$-Calculus

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, Polytechnique - X, CNRS - Centre National de la Recherche Scientifique : UMR7161
Abstract : It has been a long-standing open problem whether the strong λ-calculus is a reasonable computational model, i.e. whether it can be implemented within a polynomial overhead with respect to the number of β-steps on models like Turing machines or RAM. Recently, Accattoli and Dal Lago solved the problem by means of a new form of sharing, called useful sharing, and realised via a calculus with explicit substitutions. This paper presents a new abstract machine for the strong λ-calculus based on useful sharing, the Useful Milner Abstract Machine, and proves that it reasonably implements leftmost-outermost evaluation. It provides both an alternative proof that the λ-calculus is reasonable and an improvement on the technology for implementing strong evaluation.
Type de document :
Communication dans un congrès
23rd International Workshop on Logic, Language, Information, and Computation (WoLLIC 2016), Aug 2016, Puebla, Mexico. pp.1 - 21, 2016, 〈http://www.wollic.cs.buap.mx/〉. 〈10.1007/978-3-662-52921-8_1〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01425534
Contributeur : Beniamino Accattoli <>
Soumis le : mardi 3 janvier 2017 - 15:57:57
Dernière modification le : jeudi 11 janvier 2018 - 06:22:14
Document(s) archivé(s) le : mardi 4 avril 2017 - 14:37:40

Fichier

main.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Beniamino Accattoli. The Useful MAM, a Reasonable Implementation of the Strong $\lambda$-Calculus. 23rd International Workshop on Logic, Language, Information, and Computation (WoLLIC 2016), Aug 2016, Puebla, Mexico. pp.1 - 21, 2016, 〈http://www.wollic.cs.buap.mx/〉. 〈10.1007/978-3-662-52921-8_1〉. 〈hal-01425534〉

Partager

Métriques

Consultations de la notice

108

Téléchargements de fichiers

36