Passer à la navigation principale Passer à la recherche Passer au contenu principal

Factorization and normalization, essentially

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collectionContribution à une conférenceRevue par des pairs

Résumé

λ-calculi come with no fixed evaluation strategy. Different strategies may then be considered, and it is important that they satisfy some abstract rewriting property, such as factorization or normalization theorems. In this paper we provide simple proof techniques for these theorems. Our starting point is a revisitation of Takahashi’s technique to prove factorization for head reduction. Our technique is both simpler and more powerful, as it works in cases where Takahashi’s does not. We then pair factorization with two other abstract properties, defining essential systems, and show that normalization follows. Concretely, we apply the technique to four case studies, two classic ones, head and the leftmost-outermost reductions, and two less classic ones, non-deterministic weak call-by-value and least-level reductions.

langue originaleAnglais
titreProgramming Languages and Systems - 17th Asian Symposium, APLAS 2019, Proceedings
rédacteurs en chefAnthony Widjaja Lin
EditeurSpringer
Pages159-180
Nombre de pages22
ISBN (imprimé)9783030341749
Les DOIs
étatPublié - 1 janv. 2019
Evénement17th Asian Symposium on Programming Languages and Systems, APLAS 2019 - Bali, Indonésie
Durée: 1 déc. 20194 déc. 2019

Série de publications

NomLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11893 LNCS
ISSN (imprimé)0302-9743
ISSN (Electronique)1611-3349

Une conférence

Une conférence17th Asian Symposium on Programming Languages and Systems, APLAS 2019
Pays/TerritoireIndonésie
La ville Bali
période1/12/194/12/19

Empreinte digitale

Examiner les sujets de recherche de « Factorization and normalization, essentially ». Ensemble, ils forment une empreinte digitale unique.

Contient cette citation