2026-07-23T20:44:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17772 2024-03-06T10:31:57Z ddc:004 open_access

Renamingless Capture-Avoiding Substitution for Definitional Interpreters Bach Poulsen, Casper Capture-avoiding substitution lambda calculus definitional interpreter Substitution is a common and popular approach to implementing name binding in definitional interpreters. A common pitfall of implementing substitution functions is variable capture. The traditional approach to avoiding variable capture is to rename variables. However, traditional renaming makes for an inefficient interpretation strategy. Furthermore, for applications where partially-interpreted terms are user facing it can be confusing if names in uninterpreted parts of the program have been changed. In this paper we explore two techniques for implementing capture avoiding substitution in definitional interpreters to avoid renaming. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Casper Bach Poulsen 2023 Is Part Of OASIcs, Volume 109, Eelco Visser Commemorative Symposium (EVCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.EVCS.2023.2 urn:nbn:de:0030-drops-177728 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.EVCS.2023.2 eng https://creativecommons.org/licenses/by/4.0/legalcode