Mostrar el registro sencillo del ítem
dc.contributor.author
Accattoli, Beniamino
dc.contributor.author
Barenbaum, Pablo
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.contributor.author
Mazza, Damiano
dc.date.available
2020-11-06T16:55:38Z
dc.date.issued
2014-09
dc.identifier.citation
Accattoli, Beniamino; Barenbaum, Pablo; Mazza, Damiano; Distilling abstract machines; Association for Computing Machinery; ACM SIGPLAN Notices; 49; 9; 9-2014; 363-376
dc.identifier.issn
1523-2867
dc.identifier.uri
http://hdl.handle.net/11336/117817
dc.description.abstract
It is well-known that many environment-based abstract machines can be seen as strategies in lambda calculi with explicit substitutions (ES). Recently, graphical syntaxes and linear logic led to the linear substitution calculus (LSC), a new approach to ES that is halfway between small-step calculi and traditional calculi with ES. This paper studies the relationship between the LSC and environment-based abstract machines. While traditional calculi with ES simulate abstract machines, the LSC rather distills them: some transitions are simulated while others vanish, as they map to a notion of structural congruence. The distillation process unveils that abstract machines in fact implement weak linear head reduction, a notion of evaluation having a central role in the theory of linear logic. We show that such a pattern applies uniformly in call-by-name, call-by-value, and call-by-need, catching many machines in the literature. We start by distilling the KAM, the CEK, and a sketch of the ZINC, and then provide simplified versions of the SECD, the lazy KAM, and Sestoft's machine. Along the way we also introduce some new machines with global environments. Moreover, we show that distillation preserves the time complexity of the executions, i.e. The LSC is a complexity-preserving abstraction of abstract machines.
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
Association for Computing Machinery
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.rights
info:eu-repo/semantics/openAccess
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/
dc.subject
ABSTRACT MACHINES
dc.subject
CALL-BY-NEED
dc.subject
EXPLICIT SUBSTITUTIONS
dc.subject
LAMBDA-CALCULUS
dc.subject
LINEAR HEAD REDUCTION
dc.subject
LINEAR LOGIC
dc.subject.classification
Ciencias de la Computación
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
Ciencias de la Computación e Información
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.title
Distilling abstract machines
dc.type
info:eu-repo/semantics/article
dc.type
info:ar-repo/semantics/artículo
dc.type
info:eu-repo/semantics/publishedVersion
dc.date.updated
2020-09-08T13:59:55Z
dc.journal.volume
49
dc.journal.number
9
dc.journal.pagination
363-376
dc.journal.pais
Estados Unidos
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.journal.ciudad
Nueva York
dc.description.fil
Fil: Accattoli, Beniamino. Universidad de Bologna; Italia. University of Carnegie Mellon; Estados Unidos
dc.description.fil
Fil: Barenbaum, Pablo. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad de Buenos Aires; Argentina
dc.description.fil
Fil: Mazza, Damiano. Centre National de la Recherche Scientifique; Francia. Universite de Paris 13-Nord; Francia
dc.journal.title
ACM SIGPLAN Notices
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1145/2628136.2628154
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://dl.acm.org/doi/10.1145/2692915.2628154
Archivos asociados