Mostrar el registro sencillo del ítem
dc.contributor.author
Balabonski, Thibaut
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
Bonelli, Eduardo Augusto
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.contributor.author
Kesner, Delia
dc.date.available
2018-04-06T19:43:58Z
dc.date.issued
2017-08
dc.identifier.citation
Balabonski, Thibaut; Barenbaum, Pablo; Bonelli, Eduardo Augusto; Kesner, Delia; Foundations of strong call by need; Association for Computing Machinery; Proceedings of the ACM on Programming Languages; 1; ICFP; 8-2017; 1-29; 20
dc.identifier.issn
2475-1421
dc.identifier.uri
http://hdl.handle.net/11336/41233
dc.description.abstract
We present a call-by-need strategy for computing strong normal forms of open terms (reduction is admitted inside the body of abstractions and substitutions, and the terms may contain free variables), which guarantees that arguments are only evaluated when needed and at most once. The strategy is shown to be complete with respect to β-reduction to strong normal form. The proof of completeness relies on two key tools: (1) the de nition of a strong call-by-need calculus where reduction may be performed inside any context, and (2) the use of non-idempotent intersection types. More precisely, terms admitting a β-normal form in pure lambda calculus are typable, typability implies (weak) normalisation in the strong call-by-need calculus, and weak normalisation in the strong call-by-need calculus implies normalisation in the strong call-by-need strategy. Our (strong) call-by-need strategy is also shown to be conservative over the standard (weak) call-by-need.
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
Evaluation Strategies
dc.subject
Call-By-Need
dc.subject
Completeness
dc.subject
Lambda Calculus
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
Foundations of strong call by need
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
2018-04-06T13:45:54Z
dc.journal.volume
1
dc.journal.number
ICFP
dc.journal.pagination
1-29; 20
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.description.fil
Fil: Balabonski, Thibaut. Université Paris Sud; Francia
dc.description.fil
Fil: Barenbaum, Pablo. Universidad de Buenos Aires; Argentina. Université Paris Diderot - Paris 7; Francia. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina
dc.description.fil
Fil: Bonelli, Eduardo Augusto. Universidad Nacional de Quilmes. Departamento de Ciencia y Tecnología; Argentina. Stevens Institute of Technology; Estados Unidos. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina
dc.description.fil
Fil: Kesner, Delia. Université Paris Diderot - Paris 7; Francia
dc.journal.title
Proceedings of the ACM on Programming Languages
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1145/3110264
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://dl.acm.org/citation.cfm?doid=3136534.3110264
Archivos asociados