Foundations of strong call by need | ||
| dc.conicet.organizacion | Université Paris Sud | |
| dc.conicet.organizacion | Universidad de Buenos Aires | |
| dc.conicet.organizacion | Université Paris Diderot - Paris 7 | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.conicet.organizacion | Universidad Nacional de Quilmes. Departamento de Ciencia y Tecnología | |
| dc.conicet.organizacion | Stevens Institute of Technology | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.conicet.organizacion | Université Paris Diderot - Paris 7 | |
| dc.contributor.author | Balabonski, Thibaut | |
| dc.contributor.author | Barenbaum, Pablo | |
| dc.contributor.author | Bonelli, Eduardo Augusto | |
| dc.contributor.author | Kesner, Delia | |
| dc.date.issued | 2017-08 | |
| 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. | es |
| 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.format | application/pdf | es |
| 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 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 2475-1421 | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/41233 | |
| dc.journal.number | ICFP | es |
| dc.journal.pagination | 1-29; 20 | es |
| dc.journal.pais | Estados Unidos | es |
| dc.journal.title | Proceedings of the ACM on Programming Languages | es |
| dc.journal.volume | 1 | es |
| dc.language.iso | eng | es |
| dc.publisher | Association for Computing Machinery | es |
| 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 | |
| dc.rights | info:eu-repo/semantics/openAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-sa/2.5/ar/ | * |
| dc.subject | Evaluation Strategies | es |
| dc.subject | Call-By-Need | es |
| dc.subject | Completeness | es |
| dc.subject | Lambda Calculus | es |
| dc.subject.classification | Ciencias de la Computación | es |
| dc.subject.classification | Ciencias de la Computación e Información | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.title | Foundations of strong call by need | es |
| dc.type | info:eu-repo/semantics/article | |
| dc.type | info:ar-repo/semantics/artículo | |
| dc.type | info:eu-repo/semantics/publishedVersion | |
Archivos
Bloque original
Cargando...
- Nombre:
- CONICET_Digital_Nro.8ebae3cc-fdc3-44dc-80dc-65a78afad907_A.pdf
- Tamaño:
- 884.01 KB
- Formato:
- Adobe Portable Document Format