License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TYPES.2018.6
URN: urn:nbn:de:0030-drops-114101
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11410/
Go to the corresponding LIPIcs Volume Portal

Sestini, Filippo

Normalization by Evaluation for Typed Weak lambda-Reduction

pdf-format:
LIPIcs-TYPES-2018-6.pdf (0.5 MB)

Abstract

Weak reduction relations in the lambda-calculus are characterized by the rejection of the so-called xi-rule, which allows arbitrary reductions under abstractions. A notable instance of weak reduction can be found in the literature under the name restricted reduction or weak lambda-reduction.
In this work, we attack the problem of algorithmically computing normal forms for lambda-wk, the lambda-calculus with weak lambda-reduction. We do so by first contrasting it with other weak systems, arguing that their notion of reduction is not strong enough to compute lambda-wk-normal forms. We observe that some aspects of weak lambda-reduction prevent us from normalizing lambda-wk directly, thus devise a new, better-behaved weak calculus lambda-ex, and reduce the normalization problem for lambda-w to that of lambda-ex. We finally define type systems for both calculi and apply Normalization by Evaluation to lambda-ex, obtaining a normalization proof for lambda-wk as a corollary. We formalize all our results in Agda, a proof-assistant based on intensional Martin-Löf Type Theory.

BibTeX - Entry

@InProceedings{sestini:LIPIcs:2019:11410,
  author =	{Filippo Sestini},
  title =	{{Normalization by Evaluation for Typed Weak lambda-Reduction}},
  booktitle =	{24th International Conference on Types for Proofs and Programs (TYPES 2018)},
  pages =	{6:1--6:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-106-1},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{130},
  editor =	{Peter Dybjer and Jos{\'e} Esp{\'\i}rito Santo and Lu{\'\i}s Pinto},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11410},
  URN =		{urn:nbn:de:0030-drops-114101},
  doi =		{10.4230/LIPIcs.TYPES.2018.6},
  annote =	{Keywords: normalization, lambda-calculus, reduction, term-rewriting, Agda}
}

Keywords: normalization, lambda-calculus, reduction, term-rewriting, Agda
Collection: 24th International Conference on Types for Proofs and Programs (TYPES 2018)
Issue Date: 2019
Date of publication: 18.11.2019
Supplementary Material: https://github.com/fsestini/nbe-weak-stlc

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI