License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.EVCS.2023.2
URN: urn:nbn:de:0030-drops-177728
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17772/
Bach Poulsen, Casper
Renamingless Capture-Avoiding Substitution for Definitional Interpreters
Abstract
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.
BibTeX - Entry
@InProceedings{bachpoulsen:OASIcs.EVCS.2023.2,
author = {Bach Poulsen, Casper},
title = {{Renamingless Capture-Avoiding Substitution for Definitional Interpreters}},
booktitle = {Eelco Visser Commemorative Symposium (EVCS 2023)},
pages = {2:1--2:10},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-267-9},
ISSN = {2190-6807},
year = {2023},
volume = {109},
editor = {L\"{a}mmel, Ralf and Mosses, Peter D. and Steimann, Friedrich},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17772},
URN = {urn:nbn:de:0030-drops-177728},
doi = {10.4230/OASIcs.EVCS.2023.2},
annote = {Keywords: Capture-avoiding substitution, lambda calculus, definitional interpreter}
}
