2026-07-24T05:47:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11410 2024-03-06T10:46:05Z ddc:004 open_access

Normalization by Evaluation for Typed Weak lambda-Reduction Sestini, Filippo normalization lambda-calculus reduction term-rewriting Agda 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Filippo Sestini 2019 Is Part Of LIPIcs, Volume 130, 24th International Conference on Types for Proofs and Programs (TYPES 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TYPES.2018.6 urn:nbn:de:0030-drops-114101 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TYPES.2018.6 eng https://creativecommons.org/licenses/by/3.0/legalcode