Renamingless Capture-Avoiding Substitution for Definitional Interpreters

Casper Bach Poulsen

Date: Wed, March 08, 2023
Time: 12:00
Room: Turing 0.E420

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 |
Next: Aron Zwaan, Hendrik van Antwerpen |