Renamingless Capture-Avoiding Substitution for Definitional Interpreters

Casper Bach Poulsen

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.

---

Previous: Peter D. Mosses | Using Spoofax to Support Online Code Navigation
Next: Aron Zwaan, Hendrik van Antwerpen | Scope Graphs: The Story so Far